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 am reading an explanation (awesome "Parsing Techniques" by D.Grune and C.J.H.Jacobs; p.293 in the 2nd edition) and I moved forward from my last question: How to get lookahead symbol when constructing LR(1) NFA for parser?

Now I have such "problem" (maybe not a problem, but rather need of confirmation from some more knowledgeable people).

The authors present state in LR(0) which has reduce/shift conflict. Then they build DFA for LR(1) for the same grammar. And now they say it does not have a conflict (lookaheads at the end):

S -> E .        eof
E -> E . - T    eof
E -> E . - T    -

and there is an edge from this state labeled - but no labeled eof. Authors says, that on eof there will be reduce, on - there will be shift.

However eof is for shift as well (as lookahead). So my personal understanding of LR(1) DFA is this -- you can drop lookaheads for shifts, because they serve no purpose now -- shifts rely on input, not on lookaheads -- and after that, remove duplicates.

S -> E .        eof
E -> E . - T    

So the lookahead for reduce serves as input really, because at this stage (all required input is read) it is really incoming symbol right now. For shifts, the input symbols are on the edges.

So my question is this -- am I actually right about dropping lookaheads for shifts (after fully constructing DFA)?

share|improve this question

1 Answer 1

up vote 0 down vote accepted

Lookaheads in final form in DFA do not matter -- next symbol for shift is on the edge.

share|improve this answer

Your Answer


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.