コンパイル原理のLL(1), LR(0), SLR, LR(1), LALRの文法比較

編纂原理の試験を終えてからしばらく経ちますが、上記の5つの文法に戸惑った記憶があるので、勉強している人の参考になるような記事を書ければと思います。以下の内容は中国語版の龍本に基づいています、先生が違うため、ところどころ似ているところがあるかもしれません、間違いがあれば、指摘してください、ありがとうございます〜。

以下の記事が元になっています。 LL LR SLR LALRと見分けがつかない。

の4つの文法的含意関係を示す図から始めましょう。 LR(1)の文法が最も範囲が広く、LR(0)の文法が最も範囲が狭い。 . また、4つの文法解析処理の強さ、つまりLR(1)文法解析が最も強く、LR(0)文法解析が最も弱いことも示している。

では、なぜLL(1)文法がないのか？それは、上の4つの文法とは異なるからです。

LL(1)解析はトップダウン解析、lr(0), lr(1), slr(1), lalr(1)はボトムアップ解析です。

Top-down：開始記号を起点に生成規則に従って文を派生させる。導出されたものが使用される。

ボトムアップ：与えられた文法制定から文法の開始記号まで。還元的な慣例が用いられている。

他の4つの文法解析処理は、基本的に、オートマトン（＝LR(0)またはLR(1)のアイテムセット族、後にオートマトンと呼ぶ）の記述 -> 文法解析テーブルの構築 -> 文法解析処理の実行、という大きく3ステップになります。最後の2つのステップは似たり寄ったりで、最初のステップのオートマトンには2種類ある。LR(0)オートマトンとLR(1)オートマトンです。LR(0)とSLR文法はLR(0)オートマトンで解析し、LR(1)とLALR文法はLR(1)オートマトンで解析することにします。LR(1)オートマトンはLR(0)オートマトンと同様に構築されるが、前方探索記号が追加される。

I. LL(1)文法解析

解析のプロセス

LL(1)解析は予測解析とも呼ばれ、文法を最小に分割すること、つまり"|"の生成器を書かず、各生成器の選択集合を書くことから始まります。        次に、入力文字列に対して、一番左の列が非終端記号、一番上の列が入力文字列に現れる終端記号で、文の括弧 "#" が含まれていることに注意して予測分析表を書きます。

続いて、いよいよ予測分析です。授業の先生が板書してくれたので、私は書くのが面倒なので.........自分でやってください。予測分析のプロセスは、この後のLR分析のプロセスとほぼ同じで、一番上の行にあるべき項目は、「ステップ」「シンボルスタック」「残りの文字列」「アクション」です。記号スタックの先頭の記号と残りの文字列の左端の記号が同じなら一致、その逆なら不一致となる。どのジェネレータをシフトさせるかは、上記の予測分析表に基づいて決定する。すなわち、シンボルスタックの先頭の非終端記号と残りの文字列の左端の終端記号に対応するジェネレータをシフトさせるべきである。対応する生成器がない場合は、マッチングが誤りであり、与えられた入力文字列は文法の文ではない、マッチングが完全である場合は、acc（受理）である。

LL(1)文法判定。

主に2つの方法があり、1つは選択集合に頼る方法で、任意の2つの生成器の左側部分が同じである選択集合が空と交差し、両者を同時に押し出すことができなければ、それはLL（1）文法となります。次に、予測解析表に複数の項目がない場合（解析表の1つのセルに1つの生成器しかない場合）、LL(1)文法であることがわかる。

II. LR(0)文法の解析

解析の流れ

つまり、文法が非終端記号から別の非終端記号生成式で始まっていない場合、S'->S を追加するなどして結合する必要があります。

次に、LR(0)オートマトンを構成する必要がありますが、これはドットを加えたもので、ドットの後の記号が処理対象であり、ドットの後に非終端記号が続く場合は、その終端記号が生成方程式の左辺にあるすべての生成子を書き出す必要があります。以上の作業を展開されなくなるまで繰り返す。それらに番号を振って、次のシンボル（つまりドットの後のシンボル）を読み込むとどこにジャンプするのかを書き出す。

