regast

regast is a regular-expression analysis engine for Rust. It exposes a lossless pattern AST and a complete parse tree for each match, including groups, alternation choices, and repetition boundaries.

Features

• Whole-input parsing and leftmost-longest substring search
• Lossless pattern AST with JSON, S-expression, and Graphviz DOT output
• Match parse trees with UTF-8 byte spans and capture-compatible views
• POSIX and greedy/lazy disambiguation
• Brzozowski derivative, Antimirov partial-derivative, and tagged Thompson NFA backends
• Unicode scalar-value literals, dot, character classes, and Perl character classes
• Capturing, named, and non-capturing groups
• Optional, Kleene, plus, and counted repetitions
• Start (^) and end ($) anchors
• Configurable matching-state limits

Backreferences and lookaround are intentionally unsupported because they are outside the regular language model used by the engine.

Requirements

• Rust 1.85 or later
• Rust 2024 edition

Installation

Until the crates are published on crates.io, add the library from the Git repository:

[dependencies]
regast = { git = "https://github.com/ydah/regast" }

Install the command-line application directly from the repository:

cargo install --git https://github.com/ydah/regast regast-cli

Library usage

use regast::{Backend, Regast, Span};

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let regex = Regast::builder("(a|b)*c")
        .backend(Backend::TaggedNfa)
        .build()?;

    let tree = regex.parse("abac")?;
    assert_eq!(tree.flatten(), "abac");
    assert_eq!(tree.match_span(), Span::new(0, 4));
    assert_eq!(tree.group_all(1).len(), 3);

    let found = regex.find_parse("zzabac")?.expect("a match");
    assert_eq!(found.flatten(), "abac");
    assert_eq!(found.match_span(), Span::new(2, 6));

    Ok(())
}

parse requires the complete input to match. find_parse returns the leftmost-longest match and reports spans relative to the original input.

Matching backends

Select a backend with Regast::builder(...).backend(...):

All backends preserve the same public parse-tree and disambiguation semantics. Antimirov and tagged-NFA parsing reconstruct typed values through a bounded IR chart without falling back to Brzozowski derivatives.

Command-line usage

regast ast '(a|b)*c' --format json --shape tree
regast parse '(a|b)*c' abac --format sexpr --posix
regast find '^a|ab+$' zabbb --backend antimirov
regast parse '^([ab]+)$' abba --backend tagged-nfa
regast check 'a+' aaa
regast trace 'a+b' aaab

Run regast --help or regast <command> --help for the complete option reference.

Workspace

Development

cargo test --workspace
cargo test --workspace --release
cargo clippy --workspace --all-targets --all-features -- -D warnings
cargo fmt --all -- --check

License

Licensed under either the Apache License, Version 2.0 or the MIT License, at your option.