端末で左回帰を削除する

Question

左の再帰を次のルールで削除するにはどうすればいいですか：

S - > aSAbb | aA

私はそれをS - > SAで実行する方法を理解しています。 A

これはS→A |として'; S '→A | AS 'だが、端末はこの質問で私を捨てる。

EDIT：

申し訳ありませんが、どうやら私はある再帰を残したものにと混乱していました。私は右手側から左手の記号を取り除く方法を尋ねたはずです。

Answer 1

ルール

S -> aSAbb | aA 

は、再帰的に残っていません。左再帰ルールは、フォームUは端末と非終端記号のシーケンスである

A -> Au 

を有しています。 Sルールの右側からシンボルSを削除するには、考慮してください。

S => aSAbb 
    => a(aSAbb)Abb 
    => a^n(aA)(Abb)^n 

S上の再帰の役割は、このシーケンスを生成することです。同等の文法は次のとおりです。

S -> aKAbb | aA 
K -> aSAbb | aA 

任意の派生

S => aSAbb 
    => a(aSAbb)Abb 
    => a(a(aSAbb)Abb)Abb 

は今ちょうど派生

S => aKAbb 
    => a(aSAbb)Abb 
    => a(a(aKAbb)Abb)Abb 

であり、各導出はaAによって終了しているので文法は、等価である（私は思います。私が間違っている場合は私を修正してください）。