🐯 tygr: TYpes into Grammar Routines

Define your grammar once as Rust types and get parser, printer, and presentation in EBNF for free.

Example

Given this EBNF:

Expr  = Expr1 { Op1 Expr1 } ;
Op1   = "+" | "-" ;
Expr1 = Expr2 { Op2 Expr2 } ;
Op2   = "*" | "/" ;
Expr2 = "(" Expr ")" | Int ;
Int   = 'digit' { 'digit' } ;

Write it once in Rust:

use tygr::*;

#[derive(Grammar, Debug, PartialEq, Eq)]
pub struct Expr(pub Expr1, pub Vec<(Wrap<Ws, Op1, Ws>, Expr1)>);

#[derive(Grammar, Debug, PartialEq, Eq)]
pub enum Op1 {
    Add(StringEq!("+")),
    Sub(StringEq!("-")),
}

#[derive(Grammar, Debug, PartialEq, Eq)]
pub struct Expr1(pub Expr2, pub Vec<(Wrap<Ws, Op2, Ws>, Expr2)>);

#[derive(Grammar, Debug, PartialEq, Eq)]
pub enum Op2 {
    Mul(StringEq!("*")),
    Div(StringEq!("/")),
}

#[derive(Grammar, Debug, PartialEq, Eq)]
pub enum Expr2 {
    Paren(Wrap<(StringEq!("("), Ws), Box<Expr>, (Ws, StringEq!(")"))>),
    Number(Int),
}

char_class!(pub IsDigit, "digit", |ch| ch.is_ascii_digit());

#[derive(Grammar, Debug, PartialEq, Eq)]
pub struct Int(pub StringOf1<IsDigit>); // StringOf1: one or more digits

char_class!(pub IsSpace, "space", |ch| ch.is_ascii_whitespace());

#[derive(Grammar, Debug, PartialEq, Eq)]
#[grammar(hidden)] // parsed & printed, but omitted from the BNF
pub struct Ws(pub StringOf<IsSpace>); // StringOf: zero or more spaces

Get parser, printer, and EBNF generator:

let e = Expr::parse("1 + 2 * 3").unwrap();  // parse
assert_eq!(e.print(), "1 + 2 * 3");         // round-trip print
assert_eq!(bnf_rules![Expr, Op1, Expr1, Op2, Expr2, Int].to_string(),
            "\
Expr = Expr1 { Op1 Expr1 } ;
Op1 = \"+\" | \"-\" ;
Expr1 = Expr2 { Op2 Expr2 } ;
Op2 = \"*\" | \"/\" ;
Expr2 = \"(\" Expr \")\" | Int ;
Int = 'digit' { 'digit' } ;"
        );

More examples

• arith — the grammar above, as a runnable example.
• json — a full JSON grammar.
• json_optimized — the same JSON grammar, hand-tuned for parsing throughput.

Each is a small CLI:

cargo run --example json -- bnf              # print the grammar as EBNF
echo '{"a": [1, true]}' | cargo run --example json -- parse   # parse, print the AST
echo '{"a": 1}'         | cargo run --example json -- test    # check well-formed (exit 0/1)

The optimized JSON grammar is also benchmarked (cargo bench) against the inputs in data/.

How it works

See also

Deriving many routines from one spec. Writing a grammar once and deriving several routines from it is an old idea: BNFC, for example, turns a single labelled-BNF file into a parser, a pretty-printer, and a LaTeX document of the grammar. tygr follows this spirit — one Rust type yields a parser, a printer, and an EBNF presentation.

Deriving parsers from grammars. There are far too many parser libraries to list; a few available to the Rust ecosystem, grouped by how the grammar is written:

Writing the grammar as types is what tygr trades on. A DSL lives outside the language, so it misses the tooling — go-to-definition, refactoring, type checking — and composes poorly with the rest of Rust (traits, generics, #[derive], functions). Expression-based combinators keep all of that, but you write the parsing expressions and the types you want the result in — two descriptions of the same structure to keep in sync. With tygr the type is the grammar, so there is nothing to keep in sync.

PEG and parser combinators. tygr reads a grammar as a recursive-descent parser with backtracking, the reading refined by Parsing Expression Grammars (PEG) and parser combinators (Parsec).

Contributing

Please open an issue before starting a pull request. See CONTRIBUTING.md for the development workflow.

License

This software is provided AS-IS, with no implied warranties, support, or conditions of any kind.

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

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in this work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.