meta_language/grammar/import/
ebnf.rs

1use ::ebnf::{
2    Grammar as EbnfGrammar, Node as EbnfNode, RegexExtKind as EbnfRegexExtKind,
3    SymbolKind as EbnfSymbolKind,
4};
5
6use super::{parse_error, unsupported_error, GrammarImportError};
7use crate::grammar::{Grammar, GrammarExpr, GrammarFormat, GrammarRule};
8
9const EMPTY_SENTINEL: &str = "\u{0}meta-language-empty\u{0}";
10
11/// Parses Extended Backus-Naur Form text into the grammar IR.
12///
13/// The parser accepts the ISO-style `name = expression ;` spelling used by the
14/// issue fixtures and the `::=` spelling accepted by the upstream `ebnf` crate.
15///
16/// # Errors
17///
18/// Returns [`GrammarImportError`] when the EBNF text cannot be parsed, when a
19/// parsed construct cannot be represented, or when a non-terminal reference does
20/// not resolve to a rule in the imported grammar.
21pub fn import_ebnf(text: &str) -> Result<Grammar, GrammarImportError> {
22    if let Some(construct) = find_special_sequence(text) {
23        return Err(unsupported_error(GrammarFormat::Ebnf, construct));
24    }
25
26    let normalized = normalize_empty_alternatives(text);
27    let parsed = ::ebnf::get_grammar(&normalized)
28        .map_err(|error| parse_error(GrammarFormat::Ebnf, format!("{error:?}")))?;
29    let grammar = lower_grammar(&parsed)?;
30    validate_references(&grammar)?;
31    Ok(grammar)
32}
33
34fn lower_grammar(parsed: &EbnfGrammar) -> Result<Grammar, GrammarImportError> {
35    let mut grammar = Grammar::new().with_source_format(GrammarFormat::Ebnf);
36    for expression in &parsed.expressions {
37        grammar.add_rule(GrammarRule::new(
38            expression.lhs.clone(),
39            lower_node(&expression.rhs)?,
40        ));
41    }
42    Ok(grammar)
43}
44
45fn lower_node(node: &EbnfNode) -> Result<GrammarExpr, GrammarImportError> {
46    match node {
47        EbnfNode::String(value) if value.is_empty() || value == EMPTY_SENTINEL => {
48            Ok(GrammarExpr::Empty)
49        }
50        EbnfNode::String(value) => Ok(GrammarExpr::Terminal(value.clone())),
51        EbnfNode::RegexString(value) => Err(unsupported_error(
52            GrammarFormat::Ebnf,
53            format!("inline regex {value:?}"),
54        )),
55        EbnfNode::Terminal(name) => Ok(GrammarExpr::NonTerminal(name.clone())),
56        EbnfNode::Multiple(nodes) => lower_sequence(nodes.iter().map(lower_node)),
57        EbnfNode::RegexExt(inner, kind) => lower_regex_extension(inner, kind),
58        EbnfNode::Symbol(left, EbnfSymbolKind::Concatenation, right) => {
59            lower_sequence([lower_node(left), lower_node(right)])
60        }
61        EbnfNode::Symbol(left, EbnfSymbolKind::Alternation, right) => {
62            lower_choice([lower_node(left), lower_node(right)])
63        }
64        EbnfNode::Group(inner) => lower_node(inner),
65        EbnfNode::Optional(inner) => lower_node(inner).map(GrammarExpr::optional),
66        EbnfNode::Repeat(inner) => lower_node(inner).map(GrammarExpr::zero_or_more),
67        EbnfNode::Unknown => Err(unsupported_error(GrammarFormat::Ebnf, "unknown node")),
68    }
69}
70
71fn lower_regex_extension(
72    inner: &EbnfNode,
73    kind: &EbnfRegexExtKind,
74) -> Result<GrammarExpr, GrammarImportError> {
75    let expr = lower_node(inner)?;
76    Ok(match kind {
77        EbnfRegexExtKind::Repeat0 => GrammarExpr::zero_or_more(expr),
78        EbnfRegexExtKind::Repeat1 => GrammarExpr::one_or_more(expr),
79        EbnfRegexExtKind::Optional => GrammarExpr::optional(expr),
80    })
81}
82
83fn lower_sequence<I>(items: I) -> Result<GrammarExpr, GrammarImportError>
84where
85    I: IntoIterator<Item = Result<GrammarExpr, GrammarImportError>>,
86{
87    let mut lowered = Vec::new();
88    for item in items {
89        push_sequence_item(&mut lowered, item?);
90    }
91
92    Ok(match lowered.len() {
93        0 => GrammarExpr::Empty,
94        1 => lowered.remove(0),
95        _ => GrammarExpr::Sequence(lowered),
96    })
97}
98
99fn push_sequence_item(items: &mut Vec<GrammarExpr>, item: GrammarExpr) {
100    match item {
101        GrammarExpr::Empty => {}
102        GrammarExpr::Sequence(nested) => {
103            for item in nested {
104                push_sequence_item(items, item);
105            }
106        }
107        item => items.push(item),
108    }
109}
110
111fn lower_choice<I>(alternatives: I) -> Result<GrammarExpr, GrammarImportError>
112where
113    I: IntoIterator<Item = Result<GrammarExpr, GrammarImportError>>,
114{
115    let mut lowered = Vec::new();
116    for alternative in alternatives {
117        push_choice_alternative(&mut lowered, alternative?);
118    }
119
120    if lowered.iter().all(|expr| expr == &GrammarExpr::Empty) {
121        return Ok(GrammarExpr::Empty);
122    }
123
124    Ok(match lowered.len() {
125        0 => GrammarExpr::Empty,
126        1 => lowered.remove(0),
127        _ => GrammarExpr::Choice {
128            ordered: false,
129            alternatives: lowered,
130        },
131    })
132}
133
134fn push_choice_alternative(alternatives: &mut Vec<GrammarExpr>, alternative: GrammarExpr) {
135    match alternative {
136        GrammarExpr::Choice {
137            ordered: false,
138            alternatives: nested,
139        } => alternatives.extend(nested),
140        alternative => alternatives.push(alternative),
141    }
142}
143
144fn validate_references(grammar: &Grammar) -> Result<(), GrammarImportError> {
145    if let Some(name) = grammar.undefined_nonterminals().into_iter().next() {
146        return Err(parse_error(
147            GrammarFormat::Ebnf,
148            format!("undefined non-terminal {name}"),
149        ));
150    }
151    Ok(())
152}
153
154fn find_special_sequence(text: &str) -> Option<String> {
155    let mut scanner = Scanner::new(text);
156    while let Some((index, character, is_code, _)) = scanner.next() {
157        if is_code && character == '?' && is_special_sequence_start(text, index) {
158            let end = text[index + character.len_utf8()..]
159                .find('?')
160                .map_or(text.len(), |relative| {
161                    index + character.len_utf8() + relative + 1
162                });
163            let construct = text[index..end].trim();
164            return Some(format!("special sequence {construct:?}"));
165        }
166    }
167    None
168}
169
170fn is_special_sequence_start(text: &str, index: usize) -> bool {
171    text[..index]
172        .chars()
173        .rev()
174        .find(|character| !character.is_whitespace())
175        .map_or(true, |character| {
176            matches!(character, '=' | '|' | ',' | '(' | '[' | '{' | ';')
177        })
178}
179
180fn normalize_empty_alternatives(text: &str) -> String {
181    let mut normalized = String::with_capacity(text.len());
182    let mut scanner = Scanner::new(text);
183    let mut in_rhs = false;
184    let mut empty_alternative_pending = false;
185
186    while let Some((index, character, is_code, depth)) = scanner.next() {
187        if is_code {
188            if in_rhs {
189                match character {
190                    '|' => {
191                        if empty_alternative_pending {
192                            push_empty_sentinel(&mut normalized);
193                        }
194                        empty_alternative_pending = true;
195                    }
196                    ';' if depth == 0 => {
197                        if empty_alternative_pending {
198                            push_empty_sentinel(&mut normalized);
199                        }
200                        in_rhs = false;
201                        empty_alternative_pending = false;
202                    }
203                    ')' | ']' | '}' => {
204                        if empty_alternative_pending {
205                            push_empty_sentinel(&mut normalized);
206                        }
207                        empty_alternative_pending = false;
208                    }
209                    '(' | '[' | '{' => {
210                        empty_alternative_pending = true;
211                    }
212                    ',' => {
213                        empty_alternative_pending = false;
214                    }
215                    _ if character.is_whitespace() => {}
216                    _ => {
217                        empty_alternative_pending = false;
218                    }
219                }
220            } else if depth == 0 && character == '=' {
221                in_rhs = true;
222                empty_alternative_pending = true;
223            }
224        }
225        normalized.push_str(&text[index..index + character.len_utf8()]);
226    }
227    normalized
228}
229
230fn push_empty_sentinel(text: &mut String) {
231    text.push('"');
232    text.push_str(EMPTY_SENTINEL);
233    text.push('"');
234}
235
236#[derive(Clone, Copy, Debug, PartialEq, Eq)]
237enum ScanState {
238    Code,
239    SingleQuote,
240    DoubleQuote,
241}
242
243#[derive(Clone, Debug)]
244struct Scanner<'text> {
245    text: &'text str,
246    cursor: usize,
247    state: ScanState,
248    escaped: bool,
249    depth: usize,
250}
251
252impl<'text> Scanner<'text> {
253    const fn new(text: &'text str) -> Self {
254        Self {
255            text,
256            cursor: 0,
257            state: ScanState::Code,
258            escaped: false,
259            depth: 0,
260        }
261    }
262
263    fn next(&mut self) -> Option<(usize, char, bool, usize)> {
264        let rest = self.text.get(self.cursor..)?;
265        let mut chars = rest.char_indices();
266        let (_, character) = chars.next()?;
267        let index = self.cursor;
268        let was_code = matches!(self.state, ScanState::Code);
269        let previous_depth = self.depth;
270        self.cursor += character.len_utf8();
271
272        match self.state {
273            ScanState::Code => match character {
274                '\'' => self.state = ScanState::SingleQuote,
275                '"' => self.state = ScanState::DoubleQuote,
276                '(' | '[' | '{' => self.depth += 1,
277                ')' | ']' | '}' => self.depth = self.depth.saturating_sub(1),
278                _ => {}
279            },
280            ScanState::SingleQuote => self.scan_quoted(character, '\''),
281            ScanState::DoubleQuote => self.scan_quoted(character, '"'),
282        }
283
284        Some((index, character, was_code, previous_depth))
285    }
286
287    fn scan_quoted(&mut self, character: char, quote: char) {
288        if self.escaped {
289            self.escaped = false;
290        } else if character == '\\' {
291            self.escaped = true;
292        } else if character == quote {
293            self.state = ScanState::Code;
294        }
295    }
296}
meta_language/grammar/import/ebnf.rs

meta_language/grammar/import/
ebnf.rs
