How does operator precedence in Bison work?

Question

This is probably a simple question and has already been asked but I'm having difficulty understanding Bison and in particular operator precedence. If I have this code and + has left association.

%left '+'
%%
S:
   S E ’\n’ { printf("%d\n", $2); }
|
; 

E:
   num { $$ = $1; }
| E '+' E {$$ = $1 + $3;}
| E '*'  E {$$ = $1 * $3;}
; 
%%

The input is 2+3+4*5 and the output is 25. My answer was 45.

Could someone show me step by step what Bison does? I mean how elements are pushed to the stack and how and when they are reduced. Or even the parse tree if is possible.

Answer 1

The easiest way to see what is going on in a grammar is to enable bison's trace facility, explained in the bison manual section on debugging parsers. It's useful to have the state machine handy while you're reading traces, since the trace provides the path through the state machine. To see the state machine, use bison's -v option, which will create a file with extension .output.

$ cat minimal.y
%{
#include <stdio.h>
#include <ctype.h>
int yylex(void);
void yyerror(const char* msg) {
  fprintf(stderr, "%s\n", msg);
}
%}
%token num
%left '+'
%%
S: S E '\n' { printf("%d\n", $2); }
 |
E: num { $$ = $1; }
 | E '+' E {$$ = $1 + $3;}
 | E '*'  E {$$ = $1 * $3;}
%%
int yylex(void) {
  int c;
  do c = getchar(); while (c == ' ');
  if (isdigit(c)) {
    yylval = c - '0';
    return num;
  }
  return c == EOF ? 0 : c;
}
int main(int argc, char* argv[]) {
#if YYDEBUG
  yydebug = 1;
#endif
  return yyparse();
}

Compile and run:

$ bison -t -v -o minimal.c minimal.y
minimal.y: warning: 3 shift/reduce conflicts [-Wconflicts-sr]
$ gcc -Wall -o minimal minimal.c
$ ./minimal <<<'2+3+4*5'
Starting parse
Entering state 0
Reducing stack by rule 2 (line 14):
-> $$ = nterm S ()
Stack now 0

I snipped the trace (although you can see it at the bottom of the answer). Look through the trace for the line which says that it is reading the token *:

Entering state 8
Reading a token: Next token is token '*' ()
Shifting token '*' ()
Entering state 7

Here's the definition of State 8 from minimal.output, complete with shift-reduce conflict (indicated by the square brackets around the action which will not be taken) and the default resolution:

State 8

    4 E: E . '+' E
    4  | E '+' E .
    5  | E . '*' E

    '*'  shift, and go to state 7

    '*'       [reduce using rule 4 (E)]
    $default  reduce using rule 4 (E)

Here's the complete trace (although I strongly encourage you to do the experiment on your own machine):

Starting parse
Entering state 0
Reducing stack by rule 2 (line 14):
-> $$ = nterm S ()
Stack now 0
Entering state 1
Reading a token: Next token is token num ()
Shifting token num ()
Entering state 3
Reducing stack by rule 3 (line 16):
   $1 = token num ()
-> $$ = nterm E ()
Stack now 0 1
Entering state 4
Reading a token: Next token is token '+' ()
Shifting token '+' ()
Entering state 5
Reading a token: Next token is token num ()
Shifting token num ()
Entering state 3
Reducing stack by rule 3 (line 16):
   $1 = token num ()
-> $$ = nterm E ()
Stack now 0 1 4 5
Entering state 8
Reading a token: Next token is token '+' ()
Reducing stack by rule 4 (line 17):
   $1 = nterm E ()
   $2 = token '+' ()
   $3 = nterm E ()
-> $$ = nterm E ()
Stack now 0 1
Entering state 4
Next token is token '+' ()
Shifting token '+' ()
Entering state 5
Reading a token: Next token is token num ()
Shifting token num ()
Entering state 3
Reducing stack by rule 3 (line 16):
   $1 = token num ()
-> $$ = nterm E ()
Stack now 0 1 4 5
Entering state 8
Reading a token: Next token is token '*' ()
Shifting token '*' ()
Entering state 7
Reading a token: Next token is token num ()
Shifting token num ()
Entering state 3
Reducing stack by rule 3 (line 16):
   $1 = token num ()
-> $$ = nterm E ()
Stack now 0 1 4 5 8 7
Entering state 9
Reading a token: Next token is token '\n' ()
Reducing stack by rule 5 (line 18):
   $1 = nterm E ()
   $2 = token '*' ()
   $3 = nterm E ()
-> $$ = nterm E ()
Stack now 0 1 4 5
Entering state 8
Next token is token '\n' ()
Reducing stack by rule 4 (line 17):
   $1 = nterm E ()
   $2 = token '+' ()
   $3 = nterm E ()
-> $$ = nterm E ()
Stack now 0 1
Entering state 4
Next token is token '\n' ()
Shifting token '\n' ()
Entering state 6
Reducing stack by rule 1 (line 13):
   $1 = nterm S ()
   $2 = nterm E ()
   $3 = token '\n' ()
25
-> $$ = nterm S ()
Stack now 0
Entering state 1
Reading a token: Now at end of input.
Shifting token $end ()
Entering state 2
Stack now 0 1 2
Cleanup: popping token $end ()
Cleanup: popping nterm S ()