Rewriting Bison grammar to fix shift/reduce conflicts

Question

Here are the relevant parts of my Bison grammar rules:

statement:
  expression ';' |
  IF expression THEN statement ELSE statement END_IF ';' 
  ;

expression:
  IDENTIFIER |
  IDENTIFIER '('expressions')' |
  LIT_INT |
  LIT_REAL |
  BOOL_OP |
  LOG_NOT expression |
  expression operator expression |
  '('expression')'
  ;

expressions:
  expression |
  expressions ',' expression  
  ;

operator: 
  REL_OP |
  ADD_OP |
  MULT_OP |
  LOG_OR  |
  LOG_AND
  ;

When compiling, I get 10 shift/reduce conflicts:

5 conflicts are caused by the LOG_NOT expression rule:

State 45

   25 expression: LOG_NOT expression .
   26           | expression . operator expression

    REL_OP   shift, and go to state 48
    ADD_OP   shift, and go to state 49
    MULT_OP  shift, and go to state 50
    LOG_OR   shift, and go to state 51
    LOG_AND  shift, and go to state 52

    REL_OP    [reduce using rule 25 (expression)]
    ADD_OP    [reduce using rule 25 (expression)]
    MULT_OP   [reduce using rule 25 (expression)]
    LOG_OR    [reduce using rule 25 (expression)]
    LOG_AND   [reduce using rule 25 (expression)]
    $default  reduce using rule 25 (expression)

    operator  go to state 54

5 conflicts are caused by the expressions operator expression rule:

State 62

   26 expression: expression . operator expression
   26           | expression operator expression .

    REL_OP   shift, and go to state 48
    ADD_OP   shift, and go to state 49
    MULT_OP  shift, and go to state 50
    LOG_OR   shift, and go to state 51
    LOG_AND  shift, and go to state 52

    REL_OP    [reduce using rule 26 (expression)]
    ADD_OP    [reduce using rule 26 (expression)]
    MULT_OP   [reduce using rule 26 (expression)]
    LOG_OR    [reduce using rule 26 (expression)]
    LOG_AND   [reduce using rule 26 (expression)]
    $default  reduce using rule 26 (expression)

    operator  go to state 54

I know that the problem has to do with precedence. For instance, if the expression was:

a + b * c

Does Bison shift after the a + and hope to find an expression, or does it reduce the a to an expression? I have a feeling that this is due to the Bison 1-token look-ahead limitation, but I can't figure out how to rewrite the rule(s) to resolve the conflicts.

My professor will take points off for shift/reduce conflicts, so I can't use %expect. My professor has also stated that we cannot use %left or %right precedence values.

This is my first post on Stack, so please let me know if I'm posting this all wrong. I've searched existing posts, but this really seems a case-by-case thing. If I use any code from Stack, I will note the source in my submitted project.

Thanks!

rici rici · Accepted Answer · 2013-09-14T15:13:32

As written, your grammar is ambiguous. So it must have conflicts.

There is no inherent rule of binding precedences, and apparently you're not allowed to use bison's precedence declarations either. If you were allowed to, you wouldn't be able to use operator as a non-terminal, because you need to distinguish between

expr1 + expr2 * expr3             expr1 * expr2 + expr3
  |       |       |                 |       |       |
  |       +---+---+                 +---+---+       |
  |           |                         |           |
  |          expr                      expr         |
  |           |                         |           |
  +-----+-----+                         +-----+-----+         
        |                                     |
       expr                                  expr

And you cannot distinguish between them if + and * are replaced with operator. The terminals actually have to be visible.

Now, here's a quick clue:

expr1 + expr2 + expr3    reduces expr1 + expr2 first
expr1 * expr2 + expr3    reduces expr1 * expr2 first

So in non-terminal-1 + non-terminal-2, non-terminal-1 cannot produce x + y or x * y. But in non-terminal-1 * non-terminal-2, non-terminal-1 can produce `x + y

Rewriting Bison grammar to fix shift/reduce conflicts

2 Answers