Interpreting shift/reduce conflicts from .output file
Hi, In my grammar I have 2 shift/reduce conflicts. I could find those by staring at my grammar until I find where I introduced it, but I thought I could learn to make use of Bison's nifty debugging -- the output file. At the top of my .output file it says: State 118 conflicts: 2 shift/reduce And state 118 looks like this: --- state 118 72 SequenceType: ItemType . 73 | ItemType . STAR 74 | ItemType . PLUS 75 | ItemType . QUESTION_MARK PLUS shift, and go to state 134 STAR shift, and go to state 135 QUESTION_MARK shift, and go to state 136 PLUS [reduce using rule 72 (SequenceType)] STAR [reduce using rule 72 (SequenceType)] $default reduce using rule 72 (SequenceType) --- State 134, 135, and 136 looks all very similar. For example, state 134 looks like this: state 134 74 SequenceType: ItemType PLUS . $default reduce using rule 74 (SequenceType) I fail to understand what is the problem, and hence how to fix it. AFAICT, both (for example) state 134 and 118 reduces the tokens to a SequenceType. I don't see where the ambiguity is. I'm neither fully sure about what the brackets are communicating in state 118. Perhaps my confusion can be cleared from what I've written so far? For those interested, the grammar can be found here: http://websvn.kde.org/*checkout*/branches/work/kdom/xpath/impl/parser/Parser.output?rev=424401 http://websvn.kde.org/*checkout*/branches/work/kdom/xpath/impl/parser/Parser.ypp?rev=424401 Cheers, Frans ___ Help-bison@gnu.org http://lists.gnu.org/mailman/listinfo/help-bison
Re: Interpreting shift/reduce conflicts from .output file
look in the output file for all of the 'go to state 118', this will give you the hints were the grammar are conflicting. hope this helps Henrik On Sunday 12 June 2005 15.04, Frans Englich wrote: > Hi, > > In my grammar I have 2 shift/reduce conflicts. I could find those by > staring at my grammar until I find where I introduced it, but I thought I > could learn to make use of Bison's nifty debugging -- the output file. > > At the top of my .output file it says: > > State 118 conflicts: 2 shift/reduce > > > And state 118 looks like this: > > --- > state 118 > >72 SequenceType: ItemType . >73 | ItemType . STAR >74 | ItemType . PLUS >75 | ItemType . QUESTION_MARK > > PLUS shift, and go to state 134 > STAR shift, and go to state 135 > QUESTION_MARK shift, and go to state 136 > > PLUS [reduce using rule 72 (SequenceType)] > STAR [reduce using rule 72 (SequenceType)] > $default reduce using rule 72 (SequenceType) > > --- > State 134, 135, and 136 looks all very similar. For example, state 134 > looks like this: > > state 134 > >74 SequenceType: ItemType PLUS . > > $default reduce using rule 74 (SequenceType) > > > I fail to understand what is the problem, and hence how to fix it. AFAICT, > both (for example) state 134 and 118 reduces the tokens to a SequenceType. > I don't see where the ambiguity is. I'm neither fully sure about what the > brackets are communicating in state 118. > > Perhaps my confusion can be cleared from what I've written so far? > > For those interested, the grammar can be found here: > > http://websvn.kde.org/*checkout*/branches/work/kdom/xpath/impl/parser/Parse >r.output?rev=424401 > http://websvn.kde.org/*checkout*/branches/work/kdom/xpath/impl/parser/Parse >r.ypp?rev=424401 > > > Cheers, > > Frans > > > ___ > Help-bison@gnu.org http://lists.gnu.org/mailman/listinfo/help-bison ___ Help-bison@gnu.org http://lists.gnu.org/mailman/listinfo/help-bison
Re: Interpreting shift/reduce conflicts from .output file
Frans Englich wrote: state 118 72 SequenceType: ItemType . 73 | ItemType . STAR 74 | ItemType . PLUS 75 | ItemType . QUESTION_MARK PLUS shift, and go to state 134 STAR shift, and go to state 135 QUESTION_MARK shift, and go to state 136 PLUS [reduce using rule 72 (SequenceType)] STAR [reduce using rule 72 (SequenceType)] $default reduce using rule 72 (SequenceType) bison tells you in the output file that, in state 118, seeing PLUS or STAR in its lookahead window, he cannot choose between shift (to states 134 and 135 respectively) and reduce (using rule 72: "SequenceType: ItemType"). It seems that your SequenceType can be followed by a STAR or a PLUS in some other rules (rules 17 and 20 to be precise), so when bison has recognized an ItemType, he doesn't know which parsing action to do, shift or reduce. The brackets indicate that the reduction will not occur in front of PLUS or STAR because shift has the priority in bison. In general, what you should do: 1) first try to remove the conflict by rewriting your grammar. This can be difficult, and dangerous if you end up recognizing a language different from the one you intended to parse. 2) otherwise find in which cases this shift/reduce conflict can occur, and see if the default shift is good enough; if this is the case, %expect is your friend. 3) otherwise try 1) harder. 4) turn to a GLR parser using %glr-parser. Looking at your grammar, one can have the derivations MutliplicativeExpr => MultiplicativeExpr STAR UnionExpr (rule 20) => UnionExpr STAR UnionExpr (rule 19) =>InstanceOfExpr STAR UnionExpr (rule 28) => TreatExpr INSTANCE OF SequenceType STAR UnionExpr (rule 30), and then => TreatExpr INSTANCE OF ItemTypeSTAR UnionExpr (rule 72) or => TreatExpr INSTANCE OF ItemType STAR STAR UnionExpr (rule 73) This language is not easily generated in an LALR(1) grammar. Can you modify it, for instance by adding parenthesis around the SequenceType? state 134 74 SequenceType: ItemType PLUS . $default reduce using rule 74 (SequenceType) There is no conflicting shift action there, only a reduce. -- Sylvain ___ Help-bison@gnu.org http://lists.gnu.org/mailman/listinfo/help-bison
