1. Bulid parsing table for grammar S -> iSeS | iS | a
  2. Resolve conflicts in this table and simulate parser work for word iiaea


I know how to make a parsing table for unambiguous grammar, and how to simulate parser. However this grammar is an example of dangling else problem.

What I tried

I was tought that I should remove left recursion and left factoring. Then make a table using first and follow. Whatever I tried I got two grammar expressions in the same row of table. Please provide me some hint what to do in this situation.

enter image description here

After left factorization

S ->  iSS' |a
S'-> e S | ε

enter image description here

Because we will never use S' -> ε (there are no other values which can give us e in the Table except Table[S'][e] ) we can remove this production from parsing table.

Final solution

enter image description here

  • $\begingroup$ Where in that chart is shown your left factoring? $\endgroup$ – rici Apr 4 '20 at 19:32
  • $\begingroup$ I updated my left factorization try. $\endgroup$ – grzegorzs Apr 4 '20 at 19:43
  • $\begingroup$ That's not a correct left-factoring. The longest left factor is $iS$, not $i$; as you can see, in your attempt you have simply created a new non-terminal in need of left-factoring. $\endgroup$ – rici Apr 4 '20 at 19:49
  • $\begingroup$ Still not right. Notice how $FIRST(S)$ suddenly includes $e$ and $\epsilon$? Try to be a bit more systematic. I'm going away now... $\endgroup$ – rici Apr 4 '20 at 20:11

Eventually you will end up with having to choose between $S'\to\epsilon$ and $S'\to eS$.

The grammar says that's a conflict. But can't we deduce which is correct? What if we choose $S\to\epsilon$? Will we ever be able to match the e?

  • $\begingroup$ I updated answer. $\endgroup$ – grzegorzs Apr 4 '20 at 20:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.