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: 211
parser
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