# Build LL(1) parsing table for grammar S -> iSeS | iS | a

Task

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

Problem

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.

After left factorization

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


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

• Where in that chart is shown your left factoring?
– rici
Apr 4 '20 at 19:32
• I updated my left factorization try. Apr 4 '20 at 19:43
• 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.
– rici
Apr 4 '20 at 19:49
• Still not right. Notice how $FIRST(S)$ suddenly includes $e$ and $\epsilon$? Try to be a bit more systematic. I'm going away now...
– rici
Apr 4 '20 at 20:11

## 1 Answer

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?

• I updated answer. Apr 4 '20 at 20:46