metrale_grammar/grammar/
parser.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2//
3// EBNFParser — parses BNF/EBNF grammar text into a `GrammarData`.
4// Port of `EBNFParser` + `ParseEBNF` from xgrammar `cpp/grammar_parser.cc`.
5//
6// The parser accepts W3C-style EBNF with xgrammar's extensions:
7//   - `#` line comments instead of C-style comments
8//   - C-style unicode escapes `ƫ`, `\U000001AB`, `\xAB`
9//
10// This file holds the error type, parser state, the core peek/consume
11// helpers, sequence/choices/rule parsing and the public entry point.
12// Element parsing is in `parser_element.rs`, quantifier/repetition
13// expansion in `parser_quant.rs`, macro/tag-dispatch parsing in
14// `parser_macro.rs` — split to keep each file under the 250-line cap.
15
16use super::builder::{BuilderError, GrammarBuilder};
17use super::data::GrammarData;
18use super::lexer::{EbnfLexer, LexError, Token, TokenType, TokenValue};
19
20#[path = "parser_element.rs"]
21mod element;
22#[path = "parser_macro.rs"]
23mod macros;
24#[path = "parser_quant.rs"]
25mod quant;
26#[path = "parser_repeat.rs"]
27mod repeat;
28#[path = "parser_tagdispatch.rs"]
29mod tagdispatch;
30#[cfg(test)]
31#[path = "parser_tests.rs"]
32mod tests;
33
34/// Maximum nesting depth of parenthesised groups.
35pub(super) const MAX_NEST_LAYER: i32 = 1000;
36
37/// An EBNF parse error.
38#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
39pub enum ParseError {
40    /// Lexer-stage error.
41    #[error(transparent)]
42    Lex(#[from] LexError),
43    /// Parser-stage error with source position.
44    #[error("EBNF parser error at line {line}, column {column}: {msg}")]
45    Parse {
46        /// 1-based source line.
47        line: i32,
48        /// 1-based source column.
49        column: i32,
50        /// Human-readable error message.
51        msg: String,
52    },
53    /// An error surfaced from the underlying [`GrammarBuilder`].
54    #[error(transparent)]
55    Builder(#[from] BuilderError),
56}
57
58/// The EBNF parser. Equivalent to xgrammar's `EBNFParser`.
59pub(super) struct EbnfParser {
60    pub(super) builder: GrammarBuilder,
61    pub(super) tokens: Vec<Token>,
62    /// Index of the current token in `tokens`.
63    pub(super) cur: usize,
64    pub(super) cur_rule_name: String,
65    pub(super) root_rule_name: String,
66    pub(super) nest_layer_guard: i32,
67}
68
69impl EbnfParser {
70    /// Token at `cur + delta`. The token stream is always `EndOfFile`-
71    /// terminated, so callers stay in bounds when reading near the end.
72    pub(super) fn peek(&self, delta: i32) -> &Token {
73        let idx = (self.cur as i32 + delta).clamp(0, self.tokens.len() as i32 - 1) as usize;
74        &self.tokens[idx]
75    }
76
77    /// Advance `cnt` tokens.
78    pub(super) fn consume(&mut self, cnt: usize) {
79        self.cur = (self.cur + cnt).min(self.tokens.len() - 1);
80    }
81
82    /// Consume a token of `ty`, or report `message`.
83    pub(super) fn peek_and_consume(
84        &mut self,
85        ty: TokenType,
86        message: &str,
87    ) -> Result<(), ParseError> {
88        if self.peek(0).ty != ty {
89            return Err(self.parse_error(message, 0));
90        }
91        self.consume(1);
92        Ok(())
93    }
94
95    /// Build a [`ParseError::Parse`] anchored at `peek(delta_element)`.
96    pub(super) fn parse_error(&self, msg: &str, delta_element: i32) -> ParseError {
97        let t = self.peek(delta_element);
98        ParseError::Parse {
99            line: t.line,
100            column: t.column,
101            msg: msg.to_string(),
102        }
103    }
104
105    /// Parse a `|`-free sequence of elements into a `Sequence` expr.
106    fn parse_sequence(&mut self) -> Result<i32, ParseError> {
107        let mut elements: Vec<i32> = Vec::new();
108        loop {
109            elements.push(self.parse_element_with_quantifier()?);
110            if matches!(
111                self.peek(0).ty,
112                TokenType::Pipe
113                    | TokenType::RParen
114                    | TokenType::LookaheadLParen
115                    | TokenType::RuleName
116                    | TokenType::EndOfFile
117            ) {
118                break;
119            }
120        }
121        Ok(self.builder.add_sequence(&elements))
122    }
123
124    /// Parse `|`-separated sequences into a `Choices` expr.
125    pub(super) fn parse_choices(&mut self) -> Result<i32, ParseError> {
126        let mut choices: Vec<i32> = vec![self.parse_sequence()?];
127        while self.peek(0).ty == TokenType::Pipe {
128            self.consume(1);
129            choices.push(self.parse_sequence()?);
130        }
131        Ok(self.builder.add_choices(&choices))
132    }
133
134    /// Parse a `(= ...)` lookahead assertion, returning its expr id.
135    fn parse_lookahead_assertion(&mut self) -> Result<i32, ParseError> {
136        self.peek_and_consume(
137            TokenType::LookaheadLParen,
138            "Expect (= in lookahead assertion",
139        )?;
140        let result = self.parse_choices()?;
141        self.peek_and_consume(TokenType::RParen, "Expect )")?;
142        Ok(result)
143    }
144
145    /// Parse one `name ::= body (= lookahead)?` rule definition.
146    fn parse_rule(&mut self) -> Result<(String, i32, i32), ParseError> {
147        if self.peek(0).ty != TokenType::RuleName {
148            return Err(self.parse_error("Expect rule name", 0));
149        }
150        self.cur_rule_name = match &self.peek(0).value {
151            TokenValue::Str(s) => s.clone(),
152            _ => return Err(self.parse_error("Expect rule name", 0)),
153        };
154        self.consume(1);
155        self.peek_and_consume(TokenType::Assign, "Expect ::=")?;
156        let body_id = self.parse_choices()?;
157        let mut lookahead_id = -1;
158        if self.peek(0).ty == TokenType::LookaheadLParen {
159            lookahead_id = self.parse_lookahead_assertion()?;
160        }
161        Ok((self.cur_rule_name.clone(), body_id, lookahead_id))
162    }
163
164    /// Pre-declare every rule name (so forward references resolve) and
165    /// verify the root rule is present.
166    fn init_rule_names(&mut self) -> Result<(), ParseError> {
167        for delta in 0..self.tokens.len() {
168            if self.tokens[delta].ty != TokenType::RuleName {
169                continue;
170            }
171            let name = match &self.tokens[delta].value {
172                TokenValue::Str(s) => s.clone(),
173                _ => continue,
174            };
175            if self.builder.get_rule_id(&name) != -1 {
176                let t = &self.tokens[delta];
177                return Err(ParseError::Parse {
178                    line: t.line,
179                    column: t.column,
180                    msg: format!("Rule \"{name}\" is defined multiple times"),
181                });
182            }
183            self.builder.add_empty_rule(name)?;
184        }
185        if self.builder.get_rule_id(&self.root_rule_name) == -1 {
186            return Err(self.parse_error(
187                &format!(
188                    "The root rule with name \"{}\" is not found",
189                    self.root_rule_name
190                ),
191                0,
192            ));
193        }
194        Ok(())
195    }
196
197    /// Run the full parse and emit the finished grammar.
198    fn parse(mut self) -> Result<GrammarData, ParseError> {
199        self.init_rule_names()?;
200        while self.peek(0).ty != TokenType::EndOfFile {
201            let (name, body_id, lookahead_id) = self.parse_rule()?;
202            self.builder.update_rule_body_named(&name, body_id)?;
203            self.builder
204                .update_lookahead_assertion_named(&name, lookahead_id)?;
205        }
206        let root = self.root_rule_name.clone();
207        Ok(self.builder.get(&root)?)
208    }
209}
210
211/// Parse a BNF/EBNF grammar string into a [`GrammarData`].
212///
213/// `root_rule_name` names the start rule (xgrammar's default is
214/// `"root"`). Returns a [`ParseError`] on malformed input rather than
215/// panicking.
216pub fn parse_ebnf(ebnf_string: &str, root_rule_name: &str) -> Result<GrammarData, ParseError> {
217    let tokens = EbnfLexer::tokenize(ebnf_string)?;
218    let parser = EbnfParser {
219        builder: GrammarBuilder::new(),
220        tokens,
221        cur: 0,
222        cur_rule_name: String::new(),
223        root_rule_name: root_rule_name.to_string(),
224        nest_layer_guard: 0,
225    };
226    parser.parse()
227}
228
229/// Parse a grammar string with the default root rule name `"root"`.
230pub fn parse_ebnf_default(ebnf_string: &str) -> Result<GrammarData, ParseError> {
231    parse_ebnf(ebnf_string, "root")
232}
metrale_grammar/grammar/parser.rs

metrale_grammar/grammar/
parser.rs
