# 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

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

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.