構文解析器を使った例
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2015/11/30 09:29 UTC 版)
「ボトムアップ構文解析」の記事における「構文解析器を使った例」の解説
以下に簡単な例を示す。下記のような簡単な文法があるとする。 S → Ax …①A → a …②A → b …③ 入力が "ax" だった場合、左端導出（トップダウン構文解析）では次のように導出される。 (1) S ⇒ （開始記号）(2) Ax ⇒ （①を適用）(3) ax （②を適用） 開始記号(S)以外の非終端記号が1つしかないため、右端導出でも偶然同じ導出となる。 LL(1)構文解析は開始記号(S)から開始し、「どの生成規則を適用すべきか」を判断する。この場合、生成規則の左辺に S があるものは1つしかない。次に A を置き換えるために A に対応する手続きを実施する（再帰下降構文解析の場合）。この場合、 A → a が入力とマッチするのでこれが選択され、構文解析が完了する。導出された構文木は次のようになる。 S / \\A x|a ボトムアップ構文解析では、これを逆から行い、以下のような順で導出する。 (1) ax ⇒ （入力文字列）(2) Ax ⇒ （②を適用）(3) S （①を適用） 直観的に、トップダウン構文解析は非終端記号が左辺にある生成規則を適用して、その右辺の文字列に展開していく。一方、ボトムアップ構文解析は生成規則の左辺と入力がマッチするものを選び、生成規則を逆向きに適用して最終的に開始記号（非終端記号）へと還元させる。ボトムアップ構文解析では、まず "a" を A に置換して "Ax" とし、次に "Ax" を S に置換する。入力された文字列が全体として S に還元された時点で構文解析は成功して停止する。 トップダウン構文解析のように力づくの方法でも機能する。つまり、パターンマッチする生成規則が見つかるまで次々に探索していく方法である。このような単純な例では示せないが、力任せの方法では不適切な規則の適用もあり、さらに規則を適用として後戻り（バックトラッキング）することになる。これは効率的ではない。そのような後戻りを防ぐために入力を先読みして不適切な規則を適用しないという方法もある。 トップダウン構文解析では、どの生成規則を適用するかという判断をしながら解析を進めていく。ボトムアップ構文解析では、以下のような2つの判断をする。 ある時点で shift アクション（トークンをスタックに移す）をすべきか、reduce アクション（生成規則を適用）をすべきか？ reduce アクションをする場合、どの生成規則を適用すべきか？
※この「構文解析器を使った例」の解説は、「ボトムアップ構文解析」の解説の一部です。
「構文解析器を使った例」を含む「ボトムアップ構文解析」の記事については、「ボトムアップ構文解析」の概要を参照ください。
- 構文解析器を使った例のページへのリンク
