LexerParser

A Swift package for building lexers and parsers from declarative grammars.

Lexers are described with a set of Rules that map regular expressions to token cases. Parsers are described with type-safe combinators that build a grammar, which is then compiled into an LL(k), SLR(k), LALR(k) or LR(k) parser. Both halves can be combined into a single value, so a complete front end for a small language is often just one try expression.

Three things set this package apart from hand-written recursive descent:

• The lexer and the parser are separate values that still stay in step. Each has its own grammar and back end, so either half works on its own — the lexer over a source, the parser over a token array you built yourself — or combined in one DFALexerLLParser or DFALexerLRParser. They cannot drift apart, because both are tied to one token type: every Transform and Skip in the parser is type-checked against the enum the lexer emits.
• Streaming by default. Parsers emit output tokens as soon as a reduction is final instead of building a whole syntax tree, and lexers pull characters from the source on demand. You can stop consuming at any point and the rest of the input is never read.
• No syntax tree required. Reduction actions are plain Swift closures over token arrays, so you can parse straight into your own domain types — or skip the parser entirely and pattern-match the token stream.

Requirements

	Version	Note
Swift	6.3 or later	Swift 6 language mode
macOS	15 or later
iOS	18 or later
Dependencies	swift-syntax 602.0.0+	for the @TokenType macro

Installation

Add the package to the dependencies of your Package.swift:

dependencies: [
    .package(url: "https://github.com/macmoonshine/LexerParser.git", from: "1.0.0")
]

And add the LexerParser product to your target:

.target(
    name: "MyTarget",
    dependencies: [
        .product(name: "LexerParser", package: "LexerParser")
    ]
)

Then import LexerParser. The umbrella module re-exports Grammar, Lookahead and ParserBuilder, so a single import is enough. If you prefer to depend on the layers individually, they are also available as the products Grammar, Lookahead and ParserBuilder.

Quick start

Here is a complete example, from an empty file to a working front end. The language is deliberately tiny — numbers, the operators + and -, a comma and parentheses — so inputs like 1, 2, 3 and (1, (2, 3)) tokenize cleanly, and whitespace between tokens is ignored.

The steps are: declare the token types, write the lexer, then consume the result. A lexer is useful in two ways once it exists, and both are covered — you can walk the token stream directly, or hand the same grammar to a parser.

1. Declare your token types

Annotate an enum with @TokenType. The macro synthesizes the TokenType conformance, so cases that carry a payload can be used directly as lexer output. The type a parser emits must conform to TokenType as well, which in practice means wrapping your result in an enum rather than using a bare Int or Double.

import LexerParser

@TokenType
enum ArithmeticToken {
    case number(Double)
    case plus
    case minus
    case comma
    case open
    case close
}

2. Write the lexer

DFALexer is built from a @GrammarBuilder closure. Each Rule is one token pattern: the elements in the rule body are concatenated, and a leading / turns a string into a regular expression. A rule without a tokenTransformer is skipped, which is how whitespace and comments are ignored.

func arithmeticLexer() throws -> DFALexer<String, ArithmeticToken> {
    try .init() {
        Rule { /"[ \t]+" }                              // no transformer: skipped
        Rule {
            /"[+-]?\\d+(\\.\\d+)?"
        }
        tokenTransformer: { .number(Double($0)!) }
        Rule(token: .plus) { "+" }
        Rule(token: .minus) { "-" }
        Rule(token: .comma) { "," }
        Rule(token: .open) { "(" }
        Rule(token: .close) { ")" }
    }
}

Order matters only for ties: the lexer prefers the longest match, and among equally long matches the rule declared first wins.

3a. Tokenize only

tokenize(_:) returns a lazy iterator. Nothing is scanned until you pull, so you can feed it straight into a hand-written loop:

let lexer = try arithmeticLexer()

for token in lexer.tokenize("1 + 2") {
    print(token)   // number(1.0), plus, number(2.0)
}

