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 $ shift

2 $ $ 4 * 2 + 1 $ shift

3 $ * $ 4 2 + 1 $ shift

4 $ * $ 4 2 + 1 $ reduce

5 $ $ 8 + 1 $ shift

6 $ + $ 8 1 $ shift

7 $ + $ 8 1 $ reduce

8 $ $ 9 $ accept

step	opr	val	input	action
1	`$`	`$`	`4 * 2 + 1 $`	shift
2	`$`	`$ 4`	`* 2 + 1 $`	shift
3	`$ *`	`$ 4`	`2 + 1 $`	shift
4	`$ *`	`$ 4 2`	`+ 1 $`	reduce
5	`$`	`$ 8`	`+ 1 $`	shift
6	`$ +`	`$ 8`	`1 $`	shift
7	`$ +`	`$ 8 1`	`$`	reduce
8	`$`	`$ 9`	`$`	accept

We define two stacks: opr, for operators, and val, for values. A ' $' 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 ' *' in 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 opr:

Input

opr + * $

+ reduce shift reduce

* reduce reduce reduce

$ shift shift accept

	Input
opr	`+`	`*`	`$`
`+`	reduce	shift	reduce
`*`	reduce	reduce	reduce
`$`	shift	shift	accept

When the input token is '+', and '+' is on opr, we reduce before shifting the new '+' to opr. 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 is '*', and '+' is in opr, we shift '*' to 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.