Theory, Part I
Operator precedence parsing is based on bottom-up shift-reduce parsing. As an expression is parsed tokens are shifted to a stack. At the appropriate time the stack is reduced by applying the operator to the top of the stack. This is best illustrated by example.
step opr val input action 1
4 * 2 + 1 $
* 2 + 1 $
2 + 1 $
$ 4 2
+ 1 $
+ 1 $
$ 8 1
We define two stacks:
opr, for operators, and
val, for values.
$' designates the end of input or end of stack. Initially the stacks
are empty, and the input contains an expression to parse. Each value, as it is encountered,
is shifted to the
val stack. When the first operator is encountered (step 2),
we shift it to the
opr stack. The second value is shifted to the
val stack in step 3. In step 4, we have a '
opr, and a
+' input symbol. Since we want to multiply before we add (giving multiplication
precedence), we'll reduce the contents of the
val, applying the '
operator to the top of the
val. After reducing, the '
operator will be shifted to
opr in step 5.
This process continues until the input and
opr are empty. If all went well,
we should be left with the answer in the
val. The following table summarizes the
action taken as a function of input and the top of
reduce shift reduce
reduce reduce reduce
shift shift accept
When the input token is '
+', and '
+' is on
opr, we reduce before shifting the new '
This causes the left-most operator to execute first, and implies that addition is left-associative.
If we were to shift instead, then addition would be right-associative. When the input token
*', and '
+' is in
opr, we shift
opr. Later, when reducing, '
is popped before '
+', giving precedence to multiplication. By appropriately
specifying shift and reduce actions, we can control the associativity and precedence of operators
in an expression. When we encounter an operator in the input stream, and an operator is already
on the stack, take the following action:
- If the operators are different, shift to give higher precedence to the input operator.
- If the operators are the same, shift for right associativity.