Ruby Parser開発日誌 (19) - 最高の構文木の設計 2024年版 - かねこにっき
はじめに 今回はparserの生成物である構文木についてのお話です。 普段は主にparserとlexerについて考えていますが、たまに構文木について考えを巡らすこともあります。 むしろparserの目指すべき実装が固まったいまだからこそ、その主な生成物である構文木の設計について考える必要があるとも言えます。 Rubyのparserの実装は複数あり、それぞれのparserが生成する構文木もまた微妙に異なります。 それらの構文木は各parserのユースケースに合わせてアドホックに必要な要素が追加されているように見え、なにか原理原則に従っているように思えませんでした。 そのため果たして構文木に設計というものがあるのだろうかという疑問をずっと抱いていました。 Rubyの開発ではユースケースを収集し、それらのユースケースに対してどのくらい応えられているかをもって設計の良し悪しを確認するというアプロー
PEG Parser Generator + Packrat Parserを実装してみた - LINE ENGINEERING
詳しい解説はネット上に沢山存在するので割愛しますが、ご覧のようにEBNFの表現の一つに（EBNFはいくつかの表現方法があるようです。例えばこれはW3Cが定義しているものです）似ています。違いは先に述べたようにChoiceの働きが異なるのと、文法上に先読みが存在することです。 このPEGを使って四則演算を受理するシンプルなルールを書くとすると、例えばこのようになります。 # expressionからパースが始まるとする expression <- additive additive <- multitive ("+" multitive / "-" multitive)* multitive <- primary ("*" primary / "/" primary)* primary <- "(" expression ")" / number number <- digit+ digit
PLYでプログラミング言語を作る【グローバル変数】
lex/yaccでプログラミング言語を作るにはC言語を使う必要があるため、メモリ管理等の面でなかなか敷居が高いです。一方、PythonではPLYというlex/yaccのPython実装のライブラリが存在し、簡単にプログラミング言語を作成することができます。ということで、PLYを使ってプログラミング言語を作ってみました。 今回は以下の機能を作っていきます。サンプルコードはこちら。 ステートメントの順次実行 四則演算 グローバル変数のセット ちなみにプログラミング言語作成に関してはドシロートなので色々ご了承ください。 PLYの利点 PLYを使う利点は以下になります。 トークン保持に関する共用体の定義を省略できる 処理内容をPythonで書け、文法上のメリットがある＋メモリ管理をしなくて良い lex/yaccではトークンの情報を共用体を使って保持する必要があります。PLYはPythonの動的型付
Parsing in Python: all the tools and libraries you can use
The tomassetti.me website has changed: it is now part of strumenta.com. You will continue to find all the news with the usual quality, but in a new layout. This is an article similar to a previous one we wrote: Parsing in Java, so the introduction is the same. Skip to chapter 3 if you have already read it. If you need to parse a language, or document, from Python there are fundamentally three ways
JSON Parser with JavaScript | Tan Li Hau
Series: AST JavaScriptAST Understand the grammar Implementing the parser Handling the unexpected input Unexpected token Unexpected end of string Going the extra mile Error code and standard error message A better view of what went wrong Suggestions for error recovery Summary The interview question of the week for this week on Cassidoo's weekly newsletter is, Write a function that takes in a string
Scalaでパーサーを作ってみる〜1:構文定義 - きしだのHatena
Scalaの勉強をはじめました。 で、なんかパーサーコンビネータというのがあるらしく、パーサーが簡単に作れるらしく、じゃあパーサー作ってみるのがScalaの勉強にいいんじゃないかということで、簡単なパーサーを作ってみることにします。 とりあえず構文定義してみます。 今回つくるのは、整数の計算をするパーサーってことにします。整数と、+/-、*、あと()くらいが使えるものにします。割り算を入れないのは、そこは単純に処理を付け加えれば実現できるから。 式の優先順位と、同じ優先度に複数の演算子があればいいってことにします。あと、単項演算子も使いません。めんどうだから。 実装方針は「ソースコードが増えないこと」です。 JavaTokenParsersを使うと、Javaのリテラル表記がそのまま使えるパーサーが作れるらしいんですけど、構文を全部自分で定義したい病気なので、その一階層上のRegexPars
Scalaでパーサーを作ってみる〜2:構文木の作成 - きしだのHatena
Scalaの勉強をはじめたので、とりあえず簡単な数式パーサーを作ってみてます。 前回は、とりあえず構文規則を定義しました。 Scalaでパーサーを作ってみる〜1:構文定義 - きしだのはてな 今回は、その構文規則からASTオブジェクトを生成しようと思います。 基底になるASTトレイトを用意して、それぞれの構文要素を定義します。 trait AST case class AddOp(left: AST, right:AST) extends AST case class SubOp(left: AST, right:AST) extends AST case class MulOp(left: AST, right:AST) extends AST case class IntVal(value: Int) extends AST 構文ルールでAST要素を生成するようにします。Parserの
Algol 60 in PLY (Python Lex-Yacc)
PLY (Python Lex-Yacc) で作る Algol 60 処理系 2008.9.26 - 2008.10.17 - 2008.12.8 - 2009.2.17 (鈴) 第１部 1. はじめに 2. Algol 60 とは 2.1 Algol 60 修正報告書 3. PLY の導入 4. 字句解析 4.1 字句解析ルールの記述 5. 構文解析 5.1 構文解析ルールの記述 5.2 Algol 60 生成規則の修正 6. ここまでのまとめ 第２部 7. 名前の解決 8. インタープリタ - 文の単方向リンクと goto 文 9. インタープリタ - 手続きとディスプレイとスタック 10. インタープリタ - 式の中からの大域脱出 11. インタープリタ - call-by-name の実現 12. インタープリタ - のこりの言語要素 第３部 13. インタープリタへの標準関数の組
第18回 Scalaとパーザコンビネータ（実装編）
筑波大学第三学群情報学類を卒業したのち、現在は、筑波大学大学院システム情報工学研究科コンピュータサイエンス専攻博士後期課程3年。プログラミング言語や処理系に強い興味を持っている。現在の研究テーマは、プログラミング言語の構文解析アルゴリズム。Scala勉強会を不定期で行うなど、研究の合間にScalaの普及活動を行っている。 Scalaにはパーザコンビネータライブラリという、構文解析を行うための専用ライブラリが存在します。今回は、前回に説明したHello, World!パーザをより簡潔に書けるように修正していくほか、JSONのサブセットのパーザの実装までを解説します。 Hello, World!パーザを改良してみる strメソッド - 文字列を直接扱えるように 前回説明したリスト5のパーザは、プリミティブとして1文字にマッチするパーザしか扱えなかったため、いちいちそれを~でつないでいくのが面倒
Beautiful Soup: We called him Tortoise because he taught us.
You didn't write that awful page. You're just trying to get some data out of it. Beautiful Soup is here to help. Since 2004, it's been saving programmers hours or days of work on quick-turnaround screen scraping projects. Beautiful Soup is a Python library designed for quick turnaround projects like screen-scraping. Three features make it powerful: Beautiful Soup provides a few simple methods and
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Replacing CPython’s parser - Python Language Summit 2020
Incremental Packrat Parsing
http://web.cs.ucla.edu/~todd/research/pepm08.pdf
[PDF] Parsing Expression Grammars: A Recognition-Based Syntactic Foundation
GitHub - parse-community/parse-server: Parse Server for Node.js / Express
HugeDomains.com