parsing - この間接的な左再帰の段階的な除去

Question

すべての左再帰を削除するために使用できるはずのこのアルゴリズムを見てきました。しかし、私はこの特定の文法で問題に遭遇しています:

A -> Cd
B -> Ce
C -> A | B | f

何をしようとしても、ループになってしまうか、文法が間接左再帰のままになってしまいます。

この文法でこのアルゴリズムを適切に実装する手順は何ですか?

Answer 1

ルールは、最初に非終端記号の順序を確立してから、間接再帰が発生するすべてのパスを見つけることです。

この場合、順序は A < B < C となり、非終端 C の再帰の可能なパスは次のようになります。

C=> A => Cd

と

C=> B => Ce

Cの新しいルールは

C=> Cd | Ce | f

これで、直接左再帰を単純に削除できます。

C=> fC'
C'=> dC' | eC' | eps

結果の非再帰文法は次のようになります。

A => Cd
B => Ce
C => fC'
C' => dC' | eC' | eps

Answer 2

すでにそれを理解しました。

私の混乱は、この順序ではアルゴリズムが何もしないように見えたので、それは間違っているに違いないと考え、最初の反復で A -> Cd を置き換え始めました (j を無視して i を超えることはできません)。

1) ルールを並べ替える:

C -> A | B | f 
A -> Cd
B -> Ce

2) A の C を置換 -> Cd

C -> A | B | f 
A -> Ad | Bd | fd
B -> Ce

3) B はまだ j の範囲内にないため、そのままにして、A の直接左再帰を置き換えます。

C -> A | B | f 
A -> BdA' | fdA'
A'-> dA' | epsylon
B -> Ce

4) B の C を置換 -> Ce

C -> A | B | f 
A -> BdA' | fdA'
A'-> dA' | epsylon
B -> Ae | Be | fe

5) まだ終わっていません！また、新しいルール B -> Ae を置き換える必要があります (A の生成は j の範囲内です)

C -> A | B | f 
A -> BdA' | fdA'
A'-> dA' | epsylon
B -> BdA'e | fdA'e | Be | fe

6) B の生産における直接左再帰を置き換える

C -> A | B | f 
A -> BdA' | fdA'
A'-> dA' | epsylon
B -> fdA'eB' | feB'
B'-> dA'eB' | eB' | epsylon

ウーフー！左再帰の自由な文法！