[comp.unix.wizards] Trouble with %prec in yacc

ned@h-three.UUCP (ned) (07/14/88)

I can't seem to override the default precedence for rules
with the %prec keyword.  However, if I set the precedences for the
terminal tokens involved in the declarations section, then they
take effect.  For example,

/* start of works */
%token NAME
%left ADD
%left MULT
%start expr

%%

expr	:	expr MULT expr
	|	expr ADD expr
	|	NAME
	;
/* end of works */

works (and compiles with no shift/reduce conflicts), but

/* start of doesn't work */
%token NAME MULT ADD
%left PREC_ADD
%left PREC_MULT
%start expr

%%

expr	:	expr MULT expr %prec PREC_MULT
	|	expr ADD expr %prec PREC_ADD
	|	NAME
	;
/* end of doesn't work */

doesn't (and compiles with 4 shift/reduce conflicts).  Anyone know
what I'm doing wrong?  Thanks in advance.

-- Ned Robie

djones@megatest.UUCP (Dave Jones) (07/15/88)

From article <237@h-three.UUCP>, by ned@h-three.UUCP (ned):
...

 
> /* start of doesn't work */
> %token NAME MULT ADD
> %left PREC_ADD
> %left PREC_MULT
> %start expr
> 
> %%
> 
> expr	:	expr MULT expr %prec PREC_MULT
> 	|	expr ADD expr %prec PREC_ADD
> 	|	NAME
> 	;
> /* end of doesn't work */
> 
> doesn't (and compiles with 4 shift/reduce conflicts).  Anyone know
> what I'm doing wrong?  Thanks in advance.
> 
> -- Ned Robie

I'm confused also.

It looks to me as though the above should give ADD and MULT the
same precedence.  (That's probably not what you intended.)

The PREC_ADD and PREC_MULT productions both have 
higher priorities than ADD and MULT.  So reductions should always be
prefered to shifts, right?

I don't see why there should be shift/reduce conflicts.

Here is part of the y.output file:

5: shift/reduce conflict (shift 3, red'n 1) on MULT
5: shift/reduce conflict (shift 4, red'n 1) on ADD
state 5
        expr :  expr_MULT expr
        expr :  expr MULT expr_    (1)
        expr :  expr_ADD expr

        MULT  shift 3
        ADD  shift 4
        .  reduce 1

I don't get it.  Why does it not reduce by

    expr <= expr MULT expr

on either ADD or MULT, each of which has a lower priority than
PREC_MULT?  Looks like a bug to me.

Here's the way %prec is commonly used:

%token NAME
%left '+' '-'
%left '*' '/'

%start expr

%%

expr    :       expr mulop expr %prec '*'
        |       expr addop expr %prec '+'
        |       NAME
        ;

mulop   : '*'
        | '/'
        ;

addop   : '+'
        | '-'
        ;

ka@june.cs.washington.edu (Kenneth Almquist) (07/16/88)

ned@h-three.UUCP writes:
> I can't seem to override the default precedence for rules
> with the %prec keyword.  However, if I set the precedences for the
> terminal tokens involved in the declarations section, then they
> take effect.
>
> [examples deleted]

The %prec keyword sets the precedences of the rules just fine.  In
Yacc, both rules and terminal tokens can have precedences.  When Yacc
has to decide between shifting the next input token or reducing a
rule, it compares the precedence of the input token with the precedence
of the rule.  For this comparison to to be made, both the rule and
the input token must have a precedence.  In the example you give that
works, you have assigned precedences to both of these.  In the example
that does not work, you have assigned precedences to the rules, but
have neglected to assign precedences to the terminal tokens ADD and
MULT.  This explanation is rather brief; for a full explanation of
how Yacc handles precedences see the the Yacc manual.
				Kenneth Almquist