lang-forge 1.0.0

The model

Four types and one alias, one per job:

• A Language is a forged language: a lexer, a parser, and the kinds of its tree. It is immutable, Send and Sync, and parses as often as you like.
• A Parse is one result: the lossless tree, the source, and the diagnostics. Parsing never fails.
• A Kind names a token or node in the tree. It is a small Copy value that compares like an enum.
• An Error lists everything wrong with a schematic, each problem pointing into the schematic text.
• A Capability is a boxed pass-lang pass that a schematic can include by name.

What the crate guarantees:

Installation

[dependencies]
lang-forge = "1"

Or from the terminal:

cargo add lang-forge

syntax-lang, diag-lang, and pass-lang are re-exported as lang_forge::syntax_lang, lang_forge::diag_lang, and lang_forge::pass_lang, so you need not depend on them yourself. MSRV: Rust 1.85 (Rust 2024 edition).

Quick start

A calculator, from schematic to evaluated tree:

use lang_forge::Language;

let calc = Language::from_lsf(r##"
    [language]
    name = "calc"

    [lexer]
    line_comments = ["#"]

    [rules]
    program = "stmt*"
    stmt    = "'let' IDENT '=' expr ';' | expr ';'"
    group   = "'(' expr ')'"

    [rules.expr]
    operand = "NUMBER | IDENT | group"
    levels  = [
        { left   = ["+", "-"] },
        { left   = ["*", "/"] },
        { prefix = ["-"] },
        { right  = ["^"] },
    ]
"##)?;

let parse = calc.parse("let r = 2;\nlet area = 3 * r ^ 2;  # precedence decides\n");
assert!(!parse.has_errors());

// `^` binds tighter than `*`: the product's right operand is `r ^ 2`.
let binary = calc.kind("binary").expect("the default operator node");
let product = parse.tree().descendants().find(|n| *n.kind() == binary).expect("3 * r ^ 2");
assert_eq!(product.text(parse.source()), Some("3 * r ^ 2"));
# Ok::<(), lang_forge::Error>(())

parse.dump() shows the tree, one node or token per line:

program@0..55
  stmt@0..10
    let@0..3 "let"
    WHITESPACE@3..4 " "
    IDENT@4..5 "r"
    ...

Mistakes in source text

Every problem becomes a diagnostic, and the tree is complete regardless — so an editor can still highlight and navigate a half-typed file:

use lang_forge::Language;
use lang_forge::diag_lang::{Renderer, SourceMap};

let lang = Language::from_lsf(
    "[language]\nname = \"calls\"\n[rules]\nfile = \"call*\"\ncall = \"IDENT '(' (IDENT (',' IDENT)*)? ')' ';'\"\n",
)?;
let source = "open(file);\nread(file, buffer;\nclose(file);\n";
let parse = lang.parse(source);
assert_eq!(parse.diagnostics().len(), 1);
assert_eq!(parse.tree().text(source), Some(source));

let mut map = SourceMap::new();
map.add("main.calls", source).expect("fits");
let report = Renderer::new().render(&parse.diagnostics()[0], &map);
assert!(report.contains("error: expected `)`, found `;`"));
assert!(report.contains("main.calls:2:18"));
# Ok::<(), lang_forge::Error>(())

error: expected `)`, found `;`
 --> main.calls:2:18
  |
2 | read(file, buffer;
  |                  ^

Mistakes in the schematic

Forging reports everything wrong at once, each problem pointing into the schematic, many with the fix:

use lang_forge::Language;

let err = Language::from_lsf(r#"
[language]
name = "broken"

[rules]
program = "statment*"
statement = "expr ';'"
expr = "expr '+' NUMBER | NUMBER"
"#).unwrap_err();

let messages: Vec<&str> = err.diagnostics().iter().map(|d| d.message()).collect();
assert_eq!(messages, [
    "undefined rule `statment`",
    "rule `expr` is left-recursive: expr → expr",
]);
let help: Vec<&str> = err.diagnostics()[0].help().collect();
assert_eq!(help, ["did you mean `statement`?"]);

A schematic, table by table

A schematic is a NOML document — the TOML-compatible core of it — with up to four tables. Everything except [language] name and [rules] is optional.

[language]
name       = "mini"            # required
version    = "0.1.0"
extensions = ["mini"]          # without the dot
start      = "program"         # the root rule; default: the first rule

[lexer]
identifiers     = "xid"        # Unicode identifiers (UAX #31); or "ascii"
newlines        = false        # true: line breaks are NEWLINE tokens
line_comments   = ["//"]
block_comments  = [["/*", "*/"]]
nested_comments = true
strings         = ['"', { open = "#\"", close = "\"#", escape = "", multiline = true }]

[rules]
program  = "_item*"            # `_` hides a rule: its children join the parent
_item    = "function | stmt"
function = "'fn' IDENT params block"
params   = "'(' (IDENT (',' IDENT)*)? ')'"
block    = "'{' stmt* '}'"
stmt     = "'let' IDENT '=' expr ';' | 'return' expr? ';' | expr ';'"
args     = "expr (',' expr)*"
group    = "'(' expr ')'"

[rules.expr]                   # an expression rule: operand and operator levels
operand = "NUMBER | STRING | IDENT | group"
levels  = [                    # lowest precedence first
    { right   = ["="],                 node = "assign" },
    { left    = ["||"] },
    { left    = ["&&"] },
    { none    = ["==", "!=", "<", ">"], node = "compare" },
    { left    = ["+", "-"] },
    { left    = ["*", "/", "%"] },
    { prefix  = ["-", "!"],            node = "unary" },
    { postfix = ["("], then = "args? ')'", node = "call" },
]

[capabilities]
include = ["unused-variables"] # passes, run in this order

Rules are sequences of elements: quoted literals ('let', '+=' — keywords and symbols, collected from the grammar into the lexer automatically), the token classes IDENT, NUMBER, STRING, and NEWLINE, rule names, grouping with ( ), | for alternatives tried in order, and *, +, ?. Each rule builds a node named after itself.

Expression rules handle operators without left recursion: list the levels from loosest to tightest, each left, right, or none (binary), prefix, or postfix. A then adds grammar after the operator — calls, indexing, ? :. Operator nodes are named binary, prefix, and postfix unless a level sets node.

The lexer is derived, not written: every literal in the grammar becomes a keyword (if it reads like an identifier) or a symbol, matched longest first. Numbers (42, 1_000, 3.25e-4, 0xFF, 0o17, 0b1010), identifiers, whitespace, and the comments and strings [lexer] declares are built in.

The full reference — every key, type, default, and the semantics of parsing and recovery — is in docs/API.md.

Capabilities

LexerSketch never bakes a language feature in. A schematic names the capabilities it includes; the language assembles them, in order, from whatever registry of passes you provide, and refuses if one is missing:

use lang_forge::diag_lang::{Diagnostic, Label, Severity};
use lang_forge::pass_lang::{Outcome, Pass, PassError};
use lang_forge::{Capability, Language, Parse};

/// Warns about empty blocks.
struct EmptyBlocks;

impl<'a> Pass<Parse<'a>> for EmptyBlocks {
    fn name(&self) -> &'static str {
        "empty-blocks"
    }

    fn run(&mut self, parse: &mut Parse<'a>) -> Result<Outcome, PassError> {
        let block = parse.language().kind("block").ok_or_else(|| PassError::new("no blocks"))?;
        let empty: Vec<_> = parse
            .tree()
            .descendants()
            .filter(|n| *n.kind() == block && n.child_nodes().next().is_none())
            .map(|n| n.span())
            .collect();
        for span in empty {
            parse.report(Diagnostic::new(Severity::Warning, "empty block", Label::unlabelled(span)));
        }
        Ok(Outcome::Unchanged)
    }
}

let lang = Language::from_lsf(
    "[language]\nname = \"blocks\"\n[rules]\nfile = \"block*\"\nblock = \"'{' IDENT* '}'\"\n\
     [capabilities]\ninclude = [\"empty-blocks\"]\n",
)?;

let registry: Vec<Capability> = vec![Box::new(EmptyBlocks)];
let mut pipeline = lang.pipeline(registry)?;

let mut parse = lang.parse("{ a b } { }");
pipeline.run(&mut parse).expect("the pass runs");
assert_eq!(parse.diagnostics()[0].message(), "empty block");
assert!(!parse.has_errors()); // a warning, not an error
# Ok::<(), lang_forge::Error>(())

Examples

Five runnable examples ship in examples/, with four schematics in examples/schematics/: calc.lsf, json.lsf, mini.lsf (functions, control flow, eight precedence levels), and conf.lsf (an INI-style format where line breaks matter).

• Calc — forges calc.lsf, parses a program, and evaluates it by walking the tree: the smallest complete interpreter.

  cargo run --example calc
  

• Check — a command-line checker for any forged language: forge a schematic, parse a file, render every problem with source context, and optionally print the tree.

  cargo run --example check                                  # a built-in sample with two mistakes
  cargo run --example check -- --tree schematic.lsf file.src
  

• JSON — a JSON validator from json.lsf, accepting good documents and showing the first error in bad ones.

  cargo run --example json
  

• Capabilities — mini.lsf includes unused-variables; this example registers that pass (and one the language does not ask for), assembles the pipeline, and reports an unused binding.

  cargo run --example capabilities
  

• Highlight — syntax highlighting from Language::lex alone: every token, trivia included, painted by kind.

  cargo run --example highlight
  

Performance

Forging does the analysis once — every rule resolved, every set computed — so parsing consults precomputed tables instead of the grammar. The lexer dispatches on a 256-entry byte-class table, runs tight ASCII loops for identifiers, numbers, and whitespace, matches keywords through an open-addressing hash table and symbols longest-first from a short per-byte list, and only decodes UTF-8 on non-ASCII bytes. The parser tests FIRST sets as bitsets before trying anything, so it commits to the one viable alternative in almost every decision and speculates only where the grammar is genuinely ambiguous at one token; speculative attempts are memoized by rule and position, so alternatives that share a prefix never parse it twice and parsing stays linear. It records a flat list of events instead of building the tree as it goes, which makes speculation a truncation and operator nodes a forward link rather than an insertion. Error paths are kept cold and out of line, so the hot recursive functions stay small.

Measured with the benchmarks in benches/, x86_64, Rust stable, release profile. The parse figures cover lexing, parsing, building the tree, and dropping it:

On large inputs the cost is dominated by the tree itself: on Linux, for the 1 MB mini file, lexing takes about 2 ms and the parser about 3 ms, while allocating the tree's nodes takes about 6 ms and freeing them 13 ms. Run them yourself:

cargo bench --bench bench

Criterion writes per-benchmark reports to target/criterion/. Numbers vary by CPU and allocator; use the trend across runs, not a single absolute.

Design notes

• Interpreted, not generated. A forged language is tables plus a small interpreter, not Rust source to compile. Changing a schematic takes microseconds, a tool can forge languages at run time, and every language shares one well-tested parser.
• Ordered choice, pruned by FIRST sets. Alternatives are tried in order and the first that matches wins, as in a parsing expression grammar, which is forgiving to write. FIRST sets prune the attempt before it starts, so for nearly every decision exactly one alternative remains and the parser commits at once. Alternatives that begin alike are left-factored when the language is forged, which removes most of the remaining ambiguity — and reveals alternatives that could never match.
• Recovery that respects structure. A missing token is assumed; an unwanted token is skipped into an ERROR node; and skipping stops at any token an enclosing construct is waiting for, so one mistake does not swallow the rest of a block. The parser reports at most one syntax error per token.
• Errors, not panics. Schematic problems are values with spans; source problems are diagnostics. Every recursive step of the parser counts against a fixed limit, so input nested beyond it is reported instead of followed and no input can exhaust the stack.
• The schematic is static. NOML's dynamic features — environment lookups, includes, native types — are refused, so a schematic forges the same language on every machine.

Testing

The suite runs on Windows, Linux (WSL2 Ubuntu), and macOS through the CI matrix, on stable and the 1.85 MSRV:

cargo test                       # unit + integration + property + doctests
cargo clippy --all-targets --all-features -- -D warnings
cargo bench --bench bench

The property tests in tests/proptests.rs generate random valid mini programs, which must parse without a single diagnostic; random token soup and arbitrary Unicode text, which must parse into lossless, properly nested trees in every example language; and arbitrary and randomly mutated schematics, which must forge or fail cleanly. Further properties, in the parser's unit tests, hold the recovering parser to a strict reference parser on every input it accepts without error, and require memoization never to change a tree or a diagnostic. tests/regressions.rs keeps every input an adversarial review used against the crate — stack-exhausting grammars, exponential and quadratic speculation, recursion without progress — and holds them to time and stack bounds. 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 schematic forges the same language, and a source parses into the same tree, on every platform.

Contributing

See REPS.md for the engineering standards every change is held to, and dev/ROADMAP.md for what may come in 1.x. Before a PR: cargo fmt --all, cargo clippy --all-targets --all-features -- -D warnings, and cargo test --all-features must be clean.