正規LR法

LR(1)構文解析表は、各アイテムが先読みによって比較される終端記号を含むように変更することで、LR(0)構文解析表と同様の方法で作成できる。これは、LR(0)法と異なり、処理すべきアイテムの後に異なる終端記号が続く場合、異なるアクションが実行される可能性があることを意味する。

言語の生成規則から始めて、まず、この言語のアイテム集合を決定する必要がある。わかりやすく言えば、アイテム集合とは生成規則のリストであり、各生成規則には現在処理されている記号が含まれている。集合内のアイテムが（次の記号とともに）どの状態遷移とアクションを適用すべきかを決定するために用いられている限り、アイテム集合は構文解析器の状態と1対1で対応している。各アイテムは目印を含んでおり、アイテムが表す規則内において現在処理されている記号が現れる位置を示すために用いられる。LR(1)法においては、各アイテムは先読みによって比較される終端記号に特有であり、したがって、その終端記号もまた各アイテムの内部に記録される。

例えば、終端記号としてn、'+'、'('、')'、非終端記号としてE、T、開始記号としてS、そして以下のような生成規則を含む言語を仮定する。

S → E

E → T

E → ( E )

T → n

T → + T

T → T + n

アイテム集合はLR(0)法の手続きに類似した方法で生成する。初期状態を表すアイテム集合0は開始規則から作成する。

[S → • E, $]

ドット•は規則内の現在の構文解析位置を示す目印である。この規則を適用するために先読みが予期された終端記号はコンマの後に示す。$記号は開始規則の場合のように入力の終わりが予期されたことを示す。

しかし、アイテム集合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]

先読みと比較される終端記号を決定するには、いわゆるFirst集合とFollow集合を用いる。First(A)とは、非終端記号Aに合致する規則のあらゆる連鎖の最初の要素となりうる終端記号の集合である。アイテムI [A → α • B β, x] のFollow(I)とは、非終端記号Bの直後となりうる終端記号の集合であり、ここで、α, βは任意の記号列、xは任意の先読み終端記号である。アイテム集合kおよび非終端記号BのFollow(k,B)とは、•にBが続くようなkに含まれるすべてのアイテムのFollow集合の和集合である。First集合は言語のすべての非終端記号の閉包から直接決定できるが、Follow集合はFirst集合を使用してアイテムから決定される。

今回の例では、下記のアイテム集合の完全なリストから確認できるように、First集合は以下のようになる。

First(S) = { n, '+', '(' }

First(E) = { n, '+', '(' }

First(T) = { n, '+' }

アイテム集合0からFollow集合が以下のように得られる。

Follow(0,S) = { $ }

Follow(0,E) = { $, ')'}

Follow(0,T) = { $, '+', ')' }

ここから、LR(1)法での完全なアイテム集合0は、LR(0)アイテム集合の各アイテムについて、左辺にある非終端記号のFollow集合内の各終端記号に対するコピーを作成することで作成できる。Follow集合の各要素は有効な先読み終端記号である。

[S → • E, $]

[E → • T, $]

[E → • T, )]

[E → • ( E ), $]

[E → • ( E ), )]

[T → • n, $]

[T → • n, +]

[T → • n, )]

[T → • + T, $]

[T → • + T, +]

[T → • + T, )]

[T → • T + n, $]

[T → • T + n, +]

[T → • T + n, )]

残りのアイテム集合は以下のアルゴリズムで作成できる。

1. 既存の各アイテム集合kにおいて•の後に現れる各記号Aについて、•の直後がAであるkのすべての規則を追加することで新しいアイテム集合mを作成する。ただし、mがステップ3以降ですでに存在しているアイテム集合と同じとならない場合に限る。
2. 新しいアイテム集合内の各規則においてすべての•を記号1つ分右にシフトする
3. 新しいアイテム集合の閉包を作成する
4. 新しいアイテム集合が追加されなくなるまで、追加されたすべてのアイテム集合についてステップ1から繰り返す。

今回の例では、アイテム集合0からさらに5つのアイテム集合を得られる。

アイテム集合1（非終端記号E）

[S → E •, $]

アイテム集合2（非終端記号T）

[E → T •, $]

[T → T • + n, $]

[T → T • + n, +]

...

アイテム集合3（終端記号n）

[T → n •, $]

[T → n •, +]

[T → n •, )]

アイテム集合4（終端記号'+'）

[T → + • T, $]

[T → + • T, +]

[T → • n, $]

[T → • n, +]

[T → • + T, $]

[T → • + T, +]

[T → • T + n, $]

[T → • T + n, +]

...

アイテム集合5（終端記号'('）

[E → ( • E ), $]

[E → • T, )]

[E → • ( E ), )]

[T → • n, )]

[T → • n, +]

[T → • + T, )]

[T → • + T, +]

[T → • T + n, )]

[T → • T + n, +]

...

アイテム集合2、4および5からさらにいくつかのアイテム集合が作成される。完全なリストはかなり長いためここでは述べない。この文法の詳細なLR(k)での扱いは例えばに示されている。

LR(1)アイテムの先読みはreduceアクション時（つまり、• の目印が右端にある場合）のみ直接使用される。

LR(1)アイテム [S → a A • B e, c] のコア (core) とは、LR(0)アイテム S → a A • B e のことである。異なるLR(1)アイテムが同じコアを共有する場合もある。

例えば、アイテム集合2では

[E → T •, $]

[T → T • + n, $]

[T → T • + n, +]

となり、構文解析器は次の記号が$ならば還元 [E → T] を要求されるが、次の記号が'+'ならばシフトを要求される。LR(0)構文解析器はアイテムのコアのみを考慮するためこの決定ができず、shift-reduce衝突を報告することに注意されたい。

[A → α • X β, a]を含む状態はラベルXで[A → α X • β, a]を含む状態に遷移する。

それぞれの状態はGOTO表にしたがう遷移をもつ。

もし [A → α • b β, a] が状態I_kにあり、I_kがI_mにラベルbで遷移するならば、アクション表には

action[I_k, b] = "shift m"

を追加する。

もし [A → α •, a] が状態I_kにあるならば、アクション表には

action[I_k, a] = "reduce A → α"

を追加する。

• Syntax Analysis PowerPointプレゼンテーション, Aggelos Kiayias, コネチカット大学
• LR parsing PowerPointプレゼンテーション, Aggelos Kiayias, コネチカット大学
• Practical LR(k) Parser Construction HTMLページ, David Tribble
• First & Follow Sets Construction in Python (Narayana Chikkam)