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?


closed as unclear what you're asking by Yuval Filmus, Raphael Mar 29 '14 at 11:54

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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).


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