ToolSphere

Operator Precedence Parser

Computer science

Operator precedence parsing online: LEADING and TRAILING sets, the relation table, precedence functions f and g, and a stack trace of your string.

Type a grammar and a string to compute precedence relations and follow the parse.

Accepted: the input matches this operator-precedence grammar.

Grammar (one rule per line)

One rule per line, spaces between symbols: E -> E + T | T. Write ε (or eps) for an empty right side, one that matches nothing. The first rule is the start.

An operator grammar has no ε-productions and never two non-terminals side by side. ⋖ means the next terminal has higher precedence (shift), ⋗ means the top of the stack does (reduce), ≐ means both belong to the same handle.

1. LEADING and TRAILING

Non-terminalLEADINGTRAILING
E{ +, *, (, id }{ +, *, ), id }
T{ *, (, id }{ *, ), id }
F{ (, id }{ ), id }

2. Precedence relation table

Row: topmost terminal on the stack. Column: next input token. Hover a cell to see the rule that produced it.

top \ next+*()id$
+⋗⋖⋖⋗⋖⋗
*⋗⋗⋖⋗⋖⋗
(⋖⋖⋖≐⋖
)⋗⋗⋗⋗
id⋗⋗⋗⋗
$⋖⋖⋖⋖

3. Precedence functions

+*()id$
f240440
g135050

f(a) < g(b) when a ⋖ b, f(a) = g(b) when a ≐ b and f(a) > g(b) when a ⋗ b. Each value is the longest path from that node in the graph of the relations, so blank cells of the table are lost: a parser using f and g detects some errors later.

4. Parse of id + id * id

Compare the topmost terminal on the stack with the next token: shift on ⋖ or ≐; on ⋗ pop back to the last ⋖ and reduce that handle. Single-non-terminal rules such as E → T are never applied, as in every operator precedence parser.

Accepted in 11 steps

StepStackInputAction
1$id + id * id $$ ⋖ id: shift id
2$ id+ id * id $id ⋗ +: reduce by F → id
3$ F+ id * id $$ ⋖ +: shift +
4$ F +id * id $+ ⋖ id: shift id
5$ F + id* id $id ⋗ *: reduce by F → id
6$ F + F* id $+ ⋖ *: shift *
7$ F + F *id $* ⋖ id: shift id
8$ F + F * id$id ⋗ $: reduce by F → id
9$ F + F * F$* ⋗ $: reduce by T → T * F
10$ F + T$+ ⋗ $: reduce by E → E + T
11$ E$Accept

On this browser only

Give feedback

Did this tool help?

Tell us what worked, what didn’t, or what you’d like next.

Opens Google Forms in a new tab with this tool’s name filled in. No sign-in or email required. Feedback is optional.

How to use Operator Precedence Parser

  1. 1Type an operator grammar, one rule per line, or load the expression grammar, the list grammar or the right-associative power example.
  2. 2Read LEADING and TRAILING for every non-terminal.
  3. 3Read the relation table: row is the topmost terminal on the stack, column is the next token. Hover a cell to see which rule produced it.
  4. 4Check the precedence functions f and g, computed from the table.
  5. 5Type a string to see the shift-reduce trace with the relation used at every step.

About Operator Precedence Parser

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.

Guides and tutorials

Frequently asked questions

How do you construct an operator precedence table?

Compute LEADING and TRAILING for every non-terminal. Then scan each right-hand side: adjacent terminals, or terminals with one non-terminal between them, are ≐; a terminal before a non-terminal B is ⋖ everything in LEADING(B); everything in TRAILING(B) is ⋗ a terminal after B. Add the end-marker rows from LEADING and TRAILING of the start symbol.

What are LEADING and TRAILING in compiler design?

LEADING(A) is the set of terminals that can appear first in a string derived from A, allowing one non-terminal before it. TRAILING(A) is the set that can appear last, allowing one non-terminal after it. They play the role FIRST and FOLLOW play in LL(1) parsing.

What is an operator grammar?

A grammar with no ε-productions in which no right-hand side has two adjacent non-terminals. E -> E + T is fine; E -> E A E is not, because E and A sit side by side. The tool checks this first and names the offending rule.

How do you find precedence functions from the relation table?

Create nodes f(a) and g(a) for every terminal, merge f(a) with g(b) when a ≐ b, draw an edge from f(a) to g(b) when a ⋗ b and from g(b) to f(a) when a ⋖ b. Each function value is the length of the longest path from its node. A cycle means there are no precedence functions.

What do the symbols ⋖, ⋗ and ≐ mean?

a ⋖ b means b has higher precedence, so the parser shifts b. a ⋗ b means a has higher precedence, so the parser reduces the handle ending at a. a ≐ b means both are part of the same handle, such as the two parentheses of ( E ).

Why does the parser never use rules like E -> T?

An operator precedence parser only looks at terminals, so it cannot see the difference between E, T and F. Reductions by single-non-terminal rules change nothing it can observe. This is why the stack in the trace can show T + F; the shape of the parse is still correct.

Can operator precedence parsing handle ambiguous grammars?

Not directly from the grammar: E -> E + E | E * E | id produces cells with both ⋖ and ⋗, and the tool reports them. Practical parsers use a separate table of operator precedence and associativity instead, which is the idea yacc's %left and %right declarations use for LR parsers.

How is right associativity shown in the table?

Through right recursion. For T -> F ^ T the tool gives ^ ⋖ ^, so the parser shifts the second ^ before reducing the first and id ^ id ^ id groups from the right. Left recursion such as E -> E + T gives + ⋗ +, which groups to the left.

What are the disadvantages of operator precedence parsing?

It only works for operator grammars, cannot handle a symbol like unary minus that has two precedences without extra tricks, and recognises some strings that are not in the language because it ignores non-terminal names. Precedence functions also lose the blank error cells of the table.

How is operator precedence parsing different from LR parsing?

Both are shift-reduce parsers. Operator precedence decides from relations between terminals only, while an LR parser uses states built from items and works for a much larger class of grammars. The LR parser tool builds those states and tables.

Have a suggestion for Operator Precedence Parser?Share your feedback ↗