3.4 Case Study: The Calculator Parser

The file simple_calc.y contains the Bison grammar for the calculator parser (without semantics actions). Notice the section that specifies the precedence and associativity of the terminals symbols:

%nonassoc ELSE
%right OR
%right AND
%nonassoc NOT
%left EQ LT GT LE GE NE
%left PLUS MINUS
%left TIMES DIV

This lists the terminals in order of precedence, from lower to higher. Thus, TIMES and DIV have the highest precedence. For example, 1+3*4 is equivalent to 1+(3*4) since TIMES has higher precedence than PLUS. In addition, the keywords left, right, and nonassoc indicate that the operators have left, right, or no associativity at all, respectively. This means that 1+2+3 is equivalent to (1+2)+3, while (x and y and z) is equivalent to (x and (y and z)). This list is very important for helping Bison resolve shift-reduce conflicts. The reason that we set ELSE to the lowest precendence is to resolve the infamous if-then-else conflict: It basically means that we always shift in case of nested if-then-elses.

Another thing to notice is that, when there is a choice, left recursion is preferred from right recursion, such as in:

expl: expl COMMA exp
    | exp

The file simple_calc.output was generated automatically by Bison (using the option -v) and contains the LALR(1) item sets and transitions of the grammar. This file is very useful when you try to resolve shift-reduce and reduce-reduce conflicts.