再帰下降構文解析
『コンピュータシステムの理論と実装』10.1.3
構文木を構築するためのアルゴリズム
トップダウン的なアプローチ
言語の文法によって規定されるネスト化された構文を使って、トークンの列に対して再帰的に構文解析を行う
実装(ルーチンとして)
入力は非終端要素
非終端要素が終端要素だけからのみ構成される場合
単にその終端要素を(構造化された方法で)出力するだけ
そうでない場合
非終端要素の右側にあるルールについては、そのルーチンはこの非終端要素を構文解析するように設計したルーチンを再帰的に呼ぶ
ルールの例(図10-1 C言語)
code:txt
...
statement: whileStatement
| ifStatement
| ...
ポイント:再帰的に実装する
入力で最初のトークンの種類は何かを決定するところから始め
トークンが識別できたら、そのルーチンは、それがどの文であるかを把握しているため、その種類の文に関するルーチンを呼ぶことができる
例:parseStatementからparseWhileStatementを呼ぶ
同じロジックは、ソースコードの構文エラーを検出するためにも用いることができる
LL(1)
非終端要素の種類を決めるにあたり、いくつかの選択肢があった場合、最初のトークンだけから、そのトークンの種類を決定することができる
例:最初のトークンがwhile→while文のパースルーチンを呼ぶ
LL(1)性質を満たす文法は、「再帰下降アルゴリズムによって簡単に扱うことができる」
Jack言語の文法はほとんどLL(1)
唯一の例外は式をパースするときであり、その場合は先読みが必要になる