LR法
E → E • * B
E → E • + B
非終端記号 B については次の通り:
アイテム集合 4
E → B •
これらのクロージャではドットの後に非終端記号がないため、新たなアイテムが追加されていない。この手続きを新たなアイテム集合がなくなるまで続ける。アイテム集合1, 2, 4 はドットの後に記号がないため、ここで終わりである。アイテム集合 3 についてはドットの後に終端記号 '*' と '+' がある。'*' についての遷移は次のアイテム集合で表される。
アイテム集合 5
E → E * • B
+ B → • 0
+ B → • 1
同様に '+' については次の通り:
アイテム集合 6
E → E + • B
+ B → • 0
+ B → • 1
アイテム集合 5 では、終端記号 '0' と '1'、非終端記号 B を考慮する必要がある。終端記号については既出のアイテム集合 1 と 2 が対応する。非終端記号 B については次のような遷移が導かれる:
アイテム集合 7
E → E * B •
アイテム集合も同様に終端記号 '0' と '1'、非終端記号 B を考慮する必要がある。また、同様に終端記号については既出のアイテム集合 1 と 2 が対応する。非終端記号 B については次のような遷移が導かれる:
アイテム集合 8
E → E + B •
これらのアイテム集合もドットの後に記号がないので、アイテム集合はこれで全部である。これらから、オートマトンの状態遷移表は次の通りとなる:
次の入力記号を見ると '+' であり、アクション表によれば状態 6 に遷移しなければならない。
[0 E 3 '+' 6]
このスタックは有限オートマトンの動作履歴のようなものであり、現在は非終端記号 E を読んだ直後に終端記号 '+' を読んだ状態を示している。このオートマトンの状態遷移表はアクション表の shift 指定と GOTO表から構成される。
次の入力記号は '1' なので、アクション表から状態 2 への遷移となる:
[0 E 3 '+' 6 '1' 2]
前に '1' を読んだときと同様、文法規則の適用により B に還元され、スタックは次のようになる:
[0 E 3 '+' 6 B 8]
これは有限オートマトンが、非終端記号 E と 終端記号 '+' と 非終端記号 B を順に読んだ状態である。状態 8 では常に規則 2 番を適用する。従ってスタック上の3個の状態がその文法規則の右辺の3個の記号に対応する。
[0 E 3]
最後に '$' を入力ストリームから読むと、現在状態は 3 なので「受容」すなわち構文解析完了である。以上から出力ストリームに書かれる規則番号の列は [5, 3, 5, 2] となる。これは "1 + 1" という文字列を右端導出する際の適用規則列を逆転させたものと同じである。
LR法のアルゴリズムは次のように動作する:
スタックは [0] で初期化される。現在状態は常にスタックのトップにある状態で表される。
現在状態と入力にある記号からアクション表を参照する。ここで4つのケースがある: sn に従って状態遷移する。 現在の終端記号を入力ストリームから取り除く。 状態 n をスタックにプッシュし、それを現在状態とする。 rm に従って文法規則を適用する。 番号 m を出力ストリームに書き出す。 m 番の規則の右側にある各記号についてスタックから状態を削除する(例えば E * B なら3個ポップする)。 その時点のスタックのトップを状態とし、それと m 番の文法規則の左側からGOTO表を参照し、そこにある状態をスタックにプッシュして新たな状態とする。 受容の場合、文字列の構文解析が完了。 アクションが指定されていない場合、文法エラーを報告する。
上のステップを「受容」となるか「文法エラー」となるまで繰り返す。
このアルゴリズムが何故うまく動作するのかを説明するため、文字列 "1 + 1" をこの構文解析器で解析する例を示す。下記の表はその処理の各ステップを示したものである。状態はスタックのトップで示されている(一番右の値)。次のアクションは上にあるアクション表を参照して決めている。