質問

I am reading about Representative Grammars from book, where I encountered the following grammar:

$$ E \rightarrow E + T \ | \ T $$ $$ T \rightarrow T * F \ | \ F $$ $$ F \rightarrow (E) \ | \ id$$

The above grammar is left-recursive, which is bad. So in order to eliminate left recursion, they changed it to the following:

$$ E \rightarrow TE' $$ $$ E' \rightarrow +TE' \ | \ \epsilon $$ $$ T \rightarrow FT' $$ $$ T' \rightarrow *FT' \ | \ \epsilon $$ $$ F \rightarrow (E) \ | \ id $$

But why bother so much? Why not simply use a right recursion instead, like the following:

$$ E \rightarrow T + E \ | \ T$$ $$ T \rightarrow F * T \ | \ F$$ $$ F \rightarrow (E) \ | \ id$$

  • So I am confused about whether the Right Recursive Grammar I thought of is same as the original grammar or not?
  • If not, what's the difference?
  • If they are same, why don't we write all grammars as Right Recursion?

正しい解決策はありません

ライセンス: CC-BY-SA帰属
所属していません cs.stackexchange
scroll top