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) と SLR/LALR法
上記手続きのステップ4 だけが reduce アクションを生成する。つまり、reduce アクションは必ずアクション表の1つの行で共通となるため、次の入力記号が何であっても文法規則による還元が起きる。これは LR(0) の構文解析表の特徴であり、適用すべき文法規則を決定する前に先読みをしない方式であるためである。あいまいさを排除するために先読みが必要となる文法では、1つの行に複数種類の reduce アクションが存在する可能性があり、上記手続きではそのような表を作成できない。
SLR法やLALR法のようなより洗練された方式では行全体が同じ reduce アクションとはならないような表構築手続きを実施する。つまり、これらの構文解析では LR(0) よりも適用可能な文法の範囲が広い。