コンパイル原則注17：ボトムアップ構文解析 LR(0), SLR(1) 解析テーブルの構築

LR(0)

ある文法Gの位相幾何学的文法G'の生の接頭辞を認識するオートマトンのすべての状態が以下を持たない場合：

1. 移住プロジェクトと法令プロジェクトがあります；
2. 複数の法令項目を含む

GはLR(0)文法と呼ばれます。

下図を見ると、LR(0)文法ではないことがわかります。赤枠で囲んだ状態の項目は、すべてムーブイン・ステート競合があり、そのすべてが上の項目を制定項目、下の項目をムーブイン項目としています。LR(0)文法は、接頭辞が生きているDFAを特定することで、LR分析表を直接作成することができます。

LR(0) 解析表の作成

C = {I, I, ... , I}と仮定します。 , I}

文法生成子には最初に番号が振られ、位相文法の生成子には 0 というラベルが付けられます。

そして、各項目集合Iの添え字kをアナライザーの状態とし、S'→.Sを含む集合の添え字をアナライザーの初期状態とします。

以下にACTION, GOTOサブ・テーブルの作成例を示します：

事例

1. 生成方程式に番号を付け、DFAを描きます。

   (0) S' → E
   (1) E → aA
   (2) E → bB
   (3) A → cA
   (4) A → d
   (5) B →cB
   (6) B → d
   

1. DFA の項目セットから解析器の状態を決定し、解析テーブルの行添え字を記述します。ACTION テーブルの列添え字はすべての終端子、GOTO テーブルの列添え字はトポロジー文法によって追加された新しい非終端子を除くすべての非終端子です。

2. フォームの中身を埋めていく--DFAで移された個々のエッジを実際に動かしていきます。具体的には、ひとつひとつを

   1. 移動項目：初期状態0から、aというラベルの付いたエッジが状態2に接続されます。つまり、構文解析中、スタックの先頭が状態0で、残りの入力がaのとき、移動が実行されます。
   2. 収縮する項目：非終端としてマークされたエッジの GOTO テーブルを埋めます。たとえば、シンタックス・アナライザーは、サブスタックの先頭が0、スタックの先頭がEのとき、1の状態に移ります。したがって、E列0番に1を入れます。
   3. 受信状態の場合。レシーブステートでは、入力シーケンスが読み込まれたので、残りの入力は#です。つまり、スタックの先頭が現在状態1で、残りの入力が#であれば、レシーブアクションを実行できるので、1行目の#列がaccで埋められます。
   4. 法令項目の場合。例として状態6を使います。状態 6 に達したとき、残りの入力文字がどのような終端記号であっても、制定することが可能です。状態 6 の項目で説明した E → aA. の場合、生成方程式 E → aA. で制定できることは明らかです。したがって、ACTION表の6行目のすべての列はr1

   上記の4点ルールで表全体を埋めていくと、最終的に以下のようなLR(0)分析表が完成します。

   

SLR(1)

SLR(1)はコンフリクトを解決する簡単な方法を提案します。それは、生きている接頭辞のDFAを特定し、ターミネータを単純に先読みすることによってSLR(1)の解析表を構築することです。

ライブ接頭辞を認識するDFAにおいて、転入-立法の競合、または制定-立法の競合がある場合、この方法を用いて競合の解決を試みることが可能です。

ここで、LR(0)が解けなかった文法を例にとってみましょう。

この文法はLR(0)文法ではありませんが、SLR(1)文法です。

上のDFAで状態2を観察し、現在のオートマトンがこの状態にあると想像してください：サブスタックのトップがTとして制定され、スタックのトップも現在の状態2にあり、現在の残りの入力は*です。

もし、このオートマトンがもう一歩前を見ないとすると、この状態のオートマトンにとって、状態2のmove-in項目とstatute項目の両方がオプションであるように見えます。これは着手と立法の衝突です。

この葛藤を解決するために、もう一歩先のフィールドに目を向ける番です。つまり、現在残っているインプットを考慮に入れ、プロジェクトの選択に役立てるのです：

• 最初の項目によると、TがEとして制定されている場合、次の*はEに続くことになります。そして、* ∉ FOLLOW(E)、つまり、* に E が続くことはありえません；
• しかし、2番目の項目に従ってムーブインが行われた場合、*がムーブインされるとTに従います。そして、*∈FOLLOW(T)なので、*を移動させても問題は生じません。
• もし*がFOLLOW(T)とFOLLOW(E)の両方に属していれば、この判定方法は機能しません。

他のコンフリクトでも同じ判定方法です。

この相反する行為に対する解をSLR(1)解と呼びます。

SLR 表構文の解析

準備セクションは、LR(0)アナライザーテーブルとほぼ同じ方法で構築されます。各アイテムセットの同じ状態番号がアナライザーの状態番号として使用され、行の添え字としても使用されます。

現在のステートにアイテムA→α.aβとA→α.があり、サブスタックのトップがこのポイントαにあり、リード/ライトヘッドがaをリードする場合、a∈FOLLOW(A)の場合に限り、A→αがαの制定に使用されます。

ある文法に対してSLR(1)表を作成する場合、その表のすべての項目に多重定義がなく、その文法がSLR(1)文法であればよい。SLR(1)表を使用する解析器はSLR(1)解析器と呼ばれます。

非SLR文法の例

つのセンス文法はどちらもSLR(1)文法ではありません。

どのようなバイナリ文法に対してもSLR(1)解析表は作成できません。

例：他をぶら下げる

A → S
S → iCtSS' | a
S' → eS|  
C → b

バイナリ文法ではない非SLR(1)文法

例

S  L=R | R
L → *R | id
R → L

ここでLは左の値、Rは右の値と解釈できます。

計算の結果、そのDFAは以下のようになります。

状態4では、FOLLOW(L)とFOLLOW(R)の両方に"="が存在するので、その状態内ではmove-in-statuteの衝突があり、文法はSLR(1)文法ではありません。

このような非二項文法は、前方を見る終端記号の数を増やすことで矛盾を解決できますが、問題が複雑になるため、一般的には使われません。一方、分離型文法は、前方を見る終端記号をいくら増やしても、分離を解決することはできません。