日記/2009/11/24/構文解析(LL,LR,LALR,yacc関連)メモ

ざっとまとめただけです。

大元：文脈自由文法

元々は言語学だが、プログラミング言語の文法や構文を扱うのに優れている。
で、入力されたテキストの文法的な関係を説明するのが構文解析。

構文解析は通常、字句解析結果をその言語の文法に沿った木構造に変換する。
日本語で言えば助詞、プログラミング言語では"("や"{"などの括弧など、グループ化の為の葉まで含めたのが構文木。
英語版だと"Concrete syntax tree"：http://en.wikipedia.org/wiki/Concrete_syntax_tree

構文木から、"("や"{"などプログラム的に意味のない部分を取り除いたのが抽象構文木。
英語版だと"Abstract syntax tree"：http://en.wikipedia.org/wiki/Abstract_syntax_tree

構文解析を行うのが構文解析器。
その例として、次の二種類。

• トップダウン構文解析
  • 入力テキストを、入力された順番に解析して、生成規則を適用していく。
  • LL法がプログラミング言語で主流。左端導出を使う。
  • k個のトークンを先読みする場合はLL(k)法と呼ばれる。1990年代まではLL(1)までしか使われていなかったが、計算機の性能向上によりJavaCCやANTLRなどで1以上のkによるLL(k)法を使うパーサもあらわれた。
• ボトムアップ構文解析
  • 入力テキストを、最後に入力された要素から逆順に解析して、生成規則を適用していく。
  • LR法がプログラミング言語で主流。右端導出を使う。
  • yaccなどは先読み(LookAhead)を行うLRである、LALR法を使っている。

左端導出、右端導出については「文脈自由文法」を参照。

トップダウン構文解析に使われる解析手法でもう一つ有名だったのが再帰下降構文解析。
LL法とどう違うかというと(Wikipediaからの抜き書きです)・・・

• "バックアップ"の無い再帰下降は「予言的パーサ」とも呼ばれ、これはLL(k)文法でのみ実現可能。左再帰が含まれていると使えない。
• "バックアップ"のある再帰下降はLL(k)以外の文法でも使えるが、時間かかるみたい。

基本的にLL(k)法を扱うパーサは再帰下降と考えてOKっぽい。

左再帰というのが出てくるが、これは生成規則の先頭に(=左側に)自分自身が再度定義されている規則。
右再帰というのは逆に、生成規則の後ろに(=右側に)自分自身が再度定義されている規則。

左再帰:
A => A + B
右再帰:
A => B + A

詳細は以下参照：

• 左再帰
• http://en.wikipedia.org/wiki/Left_recursion

yaccの内部動作を知りたい場合は、下記英語リソースが図や表も多用されてて分かりやすかった・・・ように見えるので、情けないけど「あとで見る」という事に。

• Understanding parsers generated by GNU Bison
  • http://www.cs.uic.edu/~spopuri/cparser.html
• Geyacc: Parser Algorithm
  • http://www.gobosoft.com/eiffel/gobo/geyacc/algorithm.html
• CS362 2004S : Class 20: Shift-Reduce Parsing (1)
  • http://www.cs.grinnell.edu/~rebelsky/Courses/CS362/2004S/Outlines/outline.20.html
• 3.3.2 Shift-Reduce Parsing Using the ACTION/GOTO Tables
  • http://lambda.uta.edu/cse5317/notes/node18.html