For example,

Let the Grammar be:


Thus, S->Sa->Saa->...->Saa...aaa->Baa...aaa

What's wrong with this?

Why is right recursion a solution to the problem?

  • 3
    $\begingroup$ Who is saying left recursion is a problem? Then right recursion can be one too, since this is symmetrical. Maybe it depends on what you are doing with the grammar. Are you doing anything that distinguishes left from right? By the way, what kind of grammar are you using? ... there are many kinds, $\endgroup$ – babou Mar 29 '14 at 5:23

I am assuming that you are talking about context free grammars.

There is no difference between the two grammars. They are a different representation of the same set.

What do you mean by a problem?

Left recursion is a problem for LL(k) parsers, but they can handle right recursion. LL(k) parsers are preferred because of they use less stack space and they tend to be faster (not always though).

| cite | improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.