そして、左側に項目セットファミリ番号、上側にターミネータと非ターミネータを配置したLR(0)分析表が作成される。真ん中の内容は、その番号を持つ項目集合ファミリーが非終端記号に遭遇したときに、接近すべきか包含すべきかを示し、番号はジャンプ先の項目集合ファミリー番号で、点が生成式の右端に到達すれば包含すべき、逆もまた然りである。ターミネーターに遭遇した場合は、対応するアイテムセット番号を記入すればよい。例えば、(0,a)は0行目a列のS2に対応し、これは項目集合ファミリーI0に対して、次の読み込み記号がaであれば、項目集合ファミリーI2に移動することを意味し、例えば、4行目はr1に対応し、これは項目集合ファミリーI4に対して、次の読み込み記号がターミネータなら、生成式番号（1）に従ってサブサム（subsum）する必要があることを示しています。(0,E)は1に対応し、項目集合ファミリーI4において、次の読み込んだシンボルがターミネータであれば、(1)の生成式に従ってサブサムされるべきことを意味する。は、項目集合ファミリーI0に対して、次に読み込まれたシンボルが非終端記号Eであれば、項目集合ファミリーI1に移行することを意味する。

次に解析処理である。この文法には、最後に別途説明する解析過程がないので、以下の文法では、解析過程の表には触れないことにする。ほとんど同じである。

LR(0)文法判定。

LR(0)文法とは、その文法に対応するオートマトンに移動-復帰の競合がなく、かつ復帰-復帰の競合がない場合である。つまり、LR(0)文法解析ではどちらの競合も解決できないので、その範囲は最小となる。移動-復帰の競合とは、同じ項目集合族に移動可能な生成式と包含可能な生成式が共に存在する場合である。復帰-後退の競合も同様である。

III. SLR文法解析

解析のプロセス

位相文法、ライティングオートマトン、解析処理表はLR(0)文法と同じである。ただし、SLR解析テーブルは、移動-反転の競合が起こりうるため、複数の項目（すなわち、同じフレームにシフトとリダクションの両方）が存在する場合がある。

一眼レフ文法判定。

SLR文法は復帰矛盾を持たない。復帰矛盾があっても、フォローセットで解決できる場合はSLR文法となる。つまり、SLR文法解析処理では、復帰矛盾は解決できるが、復帰移動矛盾は解決できない場合がある。follow setがemptyと交差する場合はSLR文法であるが、その逆はない。もちろん、どちらの競合も存在しなければ、自然である。

IV. LALR文法の解析

解析のプロセス

広辞苑は前回と整合性が取れている。

オートマトンでは、LR(1)オートマトンを作る必要があるが、LR(0)オートマトンとの違いは、前方探索演算子の数が多い点である。LALRでは、同心円状の集合をマージする必要がある。つまり、同じ生成子で異なる順方向探索演算子を持つアイテムの族をマージするのである。

I3 と I6 が統合された場合、対応するセルには S36 を記入する必要がある。

LALR文法判定。

一つの結論は、同心円状の集合をマージしても新たな移動-復帰の競合は生じないが、新たな復帰-復帰の競合は生じ、競合が生じなければLALR文法であり、その逆もまた然りであることである。

V. LR(1)文法解析

解析の流れはLALR文法と同じである。

LR(1)文法判定。

LR(1)文法は比較的大きな範囲を持つので、文法はほとんどLR(1)であり、現在知られているのは、マージされた同心集合がインピュテーション-インピュテーション衝突を生じる場合のみで、それ以外の文法はLR(1)文法でないことが分かっている。

なお、冒頭のグラフから、「小さい文法は大きい文法でなければならない」ということがわかると思います。これは注意する必要があります。

解析プロセスの表。

解析処理は4つの文法とも同じで、状態スタックの先頭と残っている文字列の左端の記号を元に解析表を調べ、着手であれば2つのスタックに数字と非終端記号を詰める。復帰であれば、まず状態スタックの先頭と記号スタックの先頭を出し、非終端記号を記号スタックに入れ、解析表を現在の状態スタックの先頭と残りの文字列の左端の記号を元に調べ、数字を状態スタックに充填する。