正規LR法
LR(1)法は決定性オートマトンを用いているが、オートマトンとしての動作は静的な状態遷移表に基づいている。状態遷移表はオートマトンが認識する言語の文法をコード化しており、概して「構文解析表」と呼ばれる。
LR(1)法の構文解析表は先読みと比較される終端記号によってパラメータ化される。単純な構文解析表(LR(0)法で用いられるようなもの)は以下の形式で文法規則を表現する。
A1 → A, B
これは、状態Aから状態Bに遷移したならば、次に状態A1に遷移することを意味する。このような規則を先読みによってパラメータ化すると、次を得る。
A1 → A, B, a
これは、先読みされた終端記号がaであったときのみ遷移が発生することを意味する。これによって、先読みされた文脈によって単純な規則が多様な意味をもつようなより豊かな言語を考慮できる。例えば、LR(1)文法では、同じ状態系列に基づいているにもかかわらず、以下のすべての規則が別の異なる状態へ遷移する。
A1 → A, B, a
A2 → A, B, b
A3 → A, B, c
A4 → A, B, d
先読みされた終端記号を考慮しなかった場合、同じことは当てはまらない。構文解析エラーについては、エラーとする規則を宣言することで構文解析器が入力全体を読み取ることなく識別できる。例えば、
E1 → B, C, d
は構文解析器の停止を引き起こすようなエラーであると宣言できる。これは以下の例のように、先読み情報もまたエラーを補足するために使用できることを意味する。
A1 → A, B, a
アイテム集合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, )]