コンパイル原則注16：ボトムアップ構文解析はDFAを構築し、DFAは次の解析の指針を示す

分析テーブルとドライバー・アルゴリズムがLRアナライザーの中核です。

解析中、文法パーサーは常にスタックの先頭、現在の残りの入力の最初のターミネーターの状態に基づいて解析テーブルを照会し、パターンを変更して実行するアクションを決定し、スタックの内容と残りの入力の修正を実現し、1つのパターンから別のパターンに移動し、解析が完了するまで繰り返します。

LR(0)、SLR(1)解析表を作成するための最初のステップです。

サブセット法によるNFAからのDFA構築

前回のブログではNFAを構築する方法を説明しましたが、NFAがあればサブセット法を使ってDFAを構築することができます。

構築方法は、字句解析のNFAからDFAへの構築方法と似ているので、ここでは繰り返しませんが、このDFAの特徴について一言。

DFAの各状態は元のNFAの状態集合です。そして、NFAの各状態はアイテムに対応するので、DFAの各状態はアイテム集合です。

DFAの初期状態は、元のNFAの初期状態からε-closureを解くことで得られ、DFA内のすべての状態はその終了状態です。

字句解析 NFA の状態番号が単なる番号であるのに対し、ここでは状態番号が項目に対応し、各番号が項目に対応し、状態の伝達関係はこれらの項目に基づいています。

ではプロジェクトから直接DFAを構築することも可能です。

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

LR(0)項目集合正準族：ある文法の生の接頭辞を識別するDFAを構成する項目の集合を、その文法のLR(0)項目集合正準族と呼びます。この正準ファミリーは、LR(0) および SLR アナライザーのクラスを構築するための基礎となります。

実際には、この正準ファミリーは、ライブ接頭辞を識別するために構築されるDFAの状態全体、つまり上記のDFAのすべての矩形状態を合わせたものです。この主な理由は、DFAの各状態がLR(0)項目集合であるため、LR(0)項目集合族と呼ばれているからです。

プロジェクトを分類し、名前をつけることから始めましょう：

• ドットの一番右の項目は「法令項目」と呼ばれ、法令項目が表示されると法令アクションを実行できます；
• 文法上の開始記号S'が付された規約の項目を「受諾項目」と呼びます；
• A→α.aβの形の項目を「着手項目」と呼び、aは終端記号。この状態で、次の入力が終端記号aであれば、着手動作が可能；
• A→α.Bβの形の項目を「保留項目」と呼び、Bは非終端記号です。Bβは非終端です。 保留項目」の意味は、Bが法令化されるのを待つことです。この生成式に従って法令化したい場合は、まずBを出す方法を見つけなければならず、それを見てからでないと法令化はできません；

テクトニックDFA

文法G'の拡大を求めて

トポロジー文法： G' = G∪ { S' → S }.

実際、トポロジカル文法の新しい開始記号として新しい非終端S'を導入することから始まり、新しい生成S'→S

クローズ＆ゴー

1. CLOSURE( I ): アイテムセットIから文法表記を経ずに到達したアイテムの集合
2. GO( I, X ): Iから文法記号Xを経由して到達できるすべての項目。Xは単なる文法記号で、終端記号でも非終端記号でもよい。

例

以下の文法Gについて、I = { S → .E }とすると

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

