ボトムアップ構文解析
以下に主なボトムアップ構文解析手法を挙げる。
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法を参照)。