Re: Interpreting shift/reduce conflicts from .output file

[Frans Englich]

On Sunday 12 June 2005 18:13, Sylvain Schmitz wrote:
> 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.

Yes. To exemplify, this is a valid expression:

3 treat as xs:int* * 3

The first star is a kleene operator, and have higher precendence(defined by 
the language) than multiplification, and hence the expression should be 
interpreted as "(3 treat as xs:int*) * 3".

Similarly, in "3 treat as xs:int* + 3" is the star a kleene operator.

So, I considered this as a standard case of operator precedence, that when "*" 
occured where it should be a kleene operator(the SequenceType), it should 
precede the multiplification operator. Practically, I added a "bogus" token 
for use in %left and %spec, similar to the example given in 
"Context-Dependent Precedence"[1].

FYI, for the language my grammar is for, XPath 2.0, I found this in its spec:

<quote>
The '+' and '*' Kleene operators are tightly bound to the SequenceType 
expression, and have higher precedence than other uses of these symbols. Any 
occurrence of '+' and '*', as well as '?', following a sequence type is 
assumed to be an occurrence indicator. Thus, 4 treat as item() + - 5 is 
interpreted as (4 treat as item()+) - 5, so that the '+' would be an 
occurrence operator, and the '-' in this case would be a subtraction 
operator. To have this interpreted as an addition operator of a negative 
number, the form (4 treat as item()) + -5 would have to be used, so that the 
SequenceType expression is bounded by a parenthesis.
</quote>


btw, GLR parsers seem to be very handy in cases like this, but they should be 
avoided like the plague from a performance perspective, right?


Thanks for the help,

                Frans

1.
http://dinosaur.compilertools.net/bison/bison_8.html#SEC76