正規LR法
もし [A → α • b β, a] が状態Ikにあり、IkがImにラベルbで遷移するならば、アクション表には
action[Ik, b] = "shift m"
を追加する。
$記号は開始規則の場合のように入力の終わりが予期されたことを示す。
しかし、アイテム集合0はこれで完成ではない。各アイテム集合は「閉じる」必要がある。つまり、•に続く各非終端記号に対応するすべての生成規則は、そのようなすべての非終端記号が処理されるまで、アイテム集合に再帰的に含まれなければならない。結果として得られるアイテム集合は開始したアイテム集合の閉包と呼ばれる。
LR(1)では、各生成規則に対して、アイテムは生成規則に後続する可能な先読み終端記号のそれぞれに含まれなければならない。より複雑な言語では、これは一般に非常に大きなアイテム集合を結果としてもたらし、LR(1)法の大きなメモリ要件の原因となっている。
今回の例では、開始記号は非終端記号Eを要求し、さらにEはTを要求しているので、アイテム集合0にはすべての生成規則が含まれる。まず初めに、先読みを見つける問題を無視して単なるLR(0)の場合を見ていく。なお、LR(0)には先読みと比較される終端記号が含まれない。したがって、(先読みなしの)アイテム集合0は以下のようになる。
[S → • E]
[E → • T]
[E → • ( E )]
[T → • n]
[T → • + T]
[T → • T + n]
LR(1)構文解析表は、各アイテムが先読みによって比較される終端記号を含むように変更することで、LR(0)構文解析表と同様の方法で作成できる。これは、LR(0)法と異なり、処理すべきアイテムの後に異なる終端記号が続く場合、異なるアクションが実行される可能性があることを意味する。