The model
A handful of types, one per job:
- A
Grammardescribes the language: tokens (literals, regular-expression patterns, and skipped trivia such as whitespace and comments), rules written one production at a time, and precedence levels.buildchecks it and generates the parser. - A
Parseris the generated lexer and parse table. It parses text into aTree, runs yourActionsinstead, or just splits text into tokens. It is immutable and shareable across threads. - A
Kindnames a token or rule; tokens aretoken_lang::Token<Kind>. - A
GrammarErrorsays why a grammar was refused; aParseErrorsays where input went wrong and lists exactly what would have been accepted, and converts into adiag_lang::Diagnostic.
What it guarantees, and how each guarantee is checked:
| Guarantee | How it is held |
|---|---|
| A grammar builds exactly when it is LALR(1) once precedence is applied. | Property tests compare the generator with a canonical LR(1) construction merged by core, the textbook definition of LALR(1), over thousands of random grammars. |
| Precedence and associativity mean what they mean in Bison. | Random grammars with random precedence levels and %prec overrides are run through both this crate and GNU Bison 3.8.2: the conflict verdicts, the accepted inputs, and the exact sequence of reductions agree. |
| The parser accepts exactly the grammar's language. | Every short input of each random grammar is checked against an Earley recognizer, and every tree against the grammar's productions. |
| Errors point at the first bad token and list exactly what could follow. | The same property tests check the error position and the expected set against the Earley recognizer's viable prefixes. |
| Token patterns match what they say. | Random regular expressions, Unicode included, are checked against a reference matcher. |
| Parsing always terminates, on any input. | Grammars that can derive a rule from itself alone are refused at build time, and property tests run arbitrary text through a parser and check that it never panics. |
| Lexing is linear in the input, even on hostile text. | Tests lex a megabyte of unclosed comment openers and count the DFA transitions, and a property test checks every token stream against a brute-force longest match. |
Installation
[]
= "1"
Without the standard library:
[]
= { = "1", = false }
Quick start
An arithmetic grammar, with the operator precedence declared rather than encoded in the rules:
use Grammar;
let parser = new
.literal
.literal
.literal
.literal
.literal
.literal
.pattern
.skip
.left
.left
.rule
.rule
.rule
.rule
.rule
.rule
.build?;
let tree = parser.parse.unwrap;
assert_eq!;
let err = parser.parse.unwrap_err;
assert_eq!;
# Ok::
Semantic actions
parse_with hands each token and each completed production to your Actions, children before parents, so the result can be anything — here, the value itself:
use ;
use Drain;
;
let parser = new
.literal
.literal
.literal
.literal
.pattern
.left
.left
.rule
.rule
.rule
.rule
.build?;
assert_eq!;
# Ok::
Mistakes caught at build time
Every problem is a value that names the grammar's own symbols:
use ;
// Ambiguous: does `1 - 2 - 3` group to the left or the right?
let err = new
.literal
.pattern
.rule
.rule
.build
.unwrap_err;
assert_eq!;
// A keyword declared after a pattern that matches it still wins: literals
// outrank patterns. Two patterns are a different story.
let err = new
.pattern
.pattern
.rule
.build
.unwrap_err;
assert_eq!;
Diagnostics
A ParseError becomes a diag_lang::Diagnostic, which the family's renderer prints against the source:
use ;
use Grammar;
let parser = new
.literal
.pattern
.pattern
.skip
.rule
.rule
.rule
.build?;
let source = "port = 80\nhost = x\n";
let err = parser.parse.unwrap_err;
let mut map = new;
map.add.unwrap;
let report = new.render;
assert!;
assert!;
# Ok::
Examples
Runnable programs in examples/:
| Example | What it shows |
|---|---|
calculator |
Evaluating while parsing: precedence, right associativity, unary minus with prec. cargo run --example calculator -- "2 ^ 3 ^ 2" |
json |
A complete RFC 8259 JSON parser that builds a typed value, borrowing string contents from the input. |
ast |
Building a typed AST straight into an ast-lang arena, then walking it with an ast-lang visitor. |
diagnostics |
Rendering parse errors with diag-lang for a small configuration language. |
highlight |
A highlighter from the token stream alone, carrying on past characters no token matches. |
Performance
Parsing is a single pass. The lexer finds each token by longest match in a minimized DFA laid out as one flat table: bytes map to equivalence classes, row offsets are pre-multiplied, and each transition carries flags for "a token ends here" and "nothing can follow", so the inner loop is one load and one test per byte and single-character tokens stop at once. The parser fetches tokens on demand and takes one table load per shift or reduce. Building a tree is a push per node into flat arrays, and actions that build nothing cost nothing. Work on the error path — replaying to find the exact expected tokens — is never paid by a successful parse.
Measured with the benchmarks in benches/, x86_64, Rust stable, release profile:
| Benchmark | What it measures | Windows | Linux (WSL2) |
|---|---|---|---|
build/expression |
Generate the parser for a 7-production expression grammar. | ~21 µs | ~9 µs |
build/json |
Generate the JSON parser (12 tokens, 16 productions). | ~76 µs | ~57 µs |
build/c_like |
Generate a C-like language: 51 tokens, 78 productions, a 10-level expression grammar (161 states). | ~0.43 ms | ~0.33 ms |
json_1mib/tokens |
Lex 1 MiB of JSON, whitespace included. | ~690 MiB/s | ~895 MiB/s |
json_1mib/parse_with_noop |
Lex and parse 1 MiB of JSON with actions that build nothing. | ~250 MiB/s | ~300 MiB/s |
json_1mib/parse_tree |
Lex, parse, and build the full concrete syntax tree. | ~114 MiB/s | ~216 MiB/s |
expression/evaluate |
Evaluate a 324 KB arithmetic expression in actions. | ~132 MiB/s | ~156 MiB/s |
Generating even the C-like grammar's parser takes a third of a millisecond, so building grammars at startup — or from data at runtime — costs next to nothing. Tree building is the most allocation-heavy path, which is where the platforms differ most.
Criterion writes per-benchmark reports to target/criterion/. Numbers vary by CPU; use the trend across runs, not a single absolute.
Design notes
- Bison's semantics, stricter defaults. A production takes the precedence of its last token unless
precnames another; precedence settles shift/reduce conflicts before reduce/reduce conflicts are judged; and states that only a disabled shift could reach are dropped, conflicts and all. That is exactly what Bison does, which the differential tests confirm. Where Bison then picks a default — shift, or the earlier rule — this crate refuses the grammar and says why. - Exact errors from an LALR table. LALR(1) merges lookaheads, so its tables can report tokens that could never follow, and may reduce before noticing an error. On an error, the parser replays the input to the stack it had when the bad token arrived and asks, token by token, whether each would be shifted. The expected set is then exact, and the cost falls only on input that fails.
- Termination is a build-time property. A rule that can derive itself alone makes some input infinitely ambiguous; with a precedence hiding the conflict, a table-driven parser would reduce around the cycle forever. Such grammars are refused, so every parse ends.
- Tokens are bytes, characters are Unicode. Patterns are compiled to UTF-8 byte automata, so
[α-ω]and.match whole characters while the scanner never decodes. Every match ends on a character boundary. - Longest match without rescanning. A longest-match scan can read far past the token it returns: an unclosed
/*makes the comment pattern scan to the end of the input before the lexer falls back to/. Started again at every/, that is quadratic. The lexer remembers each DFA state and position a scan passed through after its last match, since no token can be found from there, and a later scan that reaches one stops at once. Each pair is remembered at most once, so the whole pass stays linear, and ordinary input never touches the memo. - No recursion anywhere input reaches. Pattern nesting is bounded, the digraph traversal behind the lookahead sets is iterative, and tree building, display, walking, and dropping are flat. A 100,000-deep nesting parses, prints, and drops without touching the stack limit.
Testing
The suite runs on Windows, Linux (WSL2 Ubuntu), and macOS through the CI matrix, on stable and the 1.85 MSRV:
The property tests in tests/properties.rs hold the generator to independent references written in the test: a canonical LR(1) construction merged by core decides which random grammars are LALR(1); an Earley recognizer decides which inputs each accepts, where the first error must be, and which tokens could follow it; a direct interpreter decides what each random pattern matches. Further properties run the parser on arbitrary text and check that the token stream tiles the input exactly and matches a brute-force longest match. Every rust example in this README and in docs/API.md is compiled and run as a doctest.
Cross-platform support
- Linux (x86_64, aarch64)
- macOS (x86_64, Apple Silicon)
- Windows (x86_64)
The crate uses no operating-system facilities and no platform-specific code; a grammar builds the same tables, and parses the same way, on every platform.
Contributing
See REPS.md for the engineering standards every change is held to, and dev/ROADMAP.md for the roadmap and the additive work planned for 1.x. Before a PR: cargo fmt --all, cargo clippy --all-targets --all-features -- -D warnings, and cargo test --all-features must be clean.