正規LR法
先読みと比較される終端記号を決定するには、いわゆる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, '+' }
計算機科学において、正規LR法、LR(1)法、正規LR構文解析器、LR(1)構文解析器とは、k=1の場合におけるLR(k)、すなわち、終端記号1つを先読みする構文解析手法/構文解析器である。この手法の特徴は、k>1であるすべてのLR(k)構文解析器がLR(1)構文解析器に変形できるということにある。そのため、LR(1)法はすべての決定性文脈自由言語を扱うことができる。かつてこのLR(k)法は巨大なメモリを必要とするために、LALR法やLL(1)法のようなLR(k)法ほど強力ではない代替手法が選ばれ、使用を避けられてきた。しかし、近年、空間計算量がLALR法ほどである「最小LR(1)法」がいくつかのパーサジェネレータで採用されてきている。
ほとんどの構文解析器と同様に、LR(1)構文解析器は、GNU Bison、MSTA、Menhir、HYACC、 そして、LRSTARのような、パーサジェネレータで自動生成することができる。