Design and Implementation of a Functional Expression Engine Using Parser Combinators in Swift

This article introduces a practical solution for building an expression engine that can evaluate string‑based expressions in a messaging scenario. The motivation is to replace the limited NSPredicate‑based approach with a custom parser that supports nested keys, multi‑dimensional configuration, and high performance.

What is an expression engine? An expression is a syntactically correct combination of symbols representing values and operations. For example, 1+2*3 evaluates to 7 . An expression engine parses such strings at runtime and produces a Boolean or other result.

The original system suffered from configuration explosion, redundancy, and maintenance overhead because each Key ‑ Value pair had to be managed separately. By treating the Value as the primary dimension and using logical expressions, the number of configuration entries can be dramatically reduced.

Parser architecture

The solution is organized into four layers:

Base Parser Monad abstraction that defines the parser signature typealias ParserF = (String) -> (A, String)? .

Three primitive parsers: Node (success), Fail (failure), and NextChar (consume one character).

Higher‑order combinators such as check , isChar , or , many , many1 , and bracketLazy that enable sequencing, choice, repetition, and lazy recursion.

Expression‑tree definition (Swift enum Expr2 ) and concrete parsing functions that build the tree.

Core parser definitions

public typealias ParserF
= (String) -> (A, String)?

public class Parser
{ let f: ParserF
; init(_ f: @escaping ParserF
) { self.f = f } ... }

class Node
: Parser
{ init(_ v: V) { super.init { string in (v, string) } } }

class Fail
: Parser
{ init() { super.init { _ in nil } } }

class NextChar: Parser
{ init() { super.init { string in string.first.map { (c, String(string.dropFirst())) } } }

public func check(p: @escaping (Character) -> Bool) -> Parser
{ NextChar().flatMap { c in p(c) ? Node(c) : Fail() } }

public func isChar(_ c: Character) -> Parser
{ check { $0 == c } }

public func or
(_ p1: Parser
, _ p2: Parser
) -> Parser
{ Parser { s in p1.runParser(s) ?? p2.runParser(s) } }

public func many
(_ p: Parser
) -> Parser<[A]> { or(p.flatMap { a in many(p).flatMap { suffix in Node([a] + suffix) } }, Node([])) }

public func many1
(_ p: Parser
) -> Parser<[A]> { p.flatMap { a in many(p).flatMap { suffix in Node([a] + suffix) } } }

public func bracketLazy
(open: Parser
, p: @escaping () -> Parser
, close: Parser
) -> Parser
{ open.flatMap { _ in p().flatMap { a in close.flatMap { _ in Node(a) } } } }

Expression grammar

The grammar is expressed as:

expr   := expr andor term | term

andor  := && | ||

term   := factor compare factor | factor

compare:= == | >= | > | <= | < | !=

factor := identifier | num | str | (expr)

identifier := "${" [a-zA-Z0-9_.]+ "}"

Left‑recursion is eliminated by extracting left factors, e.g.:

expr  := term expr'

expr' := andor expr | ε

The parser functions are built using the combinators above (e.g., identifier() , num() , bracketExpr() , expr() ).

Expression tree

public enum Expr2 { case AND(Expr2, Expr2); case OR(Expr2, Expr2); case EQ(Expr2, Expr2); case NOTEQ(Expr2, Expr2); case BIGTHAN(Expr2, Expr2); case BIGEQTHAN(Expr2, Expr2); case SMALLEQTHAN(Expr2, Expr2); case SMALLTHAN(Expr2, Expr2); case BRACKET(Expr2); case IDENTIFIER(String); case NUM(Int); case STRING(String) }

Evaluation walks the tree and resolves identifiers via KVC against a context dictionary.

Performance

On an iPhone 7, parsing a typical expression takes ~5 ms (first run) and evaluation thereafter < 0.5 ms. Parsing dominates the cost; caching parsed trees yields further gains.

Conclusion

By leveraging the Monad abstraction and parser combinators, a clean, composable, and high‑performance expression engine is built in Swift, solving the limitations of NSPredicate and providing a solid foundation for future feature extensions.