0

この文法の左再帰除去アルゴリズムを終了する方法がわかりません。

S ::= a B | B S b | S a | S B A | b
B ::= S b A | B B | A S B | a
D ::= b a | S b
A ::= b S A | b | a b

これが私の仕事です。

using the order S, B, D, A.

S ::= a B M | B S b M | b M
M ::= a M | B A M | ε

B ::= a B M b A | B S b M b A | b M b A | B B | A S B | a

B ::= a B M b A N | b M b A N | A S B b A N | a N
N ::= S b M N | B N | ε

ここからどう進めばいいですか？

4

1 に答える 1

2

ドラゴンブックより。

次のルールがあるとします。

A → Aα1 | ... | Aαm | β1 | ... | βn

ここで、βi は非左再帰的な右辺であり、次のように記述します。

A → β1 A' | ... | βn A'
A' → α1 A' | ... | αm A' | ε

すべての左再帰を削除するには、このアルゴリズムを使用して、各非終端記号 A1...An に番号を割り当て、次のようにします。

for(int i = 1; i <= n; i++)
    for(int j = 1; j < i; j++)
        foreach(Ai → Ajα && Aj → β1 | ... | βn)
            replace with Ai → β1α |... | βnα
   remove left recursion from Ai
于 2013-11-02T02:37:26.987 に答える