Use tokens(source:) if you would rather have an array. To drive the lexer yourself, iterate manually and call isAtEnd() to tell a clean end of input apart from a position where no rule matched:

let tokens = Array(lexer.tokens(source: "1 + 2"))

var iterator = lexer.tokenize("1 + 2")
while !iterator.isAtEnd() {
    guard let token = iterator.next() else {
        // No rule matched at the current position.
        break
    }
    print(token)
}

The iterator also reports where each token came from, which is what you want for diagnostics:

var iterator = lexer.tokenize("1 +\n2")
while let token = iterator.next() {
    let position = iterator.lastTokenPosition
    print(token, position.start.line, position.start.column, position.end.offset)
}

You can find out more about Lexer here.

3b. Lexer and parser together

When you also need a parser, combine both halves in one value. The first closure builds the lexer grammar, the second the parser grammar, and the leading argument selects the parser class. The parser emits tokens of an output type, which is declared like any other token type:

@TokenType
enum Value {
    case number(Double)
    case comma
}

func arithmeticParser() throws -> DFALexerLRParser<String, ArithmeticToken, Value> {
    try .init(.lr(k: 1)) {
        Rule { /"[ \t]+" }
        Rule {
            /"[+-]?\\d+(\\.\\d+)?"
        }
        tokenTransformer: { .number(Double($0)!) }
        Rule(token: .plus) { "+" }
        Rule(token: .minus) { "-" }
        Rule(token: .comma) { "," }
        Rule(token: .open) { "(" }
        Rule(token: .close) { ")" }
    }
    parser: {
        Repeated(quantifier: .any) {
            Transform<ArithmeticToken, Value>(.number) { token in
                guard case .number(let value) = token else { return [] }
                return [.number(value)]
            }
        } separator: {
            Skip<ArithmeticToken, Value>(.comma)
        }
    }
}

parse(source:) runs the whole pipeline and returns a lazy iterator over the output tokens. collect() runs it to completion and rethrows any parse error:

let parser = try arithmeticParser()
var output = parser.parse(source: "1, 2, 3")

print(try output.collect())   // [number(1.0), number(2.0), number(3.0)]

Use DFALexerLLParser instead if your grammar is not LR — the DSL is identical, only the parser class differs.

The lexer DSL

See also: lexer.md is a dedicated guide to the NFA and DFA lexers, covering the Rule and Choice combinators and how named states are created and referenced with the * prefix operator.

A lexer turns text into a stream of tokens. The grammar is an ordered list of rules, and each rule matches one of several things:

• a regular expression, written by prefixing a string with /
• literal characters, written as plain strings
• a named rule, referenced with the * prefix operator

Elements within a rule are concatenated, so Rule { "(" /"\\d+" ")" } matches a parenthesized number. Each rule then decides what it emits: a fixed token, a token derived from the matched text, or nothing at all. DFALexer and NFALexer both take such a grammar, and the grammar can also be built as a standalone value for reuse or testing.

Rules

Form	Effect
Rule { … }	A pattern that is matched but produces no tokens (whitespace, comments)
Rule(token: .plus) { "+" }	A pattern that always emits the same token
Rule { … } tokenTransformer: { … }	A pattern whose match is converted to tokens

A tokenTransformer receives the matched source text and returns the token to emit:

Rule { /"\\d+" } tokenTransformer: { .text($0) }

Use $0 (or build the value from it) rather than returning a bare case with no payload, so the compiler can settle on the one-argument overload of tokenTransformer.

Combining patterns inside a rule

Rule bodies use @RuleElementBuilder, where the elements are concatenated. Pass several elements to Choice to make them alternatives, and use its quantifier: to repeat them:

Rule {
    "\""
    Choice(quantifier: .any) {
        /"\\\\u[0-9A-Fa-f]{4}"
        /"[^\\\\\"]"
    }
    "\""
}
sourceTransformer: { resolveEscapes($0) }
tokenTransformer: { _ in [.stringBody] }

