コンパイルの原則 注15：ボトムアップ構文解析 LR解析の基本、LR解析表、LR(0)解析表

LR

LR 分析の特徴

1. 最も一般的なバックトラックのないムーブ・イン・スタチュート・アプローチを使用します；
2. ほとんどすべてのプログラミング言語に適しています；
3. エラーをタイムリーに発見できること；
4. 分析表は複雑で、手作業で作成するのは困難です。

LR分析テーブルとドライバーはLR分析の中心です。

以下のディスカッションは、以下の文法に基づいて行われます：

E → E-T| T		(1)(2)
T → T*F | F		(3)(4)
F → -F| id		(5)(6)

上記の文法は、LRの幅広い応用を説明することもできます：

• ジェネレータは左再帰的
• 同じ記号は単項式にも二項式にもなります。

LR

分析表は、アクション表と転送表の2つの部分に分かれています。

• 両テーブルの行の先頭にはアナライザーのステータス番号があり、これはライブ接頭辞を識別するDFAのステータスに対応しています；

• アクションテーブルのカラムヘッダには、ターミネータと終了文字が含まれています；

• 転送表の列見出しは文法中の非終端記号で、転送表の数字はステータス番号。

• 分析表では

  • s シフト
  • r 削減
  • acc : 受け入れ
  • ブランク：エラー

• 転送テーブルの番号は、行頭のステータス番号に対応しています。

パターンと動き

• 開始パターン：
  • 0: 解析テーブルの左上隅にある「0」に対応し、接頭辞が生きているDFAを識別するための初期状態であり、構文解析はここから開始されます；
  • ω：入力シーケンス全体；
  • パターンを変更する動作：一般的には、テーブルが最初に空白の位置までチェックされてエラーが発生しない限り、最初に移動します。
• エンドグリッド：
  • #0E1：#と0は対になり、Eと1は対になります。Eの後の1は、分析されたテーブルを調べることで得られます；
  • 残りの入力は空なので、#は1つだけ；
  • 受信：スタックの一番上の現在の状態番号は1であり、#は残りの入力シーケンスで読み取られるので、テーブルによると、このアクション[s, 1]はアクションテーブルのaccに対応する、つまり、パターンを変更するにはaccのアクションを実行しなければならないことがわかります。
  • 文法の記号列全体を文法の開始記号Eとして定義し、受信アクションを実行することができます。
• エラーパターン：
  • スタックの先頭のステート番号とリード/ライト・ヘッダが指す次のターミネータに基づいてブランクが読み取られると、エラー・パターンに到達します。

パターンを変えるアクションの意味：

1. action[s,a]=si：現在のスタックトップの状態sと、現在読み込まれている終端aに基づいて、テーブルの行s、列aを検索し、パターンを変更するアクションを決定します；
2. action[s, a] = rj: スタック上のハンドルをj番目のジェネレーターの左側部分に置き換えます；
3. action[s, a] = acc
4. action[s, a] = 空白：エラーを報告

転送テーブルの意味

• goto[s, A] = s' : ノンターミナルの状態遷移。

  アクション[s, a] = rjが実行されたばかりのとき、スタックトップのターミネータはポップされ、スタックトップにあるノンターミネータに置き換えられます。ノンターミネータと対になるステートは、スタックトップのターミネータとスタックトップのサブステートに基づいてgotoテーブルを検索し、そのステートの値が見つかったときにスタックトップに押し込むことで決定する必要があります。

完全な制定アクションは、action[s, a] = rjとgoto[s, A] = s'の2つのステップから構成されます。

LRアナライザーの作業プロセスは、実際には、スタックの内容と残りの入力シーケンスから構成されるバイナリを変更するプロセスとして見ることができます。 解析の開始時のバイナリは、各中間ステップの結果は、スタック上のすべての文法記号と状態の組み合わせから構成されるシーケンスとして表現することができます。このシーケンスは a~a 法令によって形成されるライブ接頭辞です。

