LR法
LR法またはLR構文解析器とは、文脈自由文法の構文解析手法/構文解析器である。LR法では、入力を左(Left)から右に読んでいき、右端導出(Rightmost derivation)を行う。このためLRと名づけられている。「LR(k)」といった場合、k は、消費をともなうことなく「先読み」が進められる入力記号の最大数を意味する。通常、k は 1 であり、その場合省略されることが多い。LR(k)の構文解析器が対応する文脈自由文法も LR(k) と呼ばれる。
一般に次に適用される文法規則は事前にわからないので、単一のアイテムだけで構文解析器の状態を特定することはできない。例えば、E → E * B という規則から得られるアイテム E → E • * B とアイテム E → E • + B は共に非終端記号 E を読んだ後で適用可能である。従って構文解析器の状態はアイテムの集合によって特徴付けられる。この例の場合、集合は { E → E • + B, E → E • * B } となる。
これらの構文解析表の作成は「LR(0)アイテム」(ここでは単にアイテムと呼ぶ)の記法に基づいている。アイテム記法とは、文法規則の右辺の各所に特別なドット記号を付与したものである。例えば、規則 E → E + B からは次の4つのアイテムが得られる:
E → • E + B
E → E • + B
E → E + • B
E → E + B •
A → ε という規則からは A → • というアイテムだけが得られる。これらの規則から構文解析器の状態を記述する。例えば、アイテム E → E • + B は、E を認識した状態で次に '+' を読み込み、さらに B に対応する文字列がそれに続くことを期待していることを示す。