Yasir Explains/Compiler Design/Parsing/Operator Precedence Parsing
Parsing

Operator Precedence Parsing

On this page

What is Operator Precedence Parsing?The Three Precedence RelationsThe Operator-Precedence Parsing AlgorithmComputing Precedence Relations — LEADING and TRAILINGAdvantages and Limitations
Parsing

Operator Precedence Parsing

Master a simple but powerful bottom-up technique used to parse expressions — built around precedence and associativity relations between operators (<·, =·, ·>).

What is Operator Precedence Parsing?

Operator-precedence parsing is a simple bottom-up technique that works on expression grammars. It does not need a full parsing table — only a table of relationships between pairs of terminals.

It is the technique most often used in handwritten calculator parsers and in pocket-calculator firmware.

What is an Operator Grammar?

A grammar is an operator grammar if it satisfies two rules:

  1. No production has ε on the right-hand side.
  2. No production has two adjacent non-terminals on the right-hand side.

For example, this is an operator grammar:

Example
E → E + E | E * E | ( E ) | id

Every production has non-terminals separated by a terminal (+, *, (, )). Note: the grammar is ambiguous — but operator-precedence parsing doesn't care about ambiguity because it disambiguates using a precedence table.

This is not an operator grammar:

Example
S → A B
A → a
B → b

The production S → A B has two non-terminals next to each other — not allowed.

Why "Operator Precedence"?

Because the parser uses a table of precedence relations between operators (terminals) to decide whether to shift the next token or reduce the handle on the stack.

Example
For two terminals a and b:
a <· b means "a has lower precedence than b" — shift b
a =· b means "a and b are at the same level" — shift (e.g. ( and ))
a ·> b means "a has higher precedence than b" — reduce

These three relations — <·, =·, ·> — are the entire decision-making mechanism.

The Three Precedence Relations

Let's break down the meaning of each precedence relation in detail.

a <· b — "a yields precedence to b"

When the parser has just seen a and the next token is b, and a <· b, the parser will shift b onto the stack and process b first.

Example
Example: + <· *
In a + b * c:
After seeing 'a + b', the parser sees '*' next.
Since + <· *, multiplication binds tighter, so we shift '*'
and reduce b*c first.

a =· b — "a and b are at the same level"

These two terminals appear together in some production (typically matching delimiters like ( and )).

Example
Example: ( =· )
In ( E ) :
'(' and ')' match each other — they are at the same precedence level.

a ·> b — "a takes precedence over b"

The parser must reduce before processing b.

Example
Example: * ·> +
In a * b + c:
After seeing 'a * b', the parser sees '+'.
Since * ·> +, multiplication finishes first.
Reduce 'a * b', then shift '+'.

Important — These are NOT symmetric

Don't confuse these relations with mathematical <, =, >:

Example
a <· b does NOT imply b ·> a

Each relation between any pair of terminals is independent. Some pairs may have no relation at all (error entries).

Example Precedence Table

For the grammar E → E + E | E * E | ( E ) | id:

Example
+ * ( ) id $
─────────────────────────────────────
+ ·> <· <· ·> <· ·>
* ·> ·> <· ·> <· ·>
( <· <· <· =· <· —
) ·> ·> — ·> — ·>
id ·> ·> — ·> — ·>
$ <· <· <· — <· acc

Reading the table: pick the row for the topmost terminal on the stack, the column for the next input token. The cell is the relation.

The blank cells (—) are errors — those pairs cannot legally appear next to each other.

The Operator-Precedence Parsing Algorithm

Once we have the precedence table, parsing is straightforward.

The Algorithm

Example
push $ onto the stack
read first input token
repeat:
a = topmost terminal on the stack
b = current input token
if a == $ and b == $:
accept ✓
if a <· b or a =· b:
push b onto the stack ← SHIFT
advance input
if a ·> b:
repeat:
pop the topmost terminal as 'top'
until the terminal now on the stack <· top
// (everything popped forms the handle; reduce it)
replace the popped run with the appropriate non-terminal ← REDUCE
if no relation exists:
error

The parser does not need to know which production to apply — the operators between the popped tokens uniquely identify the handle.

Step-by-Step Trace — id + id * id

Grammar: E → E + E | E * E | ( E ) | id

(Using the table above. The topmost terminal on the stack is what we compare; non-terminals are invisible to the comparison.)

