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 | ε
TomSelleck
  • 379
  • 3
  • 11
  • cstheory is for *research-level* questions. cs.stackexchange.com is more appropriate. – cody Jan 16 '13 at 20:57

2 Answers2

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)

george
  • 31
  • 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 02: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.

John R. Strohm
  • 18,043
  • 5
  • 46
  • 56