문제

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