Choice(quantifier: .one) with several elements is plain alternation; any other quantifier wraps the alternatives in a repetition, so the string rule matches a quote, then any number of characters that are either a \uXXXX escape or an ordinary character, then a closing quote.

sourceTransformer post-processes the entire match, while tokenTransformer converts it into tokens. The two are independent and can be combined.

A rule may be given a name, which turns it into a non-terminal of the lexer grammar. Other rules can then refer to it with the * prefix operator (or StateByName("…")):

func namedRuleLexer() throws -> DFALexer<String, ExtraToken> {
    try .init() {
        Rule("string") {
            "\""
            Choice(quantifier: .any) { /"[^\\\\\"]" }
            "\""
        }
        Rule { *"string" } tokenTransformer: { _ in .stringBody }
    }
}

If you build a grammar as a standalone value instead of passing a closure to a lexer, annotate a function with @GrammarBuilder. The same grammar value can then be reused for a lexer, for a parser, and for a conformance check:

@GrammarBuilder<String, ArithmeticToken>
func arithmeticGrammar() -> Grammar<LexerToken<String>, TransformingProduction<String, ArithmeticToken>> {
    Rule { /"[ \t]+" }
    Rule { /"[+-]?\\d+(\\.\\d+)?" } tokenTransformer: { .number(Double($0)!) }
    Rule(token: .plus) { "+" }
    Rule(token: .minus) { "-" }
    Rule(token: .comma) { "," }
    Rule(token: .open) { "(" }
    Rule(token: .close) { ")" }
}

let lexer = try DFALexer(grammar: arithmeticGrammar())

Regular expression syntax

Patterns are parsed by the package itself; they are not Swift's Regex and use the usual text-processing syntax:

Syntax	Meaning
|	alternation
(…)	grouping
[…], [^…]	character class, optionally negated
a-z	range inside a character class
*, +, ?	repetition
{n}, {n,}, {,n}, {n,m}	bounded repetition
^, $	start and end anchor
.	any character
\d, \D, \s, \S, \w, \W	digit, whitespace and word character classes
\n, \r, \t, \f, \v	control character escapes
\uXXXX, \xXX	Unicode and hex escapes

To match a string literally, write it as a plain string in the rule body rather than as a regex.

The parser DSL

Parsers are values conforming to Parser, combined with the @ParserBuilder result builder. Inside a @ParserBuilder block, statements run in sequence and their outputs are concatenated; inside a Choice block, alternatives are tried in order and the input is rewound before each attempt.

Combinators

Combinator	Purpose
Parse { … }	Runs the enclosed parsers in sequence
Choice { … }	Tries each alternative until one succeeds
Transform(.kind) { … }	Converts an input token into output tokens
Skip(.kind)	Consumes a token without emitting anything
Repeated(quantifier:) { … }	Repeats a parser, with an optional separator:
if / else in a block	Conditional parsing, via Conditional and Maybe
.map { … }	Maps the output token array of a parser to another array
Reference { … }	A forward reference, for recursive and mutually recursive grammars
End()	Asserts that the input is exhausted
Always() / Fail()	Succeeds or fails without consuming input

Because @ParserBuilder threads a single output token type through the whole block, the common pattern is to convert literals to your own type once with Transform, then work only with that type. Writing the generics explicitly, as in Transform<ArithmeticToken, Expression>(.number), is not required in a standalone parser, but it helps the type solver when the parser is nested inside Repeated or another builder closure.

Recursion with Reference

Reference passes its own value to the closure that fills it, which is how a grammar refers to itself. Because the value is not available until the closure has run, the reference is forward: a non-terminal can only appear where the parser has not yet committed to reducing it. In practice that means the recursion has to be right-recursive.

@TokenType
enum Expression {
    case number(Double)
    case list([Expression])
}

