Can there still be infinite recursion if I remove all left recursion?
-
05-11-2019 - |
Question
I have to transform the following grammar into a non left recursive grammar:
S → aSb | bAS
A → AaA | bAA | AAa | bAb
This is what I came up with:
A → bAAA’| bAbA’
A’ → aAA’| AaA’| ε
S → aSb | bAS
As far as I can tell, there is no more left recursion because none of the leftmost symbols on the RHS are the same as the nonterminal on the left. However, assuming S is the starting symbol, there is still infinite recursion because A calls itself repeatedly. Is this expected? Or did I derive the non left recursive grammar incorrectly?
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange