Removing Left Recursion with Terminals

3
votes

How do I remove left recursion on the following rule:

S -> aSAbb | aA

I understand how to perform 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.

1
context-free-grammarleft-recursion
It doesn't have left recursion, which is why you are having a hard time. Left recursion requires the rule start with the same nonterminal it is trying to produce, e.g., S-> S ... ; - Ira Baxter
I don't think it's possible. The grammar seems to be a^n aA (Abb)^n and I don't think there is any way to bind those two n's without recursion. - BCS

1 Answers

1
votes

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