• ムーブイン：aiをムーブインする場合、まずaiをスタックに乗せ、smとaiに従って解析テーブルをチェックし、次の状態sを決定します；
• statute: 各 statute の後、goto テーブルが検索され、スタックの先頭と対になるステート番号が生成されます。
  • action[s, a] = statute A → β の場合、スタックの先頭の記号がβの文法記号の並びを形成し、制定できることを意味します。
  • 規約は、β全体をスタックから取り出し、Aをスタックに置くことを要求します。
  • この時点で、次のスタックトップのsとスタックトップのAの値によってgotoテーブルを調べ、その結果goto[ s, A] = sをスタックに入れます。このsがAと対になった状態です。

LR分析アルゴリズム：id--id*idの分析例は以下の通りです：

その時、生徒が言ったんでしょうね：

"あ～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～全体は問題ないです。

いい質問だし、重要なことですが、なぜなのでしょうか？これは次の記事で取り上げます。

LR(k)

文法GがLR(k)文法であるのは、その解析表に多重定義項目を含まず、対応する解析器がLR(k)解析器であり、対応する言語がLR(k)言語である場合。

ここで、L: 左から右へのスキャン、R: 逆順は右端の導出、k: 次のアクションを決定するために前方にスキャンされる終端記号の数 - スタックの先頭が特定の生成式の右部分であると決定されたとき、その生成式と逆順の制定法を使用するかどうかを決定するために、入力シーケンスを通してk個のより多くの記号を後方にスキャンする必要があります。一般にk<=1であり、k=1はLRと略されます。

法令スタックの先頭で利用可能なジェネレータの選択肢が1つ以上ある場合、どのジェネレータを法令に使用するかの決定は、入力シーケンスの後の方でターミネータの1つをスキャンすることによって支援することができます。

LR分析計は分析計の一種です。分析テーブルの構造により、LR(0)、SLR(1)、LALR(1)、LR(1)に分けられます。これらの分析器は、機能性と構築の難易度の高い順に並んでいます。一般にk>1のアナライザは構築されません。

LR(0)項目およびLR(0)項目セット仕様ファミリー

LR(0) テーブル構築ステップを分析：

1. 文法 G のすべての接頭辞を認識する DFA を構築；
2. DFAからLR分析表を作成

DFAも、NFAを構築し、それを基にDFAに変更する方法と、DFAを直接構築する方法の2通りがあります。

この記事の残りの部分では、まずNFAの構築方法について説明します。

ライブプレフィックス

文法 G において、記号 α の列の右側に 0 個以上の終端記号を追加した後、正しい構文パターンを形成することが可能で、α がそのパターンのハンドルの後に記号を含まない場合、α は G のライブ接頭辞です。

• 導出の過程で、各直接導出が文型の最右端の非終端を置き換える場合、それを最右端導出と呼びます。右端導出の結果得られる文型を右文型と呼びます；
• 文型の左端の直接句；
• LR 解析のどの時点でも、スタック内のシーケンスはライブ接頭辞です。入力文字列が構文的に正しく構成されていれば、入力文字列の残りをこのライブ接頭辞の後ろにマッチさせることで、正しい文型を形成することができます；
• ライブ接頭辞は実際には記号列であり、文法は多くのライブ接頭辞を持つことになります；
• これまでの解析は、スキャンされた入力シーケンスがすべてライブ接頭辞として統計的に表現できることが保証されている限り正しい。

この生きている接頭辞というのは、柔軟性のある接頭辞のことだと思います。生きた接頭辞とは、まず接頭辞であり、そしてまた柔軟なものです。

ライブ接頭辞の例を挙げてください：

LR(0)アナライザーを構築する鍵：全てのライブ接頭辞を認識するGのDFAを構築すること。

ステップ：ライブ接頭辞を識別するNFAを構築し、決定化と最小化によりDFAに変換。