/// element := number | '(' element* ')'
func element() -> Reference<ArithmeticToken, Expression> {
    Reference { rest in
        Choice {
            Transform<ArithmeticToken, Expression>(.number) { token in
                guard case .number(let value) = token else { return [] }
                return [.number(value)]
            }
            Parse {
                Skip<ArithmeticToken, Expression>(.open)
                Repeated(quantifier: .any) { rest }
                Skip<ArithmeticToken, Expression>(.close)
            }
            .map { (elements: [Expression]) -> Expression in .list(elements) }
        }
    }
}

Why the recursion has to go to the right

A left-recursive rule calls itself before it has consumed anything, so the parser has no way to make progress: every attempt to match the non-terminal immediately re-enters it, which immediately re-enters it again, and so on until the stack is exhausted. Nothing is thrown, and no input is rejected — the process simply runs out of stack. This is the classic reason recursive-descent parsers are written right-recursively, and the element rule above is right-recursive because rest only appears after '(' and before ')'.

// A parser that emits plain Int, so Int has to be made a token type first.
extension Int: TokenType {}

// Right-recursive: '1 + 2 + 3' reduces as 1 + (2 + 3). Usable with an LL parser.
func sum() -> Reference<ArithmeticToken, Int> {
    let number = Transform<ArithmeticToken, Int>(.number) { token in
        guard case .number(let value) = token else { return [] }
        return [Int(value)]
    }

    return Reference { term in
        Choice {
            Parse {
                number
                Skip<ArithmeticToken, Int>(.plus)
                term
            }
            .map { [$0[0] + $0[1]] }
            number
        }
    }
}

// Left-recursive: 'term' appears before anything has been consumed.
func leftRecursiveSum() -> Reference<ArithmeticToken, Int> {
    let number = Transform<ArithmeticToken, Int>(.number) { token in
        guard case .number(let value) = token else { return [] }
        return [Int(value)]
    }

    return Reference { term in
        Choice {
            Parse {
                term
                Skip<ArithmeticToken, Int>(.plus)
                number
            }
            .map { [$0[0] + $0[1]] }
            number
        }
    }
}

Note that ArithmeticToken needs a .plus case for this, and the extension Int: TokenType {} above is what lets a bare Int be used as a parser's output type. Wrapping the result in a @TokenType enum instead avoids the retroactive conformance, at the cost of unwrapping the values in map.

So a left-recursive grammar is only usable with one of the LR parsers. They reduce bottom-up, which means sum is never entered until its own sub-expression has already been reduced to a single token, and the recursion terminates naturally. The conformance check reports the difference, and the same grammar passes for one class and fails for the other:

leftRecursiveSum().conforms(to: .ll(k: 1))   // false — would recurse forever
leftRecursiveSum().conforms(to: .lr(k: 1))   // true
sum().conforms(to: .ll(k: 1))               // true
sum().conforms(to: .lr(k: 1))               // true

If you build an LLParser from a left-recursive grammar the attempt fails immediately with ParserError.grammarNotConformsToParserClass(LL(1)) rather than crashing later. Running the combinator parser directly — with parse(_:) on the Reference itself, bypassing a generated parser — is the one case with no such guard, and it dies with a stack overflow rather than a thrown error:

try leftRecursiveSum().parse([.number(1), .plus, .number(2)] as [ArithmeticToken])
// Never returns: SIGSEGV, exit status 139

Running a parser

A Parser can be run three ways:

let parser = element()

// Over any sequence of input tokens; returns all output tokens.
let output = try parser.parse([.open, .number(1), .close] as [ArithmeticToken])
// [list([number(1.0)])]

// Over a lookahead iterator, so it can be chained onto a lexer.
let toks = Array(try arithmeticLexer().tokenize("( 1 ( 2 ) )"))
var iterator = LookaheadIterator(toks)
let streamed = try parser.parse(&iterator)
// [list([number(1.0), list([number(2.0)])])]

// As a `Parser` value inside a larger grammar.
struct MyParser: Parser<ArithmeticToken, Expression> {
    var body: some Parser<ArithmeticToken, Expression> { element() }
}

