How do I remove left recursion on the following rule:
S -> aSAbb | aA
I understand how to perfor开发者_如何学Gom it on S -> SA | A
which becomes S -> A | AS'; S' -> A | AS', but the terminals throw me off in this question.
EDIT:
Sorry, apparently I was confused as to what left recursion is. I should have asked how to remove the left hand symbol from the right hand side.
The rule
S -> aSAbb | aA
is not left recursive. A left recursive rule has the form
A -> Au
where u is a sequence of terminals and nonterminals. To remove the symbol S
from the right side of the S
rules, consider:
S => aSAbb
=> a(aSAbb)Abb
=> a^n(aA)(Abb)^n
The role of the recursion on S
is to produce this sequence. An equivalent grammar is:
S -> aKAbb | aA
K -> aSAbb | aA
The grammars are equivalent, since any derivation
S => aSAbb
=> a(aSAbb)Abb
=> a(a(aSAbb)Abb)Abb
is now just a derivation
S => aKAbb
=> a(aSAbb)Abb
=> a(a(aKAbb)Abb)Abb
and each derivation is terminated by aA
(I think: please correct me if I'm wrong).
精彩评论