トップダウンとボトムアップパースニングの違い

トップダウン構文解析とボトムアップ構文解析の重要な違いは、トップダウン構文解析は開始記号から入力文字列までの構文解析を行うのに対し、ボトムアップ構文解析は入力文字列から開始記号までの構文解析を行う点である。また、トップダウン構文解析とボトムアップ構文解析のもう一つの重要な違いは、トップダウン構文解析は左端の派生物を使用し、ボトムアップ構文解析は右端の派生物を使用することである...。

高レベルの言語は、コンピュータのプログラムを書くのに役立ちます。プログラマーには理解しやすいが、コンピュータには理解できない。そのため、プログラムは高位プログラムに変換される。コンパイラの仕事は、人間が読めるソースコードを、機械が読めるマシンコードに変換することである。プログラムは、機械語に変換されるまでにいくつかのステップを経なければならない。このプロセス全体を「言語処理システム」と呼ぶ。そのひとつが「組み立て」です。構文解析器またはパーサーはコンパイラの中にあり、構文解析のタスクを実行します。

カタログ

1. 概要と主な相違点 2. トップダウン解析とは 3. ボトムアップ解析とは 4. 横並び比較 - 表形式でのトップダウン解析とボトムアップ解析 5. まとめ

トップダウン構文解析は何ですか？

各プログラミング言語には、その言語を表現するためのルールがあります。文法パーサーや構文パーサーは、入力された文字列を受け取り、それが正しいかどうかを文法の結果に基づいてチェックする。つまり、文法は解析木を使って文字列を生成する必要がある。

トップダウン構文解析では、構文解析は開始記号から始まり、与えられた入力文字列に到達することになる。次のような構文生成規則を考える。入力文字列(w)はカドである。

S->cAd

A->ab/A

トップダウン構文解析を行った後の構文木を以下に示す。

自上而下(top down)和自下而上分析(bottom up parsing)的区别

図01：トップダウン構文解析ツリー1

Sはc A dを、Aはbを生成する。文字列はcabdである。必須の文字列ではない。そのため、バックトラック、つまり他の選択肢を使う必要があるのです。

同様に、Sはc A dを生成し、Aに別の選択肢を適用するとAが得られる。これで、必要な文字列が得られる。したがって、パーサーはこの入力文字列を受け入れる。トップダウン構文解析を行った後の構文木を以下に示す。

図02：トップダウン構文解析ツリー2

入力文字列(w)がabcdeの場合

次のような文法生成規則を考える。

S->aABe 社

A->Abc/b

B->d

トップダウン分析では

S->aABe (A->Abcの代わりに)

S->aAbcBe (A->bを置き換える)

S->Abcbe (B->dの代わりに)

ノートルダム

代入は左端の変数から始まり、次の右端の位置へ、といった具合に行われます。したがって、左端の微分に従う。さらに、変数が存在する場合、どのような生成規則を選択するかが重要である。

ボトムアップパースニングは何ですか？

ボトムアップでは、構文解析は別の方法で行われる。解析は入力文字列から開始記号まで行う。次のような構文生成規則を考え、入力文字列をwɛcadとする。

S->cAd

A->ab/A

ボトムアップ構文解析を行った後の構文木を以下に示す。

図03：ボトムアップ構文解析の構文木

与えられた文字列はcadであり、aが生成され、c、a、dの組み合わせで開始記号Sが得られる。

入力文字列(w)がabcdeの場合

次のような文法生成規則を考える。

S->aABe 社

A->Abc/b

B->d

ボトムアップの分析では

S->aABe (B->dの代わりに)

S->aAde (A->Abcの代わり)

S->aAbcde (サブルーチン A->b)

ノートルダム

置換は，右端の変数から始まり，次の左の位置に移動する，というように，派生の左動機法に従って行われる．