# Convert grammar into an LL(1) grammar which recognises the same language

I have the following sample question for a compilers exam and wanted to check my solution.

``````Convert the following grammar into an LL(1) grammar which recognises the same
language:

E -> E + T
E -> T
T -> id
T -> id()
T -> id(L)
L -> E;L
L -> E
``````

For my answer I have

``````E  -> T E'
E' -> + T | ε
T  -> id
T  -> id()
T  -> id(L)
L  -> E L'
L' -> ;E | ε
``````

Can anybody verify the answer?

Edit

Ok so would it be similar to...

``````E  -> T E'
E' -> + E | ε
T  -> id
T  -> id()
T  -> id(L)
L  -> E L'
L' -> ;E | ε
``````
-
cstheory is for research-level questions. cs.stackexchange.com is more appropriate. – cody Jan 16 '13 at 20:57

E -> E + T | T
T -> id | id() | id(L)
L -> E;L | E

E -> TE'
E'-> +TE' | ε

L -> E;L | E

L -> EL'
L'-> ;L | ε

you need to transform T as I did with L otherwise it will be an LL(3)

-
No, L is not correct. In the original grammar, L will recognize a list containing one or more expressions. As he has the LL(1) version written, L will recognize a list containing exactly one or two expressions. – John R. Strohm Jan 17 '13 at 2:33
you're right. I edited it – george Jan 17 '13 at 15:30

Close, but not quite.

Consider the sentence "a + b + c", where a, b, and c are all ids.

The original grammar recognizes this, courtesy of the E + T recursion.

Your grammar recognizes "a + b", then crashes, because you do not recur.

[added later] Now, consider "a(b;c;d;e)". Your grammar crashes after "a(b;c", for a similar reason.

-
Oh right.. any idea how to fix it? The exam is in the morning xD – Tom celic Jan 15 '13 at 22:54