Parsing a simple expression language in F# using Active Patterns

Sometimes it is necessary to transform a string into an Abstract Syntax Tree (AST) for further manipulation. In this post I’ll show how to do that in F# using a feature called Active Patterns.

If you’re not familiar with pattern matching in F#, the official docs are a good starting point. Active Patterns extend pattern matching by letting you run a function — rather than matching against a constant — in a match arm.

The AST

We start by defining the data structures that represent our expression language:

/// Abstract syntax tree (AST)
type BinaryOperator = 
    | And | Or | Equal | NotEqual | NotEqual2
    | GreaterThan | GreaterThanOrEqual | LessThan | LessThanOrEqual

type UnaryOperator =
    | Not

and Expr = 
    | Paren of Expr
    | Binop of Expr * BinaryOperator * Expr
    | Unop  of UnaryOperator * Expr
    | Ident of string
    | String of string
    | EndOfFile

And a small pretty-printer so we can verify the output:

let BinOpToStr = dict [
    And,              "&&"; Or,             "||"
    Equal,            "=="; NotEqual,       "!="
    NotEqual2,        "<>"; GreaterThan,    ">"
    GreaterThanOrEqual,"=>"; LessThan,      "<"
    LessThanOrEqual,  "<="
]

let rec BinaryOperatorToStr op =
    match BinOpToStr.TryGetValue op with
    | true, str -> str
    | _         -> failwithf "Unknown operator %A" op

and ExprToStr = function
    | Paren e1          -> sprintf "(%s)" (ExprToStr e1)
    | Binop(e1, op, e2) -> sprintf "%s %s %s" (ExprToStr e1) (BinaryOperatorToStr op) (ExprToStr e2)
    | Unop(op, e1)      -> sprintf "%s%s" (UnaryOperatorToStr op) (ExprToStr e1)
    | Ident s           -> s
    | String s          -> sprintf "\"%s\"" s
    | EndOfFile         -> ""

and UnaryOperatorToStr = function
    | Not -> "!"

Helpers

The parser works on lists of characters, so we define a few helpers:

let charsOfStr (s : string) = List.ofArray(s.ToCharArray())
let strOfChars (chars : char seq) = System.String(Seq.toArray chars)

let lowerChar  = set (['a'..'z'] @ ['æ';'ø';'å'])
let upperChar  = set (['A'..'Z'] @ ['Æ';'Ø';'Å'])
let letter     = lowerChar + upperChar
let digit      = set ['0' .. '9']
let letterOrDigit = letter + digit

let consume s = function
    | c :: cs when Set.contains c s -> Some(c, cs)
    | _ -> None

let basic pred = function
    | c :: cs when pred c -> Some(c, cs)
    | _ -> None

let (|Any1|_|)    e = basic ((=) e)
let (|Any1But|_|) e = basic ((<>) e)

Combinator Active Patterns

The real power comes from Active Patterns that are parameterised over other Active Patterns:

let (|ZeroOrMore|) q inp =
    let rec queryAcc rvs e =
        match q e with
        | Some(v, body) -> queryAcc (v :: rvs) body
        | None          -> (List.rev rvs, e)
    queryAcc [] inp

let (|OneOrMore|) q inp =
    match q inp with
    | Some (v, body) ->
        let xs, t = (|ZeroOrMore|) q body
        v :: xs, t
    | None -> [], inp

let (|ConsumeChar|_|)       = consume letter
let (|ConsumeCharNumber|_|) = consume letterOrDigit
let (|ConsumeNumber|)       = (|OneOrMore|) (consume digit)

let (|WS|) = function
    | ZeroOrMore ((|Any1|_|) ' ') (ws, xs) -> (ws, xs)

The Parser

The string and identifier parsers build on those combinators:

let (|STRING|_|) = function
    | Any1 '"' (_, ZeroOrMore ((|Any1But|_|) '"') (xs, Any1 '"' (_, WS(_, t)))) ->
        Some (String(strOfChars xs), t)
    | _ -> None

let (|IDENTEND|_|) = function
    | '_' :: '_' :: ConsumeNumber(n, (WS(_, cs))) -> Some(['_';'_'] @ n, cs)
    | _ -> None

let (|IDENT|_|) = function
    | ConsumeChar (c, OneOrMore (|ConsumeCharNumber|_|) (cs, IDENTEND(identend, xs))) ->
        Some (Ident(strOfChars(c :: cs @ identend)), xs)
    | _ -> None

And finally the full expression parser, with mutually recursive Active Patterns:

let rec (|EXPR|_|) = function
    | NOT(u, EXPR(e, xs))      -> Some(Unop(u, e), xs)
    | VALUE(e1, xs) ->
        match xs with
        | []                             -> Some(e1, [])
        | BINOP(o, WS(_, EXPR(e2, xs))) -> Some(Binop(e1, o, e2), xs)
        | xs                             -> Some(e1, xs)
    | xs -> failwithf "EXPR: unexpected '%s'" (strOfChars xs)

and (|BINOP|_|) = function
    | '&' :: '&' :: xs -> Some(And,              xs)
    | '|' :: '|' :: xs -> Some(Or,               xs)
    | '!' :: '=' :: xs -> Some(NotEqual,          xs)
    | '>' :: '=' :: xs -> Some(GreaterThanOrEqual,xs)
    | '>'       :: xs  -> Some(GreaterThan,       xs)
    | '=' :: '>' :: xs -> Some(GreaterThanOrEqual,xs)
    | '=' :: '=' :: xs -> Some(Equal,             xs)
    | '<' :: '>' :: xs -> Some(NotEqual2,         xs)
    | '<' :: '=' :: xs -> Some(LessThanOrEqual,   xs)
    | '<'       :: xs  -> Some(LessThan,          xs)
    | _                -> None

and (|NOT|_|) = function
    | '!' :: Any1But '=' (c, WS(_, cs)) -> Some(Not, c :: cs)
    | _ -> None

and (|VALUE|_|) = function
    | STRING(s, xs)                         -> Some(s,  xs)
    | IDENT(i,  xs)                         -> Some(i,  xs)
    | '(' :: (EXPR(e, ')' :: WS(_, xs)))   -> Some(Paren e, xs)
    | []                                    -> Some(EndOfFile, [])
    | xs -> failwithf "VALUE: unexpected '%s'" (strOfChars xs)

Testing it

let parse str =
    match charsOfStr str with
    | EXPR(e, []) -> ExprToStr e
    | _           -> failwith "Parse error"

parse "!member60__1 && company__1 == \"LP\""
// → "!member60__1 && company__1 == \"LP\""

parse "(t1__1 >= t1__1 && t1__1 > t1__1 && t1__1 < t1__1)"
// → "(t1__1 => t1__1 && t1__1 > t1__1 && t1__1 < t1__1)"

Why this approach?

Compared to parser combinator libraries (FParsec) or regex, Active Patterns give you:

• Composability — small patterns combine into larger ones naturally
• Readability — the parser code mirrors the grammar
• No dependencies — pure F# standard library
• Mutual recursion — and keyword handles left-recursive grammars cleanly

The pattern of ZeroOrMore/OneOrMore parameterised over other Active Patterns is particularly powerful and appears in several production parsers I’ve written for the pensions domain.