Parser combinator

A parser combinator is a higher-order function that builds a parser from smaller parsers: the sequence of two parsers, the choice between them, the repetition of one. The parsers themselves are ordinary values of the programming language, so a grammar is written as a program that is its own parser, with no separate parser generator, and can use the language's abstractions: functions, modules, types. Combinators produce recursive descent parsers, which do not accept left-recursive rules and, with unlimited backtracking, can take exponential time; memoizing them, as packrat parsing does, makes them linear^[7]. Parsers form a monad, and the most widely used libraries, such as Parsec for Haskell, are organized around that structure^[4]^[5].

§ 01

Overview

A parser is a function from input to a result. The simplest useful type is a function from a string and a position to either failure or a parsed value together with the position where parsing stopped:

Parser a = string \times int \to (a \times int) option

Primitive parsers recognize one character satisfying a predicate, or the empty string. Combinators build larger parsers: $p < ∣ > q$ tries $p$ and, if it fails, $q$ ; $p > > = f$ runs $p$ and then the parser $f x$ chosen by its result $x$ ; $many p$ runs $p$ as often as it succeeds. A grammar rule becomes a definition, and mutually recursive rules become mutually recursive functions, so a combinator parser is a recursive descent parser written at a higher level.

§ 02

The list of successes

Wadler's formulation returns a list of results instead of an option, one for each way of parsing a prefix of the input^[2]:

Parser a = string \times int \to list (a \times int)

The empty list is failure, and choice is concatenation, so every alternative is explored and an ambiguous grammar yields every parse. Under lazy evaluation only as many results are computed as are used, and taking the first gives backtracking search.

A list-of-successes parser that splits a string into dictionary words in every possible way.

(* Wadler's list of successes: a parser returns every way of parsing a
   prefix of the input, each with the position after it. *)
type 'a parser = string -> int -> ('a * int) list
 
