Operator precedence parsing refers to a family of parsing techniques used to handle expressions containing operators with different precedence and associativity. Notable algorithms in this family include:

These algorithms share similarities and can be considered variations of the same fundamental approach with different formulations and implementations. 1 2

Motivation

We can describe the structure of our language using context-free grammar (often using BNF notation) and parse it with recursive descent parsers. However, for infix operators, this approach can be really cumbersome. Consider the following grammar:

Expr ::=
    Expr '+' Expr
  | Expr '*' Expr
  | '(' Expr ')'
  | 'number'

This grammar is ambiguous to parse, as it doesn’t express the precedence and associativity of the operators. We can fix the grammar with the following change:

Expr ::=
    Factor
  | Expr '+' Factor
 
Factor ::=
    Atom
  | Factor '*' Atom
 
Atom ::=
    'number'
  | '(' Expr ')'

This can quickly become unwieldy with more operators and more complicated precedence rules. The above fix also haven’t address the issue that some of the non-terminal in the grammar is left recursive, which can cause trouble for pure recursive-descent parsing 3.

Footnotes

  1. From Pratt to Dijkstra

  2. Pratt Parsing and Precedence Climbing Are the Same Algorithm

  3. Simple but Powerful Pratt Parsing