構文解析

提供: langdev
移動: 案内検索

字句解析済みのトークン列、もしくは、バイト列を直接読み込んで、構文木に変換するフェーズ。

構文解析器ジェネレータ[編集]

自分で構文解析器をガリガリ書いてもいいが、パーサジェネレータと呼ばれる構文解析器をDSLから自動生成するソフトを使うと楽できる。


LR(1)[編集]

Yacc[編集]

一番良く使われていると思う。

高機能GNU版のBisonもある。

使っている主な言語: gccのC言語, Rubyなど

Jison[編集]

http://zaach.github.io/jison/

JavaScript用パーサジェネレータ。LALR(1)の他、LL(1)なども使える。

LL(n)[編集]

最初のn個のトークンを見て生成規則(if文なのかwhile文なのかなど)を決定する文法。 古典的には処理効率の問題からLL(1)が多く使われる。

LL(n)やLL(k)といった場合、無限に先読みできるという意味の場合と、文法ごとに異なるある固定されたkやnまで先読みできるという意味の場合がある。 例えばCoco/RはLL(k)を前者の意味で使っているし、ANTLRは後者の意味で使っている。気をつけよう。一般的には後者の意味で使う場合が多い。また、無限先読みの意味でLL(∞)という表現を使う場合もある。

純粋なLL(1)だとCのような言語でelse文が曖昧になるので、そのような競合を解決するための規則を記述できるようになっているものもある。

再帰下降型パーサー[編集]

ジェネレータではないが、手書きで1から構文解析器を書くばあい、再帰下降型パーサーを書く事が多い。 簡単な数式程度であれば、手書きで書いてしまうのが手っ取り早いからだ。

また、Cのようにパーサジェネレータで上手く書けないような文法にも使われる。

任意の処理を書けるのでLL(n)でない(文脈自由ですらない)文法も書けるが、書きやすさの点からLL(1)+αの文法に使われる。

Coco/R[編集]

http://www.ssw.uni-linz.ac.at/coco/

生成されるパーサーは内部実装は再帰下降型パーサーである。

大量の言語に対応している。 C#, Java, C++, F#, VB.Net, Oberon etc.

昔(2005年ごろ)、C#で試した時は日本語(マルチバイト文字)が通らなかったけど、今みると通りそうな雰囲気。

本体はGPLだが、これで作ったパーサはGPLに汚染される事はないとライセンスに明記されている。

基本的にはLL(1)文法を扱うが、LL(1)の競合を真偽値を返す式で解決できる。その式の中でトークンを任意の長さ先読みできるのでLL(k)となる。

ANTLR[編集]

http://www.antlr.org/

LL(*) (正規言語を先読みできる)文法を扱えるパーサジェネレータ。

バージョン3はJava, C#, C, JavaScript, Python, Rubyなどのコードを生成できる。 バージョン4はJavaとC#のコードを生成できる。

ドキュメントはあまり揃ってないのでThe Definitive ANTLR 4 Referenceを買おう。

PEG[編集]

The Packrat Parsing and Parsing Expression Grammars Page

文脈自由文法に似た文法。バックトラッキングとメモ化を組み合わせて線形時間で解析できる。ただしメモリ消費量も線形。

Rats![編集]

https://cs.nyu.edu/rgrimm/xtc/rats-intro.html

PEGをベースにしたPackrat Parserを生成するパーザジェネレータ。Javaのコードを生成できる。特徴として、文法定義を複数の単位に分割するモジュール機能が挙げられる。ドキュメントは少ないので、処理系に同梱されているJavaパーザの記述などを参照しよう。

パーサコンビネータ[編集]

小さなパーサを演算子で繋げて大きなパーサを作る。 上手く工夫するとBNFっぽい記法で書ける。 よくMonadやArrowとして実装される。

Parsec[編集]

Parsec - HaskellWiki

Text.Parsec

Haskell用パーサコンビネータ。 文脈に依存するような文法も書けるが、バックトラックをしない文法を効率的にパースできるよう最適化されている。 Java, Ruby, Python, C#, JavaScriptなどに移植されている。