Search code examples
grammarleft-recursion

Elimination of left recursion

I am trying to remove left recursion from following grammar:

S -> id = E
S -> id [ E ] = E
E -> E [ E ]
E -> id

I tried to follow the left recursion removal algorithm that is presented at https://en.wikipedia.org/wiki/Left_recursion, but the E -> E [ E ] line gives me problems, how should it be handled? I do not want to get a complete solution to this, just some hints so I can actually learn how this works.

What I have tried so far is this:

E -> E [ E ]
E -> id

becomes:

E -> id E'
E' -> [ E ] E'

Which is incorrect. Am I even on the right track here ?

Solution

  • Following the algorithm you linked to, you want A -> Aα | β and you have

    E -> E [ E ] | id

    so A is E, α is [ E ] and β is id. The result of removing left recursion is A -> β A' and A' -> ε | α A', so you get the rules:

    E -> id E'
E' -> ε | [ E ] E'

    So it looks like you got the right result, you just left out the E' -> ε rule...