ボトムアップ構文解析
以下に簡単な例を示す。下記のような簡単な文法があるとする。
入力が "ax" だった場合、左端導出(トップダウン構文解析)では次のように導出される。
開始記号(S)以外の非終端記号が1つしかないため、右端導出でも偶然同じ導出となる。
LL(1)構文解析は開始記号(S)から開始し、「どの生成規則を適用すべきか」を判断する。この場合、生成規則の左辺に S があるものは1つしかない。次に A を置き換えるために A に対応する手続きを実施する(再帰下降構文解析の場合)。この場合、
が入力とマッチするのでこれが選択され、構文解析が完了する。導出された構文木は次のようになる。
ボトムアップ構文解析では、これを逆から行い、以下のような順で導出する。
直観的に、トップダウン構文解析は非終端記号が左辺にある生成規則を適用して、その右辺の文字列に展開していく。一方、ボトムアップ構文解析は生成規則の左辺と入力がマッチするものを選び、生成規則を逆向きに適用して最終的に開始記号(非終端記号)へと還元させる。