Skip to content
Tutorials Center
My learning

Topics

Lesson 23 of 61 ยท Parsing

Operator-Precedence Parsing

Learn grammar-based operator-precedence parsing: operator grammars, the three precedence relations, shift and reduce decisions, precedence functions and a runnable parser.

The bottom-up parsers you have seen so far build huge item-set tables. For one very common family of languages, arithmetic expressions, there is a much smaller idea. Operator-precedence parsing is a bottom-up method that ignores the structure of the grammar and looks only at the terminals next to each other: the operators and the operands. A small table says, for every pair of terminals, "which one binds tighter?". That is enough to decide when to shift and when to reduce.

It is the oldest practical bottom-up technique (it was used in early compilers), and the idea is still alive: Pratt parsing is its top-down cousin, and Bison and Yacc let you attach precedence to tokens to resolve conflicts, which uses the same intuition. In this lesson you will build the relation table, run the algorithm, and learn where it stops working.

Operator grammars

The method only works on operator grammars, which have two restrictions on the right-hand sides of the productions:

  1. No right-hand side is empty (no ฮต-productions).
  2. No right-hand side has two nonterminals next to each other.

The grammar for expressions fits:

TEXT
E -> E + E | E - E | E * E | E / E | E ^ E | ( E ) | id

Between any two nonterminals there is always a terminal, an operator or a parenthesis. That is what lets the parser decide using only terminals: the handle will always be bordered by relations between terminals. The grammar is ambiguous, but the parser does not need to rewrite it. The precedence table settles the ambiguity.

The three relations

For two terminals a (the topmost terminal on the stack) and b (the next input token), exactly one of these relations holds, or none (an error):

Relation Name Meaning Parser action
a <. b a yields precedence to b b starts a new handle on top of a shift
a =. b same precedence a and b belong to the same handle, as in ( and ) shift
a .> b a takes precedence over b the handle that ends with a is complete reduce

Think of the dots as the angle brackets of the handle: <. opens the handle, =. is inside it, and .> closes it. Between a <. and the next .> lies exactly the handle.

For expressions, the relations come straight from the precedence and the associativity of the operators:

  • If operator a has higher precedence than b, then a .> b. If lower, a <. b.
  • If they have equal precedence, associativity decides: left-associative gives a .> b (finish the left one first), right-associative gives a <. b (postpone it).
  • Every operator is <. an id or ( that follows it, and .> a ) or $ that follows it.
  • id and ) are .> to every operator and to ) and $.
  • ( is <. to everything, except it is =. to the matching ).
  • $, the end marker, is <. to everything that can start an expression, and $ $ means accept.

An empty cell, such as id followed by id, is a syntax error: two operands cannot be adjacent. In that cell no relation holds.

The algorithm

The parser keeps a stack of symbols with $ at the bottom and a pointer into the input. It repeats:

  1. Let a be the topmost terminal on the stack and b the current token. If both are $, accept.
  2. If a <. b or a =. b, shift b.
  3. If a .> b, reduce: pop symbols until the terminal you just popped has <. to the topmost terminal still on the stack. The popped symbols (plus a nonterminal that sits directly below them) form the handle. Replace it with a nonterminal.
  4. If there is no relation, report a syntax error.
flowchart TD
    S["a = topmost terminal on the stack, b = next token"] --> E{"a = $ and b = $?"}
    E -- "yes" --> ACC["Accept"]
    E -- "no" --> R{"Relation between a and b"}
    R -- "a <. b or a =. b" --> SH["Shift b"]
    R -- "a .> b" --> RE["Pop the handle and reduce it"]
    R -- "none" --> ERR["Syntax error"]
    SH --> S
    RE --> S

The decision depends only on two terminals, never on the nonterminals.

Because the nonterminals are invisible to the decision, the parser can even skip some bookkeeping: it does not need to remember which rule each reduction used, only the shape of the handle. The program below builds an AST while it reduces.

A runnable parser

