Re: Interpreting shift/reduce conflicts from .output file

[Sylvain Schmitz]

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   ItemType    STAR 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