Removing Left Recursion with Terminals

Question

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.

Answer 1

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