先読み
reduce - スタック上の E+ と新たな入力 E に対して Rule1 を適用して E とする。
shift - 入力 '*' から Rule2 が適用可能となることを予測しつつ、スタックに退避する。
reduce - Rule3 に基づき '3' を式 E にする。
reduce - スタック上の E* と新たな入力 E に対して Rule2 を適用して E とする。
これによって生成される構文木とコードは、Rule4 が考慮されていないため正しくない。
先読みなしで正しく構文解析するには、次のような対処法がある。
ユーザーが括弧付きで式を書く。これが不可能なことも多い。
構文解析器にバックトラック機能を追加し、規則違反が発生したときなどに再試行する。同様の手法はLL法で使われている。
reduce 実施を遅延させるような論理を導入し、どちらの規則を先に reduce させるのが適切かを規則に照らして判断する。LR法がこのような手法を採用している。これによって正しい構文解析が可能となるが、状態数が増え、スタックも深くなる。
先読みのある構文解析器では、次のように動作する。
shift - 入力 '1' を Rule3 が適用されることを予想しつつスタックに退避する。即座には reduce しない。
reduce - '+' を先読みして、スタック上の '1' を Rule3 に基づいて E に reduce する。