next up previous contents
Next: 4 Abstract Syntax Up: 3 Parsing Previous: 3.3.5 Practical Considerations for   Contents

3.4 Case Study: The Calculator Parser

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

precedence nonassoc	ELSE;
precedence right	OR;
precedence right	AND;
precedence nonassoc	NOT;
precedence left		EQ, LT, GT, LE, GE, NE;
precedence left		PLUS, MINUS;
precedence left		TIMES, DIV;
It 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 CUP 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



fegaras 2012-01-10