GitHub Try it
Home
All Guides

On this page

Language

Ecosystem

Community

Parser Combinators Tutorial

This tutorial builds a working parser-combinator library in pure Turmeric. By the end you will:

The focus is pedagogy, not micro-optimisation. Every line is idiomatic Turmeric with defdata, match, and no inline C.

The runnable end-to-end version of every snippet here lives in tests/fixtures/parsec-tutorial/input.tur.

Note. The snippets below use the #\<char> character-literal syntax (#\+, #\0, #\space); see docs/archive/legible-char-literals-plan.md. A #\<char> literal is a Char (from the auto-loaded stdlib/char.tur), not an :int: compare characters with char=?, classify them with digit? / alpha? / space?, and cross to the code with char->int (or back with int->char). The runnable fixture uses #\ throughout.

This tutorial builds its own combinators from scratch. For the stdlib's ready-made tur/parsec library, see the parsec tutorial and the parsec reference guide.

Why combinators?

A parser is a function that takes input and either succeeds -- consuming some prefix and returning a value plus the leftover input -- or fails.

Hand-written recursive-descent parsers mutate a shared cursor, so trying one branch, failing, and backing up requires bookkeeping. Parser combinators replace that ceremony with values: each combinator is a function from parsers to a new parser. The result reads like the grammar.

Turmeric's ADTs and GADTs let us build the same story with the type-checker on our side. A (PRes A) value can only mean "failure" or "success carrying an A"; a valid Expr node can only be one of the constructors we declared; match refuses to compile if we forget a case. Every combinator gets stronger static guarantees than the equivalent Haskell tutorial would have handed us.

Modelling the input

For a byte-oriented parser we want to walk the source one character at a time. The natural Turmeric type is a :cstr plus cstr-nth from stdlib/cstr (not autoloaded, so it takes a (import cstr :refer [cstr-len cstr-nth])). For the tutorial we keep the input as a list of characters instead -- a plain cons list walked with stdlib/list's list-head and list-tail -- because it lets every combinator take the same input type (an int list carrier) without threading an index alongside the source. The string "1+2*(3+4)" becomes:

