Re: Precedence and "overloaded" operators

[Víctor M. González]

(Sorry about the long message, but I accidentally dropped the mailing 
list when replying to Joel. This is our exchange.)

I wrote:
> > That is the precedence you declared, but it shouldn't be relevant for 
> > your example input, which has only one '+'....
> >   
> Ah... Sorry, I got mixed up. The report says: "Conflict between rule 
> 37 and token '+' resolved as reduce ('+' < LCHK)."
> LCHK is the unary operator I mentioned in my previous post. '+' in 
> this case refers, or should refer, to the one used for string. Unless 
> I'm reading this wrong, Bison seems to be confusing the '+' that's 
> used for numerical expressions and the '+' that's used for string 
> concatenation, which I told it is supposed to have the same precedence 
> as STRING_CONCATENATION, which, in turn, is supposed to be higher than 
> LCHK's, not lower.
>
> > You appear to have omitted part of you grammar, so my analysis is a 
> > guess.  Specifically, what's the context of integer?  In order for 
> > the parse you describe to be correct, it looks like '+' would have to 
> > be able to appear after integer in your grammar.  Can it?
> Here's a more complete version:
>
> integer:
>    INTEGER ;
>
> expr:
>    integer |
>    expr '+' expr |
>    expr '-' expr |
>    '+' expr %prec POS |
>    LCHK string ;
>
> string:
>    STRING |
>    string '+' string %prec STRING_CONCATENATION ;
>
> I don't believe I'm reaching any of LALR's limitations, but then 
> again, I'm not exactly versed in compiler theory. It seems to me, 
> though, that the parser shouldn't confuse two precedences just because 
> the productions happen to use the same token. For one, it doesn't 
> confuse the precedences of (expr '+' expr) and ('+' expr).
Joel E. Denny wrote:
> On Sun, 3 Jan 2010, "Víctor M. González" wrote:
>
>   
> > > That is the precedence you declared, but it shouldn't be relevant for your
> > > example input, which has only one '+'....
> > >
> > >       
> > Ah... Sorry, I got mixed up. The report says: "Conflict between rule 37 and
> > token '+' resolved as reduce ('+' < LCHK)."
> > LCHK is the unary operator I mentioned in my previous post. '+' in this case
> > refers, or should refer, to the one used for string. Unless I'm reading this
> > wrong, Bison seems to be confusing the '+' that's used for numerical
> > expressions and the '+' that's used for string concatenation, which I told it
> > is supposed to have the same precedence as STRING_CONCATENATION, which, in
> > turn, is supposed to be higher than LCHK's, not lower.
> > > You appear to have omitted part of you grammar, so my analysis is a guess.
> > > Specifically, what's the context of integer?  In order for the parse you
> > > describe to be correct, it looks like '+' would have to be able to appear
> > > after integer in your grammar.  Can it?
> > >       
> > Here's a more complete version:
> >
> > integer:
> >    INTEGER ;
> >
> > expr:
> >    integer |
> >    expr '+' expr |
> >    expr '-' expr |
> >    '+' expr %prec POS |
> >    LCHK string ;
> >
> > string:
> >    STRING |
> >    string '+' string %prec STRING_CONCATENATION ;
> >     
>
> The conflict is between shifting '+' and reducing by `expr: LCHK string'.  
> The precedence of the reduction `string: string '+' string' is not used 
> for this conflict, so the precedence of STRING_CONCATENATION is 
> irrelevant.  Perhaps you want to declare LCHK to be lower than '+'.
I wrote:
> > Perhaps you want to declare LCHK to be lower than '+'.
> Unfortunately, that's not an option. That would break for something 
> like LCHK STRING '+' INTEGER (it should be ((LCHK STRING) '+' 
> INTEGER), not (LCHK (STRING '+' INTEGER))). I can't move any of the 
> precedences.
Joel E. Denny wrote:
> On Sun, 3 Jan 2010, "Víctor M. González" wrote:
>
>   
> > > Perhaps you want to declare LCHK to be lower than '+'.
> > >       
> > Unfortunately, that's not an option. That would break for something like LCHK
> > STRING '+' INTEGER (it should be ((LCHK STRING) '+' INTEGER), not (LCHK
> > (STRING '+' INTEGER))). I can't move any of the precedences.
> >     
>
> (LCHK (STRING '+' INTEGER))) is grammatically impossible according to the 
> grammar you sent me.
>
> In the future, please do not drop the mailing list when replying.  That 
> way, many different people can offer their expertise, and other users can 
> benefit from the discussion.  Thanks.
Joel E. Denny wrote (again):
> On Sun, 3 Jan 2010, Joel E. Denny wrote:
>
>   
> > On Sun, 3 Jan 2010, "Víctor M. González" wrote:
> >
> >     
> > > > Perhaps you want to declare LCHK to be lower than '+'.
> > > >         
> > > Unfortunately, that's not an option. That would break for something like LCHK
> > > STRING '+' INTEGER (it should be ((LCHK STRING) '+' INTEGER), not (LCHK
> > > (STRING '+' INTEGER))). I can't move any of the precedences.
> > >       
> >
> > (LCHK (STRING '+' INTEGER))) is grammatically impossible according to the 
> > grammar you sent me.
> >     
>
> Sorry, that was not a helpful observation.
>
>   
> > In the future, please do not drop the mailing list when replying.  That 
> > way, many different people can offer their expertise, and other users can 
> > benefit from the discussion.  Thanks.
> >     
>
> Let's go back on the list if you want to discuss this further.  Of course, 
> you'd need to reestablish context for other readers.
My reply:
> (LCHK (STRING '+' INTEGER))) is grammatically impossible according to the 
> grammar you sent me.
Yes, it is, but that's (sort of) what the parser would receive if I was 
to give LCHK a precedence higher than the arithmetic plus. Instead of 
reducing LCHK string to expr, it would shift '+' and fail when it 
encountered the INTEGER. Mmh... but think I see the problem, now. The 
grammar I'm trying to parse requires two look-ahead tokens, not just 
one. You were right, it's a limitation of LALR(1) parsers. I guess I'll 
just stick to the right-recursive rule I was using earlier.

> Sorry, that was not a helpful observation.
No, no. Typing up the reply made me see the problem in my grammar. It 
was actually quite helpful. :-)

> In the future, please do not drop the mailing list when replying.  That 
> way, many different people can offer their expertise, and other users can 
> benefit from the discussion.  Thanks.
Sorry about that. It's my first time posting to a mailing list. I 
(incorrectly) assumed the client would automatically reply publicly, 
rather than just to you. I'll be more careful in the future.