正規LR法
A1 → A, B, b
A1 → A, B, c
E1 → A, B, d
この場合、AおよびBは先読みされた終端記号がa、b、またはcならばA1に還元され、dの場合はエラーが報告される。
先読みはまた規則をいつ還元すべきかの決定にも役立つ。先読みは先読みされた記号が有効でない場合にその規則での還元の回避を支援できる。これは現在の状態を以前の状態ではなく次の状態と結合させるべきであるということをおそらく意味する。例えば、以下のような状況である。
状態系列: A, B, C
規則:
A1 → A, B A2 → B, C
もし、構文解析器が状態Bに遷移した後の先読みが受理可能でなかった場合、つまり、遷移規則が存在しなかった場合、状態系列は
A1, C
ではなく、次のように還元される。
A, A2
なお、状態は次のように終端記号から直接生成できることに注意する必要がある。
X → y
これは出現する状態系列を考慮に入れる。
LR(1)法は個々の規則が完全なLR(1)の方法で表現される必要があるという要件がある。つまり、特定の先読みをもつ2つの状態からなる系列である。これによって、
X → y
のような単純な規則は、先読みと比較される終端記号と状態のすべての可能な組み合わせを本質的に列挙する非常に多数の不自然な規則を要求する。類似の問題は
A1 → A, B
のような非先読み規則の実装にも現れ、すべての可能な先読みの列挙が必要となる。このため、LR(1)法は著しいメモリ最適化なしでは実用的な実装が不可能である。
残りのアイテム集合は以下のアルゴリズムで作成できる。
既存の各アイテム集合kにおいて•の後に現れる各記号Aについて、•の直後がAであるkのすべての規則を追加することで新しいアイテム集合mを作成する。ただし、mがステップ3以降ですでに存在しているアイテム集合と同じとならない場合に限る。
新しいアイテム集合内の各規則においてすべての•を記号1つ分右にシフトする
新しいアイテム集合の閉包を作成する
新しいアイテム集合が追加されなくなるまで、追加されたすべてのアイテム集合についてステップ1から繰り返す。
今回の例では、アイテム集合0からさらに5つのアイテム集合を得られる。
アイテム集合1(非終端記号E)
[S → E •, $]
アイテム集合2(非終端記号T)
[E → T •, $]
[T → T • + n, $]
[T → T • + n, +]
...
アイテム集合3(終端記号n)
[T → n •, $]