Converting a grammar into LL(1) grammar: some problems

Question

This is not exactly homework but it is related to my studies:

A grammar for example is like:

E -> E+E|E*E|-E|(E)|id

After removing ambiguity it becomes (starting from lowest precedence operator)

E->-F|F
F->F+G|G
G->G*H|H
H->(E)|id

And after removing the left recursion and left factoring (not needed in this case) the final LL1 grammar is:

E->-F|F
F->GF'
F'->+GF'|e
G->HG'
B->*HG'|e
H->(E)|id

Which gives an error free parser table which works fine. Now about the problem I am facing, suppose the grammar is like this:

E -> E+E|E*E|id=E|(E)|id

Now I am not able to generate a parsing table without conflicts, which means my final grammar is not LL1. Here are the steps:

after removing ambiguity:

E->id=F|F
F->F+G|G
G->G*H|H
H->(E)|id

And after removing the left recursion and left factoring, the grammar becomes:

E->id=F|F
F->GF'
F'->+GF'|e
G->HG'
B->*HG'|e
H->(E)|id

But there is a conflict in the Parser table that I am not able to remove, which means that there is some step that I have missed, or there is some mistake in the steps that I am not able to find. Please tell me what I have done wrong, and how to fix this. I have been working on this problem for a long time now.

Unary Minus operator precedence is not lowest, it's highest always on other binary operators — ammar26

Rafał Rawicki Rafał Rawicki · Accepted Answer · 2012-03-30T23:19:27

Let's say that:

E -> E+E|E*E|id=E|(E)|id

will become:

E -> E+E|E*E|(E)|E'
E' -> id=E|id

then you can go with removing ambiguity and left-hand recursion and get:

E -> GF       FIRST(E) = FIRST(G)
F -> +GF|e
G -> HG'      FIRST(G) = FIRST(H)
G' -> *HG'|e
H -> (E)|E'   FIRST(H) = {(} + FIRST(E') = {(, id} 
E' -> idE''   FIRST(E') = {id}
E'' -> =E|e   FIRST(E'') = {=} + {#}

Of course, the problem is, that you lose the given operator precedence.

The grammar won't be LL(1) if for any nonterminal N, there will be any common elements in FIRST(N -> a) and FIRST(N -> b) for N -> a, N -> b being different productions from N.

As you see, adding a production N -> id= in any other place would break that rule.

You can create a LL(2) grammar (but this is probably not what you want), which can have id=E production at any place. (FIRST2 sets are consisted of 2-element strings).

Also, if you look at the presented grammar one more time:

E -> E+E|E*E|id=E|(E)|id

It's a high chance, that the operator precedence I made in the solution above is the right one for real application. Check it out!

Converting a grammar into LL(1) grammar: some problems

1 Answers