meta_language/grammar/import/
gbnf.rs

1use super::{parse_error, GrammarImportError};
2use crate::grammar::{CharClassItem, Grammar, GrammarExpr, GrammarFormat, GrammarRule};
3
4const FORMAT: GrammarFormat = GrammarFormat::Gbnf;
5
6/// Parses llama.cpp GBNF grammar text into the grammar IR.
7///
8/// The importer is a clean-room recursive-descent parser for the structural
9/// GBNF subset represented by the grammar IR: rules, unordered alternation,
10/// grouping, postfix repetition, string literals, and character classes.
11///
12/// # Errors
13///
14/// Returns [`GrammarImportError`] when the source cannot be parsed as GBNF or
15/// when the required `root` rule is missing.
16pub fn import_gbnf(text: &str) -> Result<Grammar, GrammarImportError> {
17    Parser::new(Lexer::new(text).tokenize()?).parse_grammar()
18}
19
20#[derive(Clone, Debug)]
21struct Parser {
22    tokens: Vec<Token>,
23    cursor: usize,
24    pending_comments: Vec<String>,
25}
26
27impl Parser {
28    const fn new(tokens: Vec<Token>) -> Self {
29        Self {
30            tokens,
31            cursor: 0,
32            pending_comments: Vec::new(),
33        }
34    }
35
36    fn parse_grammar(&mut self) -> Result<Grammar, GrammarImportError> {
37        let mut grammar = Grammar::new().with_source_format(FORMAT);
38        while !self.is_end() {
39            self.collect_comments_and_newlines();
40            if self.is_end() {
41                break;
42            }
43            grammar.add_rule(self.parse_rule()?);
44        }
45
46        if grammar.rule("root").is_some() {
47            grammar.set_start("root");
48            Ok(grammar)
49        } else {
50            Err(parse_error(
51                FORMAT,
52                "GBNF grammar does not contain root rule",
53            ))
54        }
55    }
56
57    fn parse_rule(&mut self) -> Result<GrammarRule, GrammarImportError> {
58        let comments = std::mem::take(&mut self.pending_comments);
59        let name = self.expect_ident("rule name")?;
60        self.expect_define()?;
61        let expr = self.parse_choice()?;
62        self.consume_rule_end();
63
64        let mut rule = GrammarRule::new(name, expr);
65        if !comments.is_empty() {
66            rule = rule.with_doc(comments.join("\n"));
67        }
68        Ok(rule)
69    }
70
71    fn parse_choice(&mut self) -> Result<GrammarExpr, GrammarImportError> {
72        let mut alternatives = Vec::new();
73        push_choice_alternative(&mut alternatives, self.parse_sequence()?);
74        while self.try_consume_pipe() {
75            push_choice_alternative(&mut alternatives, self.parse_sequence()?);
76        }
77        Ok(finish_choice(alternatives))
78    }
79
80    fn parse_sequence(&mut self) -> Result<GrammarExpr, GrammarImportError> {
81        let mut items = Vec::new();
82        while !self.is_sequence_end() {
83            push_sequence_item(&mut items, self.parse_postfix()?);
84        }
85        Ok(finish_sequence(items))
86    }
87
88    fn parse_postfix(&mut self) -> Result<GrammarExpr, GrammarImportError> {
89        let mut expr = self.parse_atom()?;
90        loop {
91            expr = match self.peek_kind() {
92                Some(TokenKind::Question) => {
93                    self.advance();
94                    GrammarExpr::optional(expr)
95                }
96                Some(TokenKind::Star) => {
97                    self.advance();
98                    GrammarExpr::zero_or_more(expr)
99                }
100                Some(TokenKind::Plus) => {
101                    self.advance();
102                    GrammarExpr::one_or_more(expr)
103                }
104                Some(TokenKind::LBrace) => self.parse_counted_repeat(expr)?,
105                _ => return Ok(expr),
106            };
107        }
108    }
109
110    fn parse_counted_repeat(
111        &mut self,
112        expr: GrammarExpr,
113    ) -> Result<GrammarExpr, GrammarImportError> {
114        self.expect_lbrace()?;
115        let min = self.expect_number("minimum repeat count")?;
116        let max = if self.try_consume_comma() {
117            if matches!(self.peek_kind(), Some(TokenKind::Number(_))) {
118                Some(self.expect_number("maximum repeat count")?)
119            } else {
120                None
121            }
122        } else {
123            Some(min)
124        };
125        self.expect_rbrace()?;
126        if let Some(max) = max {
127            if min > max {
128                return Err(self.error("repeat minimum exceeds maximum"));
129            }
130        }
131        Ok(GrammarExpr::repeat(expr, min, max))
132    }
133
134    fn parse_atom(&mut self) -> Result<GrammarExpr, GrammarImportError> {
135        let Some(token) = self.peek().cloned() else {
136            return Err(self.expected("expression element"));
137        };
138
139        match token.kind {
140            TokenKind::Ident(name) => {
141                self.advance();
142                Ok(GrammarExpr::NonTerminal(name))
143            }
144            TokenKind::String(value) => {
145                self.advance();
146                Ok(GrammarExpr::Terminal(value))
147            }
148            TokenKind::CharSet(content) => {
149                self.advance();
150                lower_char_set(&content, token.offset)
151            }
152            TokenKind::Dot => {
153                self.advance();
154                Ok(GrammarExpr::AnyChar)
155            }
156            TokenKind::LParen => {
157                self.advance();
158                let expr = self.parse_choice()?;
159                self.expect_rparen()?;
160                Ok(expr)
161            }
162            _ => Err(self.expected("expression element")),
163        }
164    }
165
166    fn collect_comments_and_newlines(&mut self) {
167        loop {
168            match self.peek_kind() {
169                Some(TokenKind::Comment(comment)) => {
170                    self.pending_comments.push(comment.clone());
171                    self.advance();
172                }
173                Some(TokenKind::Newline) => {
174                    self.advance();
175                }
176                _ => break,
177            }
178        }
179    }
180
181    fn consume_rule_end(&mut self) {
182        if matches!(self.peek_kind(), Some(TokenKind::Comment(_))) {
183            self.advance();
184        }
185        if matches!(self.peek_kind(), Some(TokenKind::Newline)) {
186            self.advance();
187        }
188    }
189
190    fn expect_ident(&mut self, role: &str) -> Result<String, GrammarImportError> {
191        let Some(token) = self.peek().cloned() else {
192            return Err(self.expected(role));
193        };
194        match token.kind {
195            TokenKind::Ident(value) => {
196                self.advance();
197                Ok(value)
198            }
199            _ => Err(self.expected(role)),
200        }
201    }
202
203    fn expect_number(&mut self, role: &str) -> Result<usize, GrammarImportError> {
204        let Some(token) = self.peek().cloned() else {
205            return Err(self.expected(role));
206        };
207        match token.kind {
208            TokenKind::Number(value) => {
209                self.advance();
210                Ok(value)
211            }
212            _ => Err(self.expected(role)),
213        }
214    }
215
216    fn expect_define(&mut self) -> Result<(), GrammarImportError> {
217        if matches!(self.peek_kind(), Some(TokenKind::Define)) {
218            self.advance();
219            Ok(())
220        } else {
221            Err(self.expected("'::='"))
222        }
223    }
224
225    fn expect_lbrace(&mut self) -> Result<(), GrammarImportError> {
226        if matches!(self.peek_kind(), Some(TokenKind::LBrace)) {
227            self.advance();
228            Ok(())
229        } else {
230            Err(self.expected("'{'"))
231        }
232    }
233
234    fn expect_rbrace(&mut self) -> Result<(), GrammarImportError> {
235        if matches!(self.peek_kind(), Some(TokenKind::RBrace)) {
236            self.advance();
237            Ok(())
238        } else {
239            Err(self.expected("'}'"))
240        }
241    }
242
243    fn expect_rparen(&mut self) -> Result<(), GrammarImportError> {
244        if matches!(self.peek_kind(), Some(TokenKind::RParen)) {
245            self.advance();
246            Ok(())
247        } else {
248            Err(self.expected("')'"))
249        }
250    }
251
252    fn try_consume_pipe(&mut self) -> bool {
253        let start = self.cursor;
254        while matches!(
255            self.peek_kind(),
256            Some(TokenKind::Newline | TokenKind::Comment(_))
257        ) {
258            self.advance();
259        }
260        if matches!(self.peek_kind(), Some(TokenKind::Pipe)) {
261            self.advance();
262            true
263        } else {
264            self.cursor = start;
265            false
266        }
267    }
268
269    fn try_consume_comma(&mut self) -> bool {
270        if matches!(self.peek_kind(), Some(TokenKind::Comma)) {
271            self.advance();
272            true
273        } else {
274            false
275        }
276    }
277
278    fn is_sequence_end(&self) -> bool {
279        self.is_end()
280            || matches!(
281                self.peek_kind(),
282                Some(
283                    TokenKind::Newline
284                        | TokenKind::Comment(_)
285                        | TokenKind::Pipe
286                        | TokenKind::RParen
287                )
288            )
289    }
290
291    fn expected(&self, expected: &str) -> GrammarImportError {
292        self.error(format!("expected {expected}"))
293    }
294
295    fn error(&self, message: impl Into<String>) -> GrammarImportError {
296        let offset = self.peek().map_or(0, |token| token.offset);
297        error_at(offset, message)
298    }
299
300    fn is_end(&self) -> bool {
301        self.cursor >= self.tokens.len()
302    }
303
304    fn peek(&self) -> Option<&Token> {
305        self.tokens.get(self.cursor)
306    }
307
308    fn peek_kind(&self) -> Option<&TokenKind> {
309        self.peek().map(|token| &token.kind)
310    }
311
312    fn advance(&mut self) -> &Token {
313        let token = &self.tokens[self.cursor];
314        self.cursor += 1;
315        token
316    }
317}
318
319#[derive(Clone, Debug, PartialEq, Eq)]
320struct Token {
321    kind: TokenKind,
322    offset: usize,
323}
324
325#[derive(Clone, Debug, PartialEq, Eq)]
326enum TokenKind {
327    Ident(String),
328    String(String),
329    CharSet(String),
330    Number(usize),
331    Comment(String),
332    Define,
333    Pipe,
334    LParen,
335    RParen,
336    Question,
337    Star,
338    Plus,
339    LBrace,
340    RBrace,
341    Comma,
342    Dot,
343    Newline,
344}
345
346#[derive(Clone, Debug)]
347struct Lexer<'text> {
348    text: &'text str,
349    cursor: usize,
350}
351
352impl<'text> Lexer<'text> {
353    const fn new(text: &'text str) -> Self {
354        Self { text, cursor: 0 }
355    }
356
357    fn tokenize(mut self) -> Result<Vec<Token>, GrammarImportError> {
358        let mut tokens = Vec::new();
359        while !self.is_end() {
360            self.skip_horizontal_whitespace();
361            if self.is_end() {
362                break;
363            }
364
365            let offset = self.cursor;
366            let kind = self.next_token_kind()?;
367            tokens.push(Token { kind, offset });
368        }
369        Ok(tokens)
370    }
371
372    fn next_token_kind(&mut self) -> Result<TokenKind, GrammarImportError> {
373        if self.starts_with("::=") {
374            self.cursor += 3;
375            return Ok(TokenKind::Define);
376        }
377
378        let Some(character) = self.peek_char() else {
379            return Err(error_at(self.cursor, "unexpected end of input"));
380        };
381
382        match character {
383            '\n' => {
384                self.advance_char();
385                Ok(TokenKind::Newline)
386            }
387            '\r' => {
388                self.advance_char();
389                if self.peek_char() == Some('\n') {
390                    self.advance_char();
391                }
392                Ok(TokenKind::Newline)
393            }
394            '#' => Ok(TokenKind::Comment(self.line_comment())),
395            '"' => self.string_literal().map(TokenKind::String),
396            '[' => self.char_set().map(TokenKind::CharSet),
397            '|' => {
398                self.advance_char();
399                Ok(TokenKind::Pipe)
400            }
401            '(' => {
402                self.advance_char();
403                Ok(TokenKind::LParen)
404            }
405            ')' => {
406                self.advance_char();
407                Ok(TokenKind::RParen)
408            }
409            '?' => {
410                self.advance_char();
411                Ok(TokenKind::Question)
412            }
413            '*' => {
414                self.advance_char();
415                Ok(TokenKind::Star)
416            }
417            '+' => {
418                self.advance_char();
419                Ok(TokenKind::Plus)
420            }
421            '{' => {
422                self.advance_char();
423                Ok(TokenKind::LBrace)
424            }
425            '}' => {
426                self.advance_char();
427                Ok(TokenKind::RBrace)
428            }
429            ',' => {
430                self.advance_char();
431                Ok(TokenKind::Comma)
432            }
433            '.' => {
434                self.advance_char();
435                Ok(TokenKind::Dot)
436            }
437            character if character.is_ascii_digit() => self.number().map(TokenKind::Number),
438            character if is_ident_start(character) => Ok(TokenKind::Ident(self.identifier())),
439            character => Err(error_at(
440                self.cursor,
441                format!("unexpected character {character:?}"),
442            )),
443        }
444    }
445
446    fn line_comment(&mut self) -> String {
447        let start = self.cursor;
448        while let Some(character) = self.peek_char() {
449            if character == '\n' || character == '\r' {
450                break;
451            }
452            self.advance_char();
453        }
454        self.text[start..self.cursor].trim().to_string()
455    }
456
457    fn string_literal(&mut self) -> Result<String, GrammarImportError> {
458        let start = self.cursor;
459        self.advance_char();
460        let mut value = String::new();
461        while let Some(character) = self.advance_char() {
462            match character {
463                '"' => return Ok(value),
464                '\\' => value.push(self.escape_sequence(start)?),
465                character => value.push(character),
466            }
467        }
468        Err(error_at(start, "unterminated string literal"))
469    }
470
471    fn char_set(&mut self) -> Result<String, GrammarImportError> {
472        let start = self.cursor;
473        self.advance_char();
474        let content_start = self.cursor;
475        let mut escaped = false;
476        while let Some(character) = self.advance_char() {
477            if escaped {
478                escaped = false;
479            } else if character == '\\' {
480                escaped = true;
481            } else if character == ']' {
482                let content_end = self.cursor - character.len_utf8();
483                return Ok(self.text[content_start..content_end].to_string());
484            }
485        }
486        Err(error_at(start, "unterminated character class"))
487    }
488
489    fn escape_sequence(&mut self, start: usize) -> Result<char, GrammarImportError> {
490        let Some(character) = self.advance_char() else {
491            return Err(error_at(start, "unterminated escape sequence"));
492        };
493        match character {
494            'n' => Ok('\n'),
495            'r' => Ok('\r'),
496            't' => Ok('\t'),
497            'b' => Ok('\u{08}'),
498            'f' => Ok('\u{0c}'),
499            '\\' | '"' | '\'' | '[' | ']' | '-' | '^' => Ok(character),
500            'x' => self.hex_escape(start, 2),
501            'u' => self.hex_escape(start, 4),
502            'U' => self.hex_escape(start, 8),
503            character => Ok(character),
504        }
505    }
506
507    fn hex_escape(&mut self, start: usize, digits: usize) -> Result<char, GrammarImportError> {
508        let mut value = 0_u32;
509        for _ in 0..digits {
510            let Some(character) = self.advance_char() else {
511                return Err(error_at(start, "unterminated hexadecimal escape"));
512            };
513            let Some(digit) = character.to_digit(16) else {
514                return Err(error_at(
515                    self.cursor - character.len_utf8(),
516                    "hexadecimal escape requires hexadecimal digits",
517                ));
518            };
519            value = (value << 4) | digit;
520        }
521        char::from_u32(value).ok_or_else(|| error_at(start, "invalid hexadecimal escape"))
522    }
523
524    fn number(&mut self) -> Result<usize, GrammarImportError> {
525        let start = self.cursor;
526        let mut value = 0_usize;
527        while let Some(character) = self.peek_char() {
528            let Some(digit) = character.to_digit(10) else {
529                break;
530            };
531            self.advance_char();
532            value = value
533                .checked_mul(10)
534                .and_then(|current| current.checked_add(digit as usize))
535                .ok_or_else(|| error_at(start, "number exceeds usize"))?;
536        }
537        Ok(value)
538    }
539
540    fn identifier(&mut self) -> String {
541        let start = self.cursor;
542        self.advance_char();
543        while self.peek_char().is_some_and(is_ident_continue) {
544            self.advance_char();
545        }
546        self.text[start..self.cursor].to_string()
547    }
548
549    fn skip_horizontal_whitespace(&mut self) {
550        while self.peek_char().is_some_and(|character| {
551            character != '\n' && character != '\r' && character.is_whitespace()
552        }) {
553            self.advance_char();
554        }
555    }
556
557    fn starts_with(&self, prefix: &str) -> bool {
558        self.text[self.cursor..].starts_with(prefix)
559    }
560
561    const fn is_end(&self) -> bool {
562        self.cursor >= self.text.len()
563    }
564
565    fn peek_char(&self) -> Option<char> {
566        self.text[self.cursor..].chars().next()
567    }
568
569    fn advance_char(&mut self) -> Option<char> {
570        let character = self.peek_char()?;
571        self.cursor += character.len_utf8();
572        Some(character)
573    }
574}
575
576fn lower_char_set(content: &str, offset: usize) -> Result<GrammarExpr, GrammarImportError> {
577    let mut scanner = ClassScanner::new(content, offset);
578    let negated = scanner.try_consume('^');
579    let mut items = Vec::new();
580    while !scanner.is_end() {
581        let start = scanner.read_char()?;
582        if scanner.try_consume_range_separator() {
583            let end = scanner.read_char()?;
584            if start > end {
585                return Err(error_at(offset, "character class range start exceeds end"));
586            }
587            items.push(CharClassItem::Range(start, end));
588        } else {
589            items.push(CharClassItem::Char(start));
590        }
591    }
592    if items.is_empty() {
593        return Err(error_at(offset, "character class must not be empty"));
594    }
595    Ok(GrammarExpr::CharClass { negated, items })
596}
597
598#[derive(Clone, Debug)]
599struct ClassScanner<'text> {
600    text: &'text str,
601    cursor: usize,
602    offset: usize,
603}
604
605impl<'text> ClassScanner<'text> {
606    const fn new(text: &'text str, offset: usize) -> Self {
607        Self {
608            text,
609            cursor: 0,
610            offset,
611        }
612    }
613
614    fn read_char(&mut self) -> Result<char, GrammarImportError> {
615        let Some(character) = self.advance_char() else {
616            return Err(error_at(self.offset, "unexpected end of character class"));
617        };
618        if character == '\\' {
619            self.read_escape()
620        } else {
621            Ok(character)
622        }
623    }
624
625    fn read_escape(&mut self) -> Result<char, GrammarImportError> {
626        let Some(character) = self.advance_char() else {
627            return Err(error_at(self.offset, "unterminated character class escape"));
628        };
629        match character {
630            'n' => Ok('\n'),
631            'r' => Ok('\r'),
632            't' => Ok('\t'),
633            'b' => Ok('\u{08}'),
634            'f' => Ok('\u{0c}'),
635            '\\' | '"' | '\'' | '[' | ']' | '-' | '^' => Ok(character),
636            'x' => self.hex_escape(2),
637            'u' => self.hex_escape(4),
638            'U' => self.hex_escape(8),
639            character => Ok(character),
640        }
641    }
642
643    fn hex_escape(&mut self, digits: usize) -> Result<char, GrammarImportError> {
644        let mut value = 0_u32;
645        for _ in 0..digits {
646            let Some(character) = self.advance_char() else {
647                return Err(error_at(self.offset, "unterminated hexadecimal escape"));
648            };
649            let Some(digit) = character.to_digit(16) else {
650                return Err(error_at(
651                    self.offset + self.cursor.saturating_sub(character.len_utf8()),
652                    "hexadecimal escape requires hexadecimal digits",
653                ));
654            };
655            value = (value << 4) | digit;
656        }
657        char::from_u32(value).ok_or_else(|| error_at(self.offset, "invalid hexadecimal escape"))
658    }
659
660    fn try_consume(&mut self, expected: char) -> bool {
661        if self.peek_char() == Some(expected) {
662            self.advance_char();
663            true
664        } else {
665            false
666        }
667    }
668
669    fn try_consume_range_separator(&mut self) -> bool {
670        if self.peek_char() == Some('-') && self.has_char_after_current() {
671            self.advance_char();
672            true
673        } else {
674            false
675        }
676    }
677
678    fn has_char_after_current(&self) -> bool {
679        let mut chars = self.text[self.cursor..].chars();
680        chars.next();
681        chars.next().is_some()
682    }
683
684    const fn is_end(&self) -> bool {
685        self.cursor >= self.text.len()
686    }
687
688    fn peek_char(&self) -> Option<char> {
689        self.text[self.cursor..].chars().next()
690    }
691
692    fn advance_char(&mut self) -> Option<char> {
693        let character = self.peek_char()?;
694        self.cursor += character.len_utf8();
695        Some(character)
696    }
697}
698
699fn finish_sequence(items: Vec<GrammarExpr>) -> GrammarExpr {
700    match items.len() {
701        0 => GrammarExpr::Empty,
702        1 => items.into_iter().next().expect("one sequence item exists"),
703        _ => GrammarExpr::Sequence(items),
704    }
705}
706
707fn push_sequence_item(items: &mut Vec<GrammarExpr>, item: GrammarExpr) {
708    match item {
709        GrammarExpr::Empty => {}
710        GrammarExpr::Sequence(nested) => {
711            for item in nested {
712                push_sequence_item(items, item);
713            }
714        }
715        item => items.push(item),
716    }
717}
718
719fn finish_choice(alternatives: Vec<GrammarExpr>) -> GrammarExpr {
720    if alternatives.iter().all(|expr| expr == &GrammarExpr::Empty) {
721        return GrammarExpr::Empty;
722    }
723    match alternatives.len() {
724        0 => GrammarExpr::Empty,
725        1 => alternatives
726            .into_iter()
727            .next()
728            .expect("one alternative exists"),
729        _ => GrammarExpr::Choice {
730            ordered: false,
731            alternatives,
732        },
733    }
734}
735
736fn push_choice_alternative(alternatives: &mut Vec<GrammarExpr>, alternative: GrammarExpr) {
737    match alternative {
738        GrammarExpr::Choice {
739            ordered: false,
740            alternatives: nested,
741        } => alternatives.extend(nested),
742        alternative => alternatives.push(alternative),
743    }
744}
745
746fn error_at(offset: usize, message: impl Into<String>) -> GrammarImportError {
747    parse_error(FORMAT, format!("{} at byte {offset}", message.into()))
748}
749
750const fn is_ident_start(character: char) -> bool {
751    character == '_' || character.is_ascii_alphabetic()
752}
753
754const fn is_ident_continue(character: char) -> bool {
755    character == '_' || character == '-' || character.is_ascii_alphanumeric()
756}
meta_language/grammar/import/gbnf.rs

meta_language/grammar/import/
gbnf.rs
