Sign up ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

I have the following question:

Convert the following grammar into an LL(1) grammar which recognises the same
language (you may assume that the grammar is unambiguous).
A -> int
A -> int + A
A -> int - A
A -> A - (A)

What are the steps or rules I must follow to convert this grammar to ll(1)?

share|improve this question
This sure sounds like a homework problem. You would do better to explain in more detail where you're stuck. The first thing that comes to mind when I look at this grammar is that the first three productions are ambiguous in the left hand token, and it is left recursive in the final production. Can you come up with a new grammar for the same language that does not have this ambiguity? Can you then eliminate the left recursion? – Eric Lippert Jan 4 '13 at 16:49
I don't even recognize that grammatical definition syntax. – DeadMG Jan 4 '13 at 16:57
@EricLippert I converted your answer to a comment since it's more of a pointer in the right direction than a complete answer. Valid point about this possibly being homework - we don't want to be doing people's homework for them, and if it is homework, there does need to be more explanation of what the problem is. – Thomas Owens Jan 4 '13 at 17:13
Tom, is this a homework problem? If it is, can you be more specific about where you are stuck? We tend to discourage questions where people are trying to get handed answers to coursework. Perhaps make your question more generic or explain what you've done so far and why you don't think it's right. – Thomas Owens Jan 4 '13 at 17:14
Sorry, this is a past exam question for a compiler course I am taking. – Tom celic Jan 4 '13 at 17:49

Your Answer


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

Browse other questions tagged or ask your own question.