Contents
Page-10
Prev
Next
Page+10
Index
Operator Precedence Parsing
Operator precedence parsing is easily
done using auxiliary stacks for
operands and operators. Tokens are read and processed as follows:
- Operands: push (shift) onto the operand stack.
- Operators:
While prec(top(stack)) ≥ prec(input) , reduce.
Push (shift) input onto the operator stack.
- (: Push ( onto the operator stack;
prec( ( ) < prec(any operator) .
- ): While top(stack) ≠ (, reduce.
Then discard both parentheses.
- End: While operator stack is not empty, reduce.
Result is top of operand stack.
reduce combines the two top operands and the top operator into
a subtree, which is pushed onto the operand stack.
The = part of the ≥ test for operators implements left
associativity, the usual case. For right associativity, use >
instead.