• リクエスト・クローズ(I)

  CLOSURE(I) = { S' → .E, E → .aA, E → .bB }.

  まず、S'→.Eは、文法的な表記をしなくても当然到達可能なアイテムセット自体の要素です。後者の2つの項目は、いずれも初期状態からε-edgeを経由して到達可能であるため、文法的表記なしに項目集合Iから到達可能な項目であるという要件も満たします。

• GO(I,a)を検索

  GO(I, a) = { E→a.A, A→.cA, A→.d }.

  まず、E→a.AはIのプロジェクトからaを経由して直接到達できるプロジェクトで、次の2つのプロジェクトはこのE→aから到達できます。次の2つの項目は、このE→a.Aからε-edge経由で到達可能。これは「Iから文法記号aを介して到達可能なすべての項目」の定義とも一致します。

テクトニックDFA

次の文法G'のDFAを構築しなさい。

E'   E
E   E-T | T
T   T*F | F
F   -F | id

まずCLOSURE( {E' → .E} )を見つけ、それをDFA全体の初期状態として使います：

I0を初期状態として使うには、下の図の左側のような大きな長方形の箱を描き、I0の中にこれらの項目を順番に書いていきます。この箱全体がDFAの初期状態です。そして、この初期状態から始めて、段階的にDFAを構築していきます。このステップ・バイ・ステップの構築プロセスは、初期状態から項目を一つずつ数え、どの文法記号を通してどのような新しい項目が得られるか、そして新しい項目は自然に新しい状態を形成し、その状態は転送に使われた文法記号を通して元の状態に接続されることにほかなりません。

同じルールで操作を繰り返すと、最終的に下図のようなDFAが得られます。

この DFA を使って、生きている接頭辞を識別することができます。字句解析 DFA とは異なり、この DFA のどの状態も最終状態です。つまり、初期状態からいずれかの状態までのパス上のトークンは、DFAが認識できる生の接頭辞に接続されています。

例えば、ステート 3 が認識できるライブ接頭辞は F と E-F です。ステート 6 が認識できるライブ接頭辞は E- だけです。

さて、法令への移行のプロセスを振り返ってみると、興味深いことがわかります。

実際、各瞬間において、スタックの内容は分析された表とオートマトンに関連付けられます。文法記号が散りばめられた状態番号のシーケンスは、すべて上図の左側のDFAのパスと一致します。

DFAが導く次の分析ステップ

1. DFA 各州は異なるライブプレフィックスを識別します；
2. 構文構造的に正しい入力シーケンスの解析の任意の時点で、パーサーが DFA のある状態 i にある場合、状態 i で識別されるライブ接頭辞がスタックに現れ、状態 i がスタックの先頭になります。この時点で状態 i に含まれる LR(0) 項目に基づき、文法解析器は次の解析ステップに進みます；
3. 状態 i に現れる LR(0) 項目は、状態 i が認識できるライブ接頭辞に対して有効。

さて、DFAは良いことのように見えます。では、スタックのトップが状態5にあるとします。この時点で、DFAは次の分析ステップをどのように導くのでしょうか？

効果的なプロジェクト

項目 A → β.β は、最右端の導出：S' =*> αAω => αββω が存在するとき、ライブ接頭辞 αβ に対して有効であるといいます。

項目A→β.βは、ライブ接頭辞αβに対して有効であり、現在のライブ接頭辞がαβである場合に、現在の状態における項目A→β.βが、次の分析動作をαAω⇒αββωと導くことを示す役割を果たします。

すでに読み込まれ、スタック上にあるものはライブ接頭辞です。ライブ接頭辞とは、まだアクティブな接頭辞のことで、どのような記号が追加されるかによって、ハンドルになる可能性があります。はこの生成式で書き出すことができます。

記号列 αββω については、A → ββ で制定できそうです。読み書きヘッドは入力された記号列を1つずつ読み込み、読み込んだときに移動するものも次々とスタックに押し込んでいきます。スタックがαβのとき、すでにA→β.βという項目があることがわかっていれば、次に読むのがβであれば、スタックの先頭がその生成方程式のハンドルを形成できることになり、この項目の次の項目であるA→ββを使って制定することが可能になります。

これは実際に、DFAがどのように分析を導いているかを示しています。

同じアイテムセット内のすべてのアイテムは、このアイテムセット内のすべてのライブ接頭辞に対して有効であることが知られています。つまり、アイテムセット内の各アイテムは、次のアクションを指示する権利を等しく持っています。

効果的なプロジェクトの意義

1. これまでのプロジェクトの分析は正しい；
2. は、次の分析ステップを導くことができます：
   1. A → α.aβ: 現在残っている入力が終端aの場合、aに移動；
   2. B → β.: B → βを生成して制定。