meta_language/grammar/import/
antlr.rs

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

meta_language/grammar/import/
antlr.rs