Example
Step Stack Input Relation Action
──────────────────────────────────────────────────────────────────
1 $ id+id*id$ $ <· id shift id
2 $ id +id*id$ id ·> + reduce id → E
3 $ E +id*id$ $ <· + shift +
4 $ E + id*id$ + <· id shift id
5 $ E + id *id$ id ·> * reduce id → E
6 $ E + E *id$ + <· * shift *
7 $ E + E * id$ * <· id shift id
8 $ E + E * id $ id ·> $ reduce id → E
9 $ E + E * E $ * ·> $ reduce E*E → E
10 $ E + E $ + ·> $ reduce E+E → E
11 $ E $ accept ✓

Notice how the parser automatically:

  • Reduces id to E whenever the lookahead has higher precedence.
  • Defers reducing E + E until after E * E finishes — that's how precedence is enforced.

Computing Precedence Relations — LEADING and TRAILING

So far we have used a hand-written precedence table. For a general grammar, we compute the relations using two auxiliary sets, LEADING and TRAILING, for each non-terminal.

LEADING(A)

The set of terminals that can appear as the first terminal in some string derived from A.

Example
For each production A → α:
if α = a β → add a to LEADING(A)
if α = B β → add LEADING(B) to LEADING(A)
if α = B a β → add LEADING(B) ∪ {a} to LEADING(A)

TRAILING(A)

The set of terminals that can appear as the last terminal in some string derived from A. (Mirror of LEADING — scanned right to left.)

Computing the Three Relations

Once LEADING and TRAILING are known, the relations are derived directly from the productions:

Example
Rule 1 — same-level pairs:
For any production A → α a B β:
a =· LEADING(B)[0] is NOT what we want;
a =· b whenever a and b appear adjacent in some RHS.
Rule 2 — yields:
For any production A → α a B β:
a <· every terminal in LEADING(B)
Rule 3 — takes:
For any production A → α B a β:
every terminal in TRAILING(B) ·> a

Plus, for the start symbol:

  • $ <· every terminal in LEADING(start)
  • every terminal in TRAILING(start) ·> $

Worked Example

Grammar: E → E + T | T, T → T * F | F, F → ( E ) | id

Step 1 — LEADING and TRAILING.

Example
LEADING(E) = { +, *, (, id }
LEADING(T) = { *, (, id }
LEADING(F) = { (, id }
TRAILING(E) = { +, *, ), id }
TRAILING(T) = { *, ), id }
TRAILING(F) = { ), id }

Step 2 — Apply the rules.

From E → E + T:

  • + <· LEADING(T) → + <· *, + <· (, + <· id
  • TRAILING(E) ·> + → + ·> +, * ·> +, ) ·> +, id ·> +

From T → T * F:

  • * <· LEADING(F) → * <· (, * <· id
  • TRAILING(T) ·> * → * ·> *, ) ·> *, id ·> *

From F → ( E ):

  • ( <· LEADING(E) → ( <· +, ( <· *, ( <· (, ( <· id
  • TRAILING(E) ·> ) → + ·> ), * ·> ), ) ·> ), id ·> )
  • ( =· )

After collecting all of these, we get exactly the precedence table shown in the previous section.

Advantages and Limitations

Operator-precedence parsing is one of the simplest parsing techniques in any compiler course — but it is also one of the most limited.

Advantages

AdvantageDetail
Simple to implementJust a precedence table and a stack — fits on one page
FastEach token is shifted and reduced O(1) times — O(n) overall
Small tablesOnly
No grammar transformationThe grammar can be left-recursive or ambiguous — table sidesteps this
Natural for calculatorsPocket calculators and small expression interpreters use this directly

Limitations

LimitationDetail
Only works on operator grammarsNo ε productions, no adjacent non-terminals
Reductions don't say WHICH productionCannot easily build an AST that distinguishes + and - nodes if both reduce to E (workaround: peek at popped operator)
Cannot detect every errorA blank cell catches some errors, but ambiguous grammars may accept wrong inputs
Not used in real compilersLR/LALR replaced it for serious work — but it lives on in hand-written expression parsers

When to Use

  • Building a calculator or expression interpreter by hand — operator precedence is the easiest and most practical choice.
  • Teaching parsing — its mechanics make the concepts of shift, reduce, and precedence concrete.
  • A small DSL with only expressions — quick to implement, easy to extend.

Modern Variants

The same idea lives on under different names:

  • Pratt parsing (top-down operator precedence) — a top-down variant invented by Vaughan Pratt. Used in TypeScript's parser, ESLint, and many modern hand-written compilers.
  • Shunting-yard algorithm (Dijkstra) — Dijkstra's classic algorithm that converts infix expressions into Reverse Polish Notation using exactly these precedence relations.

If you have ever written a Pratt parser, you have written an operator-precedence parser — just dressed up as recursive descent.