Expand description
§grammar-lang
A parser generator that runs at runtime. Describe a language’s tokens and
rules with Grammar, call build, and get a
Parser: a minimized DFA lexer and an LALR(1) parse table, ready to
parse text into a Tree or to drive your own Actions.
There is no code generation step and no build script. The grammar is data,
so it can come from a configuration file, a schematic, or a test, and a
malformed one is reported as a GrammarError value rather than a
compile failure — which is what the family’s language generators build on.
§Quick start
use grammar_lang::Grammar;
let parser = Grammar::new()
.literal("+")
.literal("-")
.literal("*")
.literal("/")
.literal("(")
.literal(")")
.pattern("num", r"[0-9]+(\.[0-9]+)?")
.skip("space", r"\s+")
.left(&["+", "-"])
.left(&["*", "/"])
.rule("expr", &["expr", "+", "expr"])
.rule("expr", &["expr", "-", "expr"])
.rule("expr", &["expr", "*", "expr"])
.rule("expr", &["expr", "/", "expr"])
.rule("expr", &["(", "expr", ")"])
.rule("expr", &["num"])
.build()?;
let tree = parser.parse("2 * (3 + 4)").unwrap();
assert_eq!(tree.root().name(), "expr");
assert_eq!(tree.root().text(), "2 * (3 + 4)");
let err = parser.parse("2 * (3 + )").unwrap_err();
assert_eq!(err.to_string(), "expected `(` or `num`, found `)`");§How it works
Grammar::build runs two generators.
- Lexer. Every token’s pattern is parsed and compiled, by Thompson’s construction, into one NFA over UTF-8 bytes. Subset construction over byte equivalence classes makes it deterministic, and Hopcroft’s algorithm minimizes it. The result is a flat transition table that finds the longest match at a position with one table load per input byte. Tokens that match the empty string, or that can never win a match, are rejected.
- Parser. The rules become an LR(0) automaton, and DeRemer and Pennello’s relations compute its LALR(1) lookahead sets without building LR(1) item sets. Shift/reduce conflicts between operators are resolved by the declared precedence and associativity, as in yacc; any other conflict is an error that names the competing productions, never a silent default.
Parser::parse_with then runs the classic shift-reduce loop: one ACTION
lookup per step, tokens fetched from the DFA on demand, skipped tokens
passed over, and Actions called in postorder. Parsing is linear in the
input and needs stack only for nesting, never for the length of a list.
§Family
Tokens are token_lang::Token<Kind>, and Kind implements
TokenKind, so lexer output plugs into anything else in the -lang
family that consumes tokens. A ParseError converts into a
diag_lang::Diagnostic with ParseError::to_diagnostic.
§Features
std(default): forwards to the dependencies’stdfeatures. Without it the crate isno_stdand needs onlyalloc.
§Stability
Version 1.0 freezes the public API: every item above, and the behaviour
documented for it — how the lexer chooses between matches, how conflicts
are settled, how productions are numbered, what a tree looks like, and
what an error reports. None of it changes in a breaking way before 2.0.
token-lang 1 and diag-lang 1 are public dependencies. The full promise,
and what it leaves out, is in
docs/API.md.
Re-exports§
Structs§
- Grammar
- A grammar: the tokens of a language and the rules that arrange them.
- Kind
- What a token or a tree node is: one of the grammar’s tokens or rules.
- Node
- A node of a
Tree: a rule match or a token. - Parse
Error - Why
Parser::parserejected its input. - Parser
- A parser generated from a
Grammar. - Production
- A production of the grammar, as reported to
Actions::reduce. - Tokens
- The tokens of a text, from
Parser::tokens. - Tree
- A concrete syntax tree: a node for every production a parse used and a leaf for every token it consumed.
Enums§
- Grammar
Error - Why
Grammar::buildrejected a grammar.
Traits§
- Actions
- Semantic actions: what to build as the parser recognizes the input.