Errors are thrown as ParseError, which distinguishes failed, expectedEnd, trailingInput, unexpectedToken, infiniteLoop and grammarNotSupported.

Parser classes

LLParser and LRParser are generated from the same grammar, so you can pick the strongest class your grammar supports:

ParserClass	Meaning
.ll(k:)	Left-to-right, deterministic, k tokens of lookahead, no backtracking. Requires k >= 1.
.slr(k:)	Shift-reduce, conflicts resolved with FOLLOW sets.
.lalr(k:)	Shift-reduce with merged item sets.
.lr(k:)	Shift-reduce with full lookahead in the item sets.

Each case carries its own lookahead length, which is available as parserClass.k, and renders in canonical notation as LL(1), SLR(1), LALR(1), LR(1). For k == 0 the three shift-reduce classes describe the same automaton and all normalize to LR(0).

Choosing a class

A parser grammar can be tested against a class before any parser is built, which is the cheapest way to find out whether a given grammar is LL, and with how much lookahead. conforms(to:) is available both on a Parser value and on a Grammar, and returns a plain Bool:

let parser = sum()

parser.conforms(to: .ll(k: 1))          // true
parser.conforms(to: .lr(k: 1))          // true
try parser.grammar().conforms(to: .ll(k: 1))  // same answer, from the grammar

Because a stronger class handles every grammar a weaker one does, the usual approach is to start with .lr(k: 1), fall back to .slr(k: 1) or .lalr(k: 1) if the grammar is too ambiguous for full LR tables, and reach for .ll(k:) only when the grammar is right-recursive and you want a parser without conflict tables. Trying classes in order and reporting the first one that fits is a convenient way to find the strongest class a grammar belongs to.

Building a parser for a class

A ParserClass is passed to the parser's initializer. Building a generated parser directly from a grammar looks like this:

let parser = try LLParser<ArithmeticToken, Int>(grammar: try sum().grammar(), parserClass: .ll(k: 1))
let lrParser = try LRParser<ArithmeticToken, Int>(grammar: try sum().grammar(), parserClass: .lr(k: 1))

LLParser only accepts .ll, and LRParser only accepts the three shift-reduce classes, so handing one the other's class is reported immediately:

try LRParser<ArithmeticToken, Int>(grammar: try sum().grammar(), parserClass: .ll(k: 1))
// ParserError.invalidParserClass(LL(1))

A grammar that simply is not in the requested class fails the same way, at construction time rather than during a parse:

Situation	Result
Grammar is not of the requested class	throws ParserError.grammarNotConformsToParserClass(.ll(k: 1))
Productions cannot be created for the grammar	throws ParserError.grammarNotSupported
Class does not match the parser being built	throws ParserError.invalidParserClass(.ll(k: 1))

Note that .ll(k: 0) is a programmer error rather than a throw: LL parsing cannot choose between alternatives without lookahead, and both conforms(to:) and the initializer guard k >= 1 with a precondition, so passing k: 0 traps instead of throwing.

For the common case of a lexer and a parser in one value, the combined types take the class as their first argument. DFALexerLLParser defaults to .ll(k: 1) and DFALexerLRParser to .lr(k: 1), so passing the class explicitly is only necessary to change it:

// Explicit class:
let combined = try DFALexerLRParser<String, ArithmeticToken, Int>(.lalr(k: 1)) {
    Rule { /"[ \t]+" }
    Rule {
        /"[+-]?\\d+(\\.\\d+)?"
    }
    tokenTransformer: { .number(Double($0)!) }
    Rule(token: .plus) { "+" }
} parser: {
    sum()
}

// Default class, so the argument can be omitted entirely:
let defaulted = try DFALexerLLParser<String, ArithmeticToken, Int> {
    Rule { /"[ \t]+" }
    Rule {
        /"[+-]?\\d+(\\.\\d+)?"
    }
    tokenTransformer: { .number(Double($0)!) }
    Rule(token: .plus) { "+" }
} parser: {
    sum()
}

