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 | ε
1
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)
2
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.
1