sml-pratt

A Pratt parser (aka "top down operator precedence" / TDOP) core in pure Standard ML, per Vaughan R. Pratt, "Top Down Operator Precedence", POPL 1973, and Douglas Crockford's well-known exposition "Top Down Operator Precedence" (the more commonly-read restatement, whose nud/led/binding-power terminology this library follows).

The generic engine (parseWith, cursor, grammar) is expressed with ordinary SML parametric polymorphism -- no functors needed: a ('tok, 'ast) grammar is a record of the eof/isEOF/lbp/nud/led parselet table, and parseWith is a single polymorphic function that drives any such grammar. The arithmetic grammar (+ - * / ^, unary minus, parens, function calls, ? : ternary) is one concrete instantiation of it, built entirely from the public grammar/cursor types -- nothing about the engine is hardcoded to arithmetic.

No dependencies, no FFI, no threads, no clock, no randomness: the same inputs always produce the same outputs under MLton and Poly/ML.

Precedence and associativity convention

Standard: ^ right-associative, + - * / left-associative, * / bind tighter than + -, ^ binds tighter than * /. Function calls (f(...)) bind tightest of all; the ? : ternary binds loosest of all and is itself right-associative (a ? b : c ? d : e reads as a ? b : (c ? d : e)).

Unary minus is a deliberate design choice (documented and tested, since languages disagree): it binds looser than ^ but tighter than * /. So -2 ^ 2 = -(2 ^ 2) = -4 (matching Python's -2 ** 2 == -4 and most graphing calculators), while -2 * 3 = (-2) * 3 = -6.

API

signature PRATT =
sig
  (* Generic engine -- reusable for any token/ast type. *)
  type ('tok, 'ast) cursor =
    { peek : unit -> 'tok, advance : unit -> 'tok, expr : int -> 'ast }
  type ('tok, 'ast) grammar =
    { eof : 'tok, isEOF : 'tok -> bool, lbp : 'tok -> int,
      nud : ('tok, 'ast) cursor -> 'tok -> 'ast,
      led : ('tok, 'ast) cursor -> 'ast -> 'tok -> 'ast }
  exception ParseError of string
  val parseWith : ('tok, 'ast) grammar -> 'tok list -> 'ast

  (* Arithmetic grammar: one instantiation of the engine above. *)
  datatype token = NUM of int | IDENT of string
                 | PLUS | MINUS | STAR | SLASH | CARET
                 | LPAREN | RPAREN | COMMA | QUESTION | COLON | EOF
  datatype binop = Add | Sub | Mul | Div | Pow
  datatype ast = Num of int | Var of string | Neg of ast
               | Bin of binop * ast * ast | Ternary of ast * ast * ast
               | Call of string * ast list
  exception LexError of string
  exception EvalError of string

  val arithGrammar : (token, ast) grammar
  val tokenize    : string -> token list
  val parse       : token list -> ast
  val parseString : string -> ast
  val evalWith    : (string -> int) -> ast -> int
  val eval        : ast -> int
  val evalString  : string -> int
end

Example

val 512 = Pratt.evalString "2 ^ 3 ^ 2"          (* right-assoc: 2^(3^2) *)
val ~4  = Pratt.evalString "-2 ^ 2"             (* -(2^2), documented convention *)
val ~4  = Pratt.evalString "1 - 2 - 3"          (* left-assoc: (1-2)-3 *)
val 5   = Pratt.evalString "max(1 + 2, 2 * 2)"  (* function calls, full-expr args *)

Running examples/demo.sml with make example prints:

Precedence and associativity:
  1 + 2 * 3
    ast = (1 + (2 * 3))
    val = 7
  2 ^ 3 ^ 2
    ast = (2 ^ (3 ^ 2))
    val = 512
  1 - 2 - 3
    ast = ((1 - 2) - 3)
    val = -4
  (1 + 2) * 3
    ast = ((1 + 2) * 3)
    val = 9

Unary minus vs ^ and * / (documented convention):
  -2 ^ 2
    ast = (-(2 ^ 2))
    val = -4
  -2 * 3
    ast = ((-2) * 3)
    val = -6

Ternary (?:), lowest binding power, right-associative:
  1 ? 2 : 3
    ast = (1 ? 2 : 3)
    val = 2
  0 ? 2 : 3
    ast = (0 ? 2 : 3)
    val = 3

Function calls:
  max(3, 5)
    ast = max(3, 5)
    val = 5
  min(1 + 2, 2 * 2)
    ast = min((1 + 2), (2 * 2))
    val = 3
  abs(-7)
    ast = abs((-7))
    val = 7

Error handling (parseString "1 +"):
  ParseError: unexpected token in prefix (nud) position

Build & test

Requires MLton and/or Poly/ML.

make test        # build + run the suite under MLton
make test-poly   # run the suite under Poly/ML
make all-tests   # both, plus the byte-identical gate
make example     # build + run the demo
make clean

Installing with smlpkg

smlpkg add github.com/sjqtentacles/sml-pratt
smlpkg sync

Reference lib/github.com/sjqtentacles/sml-pratt/pratt.mlb from your own .mlb (MLton / MLKit), or feed sources.mlb to tools/polybuild (Poly/ML).

Layout

sml.pkg                                     smlpkg manifest
Makefile                                    MLton + Poly/ML targets
.github/workflows/ci.yml                    CI: MLton + Poly/ML (variant A)
lib/github.com/sjqtentacles/sml-pratt/
  pratt.sig    PRATT signature: generic engine + arithmetic instantiation
  pratt.sml    parseWith engine + arithmetic grammar/lexer/evaluator
  sources.mlb  ordered source list
  pratt.mlb    public basis
examples/
  demo.sml     precedence, unary minus, ternary, calls, error handling
test/
  harness.sml  shared assertion harness
  test.sml     44 checks: precedence/assoc, AST shape, lexer, errors
  entry.sml / main.sml
tools/polybuild Poly/ML build wrapper

Tests

44 deterministic checks, hand-derived from standard arithmetic convention (the same taught in any algebra course; cross-checked against Python's operator precedence for the unary-minus-vs-^ convention). Covered:

• Precedence/associativity via evaluation: 1 + 2 * 3 = 7 (not 9), 2 ^ 3 ^ 2 = 512 (right-assoc, not 64), 1 - 2 - 3 = -4 (left-assoc), 10 / 2 / 5 = 1 (left-assoc), 2 * 3 ^ 2 = 18, 2 ^ 2 ^ 3 = 256, parenthesized override.
• Unary minus convention: -2 ^ 2 = -4, -2 * 3 = -6, nested/double unary minus, unary minus interacting with binary minus.
• Exact AST shape for the precedence/associativity cases above (the "hand-derived expected ASTs"), confirming e.g. 2 ^ 3 ^ 2 nests as Bin(Pow, 2, Bin(Pow, 3, 2)) and 1 - 2 - 3 nests as Bin(Sub, Bin(Sub, 1, 2), 3).
• Ternary: low binding power, right-associative chaining (a?b:c?d:e parses as a?b:(c?d:e)), interaction with +.
• Function calls: f(x, y) with full-expression arguments, calls binding tighter than +, unary minus inside an argument.
• Variables via evalWith's environment, and eval's free-variable error.
• Lexer: multi-digit numbers, identifiers, whitespace skipping (spaces/tabs/newlines), unrecognized-character LexError.
• Error handling: dangling operator, trailing tokens after a complete expression, unclosed paren, missing : in a ternary, calling a non-identifier, unknown function, wrong arity, negative exponent.
• Division truncates toward zero (Int.quot, not SML's own div, which floors toward negative infinity for mixed signs): -7 / 2 = -3, not -4.

Run make all-tests to verify identical output under both compilers.

License

MIT. See LICENSE.