metrale_grammar/grammar/
lexer.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2//
3// EBNFLexer — tokenizer for BNF/EBNF grammar text.
4// Port of `EBNFLexer` from xgrammar `cpp/grammar_parser.cc`.
5//
6// The lexer turns grammar source into a flat `Vec<Token>`, classifying
7// rule-definition names, identifiers, string/char-class/integer
8// literals, quantifiers and structural punctuation.
9//
10// This file holds the lexer struct + core scanning helpers. Token
11// type definitions live in `lexer_token.rs`, the literal-scanning
12// methods in `lexer_scan.rs`, tests in `lexer_tests.rs` — split to
13// keep each file under the 250-line cap.
14
15#[path = "lexer_scan.rs"]
16mod scan;
17#[cfg(test)]
18#[path = "lexer_tests.rs"]
19mod tests;
20#[path = "lexer_token.rs"]
21mod token;
22
23pub use token::{LexError, Token, TokenType, TokenValue};
24
25/// Largest integer literal accepted in a grammar (`1e15`).
26pub(super) const MAX_INTEGER_IN_GRAMMAR: i64 = 1_000_000_000_000_000;
27
28/// The EBNF lexer. Equivalent to xgrammar's `EBNFLexer::Impl`.
29pub struct EbnfLexer {
30    pub(super) input: Vec<u8>,
31    pub(super) pos: usize,
32    pub(super) line: i32,
33    pub(super) column: i32,
34}
35
36impl EbnfLexer {
37    /// Tokenize `input` into a flat token vector terminated by `EndOfFile`.
38    pub fn tokenize(input: &str) -> Result<Vec<Token>, LexError> {
39        let mut lexer = EbnfLexer {
40            input: input.as_bytes().to_vec(),
41            pos: 0,
42            line: 1,
43            column: 1,
44        };
45        let mut tokens: Vec<Token> = Vec::new();
46        loop {
47            let mut produced = lexer.next_token()?;
48            let stop = produced
49                .last()
50                .is_some_and(|t| t.ty == TokenType::EndOfFile);
51            tokens.append(&mut produced);
52            if stop {
53                break;
54            }
55        }
56        Self::convert_identifier_to_rule_name(&mut tokens)?;
57        Ok(tokens)
58    }
59
60    /// Byte at `pos + delta`, or `0` (NUL) past the end — mirrors the
61    /// C++ NUL-terminated-string `Peek`.
62    pub(super) fn peek(&self, delta: usize) -> u8 {
63        self.input.get(self.pos + delta).copied().unwrap_or(0)
64    }
65
66    /// Byte one position before `pos`, or `0` at the start.
67    fn peek_back(&self) -> u8 {
68        if self.pos == 0 {
69            0
70        } else {
71            self.input[self.pos - 1]
72        }
73    }
74
75    /// Consume `cnt` bytes, updating line/column tracking.
76    pub(super) fn consume(&mut self, cnt: usize) {
77        for _ in 0..cnt {
78            let c = self.peek(0);
79            if c == b'\n' || (c == b'\r' && self.peek(1) != b'\n') {
80                self.line += 1;
81                self.column = 1;
82            } else {
83                self.column += 1;
84            }
85            self.pos += 1;
86        }
87    }
88
89    /// Skip whitespace and `#` comments.
90    pub(super) fn consume_space(&mut self) {
91        while matches!(self.peek(0), b' ' | b'\t' | b'#' | b'\n' | b'\r') {
92            self.consume(1);
93            if self.peek_back() == b'#' {
94                while self.peek(0) != 0 && self.peek(0) != b'\n' && self.peek(0) != b'\r' {
95                    self.consume(1);
96                }
97                if self.peek(0) == 0 {
98                    return;
99                }
100                self.consume(1);
101                if self.peek_back() == b'\r' && self.peek(0) == b'\n' {
102                    self.consume(1);
103                }
104            }
105        }
106    }
107
108    /// Build a [`LexError`] at the current source position.
109    pub(super) fn err(&self, msg: impl Into<String>) -> LexError {
110        LexError {
111            line: self.line,
112            column: self.column,
113            msg: msg.into(),
114        }
115    }
116
117    /// Whether `c` can appear in an identifier.
118    pub(super) fn is_name_char(c: u8, is_first: bool) -> bool {
119        c == b'_'
120            || c == b'-'
121            || c == b'.'
122            || c.is_ascii_lowercase()
123            || c.is_ascii_uppercase()
124            || (!is_first && c.is_ascii_digit())
125    }
126
127    /// Parse a bare identifier string.
128    fn parse_identifier_str(&mut self) -> Result<String, LexError> {
129        let start = self.pos;
130        let mut first = true;
131        while self.peek(0) != 0 && Self::is_name_char(self.peek(0), first) {
132            self.consume(1);
133            first = false;
134        }
135        if start == self.pos {
136            return Err(self.err("Expect identifier"));
137        }
138        Ok(String::from_utf8_lossy(&self.input[start..self.pos]).into_owned())
139    }
140
141    /// Parse an identifier or `true`/`false` boolean.
142    pub(super) fn parse_identifier_or_boolean(&mut self) -> Result<Token, LexError> {
143        let (line, column) = (self.line, self.column);
144        let ident = self.parse_identifier_str()?;
145        if ident == "true" || ident == "false" {
146            return Ok(Token {
147                ty: TokenType::BooleanLiteral,
148                value: TokenValue::Bool(ident == "true"),
149                lexeme: ident,
150                line,
151                column,
152            });
153        }
154        Ok(Token {
155            ty: TokenType::Identifier,
156            value: TokenValue::Str(ident.clone()),
157            lexeme: ident,
158            line,
159            column,
160        })
161    }
162
163    /// Build a value-less token at `(line, column)`.
164    pub(super) fn simple_token(
165        &self,
166        ty: TokenType,
167        lexeme: &str,
168        line: i32,
169        column: i32,
170    ) -> Token {
171        Token {
172            ty,
173            lexeme: lexeme.to_string(),
174            value: TokenValue::None,
175            line,
176            column,
177        }
178    }
179}
metrale_grammar/grammar/lexer.rs

metrale_grammar/grammar/
lexer.rs
