How to read reduce/shift conflicts in LR(1) DFA?

Posted by greenoldman on Programmers See other posts from Programmers or by greenoldman
Published on 2012-11-29T21:44:29Z Indexed on 2012/11/29 23:17 UTC
Read the original article Hit count: 181

Filed under:

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)?

© Programmers or respective owner

Related posts about parser