Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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 | ε
share|improve this question
    
cstheory is for research-level questions. cs.stackexchange.com is more appropriate. –  cody Jan 16 '13 at 20:57
add comment

2 Answers

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
add comment

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
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
add comment

Your Answer

 
discard

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.