トップダウン構文解析

トップダウン構文解析とは

トップダウン構文解析は、構文解析における戦略の一つで、構文木を構築する際に、最上位の非終端記号から出発し、順次それを右辺の記号列へと書き換えていくことで導出する手法です。これは、与えられた入力が、文法規則に沿ってどのように構成されているかを解析するプロセスであり、コンパイラやインタプリタといったプログラム言語処理系で、ソースコードを内部表現に変換する際に重要な役割を果たします。反対の戦略として、ボトムアップ構文解析があります。

プログラミング言語におけるトップダウン構文解析

プログラミング言語の処理系では、ソースコードはまず構文解析器（パーサー）によって解析され、内部的な表現へと変換されます。この処理は、特定の文法に依存せず、またトップダウン構文解析に限ったものではありません。

ここでは、対象となるソースコードの文法が文脈自由文法であると仮定します。トップダウン構文解析では、入力全体が、文脈自由文法の最上位の生成規則の左辺の非終端記号にマッチすることを前提として解析を開始します。

構文解析の進め方

構文解析は、入力文字列に生成規則を適用する際、左端の記号からマッチングを進めていきます。非終端記号に遭遇すると、その非終端記号に対応する生成規則を適用します。この処理は、生成規則の右辺の左端から順に評価されるため、入れ子構造のような動作を伴います。すなわち、ある生成規則を適用し、その右辺の評価中に非終端記号が現れると、その非終端記号に対する別の生成規則を適用するという動作が繰り返されます。

具体例

例えば、以下のような生成規則を考えてみましょう。


A → aBC
B → c | cd
C → df | eg


この場合、構文解析はまず`A`から開始します。最初に `A → aBC` が適用され、次に `B` を評価する過程で、`B → c | cd` のいずれかが選択されます。そして、最後に `C` に対して、`C → df | eg` のいずれかが適用されます。

LL(1)文法とトップダウン構文解析

ある非終端記号に関する生成規則の右辺の記号列において、記号列の先頭に現れる終端記号によって、適用する記号列が一意に決定できる場合、その文法はLL(1)文法であると言えます。ここで、(1)は構文解析器が先読みする必要があるトークンの数を表します。もし先頭の終端記号だけでは適用する規則が決定できない場合、LL法を使って構文解析を行うためには、複数トークンの先読みが必要となります。

関連項目

• - ボトムアップ構文解析
• - 再帰下降構文解析
• - LL法
• - 句構造規則

もう一度検索