let return x : 'a parser = fun _ i -> [ (x, i) ]
let fail : 'a parser = fun _ _ -> []
let ( >>= ) (p : 'a parser) (f : 'a -> 'b parser) : 'b parser =
 fun s i -> List.concat_map (fun (x, j) -> f x s j) (p s i)
let ( let* ) = ( >>= )
let ( <|> ) (p : 'a parser) (q : 'a parser) : 'a parser = fun s i -> p s i @ q s i
 
let string w : string parser =
 fun s i ->
  let n = String.length w in
  if i + n <= String.length s && String.sub s i n = w then [ (w, i + n) ] else []
 
let rec many1 p = let* x = p in (let* xs = many1 p in return (x :: xs)) <|> return [ x ]
let eof : unit parser = fun s i -> if i = String.length s then [ ((), i) ] else []
 
(* Every way of splitting the input into words from a dictionary. *)
let words dict = let word = List.fold_left (fun acc w -> acc <|> string w) fail dict in
  let* ws = many1 word in let* () = eof in return ws

Running it.

4 parses of "abc":
  a + b + c
  a + bc
  ab + c
  abc
parses of "abd": 0

Sequencing, >>=, runs the second parser from every position where the first one stopped, which is List.concat_map. Wadler used the parser as an example of what he later identified as a monad^[11].

§ 03

Parsers as a monad

Return and bind satisfy the monad laws, with the parser type as the monad^[4]:

return x = λ (s, i) . [(x, i)] p > > = f = λ (s, i) . concat [f x (s, j) ∣ (x, j) \leftarrow p (s, i)]

Parsers are also a monad with zero and plus, the failing parser and choice, which gives many, optional parts and alternatives, as for any such monad. Every combinator in a library is written in terms of these few operations, and the monadic let* syntax makes a parser read like the grammar rule it implements.

A deterministic parser

Practical libraries return at most one result and report errors. Parsec introduced two refinements that make this efficient^[5]. An alternative is tried only if the first branch failed without consuming input, so the parser commits to a branch as soon as it has read a character of it, which is the behaviour of an LL(1) parser, and memory held for backtracking can be released. Explicit backtracking over a longer prefix is requested with a combinator called try or attempt. And every failure records what the parser expected at the position where it failed, so error messages can be assembled from the grammar itself:

An arithmetic expression parser with precedence, whitespace and error messages.

(* A deterministic parser in the style of Parsec. A parser either succeeds
   with a value and a new position, or fails at a position with a list of
   what it expected there. A failure after consuming input is final:
   alternatives are tried only if the first failed without consuming. *)
type 'a reply = Ok of 'a * int | Error of int * string list
type 'a parser = string -> int -> 'a reply
 
let return x : 'a parser = fun _ i -> Ok (x, i)
let ( >>= ) (p : 'a parser) (f : 'a -> 'b parser) : 'b parser =
 fun s i -> match p s i with Ok (x, j) -> f x s j | Error _ as e -> e
let ( let* ) = ( >>= )
let ( <$> ) f p = let* x = p in return (f x)
 
let ( <|> ) (p : 'a parser) (q : 'a parser) : 'a parser =
 fun s i ->
  match p s i with
  | Error (j, e1) when j = i -> (match q s i with Error (k, e2) when k = i -> Error (i, e1 @ e2) | r -> r)
  | r -> r
 
(* Name what a parser expects, for error messages. *)
let ( <?> ) (p : 'a parser) name : 'a parser =
 fun s i -> match p s i with Error (j, _) when j = i -> Error (i, [ name ]) | r -> r
 
let satisfy name pred : char parser =
 fun s i -> if i < String.length s && pred s.[i] then Ok (s.[i], i + 1) else Error (i, [ name ])
 
let rec many p = (let* x = p in let* xs = many p in return (x :: xs)) <|> return []
let spaces = many (satisfy "space" (( = ) ' '))
let lexeme p = let* x = p in let* _ = spaces in return x
let symbol c = lexeme (satisfy (Printf.sprintf "%C" c) (( = ) c))
let eof : unit parser = fun s i -> if i = String.length s then Ok ((), i) else Error (i, [ "end of input" ])
 
let number =
  lexeme
    (let* d = satisfy "digit" (fun c -> '0' <= c && c <= '9') in
     let* ds = many (satisfy "digit" (fun c -> '0' <= c && c <= '9')) in
     return (int_of_string (String.of_seq (List.to_seq (d :: ds)))))
  <?> "number"
 
(* A left-associative chain: an operand, then any number of operator and
   operand pairs, folded from the left. *)
let chainl1 p op =
  let rec rest acc = (let* f = op in let* y = p in rest (f acc y)) <|> return acc in
  let* x = p in
  rest x
 
let addop = (fun _ -> ( + )) <$> symbol '+' <|> ((fun _ -> ( - )) <$> symbol '-')
let mulop = (fun _ -> ( * )) <$> symbol '*' <|> ((fun _ -> ( / )) <$> symbol '/')
 
let rec expr s = chainl1 term addop s
and term s = chainl1 factor mulop s
and factor s = (number <|> (let* _ = symbol '(' in let* e = expr in let* _ = symbol ')' in return e)) s
 
let parse s =
  match (let* _ = spaces in let* e = expr in let* () = eof in return e) s 0 with
  | Ok (v, _) -> string_of_int v
  | Error (i, e) -> Printf.sprintf "error at column %d: expected %s" (i + 1) (String.concat " or " (List.sort_uniq compare e))

Running it.

1 + 2 * 3          ->  7
8 - 3 - 2          ->  3
(1 + 2) * 3        ->  9
2 * (3 + 4) - 1    ->  13
100 / 10 / 5       ->  2
1 + * 2            ->  error at column 5: expected '(' or number
(1 + 2             ->  error at column 7: expected ')'
12 34              ->  error at column 4: expected end of input

Precedence comes from the layering of the rules: expr is a chain of terms separated by additive operators, and term a chain of factors separated by multiplicative ones. <?> replaces the low-level expectations of a parser, such as "digit", by a name from the grammar, such as "number".

§ 04

Applicative parsers

Many parsers never use a parsed value to decide what to parse next: a sequence of fixed parsers combined by a function. These need only the operations of an applicative functor, $pure$ and $⊛$ ^[13]. The structure of such a parser is fixed before any input is read, so it can be analysed: Swierstra and Duponcheel computed the set of characters each alternative can start with, chose between alternatives without backtracking and repaired errors by inserting or deleting symbols^[6]. A monadic parser can depend on what it has read, which some formats require:

A netstring parser: the payload's length is read first and decides how much to take.

type 'a parser = string -> int -> ('a * int) option
 
let return x : 'a parser = fun _ i -> Some (x, i)
let ( >>= ) (p : 'a parser) (f : 'a -> 'b parser) : 'b parser =
 fun s i -> match p s i with Some (x, j) -> f x s j | None -> None
let ( let* ) = ( >>= )
let ( <|> ) (p : 'a parser) (q : 'a parser) : 'a parser =
 fun s i -> match p s i with Some _ as r -> r | None -> q s i
let char c : char parser = fun s i -> if i < String.length s && s.[i] = c then Some (c, i + 1) else None
let digit : char parser = fun s i -> if i < String.length s && '0' <= s.[i] && s.[i] <= '9' then Some (s.[i], i + 1) else None
let rec many p = (let* x = p in let* xs = many p in return (x :: xs)) <|> return []
let take n : string parser = fun s i -> if i + n <= String.length s then Some (String.sub s i n, i + n) else None
 
(* A netstring: a length, a colon, that many bytes, and a comma. The
   parser for the payload is chosen by the value of the length. *)
let netstring =
  let* d = digit in
  let* ds = many digit in
  let n = int_of_string (String.of_seq (List.to_seq (d :: ds))) in
  let* _ = char ':' in
  let* payload = take n in
  let* _ = char ',' in
  return payload
 
let netstrings = many netstring

Running it.

4 netstrings, 33 bytes consumed: "hello" | "" | "hello, world" | "a,b"

The payload of a netstring^[14] may contain any byte, including the comma that terminates it, and can only be delimited by the length that precedes it. That makes the language of netstrings context-sensitive, and the parser for it needs $> > =$ .

§ 05

Left recursion

A grammar rule is left-recursive if it can derive a string beginning with itself, like $expr \to expr - digit$ . A recursive descent parser for such a rule calls itself at the same position before consuming anything, and never terminates. The usual rewriting turns the left recursion into repetition^[12]:

A \to A α ∣ β ⟹ A \to β α^{*}

which in combinator form is chainl1, used above: parse one operand, then any number of operator-operand pairs, and fold them from the left. Rewriting the rule as right recursion instead also terminates, but groups the operations to the right:

The same subtraction grammar written left-recursively, right-recursively and as iteration.

type 'a parser = string -> int -> ('a * int) option
 
let return x : 'a parser = fun _ i -> Some (x, i)
let ( >>= ) (p : 'a parser) (f : 'a -> 'b parser) : 'b parser =
 fun s i -> match p s i with Some (x, j) -> f x s j | None -> None
let ( let* ) = ( >>= )
let ( <|> ) (p : 'a parser) (q : 'a parser) : 'a parser =
 fun s i -> match p s i with Some _ as r -> r | None -> q s i
let char c : char parser = fun s i -> if i < String.length s && s.[i] = c then Some (c, i + 1) else None
let digit : int parser = fun s i -> if i < String.length s && '0' <= s.[i] && s.[i] <= '9' then Some (Char.code s.[i] - 48, i + 1) else None
 
(* expr ::= expr '-' digit | digit      -- left recursive: loops *)
let rec left s = ((let* a = left in let* _ = char '-' in let* b = digit in return (a - b)) <|> digit) s
 
(* expr ::= digit '-' expr | digit      -- right recursive: wrong grouping *)
let rec right s = ((let* a = digit in let* _ = char '-' in let* b = right in return (a - b)) <|> digit) s
 
(* expr ::= digit ('-' digit)*          -- iteration, folded from the left *)
let iter s =
  let rec rest acc = (let* _ = char '-' in let* b = digit in rest (acc - b)) <|> return acc in
  (let* a = digit in rest a) s

Running it.

right "8-3-2"  ->  7     8 - (3 - 2)
iter  "8-3-2"  ->  3     (8 - 3) - 2
left  "8-3-2"  ->  Stack_overflow

Frost, Hafiz and Callaghan gave combinators that accept left-recursive and ambiguous grammars in polynomial time by limiting the depth of left-recursive calls and memoizing^[9], and Warth, Douglass and Millstein extended packrat parsing to support left recursion^[10].

§ 06

Backtracking and packrat parsing

A parser that backtracks without limit may parse the same part of the input many times. In the grammar

expr term factor \to term + expr ∣ term \to factor * term ∣ factor \to digit ∣ (expr)

the first alternative of $expr$ parses a term and then, finding no +, fails; the second alternative parses the same term again. Each rule tries its operand twice, and each level of parentheses multiplies the work by four. Ford's packrat parsing stores the result of each rule at each position, so it is computed at most once, and parsing takes linear time for any grammar of this kind^[7]:

Counting calls to factor, with plain backtracking and with memoization.

(* Unlimited backtracking can take exponential time. Grammar:
     expr   ::= term '+' expr | term
     term   ::= factor '*' term | factor
     factor ::= digit | '(' expr ')'
   The first alternative of expr parses a term and, finding no '+',
   discards it; the second parses the same term again. *)
type 'a parser = string -> int -> ('a * int) option
 
let calls = ref 0
let char c : unit parser = fun s i -> if i < String.length s && s.[i] = c then Some ((), i + 1) else None
let digit : int parser = fun s i -> if i < String.length s && '0' <= s.[i] && s.[i] <= '9' then Some (Char.code s.[i] - 48, i + 1) else None
let ( <|> ) p q s i = match p s i with Some _ as r -> r | None -> q s i
let ( let* ) p f s i = match p s i with Some (x, j) -> f x s j | None -> None
let return x _ i = Some (x, i)
 
(* The grammar, parameterized by how the three rules are called. *)
let grammar ~expr ~term ~factor =
  let expr' = (let* a = term in let* () = char '+' in let* b = expr in return (a + b)) <|> term in
  let term' = (let* a = factor in let* () = char '*' in let* b = term in return (a * b)) <|> factor in
  let factor' = digit <|> (let* () = char '(' in let* e = expr in let* () = char ')' in return e) in
  (expr', term', factor')
 
(* Plain recursive descent with backtracking. *)
let rec expr s i = let e, _, _ = grammar ~expr ~term ~factor in e s i
and term s i = let _, t, _ = grammar ~expr ~term ~factor in t s i
and factor s i = incr calls; let _, _, f = grammar ~expr ~term ~factor in f s i
 
(* Packrat: every rule remembers its result at every position. *)
let packrat s =
  let memo tbl p i = match Hashtbl.find_opt tbl i with Some r -> r | None -> let r = p i in Hashtbl.add tbl i r; r in
  let te = Hashtbl.create 16 and tt = Hashtbl.create 16 and tf = Hashtbl.create 16 in
  let rec expr s i = memo te (fun i -> let e, _, _ = grammar ~expr ~term ~factor in e s i) i
  and term s i = memo tt (fun i -> let _, t, _ = grammar ~expr ~term ~factor in t s i) i
  and factor s i = memo tf (fun i -> incr calls; let _, _, f = grammar ~expr ~term ~factor in f s i) i in
  expr s 0

Running it.

depth input                    backtracking    packrat
1     (1)                                20          2
2     ((1))                              84          3
4     ((((1))))                        1364          5
6     ((((((1))))))                   21844          7
8     ((((((((1))))))))              349524          9
10    ((((((((((1))))))))))         5592404         11
12    ...                          89478484         13

The backtracking parser makes $(4^{d + 2} - 4) /3$ calls at nesting depth $d$ , and the packrat parser $d + 1$ . The price is memory proportional to the input times the number of rules. Ford formalized the grammars that such parsers accept, with ordered choice and unlimited lookahead, as parsing expression grammars (PEGs)^[8]: a combinator parser whose choice commits to the first alternative that succeeds recognizes the language of a PEG.

§ 07

Comparison with parser generators

Parser generators such as yacc and Menhir take a grammar in a separate notation and produce an LR parser in a table. They accept left recursion, run in linear time, and report conflicts, points where the grammar is ambiguous or needs more lookahead, when the parser is generated. Combinator parsers are checked by the host language's type checker instead, can be abstracted over and composed like any other code, and handle context-sensitive formats, but an ambiguity is resolved silently by the order of the alternatives, and performance depends on how much the parser backtracks.

§ 08

Libraries

Parsec for Haskell and its successor Megaparsec follow Leijen and Meijer's design^[5]. In OCaml, Angstrom provides monadic and applicative combinators and is designed for incremental input. Rust's nom works on byte slices without copying, F# has FParsec, and Scala a parser-combinator library in its standard ecosystem. Python's pyparsing and JavaScript's Parsimmon bring the same approach to dynamically typed languages.

§ 09

History

Burge described parsers as functions and combinators on them in 1975^[1]. Wadler's 1985 paper on the list of successes^[2] and Hutton's "Higher-order functions for parsing" of 1992^[3] established the approach in lazy functional languages, and Wadler's work on monads connected it to the monad structure^[11]. Hutton and Meijer's "Monadic parsing in Haskell"^[4] and Swierstra and Duponcheel's error-correcting combinators^[6] appeared in the late 1990s, and Parsec, in 2001, made combinators practical for real parsers with good error messages^[5]. Ford introduced packrat parsing in 2002 and parsing expression grammars in 2004^[7]^[8].