1

私はこのような規則を持つ文法を持っています

A -> pq
B -> pr

Block -> { Astar Bstar }

Astar -> Astar A
       | epsilon

Bstar -> Bstar B
       | epsilon

この文法を LALR(1) に変換する方法はありますか? 私が理解できることから、パーサーがpブロック内を見ると、シフト/抽出の競合が発生します。

4

2 に答える 2

4

あなたの言語は正規表現であり、正規表現と同等\{(pq)*(pr)*\}です。問題は、文法への単純な変換では、後にqorがあるかどうかを確認するために 2 文字の先読みが必要になることです。rp

これで両方yaccにタグが付けられparsingたので、「yacc でこれをどのように処理しますか」という実用的な答えを探しているのか、それとも「この言語には LALR(1) 文法がありますか」という理論的な答えを探しているのかが明確ではありません。

実際的な答えとしては、解決策はパントすることです。Aとの認識をB字句解析器に移動し、そこで文字シーケンスpq とprをトークンAととして認識しますB。lex/flex は DFA を使用し、最も長く一致したトークンにバックトラックするため、ここでは任意の先読みに問題はありません。

理論的な答えを得るには、文法を変換して先読みの必要性をなくす必要があります。問題のある構文は(中かっこは無関係です) であり、これは次のような文法を示唆する(pq)*(pr)*ものと同等です。p(qp)*(rp)*r | p(qp)*q | epsilon

Block -> { p Astar Bstar r }
       | { p Astar q }
       | { }
A -> q p
B -> r p
Astar -> Astar A | epsilon
Bstar -> Bstar B | epsilon

別のアプローチは、starルールを分解して、空の文字列と一致しないようにすることです。

Block -> { Aplus Bplus }
       | { Aplus }
       | { Bplus }
       | { }
A -> p q
B -> p r
Aplus -> Aplus A | A
Bplus -> Bplus B | B

同じ言語に対して 2 つの非常に異なる LALR(1) 文法を提供します。

于 2013-05-01T17:54:18.177 に答える
3

LALR(1) 競合が発生している理由を正確に確認することから始めましょう。次に、文法を修正して LALR(1) にすることができるかどうかを確認します。

文法が LALR(1) ではない理由を確認するために、文法のセットを構成する LR(1) を計算することから始めましょう。

(1)
S'     -> .Block [$]
Block  -> .{ Astar Bstar } [$]

(2)
S'     -> Block. [$]

(3)
Block -> { . Astar Bstar } [$]
Astar -> .Astar A [ }p ]
Astar -> .epsilon [ }p ]

(4)
Block -> { Astar . Bstar } [$]
Astar -> Astar .A [ }p]
A     -> .pq [}p]
Bstar -> .epsilon [ }p ]
Bstar -> . Bstar B [ }p ]

この時点で、シンボル p の状態 (4) でシフト/リデュースの競合があるため、停止できA -> .pq [ {p ]ますBStar -> .epsilon [ }p ]。LR(1) 文法にはシフト/リデュースの競合があるため、文法はまったく LR(1) ではありません。つまり、LALR(1) である可能性はありません (すべての LALR(1) 文法も LR であるため)。 （1）文法）。

根本的な問題は、パーサーが a を見たときにp、それが a の先頭を見ているのかA(つまり、それをシフトする必要があることを意味します)、それとも が残っておらず、 の先頭を見ているのかを判断できないことAです。 a B(つまり、 を減らす必要があることを意味しますBstar -> epsilon)。

これを修正するために、少し調整するとどうなるか見てみましょう。私たちが遭遇した問題は、パーサーが a を見てすぐpにシフトするか削減するかを決定する必要があるということです。を見て決定を遅らせる時間を与えてからp、フォローアップのキャラクターを見てはどうでしょうか? これを行うには、書き直して文法を少し変更しましょう

Bstar -> epsilon
Bstar -> Bstar B

なので

Bstar -> epsilon
Bstar -> B Bstar

これで、パーサーは何をすべきかを決定する前に、より多くのトークンを調べることができます。を見ている場合pq、B 関連のものは見ていないことがわかります。が見られる場合pr、B を見ていることがわかり、したがって、2 番目の種類のプロダクションを開始できます。これを行うと、LR(1) 状態がどうなるか見てみましょう。

(1)
S'     -> .Block [$]
Block  -> .{ Astar Bstar } [$]

(2)
S'     -> Block. [$]

(3)
Block -> { . Astar Bstar } [$]
Astar -> .Astar A [ }p ]
Astar -> .epsilon [ }p ]

(4)
Block -> { Astar . Bstar } [$]
Astar -> Astar .A [ }p]
A     -> .pq [}p]
Bstar -> .epsilon [ } ]
Bstar -> . B Bstar [ } ]
B     -> .pr [}]

(5)
Block -> { Astar Bstar . } [$]

(6)
Block -> { Astar Bstar } . [$]

(7)
A     -> p.q [}p]
B     -> p.r [}]

(8)
A     -> .pq [}p]

(9)
B     -> pr. [}]

(10)
Bstar -> B . Bstar [ } ]
Bstar -> . B Bstar [ } ]
B     -> .pr [}]

(11)
B     -> p.r [}]

元のシフト/リデュースの競合がなくなり、この新しい文法にはシフト/リデュースの競合がまったくないことに注意してください。さらに、同じコアを持つ状態のペアがないため、上記の状態のセットは、LALR(1) テーブルにある状態のセットでもあります。したがって、上記の文法は実際に LALR(1) であり、文法の意味をまったく変更していません。

お役に立てれば！

于 2013-05-01T18:28:44.527 に答える