ボトムアップ構文解析

ボトムアップ構文解析（ボトムアップこうぶんかいせき、英: Bottom-up parsing）は、構文解析において、構文木を、木の葉に相当する終端記号の列から始めて、それを順次左辺の非終端記号へ書き換え、最終的に最上位の非終端記号（たとえば「文」）を得る、というような手順によって導出する構文解析の戦略である。逆はトップダウン構文解析。

プログラミング言語の場合

プログラミング言語のコンパイラにおけるボトムアップ構文解析は、最初に終端記号を識別し、それらを徐々に組み合わせていって非終端記号を生成する。この過程で人間の読めるソースコードで書かれたプログラムの構文木が構築され、そこからアセンブリ言語や擬似コードにコンパイルされる。

言語が異なれば構文解析技法も異なるが、実際に必要とされるより強力な構文解析技法を適用することも珍しくない。

ボトムアップ構文解析器による汎用構文解析器もあり、特定のプログラミング言語向けの構文解析器を生成するのに使われる（パーサジェネレータ）。例えば、yaccなどがある。

構文解析器を使った例

以下に簡単な例を示す。下記のような簡単な文法があるとする。

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つの判断をする。

1. ある時点で shift アクション（トークンをスタックに移す）をすべきか、reduce アクション（生成規則を適用）をすべきか？
2. reduce アクションをする場合、どの生成規則を適用すべきか？

ボトムアップ構文解析器の種類

以下に主なボトムアップ構文解析手法を挙げる。

• LR法
  • LR(0) - 先読みをしない方法
  • SLR(1) - 単純で1つだけ先読みする方法
  • LALR(1) - 完全なLR(1)ほど強力ではないが、実装が比較的単純な方法。yacc はこれを使用している。
  • LR(1) - 最も強力だが、実装も複雑になる。
  • LR(n) - n は正の整数であり、n 個のトークンを先読みすることを意味する。言語の設計によっては1より多く先読みが必要となる場合があるが、構文解析が複雑化するため、実用的な言語ではあまりそのような設計はされない。
• 順位構文解析（Precedence parser）
  • 単純順位構文解析
  • 演算子順位構文解析

典型的なボトムアップ構文解析は、shift-reduce 構文解析とも呼ばれる。これは、構文解析時に各入力トークンについて、それをスタックに移す（shift-アクション）か、あるいは生成規則を適用して右辺から左辺に置換する（reduce-アクション）ためである（詳細はLR法を参照）。

外部リンク

• Shift-Reduce Parsing Using the ACTION/GOTO Tables shift-reduce 構文解析の例
• Shift-Reduce Parsing
• Geyacc: Parser Algorithm shift-reduce 衝突を説明した文書
• Bottom-Up Parsing