Pratt parsing

Pratt parsing, also called top-down operator precedence parsing, is a method for parsing expressions with operators of different precedence and associativity^[1]. Each operator is given a binding power on each side, a number that says how tightly it holds the operand next to it. A single recursive function, given a minimum binding power, parses an operand and then keeps absorbing operators, parsing each operator's right operand by a recursive call with that operator's right binding power, until it meets an operator that binds less tightly than the minimum. Associativity comes from making the two powers of an operator unequal. The behaviour of a token is split into its null denotation, what it means when it begins an expression, like a prefix minus or an opening parenthesis, and its left denotation, what it means after an expression, like an infix or postfix operator. Vaughan Pratt described the method in 1973^[1]. Douglas Crockford's account in Beautiful Code revived it in 2007^[2], and it is now common in hand-written parsers, where it replaces the chain of one procedure per precedence level that plain recursive descent requires.

§ 01

Binding powers

Consider an operand between two operators, $x op_{1} y op_{2} z$ . The operand $y$ must belong either to $op_{1}$ or to $op_{2}$ . Give each infix operator a left power $ℓ$ and a right power $r$ ; $y$ goes to the operator that pulls harder on it, and $x op_{1} y op_{2} z$ parses as

{(x op_{1} y) op_{2} z x op_{1} (y op_{2} z) if r_{1} > ℓ_{2} if ℓ_{2} > r_{1}

Precedence levels are spaced apart, so an operator of higher precedence has both powers above those of an operator of lower precedence. Between two occurrences of the same operator, the comparison is between its own $r$ and $ℓ$ : with $ℓ < r$ the operand goes left and the operator is left-associative, with $ℓ > r$ it is right-associative. The binding powers $(5, 6)$ for + and -, $(7, 8)$ for * and $(12, 11)$ for exponentiation express the usual conventions^[7].

In 1 + 2 * 3, the operand 2 lies between the right power of + (6) and the left power of * (7). The larger wins, so 2 belongs to the multiplication, which then becomes the right operand of the addition.

§ 02

The algorithm

The parsing function expr(min) reads an operand, then loops: it looks at the next operator, and if its left power is below min it stops and returns what it has; otherwise it consumes the operator, calls expr(r) with the operator's right power to parse the right operand, and combines the two into the new left operand. The top-level call is expr(0)^[1]^[7].

The core loop for binary operators, printing each decision. Lexer.tokenize splits a string into tokens.

(* The core of the algorithm: operands and left-associative binary
   operators, printing each decision. *)
let bp = function "+" | "-" -> (5, 6) | "*" | "/" -> (7, 8) | _ -> failwith "operator"
 
let parse tokens =
  let toks = ref tokens in
  let rec expr depth min_bp =
    let pad = String.make (2 * depth) ' ' in
    let lhs = ref (List.hd !toks) in
    toks := List.tl !toks;
    Printf.printf "%sexpr %d: operand %s\n" pad min_bp !lhs;
    let continue = ref true in
    while !continue do
      match !toks with
      | op :: rest ->
        let l, r = bp op in
        if l < min_bp then begin
          Printf.printf "%s  %s binds with %d < %d: return %s\n" pad op l min_bp !lhs;
          continue := false
        end else begin
          toks := rest;
          let rhs = expr (depth + 1) r in
          lhs := "(" ^ op ^ " " ^ !lhs ^ " " ^ rhs ^ ")";
          Printf.printf "%s  %s: %s\n" pad op !lhs
        end
      | [] -> continue := false
    done;
    !lhs
  in
  expr 0 0

Parsing 1 + 2 * 3 - 4.

expr 0: operand 1
  expr 6: operand 2
    expr 8: operand 3
      - binds with 5 < 8: return 3
    *: (* 2 3)
    - binds with 5 < 6: return (* 2 3)
  +: (+ 1 (* 2 3))
  expr 6: operand 4
  -: (- (+ 1 (* 2 3)) 4)

The call parsing the right operand of + runs with minimum 6. It absorbs * 3, since 7 ≥ 6, and then returns at -, whose left power 5 is below 6, so the subtraction is applied to the whole sum. Every token is consumed exactly once and the work per token is constant, so the parser runs in linear time; the depth of recursion is at most the number of operators.

§ 03

Null and left denotations

Pratt's formulation attaches the behaviour to tokens rather than to grammar rules. A token's null denotation (nud) parses what follows when the token begins an expression, and its left denotation (led) receives the expression parsed so far when the token follows one^[1]. A number's nud returns the number. A prefix minus's nud parses its operand with its own right power. An opening parenthesis's nud parses a whole expression with minimum 0 and expects the closing parenthesis. An infix operator's led parses the right operand, and a postfix operator's led, such as factorial, needs no right operand at all. The same token can have both, as - does, and ( which is grouping as a nud and a function call as a led, and [ which is an array literal or an index. Mixfix constructs are leds that parse several parts, such as the conditional a ? b : c.

A Pratt parser for prefix, infix, postfix and ternary operators, calls and indexing.

(* A Pratt parser producing S-expressions. Each operator has a binding
   power on each side; a higher power binds more tightly. An operator
   whose right power is higher than its left is left-associative. *)
let prefix_bp = function "-" | "+" -> Some 9 | _ -> None
let postfix_bp = function "!" | "[" | "(" -> Some 13 | _ -> None
let infix_bp = function
  | "=" -> Some (2, 1)                   (* right-associative *)
  | "?" -> Some (4, 3)                   (* the ternary a ? b : c *)
  | "+" | "-" -> Some (5, 6)
  | "*" | "/" -> Some (7, 8)
  | "^" -> Some (12, 11)                 (* right-associative, above prefix minus *)
  | _ -> None
 
let parse (tokens : string list) : string =
  let toks = ref tokens in
  let peek () = match !toks with t :: _ -> Some t | [] -> None in
  let next () = match !toks with t :: r -> toks := r; t | [] -> failwith "unexpected end" in
  let expect t = if next () <> t then failwith ("expected " ^ t) in
  let rec expr min_bp =
    (* The null denotation: what a token means at the start of an expression. *)
    let lhs = ref (match next () with
      | "(" -> let e = expr 0 in expect ")"; e
      | t -> (match prefix_bp t with
          | Some r -> "(" ^ t ^ " " ^ expr r ^ ")"
          | None -> t)) in
    (* The left denotation: what an operator means after an expression.
       Stop at any operator that binds less tightly than min_bp. *)
    let rec loop () =
      match peek () with
      | None -> ()
      | Some op ->
        match postfix_bp op, infix_bp op with
        | Some l, _ when l >= min_bp ->
          ignore (next ());
          lhs := (match op with
              | "[" -> let i = expr 0 in expect "]"; "([] " ^ !lhs ^ " " ^ i ^ ")"
              | "(" -> let args = arguments () in "(call " ^ String.concat " " (!lhs :: args) ^ ")"
              | _ -> "(" ^ op ^ " " ^ !lhs ^ ")");
          loop ()
        | None, Some (l, r) when l >= min_bp ->
          ignore (next ());
          lhs := (if op = "?" then
                    let mid = expr 0 in expect ":";
                    "(? " ^ !lhs ^ " " ^ mid ^ " " ^ expr r ^ ")"
                  else "(" ^ op ^ " " ^ !lhs ^ " " ^ expr r ^ ")");
          loop ()
        | _ -> ()
    and arguments () =
      if peek () = Some ")" then (ignore (next ()); [])
      else let a = expr 0 in
        if next () = "," then a :: arguments () else [a]
    in
    loop (); !lhs
  in
  let e = expr 0 in
  if !toks <> [] then failwith ("unexpected " ^ List.hd !toks); e

A range of expressions.

Running it.

1 + 2 * 3          (+ 1 (* 2 3))
1 - 2 - 3          (- (- 1 2) 3)
(1 + 2) * 3        (* (+ 1 2) 3)
a = b = c + 1      (= a (= b (+ c 1)))
2 ^ 3 ^ 2          (^ 2 (^ 3 2))
-2 ^ 2             (- (^ 2 2))
-a!                (- (! a))
f(x, y + 1)[i]     ([] (call f x (+ y 1)) i)
a ? b : c ? d : e  (? a b (? c d e))
x = a ? b : c      (= x (? a b c))

Assignment and the conditional are right-associative, as in C. Prefix minus has power 9, below the left power 12 of exponentiation, so -2 ^ 2 is $- (2^{2})$ as in mathematics, but above the powers of multiplication, so -a * b is $(- a) \cdot b$ . The postfix operators have the highest power, which makes f(x)[i] index the result of the call.

§ 04

Open-ended operator sets

Because the parser only asks for the binding powers of the operator in front of it, the set of operators need not be fixed in advance. Pratt emphasized this: a language can let programs declare new operators with chosen powers, and the parser consults a table that grows as they are declared^[1]. OCaml takes a related approach. Programs may define any operator made of symbol characters, and its precedence and associativity are determined by its first character: |> parses like | and is left-associative, and @@ parses like @ and is right-associative^[9].

Binding powers computed from the operator, following OCaml's rules for binary operators.

(* OCaml gives an operator its precedence and associativity according
   to its first character, so a table cannot list them all. A Pratt
   parser only needs a function from operator to binding powers. *)
let level op =
  let left k = Some (2 * k, 2 * k + 1) and right k = Some (2 * k + 1, 2 * k) in
  if String.length op >= 2 && String.sub op 0 2 = "**" then right 7
  else match op with
    | "||" | "or" -> right 1
    | "&" | "&&" -> right 2
    | "!=" -> left 3
    | _ -> match op.[0] with
      | '=' | '<' | '>' | '|' | '&' | '$' -> left 3
      | '@' | '^' -> right 4
      | '+' | '-' -> left 5
      | '*' | '/' | '%' -> left 6
      | _ -> None
 
let rec expr toks min_bp =
  match toks with
  | [] -> failwith "unexpected end"
  | x :: rest ->
    let rec loop lhs = function
      | op :: rest as toks ->
        (match level op with
         | Some (l, r) when l >= min_bp ->
           let rhs, rest = expr rest r in
           loop ("(" ^ op ^ " " ^ lhs ^ " " ^ rhs ^ ")") rest
         | _ -> (lhs, toks))
      | [] -> (lhs, [])
    in
    loop x rest
 
let parse s = fst (expr (Lexer.tokenize s) 0)

To check it, the program also evaluates each expression as OCaml code in which every operator has been redefined to build an S-expression, and compares the two results.

Running it.

a |> f |> g          (|> (|> a f) g)               same as OCaml
x + y |> f           (|> (+ x y) f)                same as OCaml
f @@ g @@ x          (@@ f (@@ g x))               same as OCaml
a >>= f >>= g        (>>= (>>= a f) g)             same as OCaml
a <*> b <*> c        (<*> (<*> a b) c)             same as OCaml
a + b * c ** d ** e  (+ a (* b (** c (** d e))))   same as OCaml
a - b - c            (- (- a b) c)                 same as OCaml
s ^ t ^ u = v        (= (^ s (^ t u)) v)           same as OCaml
p @ q +. r           (@ p (+. q r))                same as OCaml
a && b || c && d     (|| (&& a b) (&& c d))        same as OCaml
a <= b && b < c      (&& (<= a b) (< b c))         same as OCaml

§ 05

Related methods

Precedence climbing

Precedence climbing, described by Clarke in 1986 and popularized by Norvell, is recursive descent in which one function handles all binary operators, taking the current minimum precedence as a parameter^[5]^[4]. It is the same algorithm as Pratt parsing restricted to binary operators, with the associativity handled by adding one to the precedence when recursing on a left-associative operator instead of by a separate right power^[10]. Clang parses binary expressions this way.

Operator-precedence parsing

Floyd's operator-precedence grammars of 1963 define a precedence relation between pairs of terminals and parse bottom-up with a stack^[6]. Dijkstra's shunting-yard algorithm of 1961, which converts infix expressions to postfix with an operator stack, and the earlier stack-based translation of Bauer and Samelson are the iterative counterparts of the same idea^[3]^[11]. Pratt parsing does the same work top-down, with the call stack in place of the operator stack.

Recursive descent

A recursive-descent parser written from a grammar needs one procedure per precedence level, each calling the next, so an expression grammar with fifteen levels parses a single number through fifteen nested calls. Pratt parsing replaces the chain with a table and one procedure, and it fits into a recursive-descent parser as the procedure for expressions, with statements and declarations parsed in the ordinary way^[8]. Parser combinator libraries usually provide the same functionality as a combinator that builds an expression parser from a table of operators.

§ 06

History

Vaughan Pratt presented “Top down operator precedence” at the first Symposium on Principles of Programming Languages in 1973^[1]. He had developed the technique for CGOL, an alternative syntax for MACLISP, and argued for it as simpler and more flexible than parsing from a grammar. The method received little attention for decades; Crockford's chapter in Beautiful Code, which used it to parse JavaScript in JSLint, brought it back in 2007^[2]. Later expositions by Nystrom, whose book uses it for the expression compiler of its bytecode interpreter, and by Kladov, whose version gives every operator an explicit pair of left and right binding powers, made it a standard technique for hand-written parsers^[8]^[7].