context-free-grammar - 端子による左再帰の削除

Question

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

S -> aSAbb | aA

S -> SA | で実行する方法を理解しています。あ

これは S -> A になります | なので'; S' -> A | AS'、しかし端末はこの質問で私を怒らせます。

編集：

申し訳ありませんが、左再帰とは何かについて混乱していたようです。右側から左側のシンボルを削除する方法を尋ねる必要がありました。

Answer 1

ルール

S -> aSAbb | aA

再帰的に残されていません。左再帰ルールの形式は

A -> Au

ここで、uは終端記号と非終端記号のシーケンスです。ルール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（私が思う：私が間違っている場合は私を訂正してください）。