2

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
3

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)

  • 1
    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
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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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