(list #\1 #\+ #\2 #\* #\( #\3 #\+ #\4 #\))

Two helpers make the rest of the code read cleanly. End-of-input is a 0 list carrier (nil), and the carrier holds each character as its code, so reading the head crosses back to a Char:

(defn at-end? [xs : int] : bool (= xs 0))

(defn head-char [xs : int] : Char (int->char (list-head xs)))

head-char xs returns the current character and list-tail xs advances the cursor. Character classification comes from the stdlib: digit?, alpha?, space? and friends all take a Char.

The result type

A parse either fails or succeeds and returns leftover input. That's a two-armed sum, parameterised over the success payload:

(defdata PRes [a]
  (PFail)
  (POK a int))

Every parser in the tutorial has the shape

Parser<A> = (fn [xs : int] : (PRes A))

where xs is the current input list.

The primitive: psat

The one primitive parser -- the atom every other combinator is built on -- consumes a single character if it matches a predicate:

(defn psat [pred : (fn [Char] bool)] : (fn [int] (PRes Char))
  (fn [xs : int] : (PRes Char)
    (if (at-end? xs)
      (PFail)
      (let [c (head-char xs)]
        (if (pred c) (POK c (list-tail xs)) (PFail))))))

psat returns a closure -- a function value that captures pred. Every combinator below follows the same shape: take some parsers (and maybe a helper), return a new parser (a (fn [int] (PRes A)) closure). Once you have psat, pchar and digit are one-liners:

(defn eq-char [target : Char] : (fn [Char] bool)
  (fn [c : Char] : bool (char=? c target)))

(defn pchar [target : Char] : (fn [int] (PRes Char))
  (psat (eq-char target)))

(defn digit [xs : int] : (PRes Char)
  ((psat digit?) xs))

pchar currying: eq-char builds a predicate closure and psat lifts it into a parser. digit invokes (psat digit?) eagerly and eta-expands the result so it can be used as a plain top-level parser.

Combinators

The combinators are the recurring shapes -- alternation, mapping, sequencing -- lifted out of ad-hoc grammar code so we can compose them freely. The tutorial spells each one monomorphically (one instance per element type: or-char / or-expr, map-int-to-expr) as a pedagogical choice -- the shapes are easier to read when the element type is spelled out. The polymorphic spelling (or-parser [A] p q) also works: the compiler infers A through the returned closure at the application site.

Alternation -- or-*

"Try p; if it fails, try q":

(defn or-char [p : (fn [int] (PRes Char)) q : (fn [int] (PRes Char))]
    : (fn [int] (PRes Char))
  (fn [xs : int] : (PRes Char)
    (match (p xs)
      (POK v rest) (POK v rest)
      (PFail)      (q xs))))

(defn or-expr [p : (fn [int] (PRes Expr)) q : (fn [int] (PRes Expr))]
    : (fn [int] (PRes Expr))
  (fn [xs : int] : (PRes Expr)
    (match (p xs)
      (POK v rest) (POK v rest)
      (PFail)      (q xs))))

The two are line-for-line identical except for the element type. They collapse to a single polymorphic defn:

(defn or-parser [A] [p : (fn [int] (PRes A)) q : (fn [int] (PRes A))]
    : (fn [int] (PRes A))
  (fn [xs : int] : (PRes A)
    (match (p xs)
      (POK v rest) (POK v rest)
      (PFail)      (q xs))))

A is a type parameter declared right after the name; it appears in both the argument closures and the returned closure, and the compiler grounds it at each application site (e.g. (or-parser paren-expr number-as-expr) grounds A = Expr). The tutorial keeps the monomorphic pair below for readability, but any call to or-char or or-expr can be replaced with or-parser verbatim.

Mapping -- map-*-to-*

"Run p; on success, transform the payload":

(defn map-int-to-expr [f : (fn [int] Expr) p : (fn [int] (PRes int))]
    : (fn [int] (PRes Expr))
  (fn [xs : int] : (PRes Expr)
    (match (p xs)
      (PFail)      (PFail)
      (POK v rest) (POK (f v) rest))))

Note the bare (PFail) on the failure arm: the enclosing fn's declared return (PRes Expr) propagates into the arm body, so no (:: (PFail) (PRes Expr)) ascription is needed. Same for the (PFail) inside or-*.

The polymorphic spelling factors the same way:

(defn map-parser [A B] [f : (fn [A] B) p : (fn [int] (PRes A))]
    : (fn [int] (PRes B))
  (fn [xs : int] : (PRes B)
    (match (p xs)
      (PFail)      (PFail)
      (POK v rest) (POK (f v) rest))))

Two type parameters this time -- the input element A and the mapped output B -- because map is where the element type actually changes shape. (map-parser to-enum number) grounds A = int, B = Expr and gives back exactly number-as-expr.

The AST as a GADT

Each constructor declares its result type after a :, and every one pins the [a] parameter to int -- so as written this Expr is not yet refined, just a sum with a pinned parameter. In a richer calculator you could add (EEq (Expr int) (Expr int) : (Expr bool)) and the type checker would then refuse EAdd (EEq ...) (ENum 1) at compile time. That's the GADT payoff -- illegal ASTs stop being representable.

(defdata Expr [a]
  (ENum int                     : (Expr int))
  (EAdd (Expr int) (Expr int)   : (Expr int))
  (ESub (Expr int) (Expr int)   : (Expr int))
  (EMul (Expr int) (Expr int)   : (Expr int))
  (EDiv (Expr int) (Expr int)   : (Expr int)))

(defn apply-op [op : Char lhs : Expr rhs : Expr] : Expr
  (if (char=? op #\+) (EAdd lhs rhs)
    (if (char=? op #\-) (ESub lhs rhs)
      (if (char=? op #\*) (EMul lhs rhs)
        (if (char=? op #\/) (EDiv lhs rhs)
          (ENum 0))))))

apply-op dispatches on the operator character. It falls through to (ENum 0) on an unknown operator, which never happens if the grammar is correct -- and if it does, eval-expr will still produce a defined value.

The grammar

expr   := term (('+' | '-') term)*
term   := factor (('*' | '/') factor)*
factor := number | '(' expr ')'
number := digit+

The two-level expr / term split is what buys precedence: * and / are one level deeper than + and -, so they bind tighter.

number -- one-or-more digits, folded

(defn digits-int-loop [xs : int acc : int] : (PRes int)
  (if (at-end? xs)
    (POK acc xs)
    (let [c (head-char xs)]
      (if (digit? c)
        (digits-int-loop (list-tail xs) (+ (* acc 10) (char->digit c)))
        (POK acc xs)))))

(defn number [xs : int] : (PRes int)
  (match (digit xs)
    (PFail)      (PFail)
    (POK d rest) (digits-int-loop rest (char->digit d))))

digit (from earlier) is the "at-least-one" gate; digits-int-loop is the tail-recursive many that greedily accumulates the rest into an int. The recursion is self-tail-call, so the compiler turns it into iteration -- no stack growth, no O(n) intermediate allocations.

factor -- alternation via or-expr

(defn to-enum [n : int] : Expr (ENum n))

(defn number-as-expr [xs : int] : (PRes Expr)
  ((map-int-to-expr to-enum number) xs))

(defn paren-expr [xs : int] : (PRes Expr)
  (if (at-end? xs)
    (PFail)
    (let [c (head-char xs)]
      (if (char=? c #\()
        (match (expr-parse (list-tail xs))
          (PFail)          (PFail)
          (POK inner rest)
          (if (at-end? rest)
            (PFail)
            (if (char=? (head-char rest) #\))
              (:: (POK inner (list-tail rest)) (PRes Expr))
              (PFail))))
        (PFail)))))

(defn factor [xs : int] : (PRes Expr)
  ((or-expr paren-expr number-as-expr) xs))

factor is now a one-liner over or-expr: try paren-expr first, fall back to number-as-expr. number-as-expr shows the map shape in action -- to-enum wraps ENum as a plain function value (a GADT constructor can't yet be passed directly as a first-class value) and map-int-to-expr lifts it into a Parser<Expr>.

paren-expr still needs to reach into match for the closing ) handling; not every one-off pattern collapses into a combinator.

One (:: (POK inner (list-tail rest)) (PRes Expr)) ascription appears in paren-expr. It is optional -- the forward-decl pass records expr-parse's compound parametric return type even though expr-parse is defined later in the file (mutual recursion), so the match binder infers correctly without it -- but the tutorial fixture carries it verbatim.

Left-associative chains -- term and expr

term := factor (('*'|'/') factor)* is a factor followed by an inlined many over (op, factor) pairs, folded left-to-right:

(defn term-tail [xs : int lhs : Expr] : (PRes Expr)
  (if (at-end? xs)
    (POK lhs xs)
    (let [c (head-char xs)]
      (if (or (char=? c #\*) (char=? c #\/))
        (match (factor (list-tail xs))
          (PFail)          (PFail)
          (POK rhs rest)   (term-tail rest (apply-op c lhs rhs)))
        (POK lhs xs)))))

(defn term [xs : int] : (PRes Expr)
  (match (factor xs)
    (PFail)          (PFail)
    (POK lhs rest)   (term-tail rest lhs)))

term-tail is where left-associativity comes from: we apply the op before recursing, so 2*3*4 folds into EMul (EMul 2 3) 4, not EMul 2 (EMul 3 4). expr and expr-tail are the same shape with +/- and term swapped in.

(defn expr-tail [xs : int lhs : Expr] : (PRes Expr)
  (if (at-end? xs)
    (POK lhs xs)
    (let [c (head-char xs)]
      (if (or (char=? c #\+) (char=? c #\-))
        (match (term (list-tail xs))
          (PFail)          (PFail)
          (POK rhs rest)   (expr-tail rest (apply-op c lhs rhs)))
        (POK lhs xs)))))

(defn expr-parse [xs : int] : (PRes Expr)
  (match (term xs)
    (PFail)          (PFail)
    (POK lhs rest)   (expr-tail rest lhs)))

The chain-fold pattern -- match the head, keep folding tails, wrap each application through apply-op -- is itself a candidate for a chainl1 combinator. Today it reads clearly enough as its own defn.

Evaluation

Evaluation is a five-line walk of the GADT. No tag comparisons, no default arm, no fall-through -- match proves every constructor is handled:

(defn eval-expr [e : Expr] : int
  (match e
    (ENum n)   n
    (EAdd l r) (+ (eval-expr l) (eval-expr r))
    (ESub l r) (- (eval-expr l) (eval-expr r))
    (EMul l r) (* (eval-expr l) (eval-expr r))
    (EDiv l r) (/ (eval-expr l) (eval-expr r))))

The round-trip

(defn main [] : int
  (let [input (list #\1 #\+ #\2 #\* #\( #\3 #\+ #\4 #\))]   ;; "1+2*(3+4)"
    (match (expr-parse input)
      (PFail)          (do (println 0) 1)
      (POK ast rest)   (do (println (eval-expr ast)) 0))))

Running the fixture prints 15. Swap eval-expr for a pretty-printer and you have a normaliser without touching the parser code -- that's the separation of syntax and semantics the ADT/GADT split buys you.

Where the types earned their keep

Looking back at what the type system gave us:

None of these are aesthetic wins. Each rules out an entire class of bugs at compile time. That is the reason to reach for GADTs and ADTs even for a tutorial-sized parser.

Where to go next

See also