Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 

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?


Ok so would it be similar to...

E  -> T E'  
E' -> + E | ε  
T  -> id 
T  -> id() 
T  -> id(L) 
L  -> E L' 
L' -> ;E | ε
share|improve this question
cstheory is for research-level questions. 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)

share|improve this answer
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.

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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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