Member Avatar for 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.

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?

Member Avatar for 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?

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.

Member Avatar for hennelh

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

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.