Search code examples
compiler-constructioncontext-free-grammarleft-recursion

Are these grammars left recursive and why?

I've got these grammars to solve the left recursion. But why are these grammars left recursive? They are not following the schema A -> Aa | b:

1., S → 0S1 | 01

2., S → + SS | * SS

Solution

  • Are these grammars left recursive

    No.

    and why?

    In both cases you can never reach S (which is the only non-terminal) without consuming a terminal first. In the first grammar the only occurrence of S is preceded by the terminal 0 and in the second each occurrence is either preceded by + or *.