Skip to main content

Crate grammar_lang

Crate grammar_lang 

Source
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’ std features. Without it the crate is no_std and needs only alloc.

§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§

pub use token_lang::Span;
pub use token_lang::Token;
pub use token_lang::TokenKind;

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.
ParseError
Why Parser::parse rejected 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§

GrammarError
Why Grammar::build rejected a grammar.

Traits§

Actions
Semantic actions: what to build as the parser recognizes the input.