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}

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 { stmt r: stmt}
stmt { stmt }

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


var id-seq {id r: id}

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.

Edited by pyTony: fixed formatting

5 Years
Discussion Span
Last Post by hennelh

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?

Edited by Taywin: n/a


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?

Edited by hennelh: last line left out


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.

Edited by Taywin: n/a


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

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.