The code builds the relation table from precedence and associativity, prints it, parses expressions with a trace, and rejects a few broken inputs.

Python An operator-precedence parser

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the output with these checks:

  • In the table, the row for + shows > under + and - (left associative) and < under *, / and ^, because higher precedence binds first. The ^ row has < under ^ itself, which makes it right associative.
  • The trace of x + y * z shifts + and then *, because + <. *, and reduces y * z before x + ..., giving ('+', 'x', ('*', 'y', 'z')).
  • a - b - c is grouped to the left and a ^ b ^ c to the right, only because of the associativity entries.
  • The bad inputs are caught by the empty cells, or because the handle has a shape that matches no rule.

Precedence functions

The full table has one cell per pair of terminals, so it grows with the square of the number of operators. A language with 40 operators needs 1,600 cells. Precedence functions compress it into two numbers per terminal: f(a) for when a is on the stack and g(b) for when b is the lookahead. The relations then become number comparisons: a <. b when f(a) < g(b), a =. b when they are equal, and a .> b when f(a) > g(b).

You find the numbers by building a graph with two nodes per terminal, f_a and g_a. For a .> b draw an edge from f_a to g_b. For a <. b draw an edge from g_b to f_a. For a =. b merge the two nodes into one, so that they get the same value. The value of a node is the length of the longest path leaving it. If the graph has a cycle, no precedence functions exist for that table.

Python Compressing the table into precedence functions

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last line is the price of the compression. The functions agree with every filled cell, but they cannot represent the empty cells, so id id now looks like a legal reduce. A parser that uses functions detects such errors later, or not until a reduction fails to match a handle. Compilers that need good error messages keep the full table.

Limits of the method

Operator-precedence parsing is small and fast, but it is weak:

  • Narrow class of grammars. Only operator grammars. Many real constructs have two adjacent nonterminals, such as if statements or declarations.
  • Unary minus. The same token - is binary in a - b and unary in - a. One table row cannot hold both relations, so you either use a separate token for the unary operator (and let the lexer decide from context) or fall back to another method.
  • Accepts wrong strings. Since nonterminals are ignored, the parser can accept some inputs that the grammar does not generate, and it only notices them when the handle does not match any rule.
  • Weak error messages. The error cells can only say "no relation between these two tokens".

For this reason it lives on in small expression sub-parsers inside larger compilers and in tools such as Yacc's %left, %right and %nonassoc. A full LR parser handles the general case, and a Pratt parser gives the same flexibility with little code.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which grammar property is required for operator-precedence parsing?

    An operator grammar has no ฮต-productions and no two adjacent nonterminals, so terminals separate everything and decisions can use only terminals. The grammar may even be ambiguous, because the table resolves it.
  2. 2. The stack's top terminal is '+' and the next token is '*'. With the usual precedences, what is the relation and the action?

    '' has higher precedence, so '+' yields to it: the parser shifts '' so that its operands are reduced first.
  3. 3. How is left associativity of '-' encoded in the table?

    With .> the parser reduces the earlier '-' before it shifts the next one, which groups a - b - c as (a - b) - c.
  4. 4. What information do precedence functions lose compared with the full table?

    Functions turn every pair into a numeric comparison, so there is always a result. The 'no relation' cells, and with them an early error report, disappear.

Summary

  • Operator-precedence parsing is bottom-up and decides by comparing the top terminal of the stack with the next token. It needs an operator grammar: no ฮต-rules and no two adjacent nonterminals.
  • The relations <., =. and .> mean shift, shift (inside a handle) and reduce. For expressions they come from operator precedence and associativity.
  • A reduce pops back to the previous <., plus a bordering nonterminal. Empty cells are syntax errors.
  • Precedence functions f and g compress the table to two numbers per terminal, computed as longest paths in a graph, at the cost of losing the error cells.
  • The method is tiny but narrow, with trouble from unary operators and poor error messages, which is why general languages use LR or Pratt parsing.

Next, move on to the general method in LR(0), SLR and LALR Parsers.