Hello everyone,

I'm really struggling with this problem:
Suppose we have the following grammar fragment for a language that allows an assignment to appear in any context in which an expression is expected: the value of the expression is the right-hand side of the assignment, which is placed into the left-hand-side as a side effect.

expr --> id := expr
     --> term term_tail
term_tail --> + term term_tail | e
term --> factor factor_tail
factor_tail --> * factor factor_tail | e
factor --> ( expr ) | id

The question asks to discuss why it is not LL(1) and what can be done to make it so.
I am thinking that there is a left recursion conflict here but I'm really not sure. I can see that in the first line the assignment operator basically assigns expr to itself which causes a conflict. I couldn't figure it out beyond that (and what I figured out is probably wrong as well! :) ).

I am not looking for quick solutions here just a general direction or some informative explanation so that I may better understand this material

Thank you so much for your help!!

6 Years
Discussion Span
Last Post by sloan31

An LL(k) language requires k tokens of lookahead to make a decision. How many do you need to decide what kind of expr you have?


It's not LL(1) because there would be difficulty in determine which choice to follow if the next token is say "id", because now you have expr --> id := expr or factor --> ( expr ) | id

I would think for the solution to this, you would want to look into left factoring.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.