LR法
構文解析表作成の第一段階は、アイテム集合クロージャ間の遷移の決定である。これはちょうど終端記号も非終端記号も読み込む有限オートマトンを検討する要領で決定できる。このオートマトンの開始状態は常に追加された規則から得られるアイテム S → • E で表される状態である。
アイテム集合 0
S → • E
+ E → • E * B
+ E → • E + B
+ E → • B
+ B → • 0
+ B → • 1
アイテムの前に付与されたプラス記号は、そのアイテムがクロージャに追加されたことを意味している。'+'記号が付与されていない初期アイテムをそのアイテム集合の「核」と言う。
初期状態 (S0) から始めて、ここから到達できる全状態を決定する。まず、各アイテムの右辺でドットの次にある記号に注目する。この場合、終端記号 '0' と '1'、および非終端記号 E と B が現われている。記号 x からアイテム集合を見つけるため、次の手続きを実行する:
現在のアイテム集合内の各アイテムで何らかの記号 x の前にドットのある全アイテムの集合 S を求める。
S 内の各アイテムについて、ドットを x の次の位置に移す。
結果として生じたアイテム集合を閉じる。
終端記号 '0' について、この手続きを行うと次のようになる:
アイテム集合 1
B → 0 •
終端記号 '1' については次の通り:
アイテム集合 2
B → 1 •
非終端記号 E では次のようになる:
アイテム集合 3
S → E •
LR法はいわゆるボトムアップ構文解析を行う。つまり、葉から始めて最上位の構文要素にたどり着く。
ほとんどのプログラミング言語の文法は LR(1) で表されるため、LR法はコンパイラがソースコードの構文を解析する際によく使われる。
一般にLR構文解析器と言った場合、文脈自由文法に基づいた特定の言語を理解する特定の構文解析器を意味していることが多い。
LR法には次のような利点がある:
多くのプログラミング言語がLR法(およびそれを一部改変したもの)で構文解析できる。例外として、C++とPerlがある。
LR法の実装は非常に効率的である。
入力を左から右に読んでいく構文解析器の中では、LR構文解析器は構文エラーを可能な限り素早く検出できる。
LR法には次のような欠点がある:
LL法に比べ、コンパイルエラー時のエラーメッセージを適切に出しにくい。
LR構文解析器を1から書くのは難しく、パーサジェネレータを使って生成するのが一般的である。構文解析表の生成手法の違いにより、単純LR法(SLR)、LALR法、正規LR法に分類される。後者ほど大規模な文法を扱える(LALR法はSLR法より強力で、正規LR法はLALR法より強力である)。yaccはLALR法による構文解析器を生成する。
異なる状態間の遷移を決定する前に、文法に次の規則を追加して強化するのが一般的である。
(0) S → E
ここで、S は新たに導入された開始記号であり、E は従来の開始記号である。この規則は構文解析器が入力文字列を受容した際に適用される。
ここでは上述の例の文法を強化して使用する。
(0) S → E
(1) E → E * B
(2) E → E + B
(3) E → B
(4) B → 0
(5) B → 1
この強化された文法についてアイテム集合とそれらの間の遷移を決定する。