When you work out 2 + 3 * 4 in your head, you never write down a grammar. You just know that * "binds tighter" than +, so you do 3 * 4 first. Operator precedence parsing turns that intuition into a parsing method. It is a shift-reduce parser (see Bottom-Up Parsing & Shift-Reduce Parsing) that finds the handle using only precedence relations between pairs of terminals.
It is one of the oldest parsing techniques, it is easy to build by hand, and it is still the idea behind the expression part of many hand-written parsers. It is also a favourite for university exams: build the relation table, trace a string, compute precedence functions.
Operator precedence parsing is a shift-reduce parsing method for operator grammars. It uses three relations, ⋖ (yields precedence), ≐ (same precedence) and ⋗ (takes precedence), defined between pairs of terminals, to locate the left and right ends of each handle.
Operator Grammars
The method only works for a restricted kind of grammar.
An operator grammar is a context-free grammar in which no production has ε as its right side and no right side has two non-terminals next to each other.
Why these two restrictions? Between any two non-terminals in a sentential form there is then always at least one terminal, an "operator". The parser can therefore ignore non-terminals almost completely and make every decision by comparing neighbouring terminals.
Grammar | Operator grammar? | Reason |
|---|---|---|
E → E + E | E * E | ( E ) | id | Yes | No ε, no adjacent non-terminals |
E → E A E | id, A → + | * | No | E A E has E next to A |
S → a S b | ε | No | Has an ε-production |
E → E + T | T, T → T * F | F, F → ( E ) | id | Yes | Unit productions are allowed |
A grammar that is not an operator grammar can often be converted by substitution. E → E A E, A → + | * becomes E → E + E | E * E by replacing A with its alternatives.
The Three Precedence Relations
For terminals a and b:
Relation | Read as | Meaning for the handle |
|---|---|---|
a ⋖ b | a yields precedence to b | b starts a handle that a is not part of (a handle's left end) |
a ≐ b | a has the same precedence as b | a and b belong to the same handle, e.g. ( and ) |
a ⋗ b | a takes precedence over b | a ends a handle (a handle's right end) |
Many textbooks write these as <·, =· and ·>. Despite the look, they are not ordinary less-than, equal and greater-than. For example + ⋗ + holds (for a left-associative +), and a pair of terminals may have no relation at all, which signals a syntax error.
How the Relations Find the Handle
Write the relations between each pair of adjacent terminals of the input, ignoring non-terminals, with $ at both ends. For id + id * id:
$ ⋖ id ⋗ + ⋖ id ⋗ * ⋖ id ⋗ $
A handle is what lies between a ⋖ and the next ⋗ (with only ≐ in between). Here each id is enclosed by ⋖ … ⋗, so each id is reduced to E. Then, ignoring the E's, the string of terminals is:
$ ⋖ + ⋖ * ⋗ $ → the handle is E * E (the * with its operands)
$ ⋖ + ⋗ $ → then E + E
The * is reduced before the +, exactly as precedence demands.
Method 1: Relations from Precedence and Associativity
For a typical expression language, you can write the table directly from the operator rules. For operators θ1 and θ2:
If θ1 has higher precedence than θ2: θ1 ⋗ θ2 and θ2 ⋖ θ1.
If they have equal precedence and are left-associative: θ1 ⋗ θ2 and θ2 ⋗ θ1.
If they have equal precedence and are right-associative: θ1 ⋖ θ2 and θ2 ⋖ θ1.
For every operator θ: θ ⋖ id, id ⋗ θ, $ ⋖ θ, θ ⋗ $, θ ⋖ (, ( ⋖ θ, ) ⋗ θ, θ ⋗ ).
Also: $ ⋖ id, id ⋗ $, $ ⋖ (, ) ⋗ $, ( ⋖ (, ) ⋗ ), ( ⋖ id, id ⋗ ), and ( ≐ ).
The left-associative rule says "if the stack already has a +, finish it before starting the next +", so a + b + c groups as (a + b) + c. The right-associative rule says "keep shifting", so a ^ b ^ c groups as a ^ (b ^ c).
Example: + lowest, then *, then ^ highest; + and * left-associative, ^ right-associative. Row = terminal on top of the stack, column = next input terminal; blank = error:
id | + | * | ^ | $ | |
|---|---|---|---|---|---|
id | ⋗ | ⋗ | ⋗ | ⋗ | |
+ | ⋖ | ⋗ | ⋖ | ⋖ | ⋗ |
* | ⋖ | ⋗ | ⋗ | ⋖ | ⋗ |
^ | ⋖ | ⋗ | ⋗ | ⋖ | ⋗ |
$ | ⋖ | ⋖ | ⋖ | ⋖ |
Check a few cells against the rules: * ⋗ + (higher precedence), + ⋗ + (left-associative), ^ ⋖ ^ (right-associative), id ⋗ every operator. The entries id–id and $–$ are blank: two operands in a row is an error, and $ against $ means "accept" rather than a relation.
Method 2: Relations from the Grammar (LEADING and TRAILING)
When you have an operator grammar instead of a list of rules, compute the relations mechanically. First define two sets for every non-terminal A:
LEADING(A): terminals that can appear as the first terminal of a string derived from A. Formally, a ∈ LEADING(A) if A ⇒+ γaδ where γ is ε or a single non-terminal.
TRAILING(A): terminals that can appear as the last terminal of a string derived from A: a ∈ TRAILING(A) if A ⇒+ γaδ where δ is ε or a single non-terminal.
Rules for computing them:
If A → aα or A → Baα, then a ∈ LEADING(A). If A → Bα, then everything in LEADING(B) is in LEADING(A).
If A → αa or A → αaB, then a ∈ TRAILING(A). If A → αB, then everything in TRAILING(B) is in TRAILING(A).
Then, scanning every right side X1X2…Xn:
Pattern in a right side | Relation added |
|---|---|
a b (two adjacent terminals), or a B b | a ≐ b |
a B (terminal followed by non-terminal) | a ⋖ every terminal in LEADING(B) |
A b (non-terminal followed by terminal) | every terminal in TRAILING(A) ⋗ b |
Start symbol S | $ ⋖ LEADING(S) and TRAILING(S) ⋗ $ |
Worked Example
E → E + T | T
T → T * F | F
F → ( E ) | id
Step 1: LEADING and TRAILING. Start from the bottom. F → ( E ) and F → id give LEADING(F) = { (, id } and TRAILING(F) = { ), id }. T → T * F adds * to both sets of T, and T → F brings in F's sets. E → E + T adds +, and E → T brings in T's sets.
Non-terminal | LEADING | TRAILING |
|---|---|---|
E | { (, +, *, id } | { +, *, ), id } |
T | { (, *, id } | { *, ), id } |
F | { (, id } | { ), id } |
Step 2: Relations from each right side.
Right side | Pattern | Relations |
|---|---|---|
E + T | E + | TRAILING(E) ⋗ +, i.e. + ⋗ +, * ⋗ +, ) ⋗ +, id ⋗ + |
E + T | + T | + ⋖ LEADING(T), i.e. + ⋖ *, + ⋖ (, + ⋖ id |
T * F | T * | TRAILING(T) ⋗ *, i.e. * ⋗ *, ) ⋗ *, id ⋗ * |
T * F | * F | * ⋖ LEADING(F), i.e. * ⋖ (, * ⋖ id |
( E ) | ( E ) | ( ≐ ) |
( E ) | ( E | ( ⋖ LEADING(E), i.e. ( ⋖ (, ( ⋖ +, ( ⋖ *, ( ⋖ id |
( E ) | E ) | TRAILING(E) ⋗ ), i.e. + ⋗ ), * ⋗ ), ) ⋗ ), id ⋗ ) |
start E | $ … $ | $ ⋖ (, +, *, id and +, *, ), id ⋗ $ |
Step 3: The table.
+ | * | ( | ) | id | $ | |
|---|---|---|---|---|---|---|
+ | ⋗ | ⋖ | ⋖ | ⋗ | ⋖ | ⋗ |
* | ⋗ | ⋗ | ⋖ | ⋗ | ⋖ | ⋗ |
( | ⋖ | ⋖ | ⋖ | ≐ | ⋖ | |
) | ⋗ | ⋗ | ⋗ | ⋗ | ||
id | ⋗ | ⋗ | ⋗ | ⋗ | ||
$ | ⋖ | ⋖ | ⋖ | ⋖ |
Every cell has at most one relation, so this grammar is an operator precedence grammar. The rows for + and * agree with Method 1: + and * are left-associative, and * has higher precedence. The grammar encoded those rules through its layering of E, T and F.
The Parsing Algorithm
The stack holds $, terminals and non-terminals, but decisions look only at a = the topmost terminal on the stack and b = the current input token:
push $; append $ to the input
loop:
a = topmost terminal on the stack; b = current input token
if a = $ and b = $: accept
else if a ⋖ b or a ≐ b: shift b onto the stack; advance input
else if a ⋗ b: /* reduce */
repeat
pop the stack
until the topmost terminal now on the stack ⋖ the terminal most recently popped
(a non-terminal directly below that terminal is part of the handle and is popped too)
replace the popped handle by a non-terminal
else: error (no relation between a and b)
The parser does not care which non-terminal it produces. All non-terminals are treated alike (we write E for every one). Unit productions such as E → T and T → F never appear as reductions, since they have no operator to locate them. The parse is a skeleton of the full parse tree, and that is all a compiler needs to evaluate or translate an expression.
Trace: id + id * id
Step | Stack | Input | Relation | Action |
|---|---|---|---|---|
1 | $ | id + id * id $ | $ ⋖ id | shift id |
2 | $ id | + id * id $ | id ⋗ + | reduce id to E |
3 | $ E | + id * id $ | $ ⋖ + | shift + |
4 | $ E + | id * id $ | + ⋖ id | shift id |
5 | $ E + id | * id $ | id ⋗ * | reduce id to E |
6 | $ E + E | * id $ | + ⋖ * | shift * |
7 | $ E + E * | id $ | * ⋖ id | shift id |
8 | $ E + E * id | $ | id ⋗ $ | reduce id to E |
9 | $ E + E * E | $ | * ⋗ $ | reduce E * E to E |
10 | $ E + E | $ | + ⋗ $ | reduce E + E to E |
11 | $ E | $ | accept |
Step 6 is the decision that matters. The top terminal is + and the next token is *; since + ⋖ *, the parser shifts and handles the multiplication first. At step 9, * ⋗ $ pops E * E, and the terminal now on top, +, satisfies + ⋖ *, so the handle is exactly E * E.
Trace: Right Associativity with id ^ id ^ id
Using the Method 1 table:
Step | Stack | Input | Relation | Action |
|---|---|---|---|---|
1 | $ | id ^ id ^ id $ | $ ⋖ id | shift id |
2 | $ id | ^ id ^ id $ | id ⋗ ^ | reduce id to E |
3 | $ E | ^ id ^ id $ | $ ⋖ ^ | shift ^ |
4 | $ E ^ | id ^ id $ | ^ ⋖ id | shift id |
5 | $ E ^ id | ^ id $ | id ⋗ ^ | reduce id to E |
6 | $ E ^ E | ^ id $ | ^ ⋖ ^ | shift ^ |
7 | $ E ^ E ^ | id $ | ^ ⋖ id | shift id |
8 | $ E ^ E ^ id | $ | id ⋗ $ | reduce id to E |
9 | $ E ^ E ^ E | $ | ^ ⋗ $ | reduce E ^ E to E |
10 | $ E ^ E | $ | ^ ⋗ $ | reduce E ^ E to E |
11 | $ E | $ | accept |
At step 6, ^ ⋖ ^ makes the parser shift the second ^ instead of reducing. The rightmost E ^ E is reduced first (step 9), so the result is id ^ (id ^ id).
Trace: Parentheses with ( id + id ) * id
Step | Stack | Input | Relation | Action |
|---|---|---|---|---|
1 | $ | ( id + id ) * id $ | $ ⋖ ( | shift ( |
2 | $ ( | id + id ) * id $ | ( ⋖ id | shift id |
3 | $ ( id | + id ) * id $ | id ⋗ + | reduce id to E |
4 | $ ( E | + id ) * id $ | ( ⋖ + | shift + |
5 | $ ( E + | id ) * id $ | + ⋖ id | shift id |
6 | $ ( E + id | ) * id $ | id ⋗ ) | reduce id to E |
7 | $ ( E + E | ) * id $ | + ⋗ ) | reduce E + E to E |
8 | $ ( E | ) * id $ | ( ≐ ) | shift ) |
9 | $ ( E ) | * id $ | ) ⋗ * | reduce ( E ) to E |
10 | $ E | * id $ | $ ⋖ * | shift * |
11 | $ E * | id $ | * ⋖ id | shift id |
12 | $ E * id | $ | id ⋗ $ | reduce id to E |
13 | $ E * E | $ | * ⋗ $ | reduce E * E to E |
14 | $ E | $ | accept |
The relation ( ≐ ) lets the parser shift the closing parenthesis onto the stack, and at step 9 the reduction pops ), E and ( together: after ) is popped, the terminal below it is (, and since ( ≐ ) rather than ⋖, popping continues until the top terminal is $ and $ ⋖ ( holds.
Error Detection
An operator precedence parser detects errors in two places:
No relation between the top terminal and the input token. Example:
id id: after shifting the first id, the pair (id, id) is blank, so the parser reports "missing operator".Reduction failure: the popped handle matches no right side. Example:
id + * id:
Step | Stack | Input | Relation | Action |
|---|---|---|---|---|
1 | $ | id + * id $ | $ ⋖ id | shift id |
2 | $ id | + * id $ | id ⋗ + | reduce id to E |
3 | $ E | + * id $ | $ ⋖ + | shift + |
4 | $ E + | * id $ | + ⋖ * | shift * |
5 | $ E + * | id $ | * ⋖ id | shift id |
6 | $ E + * id | $ | id ⋗ $ | reduce id to E |
7 | $ E + * E | $ | * ⋗ $ | error: no production matches * E |
Every individual step was legal, but the final handle * E is not the right side of any production (an operand is missing). Real implementations attach a specific error message to each blank cell and each kind of bad handle.
Precedence Functions
A relation table for n terminals has n2 cells. Compilers often compress it into two functions f and g that map terminals to integers, so that:
f(a) < g(b) whenever a ⋖ b,
f(a) = g(b) whenever a ≐ b,
f(a) > g(b) whenever a ⋗ b.
f is used for the terminal on the stack, g for the input token. Storage drops from n2 to 2n entries.
Constructing f and g
Create nodes fa and ga for every terminal a (including $).
If a ≐ b, merge fa and gb into one node.
If a ⋗ b, draw an edge fa → gb. If a ⋖ b, draw an edge gb → fa. (The edge always goes from the "bigger" side to the "smaller" side.)
If the graph has a cycle, precedence functions do not exist. Otherwise, f(a) is the length of the longest path starting at fa, and g(b) is the length of the longest path starting at gb.
Worked Example
Take the relations among id, +, * and $ from our table:
id | + | * | $ | |
|---|---|---|---|---|
id | ⋗ | ⋗ | ⋗ | |
+ | ⋖ | ⋗ | ⋖ | ⋗ |
* | ⋖ | ⋗ | ⋗ | ⋗ |
$ | ⋖ | ⋖ | ⋖ |
Edges (no ≐ relations here, so nothing is merged):
from ⋗ : f_id → g_+, g_*, g_$ f_* → g_+, g_*, g_$ f_+ → g_+, g_$
from ⋖ : g_id → f_+, f_*, f_$ g_* → f_+, f_$ g_+ → f_$
Longest paths:
g_id → f_* → g_* → f_+ → g_+ → f_$ length 5 so g(id) = 5
f_id → g_* → f_+ → g_+ → f_$ length 4 so f(id) = 4
f_* → g_* → f_+ → g_+ → f_$ length 4 so f(*) = 4
g_* → f_+ → g_+ → f_$ length 3 so g(*) = 3
f_+ → g_+ → f_$ length 2 so f(+) = 2
g_+ → f_$ length 1 so g(+) = 1
f_$, g_$ have no outgoing edges length 0 so f($) = g($) = 0
id | + | * | $ | |
|---|---|---|---|---|
f | 4 | 2 | 4 | 0 |
g | 5 | 1 | 3 | 0 |
Check: + ⋖ * needs f(+) < g(*): 2 < 3, correct. * ⋗ + needs f(*) > g(+): 4 > 1, correct. + ⋗ + needs f(+) > g(+): 2 > 1, correct. All 14 non-blank relations among these four terminals are satisfied.
The Price: Lost Error Entries
A function always returns a number, so every pair of terminals now has some relation, including pairs that were blank (errors). For id id, f(id) = 4 < g(id) = 5 looks like id ⋖ id, so the parser happily shifts the second id. The error is only caught later, when it tries to reduce the handle id E and finds no matching production. Errors are still detected, just later and with less precise messages.
When Functions Do Not Exist
Suppose terminals a and b have the relations a ≐ b, a ⋗ a, b ⋗ b and b ⋖ a. Then f(a) = g(b), f(a) > g(a), f(b) > g(b) and f(b) < g(a). Chaining these gives f(b) > g(b) = f(a) > g(a) > f(b), a contradiction. In the graph this shows up as a cycle, and no precedence functions exist for that table.
Advantages and Limitations
Advantages | Limitations |
|---|---|
Very simple to implement, even by hand | Works only for operator grammars, a small class |
Tables can be written straight from precedence and associativity rules | A token with two meanings, such as unary and binary minus, needs special handling (usually the lexer gives them different tokens) |
Precedence functions give a very compact table | Hard to be sure the parser accepts exactly the language of the grammar |
Fast: decisions depend on one pair of terminals | Weaker error detection, especially with precedence functions |
In practice, operator precedence ideas live on in expression parsing inside hand-written recursive-descent parsers (the "precedence climbing" and Pratt techniques), while whole-language parsing uses the LR methods from the next chapters.
Common Mistakes
Treating ⋖, ≐, ⋗ like <, =, >. They are not symmetric or transitive in the usual way: + ⋗ + is fine, and many pairs have no relation.
Getting associativity backwards. Left-associative means θ ⋗ θ (reduce the one on the stack first); right-associative means θ ⋖ θ (shift).
Comparing with the top of the stack when it is a non-terminal. Always use the topmost terminal.
Mixing up the rows and columns. The row is the stack terminal (f), the column is the input token (g).
Drawing function-graph edges the wrong way. a ⋗ b gives fa → gb; a ⋖ b gives gb → fa.
Calling a grammar with ε-productions an operator grammar. Both conditions (no ε, no adjacent non-terminals) must hold.
GATE & Interview Questions
Q1. Is S → SAS | a, A → bSb | b an operator grammar? If not, convert it.
No, because SAS has S next to A. Substituting A's alternatives gives S → SbSbS | SbS | a, which has no ε and no adjacent non-terminals, so it is an operator grammar for the same language.
Q2. Precedence functions give f(+) = 2, g(+) = 1, f(*) = 4, g(*) = 3. What are the relations between + and *, and between * and *?
f(+) = 2 < g(*) = 3, so + ⋖ *. f(*) = 4 > g(+) = 1, so * ⋗ +. f(*) = 4 > g(*) = 3, so * ⋗ * (left-associative).
Q3. If ^ is right-associative, what is the relation between ^ on the stack and ^ in the input, and why?
^ ⋖ ^. The parser must shift the new ^ instead of reducing the old one, so the rightmost ^ is evaluated first: a ^ b ^ c = a ^ (b ^ c).
Q4. Suppose − has higher precedence than * and − is right-associative. What is the value of 6 − 3 − 1 * 2?
− binds tighter, and right associativity groups 3 − 1 first: (6 − (3 − 1)) * 2 = (6 − 2) * 2 = 8. With the usual rules the answer would be 6 − 3 − 2 = 1.
Q5. Why are ε-productions not allowed in an operator grammar?
The parser finds a handle between a ⋖ and a ⋗ relation on terminals. An ε right side has no terminals and no length, so it can never be located or reduced this way. It would also allow two non-terminals to become adjacent in a sentential form.
Q6. For n terminals, how much space does the relation table need compared with precedence functions? What is lost?
The table needs n2 entries; functions need 2n. The blank (error) entries are lost, so some errors are discovered later, at reduction time, instead of immediately.
Q7. In the table for E → E + T | T, T → T * F | F, F → (E) | id, what are the relations ( vs ), id vs id, and ) vs (?
( ≐ ) (they appear in the same right side with one non-terminal between them). id vs id and ) vs ( are blank: two operands or ")(" in a row are errors.
Summary
Operator precedence parsing is a shift-reduce method for operator grammars (no ε-productions, no adjacent non-terminals).
Relations ⋖, ≐, ⋗ between terminals mark the left end, interior and right end of handles. They can be written from precedence and associativity rules or computed from the grammar using LEADING and TRAILING sets.
Algorithm: compare the topmost stack terminal a with input b. Shift on ⋖ or ≐; on ⋗ pop until the top terminal ⋖ the last popped one, then reduce. Non-terminals are all treated alike.
Errors: no relation between a and b, or a handle that matches no production.
Precedence functions f and g compress the table to 2n numbers, computed as longest paths in a graph. They do not exist if the graph has a cycle, and they delay error detection.
The method is simple but limited. The next chapter, LR(0) Items & LR(0) Parsing, begins the far more general LR approach.