12.2 Precedence and associativity

The bigloo lalr(1) parser generator supports operator precedence and associativity. The method for specifying the precedence for terminal symbols is described in Grammar definition. Precedence is assigned to each non-terminal production from the precedence of the last terminal symbol appearing in that production.

Typically, when the parser generator encounters a shift/reduce conflict, it produces a warning message, then chooses to reduce. When a parser generator has precedence and associativity information, it can make a much more sophisticated decision.

Let’s use this simple calculator grammar as an example:

(lalr-grammar
 ((left: op-mult op-div)
  (left: op-add op-sub)
  op-lparen op-rparen
  op-semicolon
  number)

 (file
   (())
   ((file stmt)))
 (stmt
   ((expr op-semicolon) (print expr)))
 (expr
   ((number) number)
   ((expr@a op-add expr@b) (+ a b))
   ((expr@a op-sub expr@b) (- a b))
   ((expr@a op-mult expr@b) (* a b))
   ((expr@a op-div expr@b) (/ a b))
   ((op-lparen expr op-rparen) expr))))

Let’s start with this input:

1 + 2 * 3;

At the point where the parser has read 1 + 2 and the lookahead symbol is *, the parser encounters a shift/reduce conflict. Should it first reduce by the (expr op-add expr) production or shift the * in the hopes of reducing the latter expression first?

The (expr op-add expr) production has gotten its precedence from the op-add terminal symbol. This is the precedence of the reduce. The precedence of the shift comes from the precedence assigned to the lookahead terminal symbol, which is op-mult. Since op-mult has higher precedence, the parser generator in this state chooses to shift and does not produce a warning.

Here’s an example which we can use to demonstrate associativity:

1 + 2 - 3;

The parser generator encounters a similar shift/reduce conflict this time, except that when it tries to determine whether to shift or reduce, it finds that both actions have the same precedence. In this case, the parser generator looks at the associativity of the precedence group containing the op-add and op-sub. Since these are declared to be left-associative, the parser generator chooses to reduce from this state, effectively calculating the 1 + 2. Had these symbols been right-associative, the parser would have chosen to shift, effectively calculating 2 - 3 first. If these symbols had been declared non-associative with the none: keyword, the parser would generate an error if it ever encountered this state.

This document was generated on October 23, 2011 using texi2html 5.0.