Skip to main content

grammar_lang/
lib.rs

1//! # grammar-lang
2//!
3//! A parser generator that runs at runtime. Describe a language's tokens and
4//! rules with [`Grammar`], call [`build`](Grammar::build), and get a
5//! [`Parser`]: a minimized DFA lexer and an LALR(1) parse table, ready to
6//! parse text into a [`Tree`] or to drive your own [`Actions`].
7//!
8//! There is no code generation step and no build script. The grammar is data,
9//! so it can come from a configuration file, a schematic, or a test, and a
10//! malformed one is reported as a [`GrammarError`] value rather than a
11//! compile failure — which is what the family's language generators build on.
12//!
13//! ## Quick start
14//!
15//! ```
16//! use grammar_lang::Grammar;
17//!
18//! let parser = Grammar::new()
19//!     .literal("+")
20//!     .literal("-")
21//!     .literal("*")
22//!     .literal("/")
23//!     .literal("(")
24//!     .literal(")")
25//!     .pattern("num", r"[0-9]+(\.[0-9]+)?")
26//!     .skip("space", r"\s+")
27//!     .left(&["+", "-"])
28//!     .left(&["*", "/"])
29//!     .rule("expr", &["expr", "+", "expr"])
30//!     .rule("expr", &["expr", "-", "expr"])
31//!     .rule("expr", &["expr", "*", "expr"])
32//!     .rule("expr", &["expr", "/", "expr"])
33//!     .rule("expr", &["(", "expr", ")"])
34//!     .rule("expr", &["num"])
35//!     .build()?;
36//!
37//! let tree = parser.parse("2 * (3 + 4)").unwrap();
38//! assert_eq!(tree.root().name(), "expr");
39//! assert_eq!(tree.root().text(), "2 * (3 + 4)");
40//!
41//! let err = parser.parse("2 * (3 + )").unwrap_err();
42//! assert_eq!(err.to_string(), "expected `(` or `num`, found `)`");
43//! # Ok::<(), grammar_lang::GrammarError>(())
44//! ```
45//!
46//! ## How it works
47//!
48//! [`Grammar::build`] runs two generators.
49//!
50//! - **Lexer.** Every token's pattern is parsed and compiled, by Thompson's
51//!   construction, into one NFA over UTF-8 bytes. Subset construction over
52//!   byte equivalence classes makes it deterministic, and Hopcroft's algorithm
53//!   minimizes it. The result is a flat transition table that finds the
54//!   longest match at a position with one table load per input byte. Tokens
55//!   that match the empty string, or that can never win a match, are
56//!   rejected.
57//! - **Parser.** The rules become an LR(0) automaton, and DeRemer and
58//!   Pennello's relations compute its LALR(1) lookahead sets without building
59//!   LR(1) item sets. Shift/reduce conflicts between operators are resolved by
60//!   the declared precedence and associativity, as in yacc; any other
61//!   conflict is an error that names the competing productions, never a
62//!   silent default.
63//!
64//! [`Parser::parse_with`] then runs the classic shift-reduce loop: one ACTION
65//! lookup per step, tokens fetched from the DFA on demand, skipped tokens
66//! passed over, and [`Actions`] called in postorder. Parsing is linear in the
67//! input and needs stack only for nesting, never for the length of a list.
68//!
69//! ## Family
70//!
71//! Tokens are [`token_lang::Token<Kind>`](Token), and [`Kind`] implements
72//! [`TokenKind`], so lexer output plugs into anything else in the `-lang`
73//! family that consumes tokens. A [`ParseError`] converts into a
74//! [`diag_lang::Diagnostic`] with [`ParseError::to_diagnostic`].
75//!
76//! ## Features
77//!
78//! - `std` (default): forwards to the dependencies' `std` features. Without
79//!   it the crate is `no_std` and needs only `alloc`.
80//!
81//! ## Stability
82//!
83//! Version 1.0 freezes the public API: every item above, and the behaviour
84//! documented for it — how the lexer chooses between matches, how conflicts
85//! are settled, how productions are numbered, what a tree looks like, and
86//! what an error reports. None of it changes in a breaking way before 2.0.
87//! `token-lang` 1 and `diag-lang` 1 are public dependencies. The full promise,
88//! and what it leaves out, is in
89//! [`docs/API.md`](https://github.com/jamesgober/grammar-lang/blob/main/docs/API.md#stability).
90
91#![cfg_attr(not(feature = "std"), no_std)]
92#![cfg_attr(docsrs, feature(doc_cfg))]
93#![forbid(unsafe_code)]
94#![deny(
95    warnings,
96    missing_docs,
97    unsafe_op_in_unsafe_fn,
98    unused_must_use,
99    unused_results,
100    clippy::unwrap_used,
101    clippy::expect_used,
102    clippy::panic,
103    clippy::todo,
104    clippy::unimplemented,
105    clippy::unreachable,
106    clippy::dbg_macro,
107    clippy::print_stdout,
108    clippy::print_stderr,
109    clippy::undocumented_unsafe_blocks
110)]
111
112extern crate alloc;
113
114mod error;
115mod grammar;
116mod kind;
117mod lex;
118mod lr;
119mod parser;
120mod tree;
121mod util;
122
123pub use error::{GrammarError, ParseError};
124pub use grammar::Grammar;
125pub use kind::Kind;
126pub use parser::{Actions, Parser, Production, Tokens};
127pub use tree::{Node, Tree};
128
129#[doc(no_inline)]
130pub use token_lang::{Span, Token, TokenKind};
131
132/// Compiles and runs the `rust` code blocks in `README.md` and `docs/API.md` as
133/// part of `cargo test`, so the published examples cannot drift from the API.
134///
135/// Present only while collecting doctests (`#[cfg(doctest)]`); it is not part of
136/// the public surface and does not appear in the built library or its docs.
137#[cfg(doctest)]
138#[doc = include_str!("../README.md")]
139#[doc = include_str!("../docs/API.md")]
140pub struct MarkdownDocTests;