cs375 p. 73

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 onto the operand stack.
Operators:
While prec(top-of-stack) &ge prec(op) , reduce.
Push op onto the operator stack.
(: Push ( onto the operator stack;
prec( ( ) < prec(any operator) .
): While top-of-stack &ne (, 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 &ge test for operators implements left associativity, the usual case. For right associativity, use > instead.