What operator precedence parsing is
Operator precedence parsing is the simplest bottom-up parsing method taught in compiler design courses. It works only for operator grammars: grammars with no ε-productions in which no right-hand side has two non-terminals next to each other. Arithmetic expression grammars are the typical case. Instead of building item sets like an LR parser, it decides everything from three relations between pairs of terminals: a ⋖ b (b has higher precedence, so shift it), a ⋗ b (a has higher precedence, so reduce) and a ≐ b (both belong to the same handle, like the two parentheses). This tool computes every step of the method for any operator grammar you type and runs the parser on a string.
Step 1: LEADING and TRAILING
LEADING(A) is the set of terminals that can be the first terminal in a string derived from A, where at most one non-terminal may come before it. TRAILING(A) is the same from the right. The rules are short. If A → a γ or A → B a γ, then a is in LEADING(A). If A → B γ, everything in LEADING(B) is in LEADING(A). TRAILING mirrors this from the right end of each rule. The tool repeats these rules until no set changes. For the expression grammar E → E + T | T, T → T * F | F, F → ( E ) | id it finds:
| Non-terminal | LEADING | TRAILING |
|---|---|---|
| E | + * ( id | + * ) id |
| T | * ( id | * ) id |
| F | ( id | ) id |
Step 2: the relation table
Each right-hand side is scanned for neighbouring symbols. Two terminals side by side, or separated by one non-terminal, are ≐, which gives ( ≐ ) from F → ( E ). A terminal followed by a non-terminal B is ⋖ every terminal in LEADING(B), so + ⋖ * because of E → E + T. A non-terminal B followed by a terminal b gives a ⋗ b for every a in TRAILING(B), so * ⋗ + and + ⋗ +. Finally the end marker is ⋖ everything in LEADING of the start symbol, and everything in TRAILING of the start symbol is ⋗ the end marker. Each cell of the tool's table shows the rule that produced it when you hover over it, so you can check your own table one cell at a time.
Step 3: precedence functions
A full table needs a cell for every pair of terminals. Textbooks therefore encode it as two functions f and g, with f(a) < g(b) when a ⋖ b, f(a) = g(b) when a ≐ b and f(a) > g(b) when a ⋗ b. The construction merges nodes that are ≐, draws an edge for every ⋖ and ⋗, and takes each value as the longest path in that graph. For the expression grammar the tool gives:
| + | * | ( | ) | id | end | |
|---|---|---|---|---|---|---|
| f | 2 | 4 | 0 | 4 | 4 | 0 |
| g | 1 | 3 | 5 | 0 | 5 | 0 |
These are the values in the Dragon Book. If the graph has a cycle, no functions exist, and the tool says so. Functions also lose the blank cells of the table, so a parser that uses them reports some errors later than the table would.
Step 4: the parse
The parser keeps a stack that starts with the end marker. At each step it compares the topmost terminal on the stack with the next input token. On ⋖ or ≐ it shifts. On ⋗ it pops symbols until the terminal below is ⋖ the last terminal popped, and reduces what it popped (the handle). It accepts when only the start symbol is left and the input is used up. For id + id * id the reductions are F → id three times, then T → T * F, then E → E + T, so the multiplication is reduced first. The tool names the rule whose right-hand side matches each handle. Unit rules such as E → T are never applied, and that is normal for operator precedence parsing.
Associativity comes from the grammar
Left-recursive rules such as E → E + T make + ⋗ +, so a + b + c groups to the left. Right recursion such as T → F ^ T makes ^ ⋖ ^, so powers group to the right. Load the power example to see id ^ id ^ id reduce from the right.
When the table has conflicts
The ambiguous grammar E → E + E | E * E | id gives both ⋖ and ⋗ for + followed by +, because nothing in it says which operator binds tighter or how equal operators group. The tool highlights such cells and does not run the parser. The fix is the textbook one: one non-terminal per precedence level.
Common mistakes
- Forgetting the one-non-terminal rule in LEADING. In A → B a, a belongs to LEADING(A) even though B comes first.
- Writing ⋗ the wrong way round. For B followed by b, it is TRAILING(B) ⋗ b, not b ⋗ TRAILING(B).
- Missing the ≐ across a non-terminal. ( E ) gives ( ≐ ) even though E sits between them.
- Using a non-operator grammar. A rule like E → E A E with A → + has two non-terminals side by side; substitute the operators in first.
Related tools
For other bottom-up parsers see the LR parser, which builds LR(0), SLR(1), LALR(1) and canonical LR(1) tables. Top-down parsing is in the LL(1) parser and the FIRST and FOLLOW calculator. To prepare a grammar for those, use the left recursion and left factoring calculator.