この間接的な左回帰のステップバイステップのステップ

Question

私はthis algorithmを見てきましたが、すべての左回帰を削除する必要があります。

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

私はループ内または静止間接の左再帰である文法で終わる試みるものは何でも： は、しかし、私は、この特定の文法の問題に実行していますよ。

this algorithmをこの文法に正しく実装するにはどうすればよいですか？

Answer 1

ルールでは、まず非端末のためにある種の順序を確立し、次に間接再帰が発生するすべてのパスを見つけます。注文が< B < Cなり、非端末Cの再帰のための可能な経路がそうCのための新しいルールは次のようになり

C=> A => Cd 

と

C=> B => Ce 

であろう。この場合

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を超えることはできません） 。 - Jの範囲で未> CD

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

3）B、その結果を残すと直接置き換える

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

2）にCを置き換える：ルールの順序を変更することにより

1）

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）まだ完了していません！ > 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 

woohooの制作に直接左再帰を置き換える - 新しいルールBを交換する必要があります！左回帰自由文法！