DFALexerLLParser additionally offers an initializer that takes the lookahead length directly, which is a shorthand for the same thing:

let shorthand = try DFALexerLLParser<String, ArithmeticToken, Int>(k: 2) {
    …
} parser: {
    sum()
}

Note that these classes describe grammars, not languages: the same language may be generated by both an LR(1) and a non-LR(1) grammar, and a grammar with left recursion is not LL even though the language is. Rewriting a left-recursive rule to be right-recursive is usually the cheapest way to make a grammar usable with an LL parser.

Two practical notes on the combined types

The lexer: parameter is a @GrammarBuilder closure, so it takes Rule elements directly. A prebuilt Grammar value cannot be passed there — to reuse a grammar across several parsers, assign it to a let and pass it to DFALexer(grammar:) for the lexer half.

These builders are also expensive for the type solver, and the cost is paid per file. A long chain of Reference, Choice, Parse and .map in the same file as a large lexer closure can exhaust the compiler's budget, and when it does the resulting diagnostic often points at a neighbouring expression rather than the one that is actually too complex. If you hit the compiler is unable to type-check this expression in reasonable time, split the grammar across files, name the intermediate parsers instead of inlining them, and spell out the generic arguments as described in the parser DSL section.

Streaming output

Generated parsers do not build a syntax tree. They return an iterator that emits each output token as soon as its reduction is final, so you can process large or endless inputs incrementally and stop at any time:

var output = parser.parse(source: veryLargeInput)

while let value = output.next() {
    process(value)
    if shouldStop { break }   // the rest of the input is never read
}

if let error = output.error {
    throw error
}

next() returning nil means the parse ended; output.error distinguishes success from failure. Calling collect() instead runs the parse to completion and rethrows:

var output = parser.parse(source: input)
let all = try output.collect()

Async and streaming input

Lexers work over any Sequence of characters, so they can consume a source you control. Wrapping your own iterator in a type that conforms to SourceType gives you a lexer that pulls characters one at a time, which is what you want for sockets and pipes.

For AsyncSequence input there are two dedicated lexers that accept the same grammar. The grammar is written once against String and reused as-is, because AsyncStream<Character> reports String as its LexerSourceType:

let lexer = try AsyncDFALexer<AsyncStream<Character>, ArithmeticToken>(
    grammar: arithmeticGrammar()
)

var tokens = lexer.tokenize(characters)
while let token = try await tokens.next() {
    print(token)
}

AsyncNFALexer and AsyncDFALexer differ only in how the automaton is built: the NFA variant tracks a set of active states per position, the DFA variant determinizes once at construction time and scans with a single active state. Both accept the same grammar, and the DFA variants are the default choice.

Error handling

Error	Thrown by
LexerError	Building a lexer: an invalid pattern, an unterminated group or character class, a reversed range, a missing escape, or a rule that references its own state
ParserError	Building a parser: the grammar is not supported, or does not conform to the requested ParserClass
ParseError	Running a parser: no alternative matched, unexpected token or end of input, trailing input, or an infinite loop in a repetition

Examples

The Examples/ directory contains two runnable programs, each demonstrating a different way to use the package:

• RPNCalculator — a lexer without a parser. The token stream is evaluated directly on a stack, which is the shortest path from text to a working front end.
• SymbolicExpression — a lexer and an SLR(1) parser in one value, with a recursive grammar built from Reference, including string literals with escape sequences.

See Examples/README.md for how to build and run them.

Package layout

Target	Contents
Grammar	Lexers, parsers, the grammar type and the result builders
ParserBuilder	The Parser combinators and the combined lexer/parser types
Lookahead	Iterators supporting peek, mark and reset
ParserMacros	The @TokenType macro
LexerParser	Umbrella module that re-exports Grammar, Lookahead and ParserBuilder

Tests

swift test

License

Licensed under the Apache License, Version 2.0. See the license headers in the source files.