Stacks and compilers - Data Structures and Problem Solving Using Java - page 466

1 private static final int EOL = 0;
2 private static final int VALUE = 1;
3 private static final int OPAREN = 2;
4 private static final int CPAREN = 3;
5 private static final int EXP = 4;
6 private static final int MULT = 5;
7 private static final int DIV = 6;
8 private static final int PLUS = 7;
9 private static final int MINUS = 8;
10
11 private static class Precedence
12 {
13 public int inputSymbol;
14 public int topOfStack;
15
16 public Precedence( int inSymbol, int topSymbol )
17 {
18 inputSymbol = inSymbol;
19 topOfStack = topSymbol;
20 }
21 }
22
23 // precTable matches order of Token enumeration
24 private static Precedence [ ] precTable =
25 {
26 new Precedence( 0, -1 ), // EOL
27 new Precedence( 0, 0 ), // VALUE
28 new Precedence( 100, 0 ), // OPAREN
29 new Precedence( 0, 99 ), // CPAREN
30 new Precedence( 6, 5 ), // EXP
31 new Precedence( 3, 4 ), // MULT
32 new Precedence( 3, 4 ), // DIV
33 new Precedence( 1, 2 ), // PLUS
34 new Precedence( 1, 2 ) // MINUS
35 }

figure 11.20
Table of precedences
used to evaluate an
infix expression

A consequence of this rule is that any two operators that have different
precedences are still correctly ordered. However, if a + is on the operator stack
and is also the input symbol, the operator on the top of the stack will appear to
have higher precedence and thus will be popped. This is what we want for
left-associative operators.
Similarly, if a ^ is on the operator stack and is also the input symbol, the
operator on the top of the stack will appear to have lower precedence and thus
it will not be popped. That is what we want for right-associative operators.
The token VALUE never gets placed on the stack, so its precedence is meaning-
less. The end-of-line token is given lowest precedence because it is placed on