このNFAは、初期状態から最終状態までの経路上のマーカーが生の接頭辞である、すべての文法Gの生の接頭辞を識別するために使われるものです。

状態遷移図：

E→E＋Tの生成式は、Eが実際にはプラス記号に接続されたEに由来する記号列と、それに接続されたTに由来する記号列にすぎないことを示しています。

図の状態0は状態遷移図の初期状態を表し、その後いくつかの状態が続きます。オートマトンが状態0に接続された状態1にジャンプするとき、オートマトンはすでにEに由来する入力シーケンスを見たことを意味します。

つまり、ライブ接頭辞を識別するということは、NFAの状態に、私が生成記号のどの部分を見て、どの部分を見ていないかを記録すること、つまり、ライブ接頭辞を識別するNFAの状態は、生成記号、見たもの、まだ見ていないものに関する情報を含み、具現化する必要があるのです

LR(0)

NFAの各状態は、初期状態から現在の状態まで、どの生成式の右の部分がどれだけ見られたかを**記録できるべきです。** そしてそれに基づいて次に何をすべきか、すなわちアナライザーが現在の状態にある場合、次に選択すべきアクションが着手なのか制定なのか、制定であればどの生成式を制定に使用するのかを決定します。

生成方程式の右側で結ばれた点。 右側の位置はNFA状態を表します。この後にNFA状態を表すLR(0)項目が続きます。

LR(0)の項目は、右辺のどこかに点" . ".特別に、A → εに対して、1つのプロジェクトA → .

このような項目はNFAの状態を表し、前のドットは見た生成部分を、後ろのドットは見ていない生成部分を示します。

例えば、生成方程式A → XYZには、A → .XYZ、A → X.YZ、A → XY.Z、A → XYZの4つの項目があります。

プロジェクトの意義

プロジェクト記述分析プロセスの各瞬間は、例えば、生成式のどのように大きな部分を見てきました：

• A → .XYZは、次の入力文字列でXYZから押し出せる記号列を見たいので、見たい場合はここに移動してください、という意味です。
• A → X.YZは、入力文字列のXから発進できるシンボルの文字列をすでに見ていて、YZから発進できるシンボルの文字列を見たい場合、ここに移動し続ける必要があることを意味します。
• A → XYZ.は、現在のスタックの一番上にハンドルが形成され、その時点で制定が実行できることを示します。

例えば次のような例です：

次のコースはおそらくこんな感じ：

文法G => 文法GのLR(0)プロジェクト => Gの全生存接頭辞を識別するNFAを構築 => Gの全生存接頭辞を識別するDFAを構築 => 文法GのLR(0)解析表を構築

字句解析におけるNFA構築の道筋に近い。

ライブ接頭辞を識別するためのNFAは、文法のLR(0)項目から構成されます。

1. 各LR(0)項目はNFAの状態

2. Σ：文法記号とε

3. 一次状態：左側に文法上の開始記号があり、右側の一番左に点がある項目

4. 終了状態：NFAのすべての状態

5. 状態遷移関係の移動：状態iとjが同じ生成方程式から来ており、状態jのドットが状態iのドットより1つだけ後ろの位置にある場合、iから状態jにYとラベル付けされた辺を引きます；

   状態iのドットの後に非終端、例えばi: X → α.Aβが続く場合、iからすべての状態A → .γにε個のエッジを引きます。

以下に文法Gの例を示します：

S' → E
E → aA| bB
A → cA| d
B → cB| d

そのプロジェクト

1 S'  .E
2 S'  E.
3 E  .aA
4 E  a.A
5 E  aA.
6 A  .cA
7 A  c.A
8 A → cA.
9 A → .d
10 A → d.
11 E → .bB
12 E → b.B
13 E → bB.
14 B → .cB
15 B → c.B
16 B → cB.
17 B → .d
18 B → d.

方法：