Parser combinator

A parser is a function from input to a result and the rest of the input, or failure. Parser combinators build parsers from smaller ones: sequencing, choice, repetition. A grammar becomes a set of ordinary recursive definitions in the host language.

Parser a = String \to Maybe (a \times String)

Sequencing, $p > > = f$ , runs $p$ and then the parser that $f$ builds from its result, on the remaining input. Choice, $p < ∣ > q$ , tries $q$ where $p$ fails. Everything else is defined from those two and $return$ .

A parser for arithmetic, with the usual precedence and left associativity. Positions stand in for the rest of the input.

(* A parser takes the input and a position, and either fails or returns a
   value and the position after it. *)
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 ( <|> ) (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 ( let* ) = ( >>= )
 
let satisfy pred : char parser =
 fun s i -> if i < String.length s && pred s.[i] then Some (s.[i], i + 1) else None
let char c = satisfy (( = ) c)
 
let rec many p = (let* x = p in let* xs = many p in return (x :: xs)) <|> return []
let many1 p = let* x = p in let* xs = many p in return (x :: xs)
 
let number =
  let* ds = many1 (satisfy (function '0' .. '9' -> true | _ -> false)) in
  return (int_of_string (String.of_seq (List.to_seq ds)))
 
(* Left-associative chains without left recursion: parse one operand, then
   fold every (operator, operand) that follows onto it 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 rec expr s i = chainl1 term (char '+' >>= (fun _ -> return ( + )) <|> (char '-' >>= fun _ -> return ( - ))) s i
and term s i = chainl1 factor (char '*' >>= (fun _ -> return ( * )) <|> (char '/' >>= fun _ -> return ( / ))) s i
and factor s i = (number <|> (let* _ = char '(' in let* e = expr in let* _ = char ')' in return e)) s i
 
let parse s = match expr s 0 with Some (v, j) when j = String.length s -> Some v | _ -> None

Running it.

1+2*3          ->  7
8-3-2          ->  3
(1+2)*3        ->  9
100/10/5       ->  2
2*(3+4)-1      ->  13
1+             ->  no parse

The textbook grammar $expr ::= expr - term ∣ term$ cannot be written directly: expr would call itself at the same position before consuming anything, and never return (in OCaml, a stack overflow). chainl1 parses the same language by reading one operand and then folding each following operator and operand onto it from the left, which is why 8-3-2 is 3 and not 7.

$< ∣ >$ here commits to the first alternative that succeeds, as in a PEG. Returning a list of successes instead of an option gives every parse, which handles ambiguous grammars at exponential worst-case cost. Parsec commits as soon as an alternative has consumed input, which gives precise error positions and linear time on LL(1)-style grammars, with try to ask for backtracking explicitly.

Because $> > =$ can choose the next parser from a value already parsed, monadic combinators are context-sensitive: a length field followed by that many bytes is one line. Applicative combinators give that up, and in exchange a parser built from them can be inspected before it runs.