Solving a shift/reduce conflict with an explicit precedence

Paul Davis <>
23 Jul 2003 10:39:04 -0400

          From comp.compilers

Related articles
Solving a shift/reduce conflict with an explicit precedence (Paul Davis) (2003-07-23)
Re: Solving a shift/reduce conflict with an explicit precedence (2003-07-25)
Re: Solving a shift/reduce conflict with an explicit precedence (Derk Gwen) (2003-07-25)
| List of all articles for this month |

From: Paul Davis <>
Newsgroups: comp.compilers
Date: 23 Jul 2003 10:39:04 -0400
Organization: Compilers Central
Keywords: parse, yacc, question
Posted-Date: 23 Jul 2003 10:39:04 EDT

I'm having a problem getting rid of a shift/reduce conflict in Bison,
and would appreciate advice on how to set some precedences to do this.
My basic problem is that, for simplicity, I have an ambiguous syntax.
This will never cause a problem in real usage, but I can't convince
Bison of that. I have rules of the form:

      : NAME '=' const_expr
      | NAME '=' NAME

      : expr {..check that expr was actually constant..}

expr : huge_number_of_sub_expr_productions ;

last_sub_expr : NAME ;

'const_expr' is a compile-time constant expression, and NAME is an
identifier. 'const_expr' is identical to a general expression, and
it's checked for const-ness *after* parsing. In correct usage, a
'const_expr' will never include a NAME, since it would no longer be
constant. However, an expr *can* include an identifier, so the 'dummy'
production is ambiguous. The obvious solution to fix this is to
rewrite 'const_expr' so that it doesn't include NAME. However, the
problem is that expressions are complex, and I don't want to duplicate
the entire expression syntax just for the special case of a constant
expression, hence my decision to check for const-ness after parsing.

Given this, is there any way to fix the priorities of the two rules in
'dummy' as follows:

      : NAME '=' const_expr // low priority, check second
      | NAME '=' NAME // high priority, check first

In other words, an input NAME token must reduce, and not shift. My
current attempt to do this is:

%nonassoc NAME
%nonassoc EXPCONST
%nonassoc EXPNAME
      : NAME '=' const_expr %prec EXPCONST // rule 115
      | NAME '=' NAME %prec EXPNAME // rule 116

My reasoning here is that I have to avoid a conflict when the second
'NAME' token is seen. I've given the NAME token a lower precedence
than either of rules 115 or 116, so I should get a reduction if a NAME
is seen. However, I'm still getting a shift.

any ideas on how to fix this? Is there a fool-proof way to do this
with precedences, or any other way to do this short of duplicating the
entire expression syntax for a constant expression?

Many thanks



State 282 contains 1 shift/reduce conflict.

state 282

        dummy -> NAME '=' . const_expr (rule 115)
        dummy -> NAME '=' . NAME (rule 116)

        NAME shift, and go to state 346

        NAME [reduce using rule 221 (@15)]
        $default reduce using rule 221 (@15)

        const_expr go to state 347
        @15 go to state 60


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.