Left Recursion Elimination

[hennelh]

I have a list of productions. There are several instances of left recursion in it. I'm having trouble eliminating them even after reading my notes and the textbook on it.

*Production* (With AST definition)


MuMu-program:   declaration-list; stmt-seq  {Mumuprog l: id r: stmt}


stmt:
id := expr  {assstmt l: id r: expr}
if expr then stmt {ifstmt   l: exp r: stmt }
if expr then stmt else stmt { iftmt l: expr c: stmt r:stmt }
for id := expr to expr do stmt {forstmt l: expr c:expr r: stmt}
break {brkstmt}
null {nullstmt}


stmt-seq:
stmt-seq; stmt { stmt r: stmt}
stmt { stmt }


expr:
integer-constant { expr }
id { expr }
( expr ) { expr }
- expr  { expr }
expr binary-operator expr { op l: expr r: expr}


null:


declaration-list:
var id-seq {id r: id}


id-seq:
id { id }
id-seq, id { id r: id }



I get that Mumu-Program: declaration-list; stmt-seq is the start.
I step into declaration-list: id-seq.
id-seq: id
id-seq: id-seq, id (The instance of left recursion, because the Non-terminal is the first element in the RHS)

My textbook says to introduce a new non-terminal id-seq'
Would the production become:

id-seq: id-seq' , id
id-seq: id
id-seq': id-seq
id-seq': epislon

Not sure if that is all I need to do to eliminate the left recursion of id-seq. Have I defined id-seq' enough?

Thanks in advance for any comments.

[Taywin]

This looks to me very similar to a language grammar. It looks good to me. I assume that epsilon is the terminated value.

OK, from this site http://web.cs.wpi.edu/~kal/PLT/PLT4.1.2.html describing how to eliminate left recursion.

For each rule which contains a left-recursive option,
  A --> A alpha | beta

introduce a new nonterminal A' and rewrite the rule as
  A --> beta A'
  A' --> epsilon | alpha A'

So apply the same way to your problem...

id-seq -> id-seq | id

id-seq -> id , id-seq'
id-seq' -> epsilon | id-seq'

Does that make sense to you?

[hennelh]

Thanks Taywin for helping. Found the link helpful as well. Epsilon is indeed the terminated value.

The initial rule for id-seq(Written in same style as you now):

id-seq -> id | id-seq, id

So would that become:

id-seq -> id-seq', id
id-seq' -> id-seq | epsilon

I think I may still be a bit confused. Is your last example not an incidence of left recursion?

id-seq' -> epsilon | id-seq'

ie. cant that be written as

id-seq' -> id-seq' | epsilon

and therefore be a left recursion example?

[Taywin]

It is not a left recursion because...

id-seq -> id | id-seq, id

has no terminated value, but

id-seq' -> id-seq' | epsilon

has a terminated value which guarantees that the recursion will end eventually. :) That's why the epsilon is there.

[hennelh]

Thank you Taywin. I appreciate the help. This will assist me in studying for my finals. :)