Operator-Precedence Parser

1. What it is

An operator-precedence (OP) parser is a bottom-up shift–reduce parser whose shift/reduce decision is based only on a precedence relation table between terminal symbols (operators) — not on a full LR state machine.

2. Operator grammar preconditions

The grammar must be an operator grammar:

• no $\epsilon$-production,
• no two adjacent nonterminals on any right-hand side.

3. Precedence relations

Between terminals a and b:

• $a \lessdot b$ — a has lower precedence than b (→ shift b)
• $a \doteq b$ — equal precedence (→ shift)
• $a \gtrdot b$ — a has higher precedence than b (→ reduce)

Computed from the grammar using the FIRST/LAST terminal sets:

• if $\alpha\, a\, B\, \beta$ and $b\in \mathrm{FIRST}(B)$ then $a \lessdot b$;
• if $A\to \alpha\, a b\, \beta$ then $a \doteq b$;
• if $A\to \alpha\, B\, b\,\beta$ and $a\in \mathrm{LAST}(B)$ then $a \gtrdot b$.

This yields the operator-precedence matrix $M[t_1][t_2]$ for all terminal pairs.

4. Algorithm (stack with $` at bottom; input ends with `$):

1. Compare precedence of the input symbol with the relevant top-of-stack terminal.
2. If top $\lessdot$ next, or top $\doteq$ next → shift the next token.
3. If top $\gtrdot$ next → a handle boundary has been found: scan back until the first preceding $\lessdot$ relation; the substring between them is the handle → reduce it to its nonterminal. No state/lookahead table needed.
4. Accept when the stack holds exactly the start symbol with no input left.

5. Example — id + id * id with precedence * > +

stack: $ id + id * id
shift id, shift +, shift id
when `*` (input) and top `id` reduce id→E... 
then top `*` vs input `+`: since `*` ⋗ `+`, reduce E*E before E+ 
→ matches the expected "multiply before add" behaviour.

6. Advantages & disadvantages

Advantages:

• very fast (simple matrix lookup), small table,
• easy to implement (no GOTO states).

Disadvantages:

• works only for operator grammars (no adjacent nonterminals, no $\epsilon$),
• handle detection is purely local — it ignores surrounding context, so many real languages need LR/LALR instead,
• usually used in small/expression-oriented compilers or inside calculator-style evaluators.

Example precedence table (* binds tighter than +):

op	+	*
+	$\doteq, \gtrdot$	$\lessdot$
*	$\gtrdot$	$\gtrdot$

Rule: shift on $\lessdot$ / $\doteq$, reduce on $\gtrdot$ — which reproduces standard arithmetic precedence.