この文法の項目セットを拡張するにはどうすればよいですか？

Aug 23 2020

私はこの文法を持っています

E -> E + i
E -> i

拡張文法

E' -> E
E -> E + i
E -> i

今度はアイテムセット0を展開しようとします

I0)
 E' -> .E
+E  -> .E + i
+E  -> .i

私が持っているので、その後、.E中にI0私はそれを拡大するだろうが、私は別のを取得しますEので、上のルールを、そして、これが私の最初の疑いがあります。

これで問題ないと仮定すると、次のアイテムセットは

I0)
 E' -> .E
+E  -> .E + i
+E  -> .i

I1) (I moved the dot from I0, no variables at rhs of dot)
E' -> E.
E -> E. + i
E -> i.

I2) (I moved the dot from I1, no vars at rhs of dot)
E -> E +. i

I3) (I moved the dot from I2, also no vars)
E -> E + i.

次に、このDFAを使用します

I0 -(E, i)-> I1 -(+)-> I2 -(i)-> I3
              |                   |
              +-(∅)-> acpt <-(∅)--+

E -> E + i受け入れる必要i + i + ..があるために何かが足りませんが、DFAがI0に戻らないため、私には間違っているようです。私の推測では、I0からI0への遷移があるはずですが、それがドットと関係があるのかわかりません。

回答

2 rici Aug 24 2020 at 00:14

アイテムセットの「拡張」と呼ばれるものは、実際にはクロージャです。それが私が見たアルゴリズムのすべての説明（少なくとも教科書では）で説明されている方法です。他のクロージャ操作と同様に、固定小数点に到達するまで変換を続けます。の作品を含めるとE、それらが含まれます。

ただし、重要な点は、DFAを構築していないということです。あなたはプッシュダウンオートマトンを構築していますが、DFAはその一部にすぎません。DFAはシフト操作に使用されます。新しい端末をシフトすると（現在の解析スタックがハンドルではないため）、DFAに従って状態遷移を実行します。ただし、現在の状態をPDAのスタックにプッシュすることもできます。

興味深い部分は、オートマトンがリダクションを実行することを決定したときに何が起こるかです。これにより、プロダクションの右側が非終端記号に置き換えられます。（スタックの一番上の右側は「ハンドル」と呼ばれます。）リダクションを行うには、スタックを巻き戻し、右側の各シンボル（および対応するDFA状態）を次の先頭に到達するまでポップします。生産。これは、DFAを、最初のシンボルを右側からシフトする前の状態に巻き戻します。（どのプロダクションが使用されたかを確実に知るのはこの時点だけであることに注意してください。）DFAがリセットされると、検出された非終端記号をシフトし、対応するDFA遷移を実行して、解析を続行できます。

この手順の基本は、パーサースタックが常に「実行可能なプレフィックス」であるという事実です。つまり、開始記号から派生できるいくつかの正しいセンテンス形式の接頭辞である記号のシーケンス。文脈自由文法の実行可能な接頭辞のセットについて興味深いのは、それが正規言語であり、その結果、DFAによって認識できることです。上記の削減手順は、ハンドルが「剪定」されたときのこの認識手順を正確に表しています（Knuthの元の語彙を使用するため）。

その意味で、有効な回答が提供される限り、どのハンドルをプルーニングするかを決定するためにどのプロシージャを使用するかは実際には重要ではありません。たとえば、スタックの最上位で潜在的なハンドルが検出されるたびに解析をフォークし、両方のフォークと並行して続行することができます。巧妙なスタック管理により、この並列検索は、文脈自由文法の最悪の場合のO（n ³）時間で実行できます（文法があいまいでない場合は、これを減らすことができます）。これは、アーリーパーサーの非常に大まかな説明です。

ただし、LR（k）パーサーの場合は、文法が明確である必要があります。またk、入力ストリームからのシンボル（O（1））を確認するだけで、削減を識別できる必要があります。k修正されてからの操作。解析の各ポイントで削減するかどうかがわかっている場合、どの削減を選択するかがわかっている場合は、上記で概説したように削減を実装できます。各削減は、固定された文法に対してO（1）時間で実行でき（特定の文法の右側の最大サイズが固定されているため）、解析での削減の数は、入力の場合、解析全体を線形時間で実行できます。

それは少し非公式でしたが、直感的な説明として役立つことを願っています。正式な証明に興味がある場合は、ドナルド・クヌースの元の1965年の論文（左から右への言語の翻訳について）は簡単に見つけられ、これらのことが進むにつれて非常に読みやすくなります。