meta_language/grammar/import/
bnf.rs

1use ::bnf::{Expression as BnfExpression, Grammar as BnfGrammar, Term as BnfTerm};
2
3use super::{parse_error, unsupported_error, GrammarImportError};
4use crate::grammar::{Grammar, GrammarExpr, GrammarFormat, GrammarRule};
5
6/// Parses classic Backus-Naur Form text into the grammar IR.
7///
8/// # Errors
9///
10/// Returns [`GrammarImportError`] when the BNF text cannot be parsed, when a
11/// parsed construct cannot be represented, or when a non-terminal reference does
12/// not resolve to a rule in the imported grammar.
13pub fn import_bnf(text: &str) -> Result<Grammar, GrammarImportError> {
14    let normalized = normalize_empty_alternatives(text);
15    let parsed = BnfGrammar::parse_from::<::bnf::BNF>(&normalized)
16        .map_err(|error| parse_error(GrammarFormat::Bnf, error.to_string()))?;
17    let grammar = lower_grammar(&parsed)?;
18    validate_references(&grammar)?;
19    Ok(grammar)
20}
21
22fn lower_grammar(parsed: &BnfGrammar) -> Result<Grammar, GrammarImportError> {
23    let mut grammar = Grammar::new().with_source_format(GrammarFormat::Bnf);
24    for production in parsed.productions_iter() {
25        let name = match &production.lhs {
26            BnfTerm::Nonterminal(name) => name.clone(),
27            BnfTerm::Terminal(value) => {
28                return Err(unsupported_error(
29                    GrammarFormat::Bnf,
30                    format!("terminal production lhs {value:?}"),
31                ));
32            }
33        };
34        let alternatives = production
35            .rhs_iter()
36            .map(lower_expression)
37            .collect::<Vec<_>>();
38        let expr = lower_alternatives(alternatives);
39        grammar.add_rule(GrammarRule::new(name, expr));
40    }
41    Ok(grammar)
42}
43
44fn lower_alternatives(alternatives: Vec<GrammarExpr>) -> GrammarExpr {
45    if alternatives.iter().all(|expr| expr == &GrammarExpr::Empty) {
46        return GrammarExpr::Empty;
47    }
48    match alternatives.len() {
49        0 => GrammarExpr::Empty,
50        1 => alternatives
51            .into_iter()
52            .next()
53            .expect("one alternative exists"),
54        _ => GrammarExpr::Choice {
55            ordered: false,
56            alternatives,
57        },
58    }
59}
60
61fn lower_expression(expression: &BnfExpression) -> GrammarExpr {
62    let mut items = Vec::new();
63    for term in expression.terms_iter() {
64        let item = lower_term(term);
65        if item != GrammarExpr::Empty {
66            items.push(item);
67        }
68    }
69
70    match items.len() {
71        0 => GrammarExpr::Empty,
72        1 => items.remove(0),
73        _ => GrammarExpr::Sequence(items),
74    }
75}
76
77fn lower_term(term: &BnfTerm) -> GrammarExpr {
78    match term {
79        BnfTerm::Terminal(value) if value.is_empty() => GrammarExpr::Empty,
80        BnfTerm::Terminal(value) => GrammarExpr::Terminal(value.clone()),
81        BnfTerm::Nonterminal(name) => GrammarExpr::NonTerminal(name.clone()),
82    }
83}
84
85fn validate_references(grammar: &Grammar) -> Result<(), GrammarImportError> {
86    if let Some(name) = grammar.undefined_nonterminals().into_iter().next() {
87        return Err(parse_error(
88            GrammarFormat::Bnf,
89            format!("undefined non-terminal <{name}>"),
90        ));
91    }
92    Ok(())
93}
94
95fn normalize_empty_alternatives(text: &str) -> String {
96    text.lines()
97        .map(normalize_empty_alternatives_in_line)
98        .collect::<Vec<_>>()
99        .join("\n")
100}
101
102fn normalize_empty_alternatives_in_line(line: &str) -> String {
103    let Some(separator) = find_production_separator(line) else {
104        return line.to_string();
105    };
106    let (head, tail) = line.split_at(separator + "::=".len());
107    let (rhs, comment) = split_comment(tail);
108    let alternatives = split_alternatives(rhs);
109    if alternatives
110        .iter()
111        .all(|alternative| !alternative.trim().is_empty())
112    {
113        return line.to_string();
114    }
115
116    let normalized = alternatives
117        .into_iter()
118        .map(|alternative| {
119            if alternative.trim().is_empty() {
120                " '' ".to_string()
121            } else {
122                alternative
123            }
124        })
125        .collect::<Vec<_>>()
126        .join("|");
127    format!("{head}{normalized}{comment}")
128}
129
130fn find_production_separator(line: &str) -> Option<usize> {
131    let mut scanner = Scanner::new(line);
132    while let Some((index, character)) = scanner.next() {
133        if scanner.is_code() && character == ':' && line[index..].starts_with("::=") {
134            return Some(index);
135        }
136    }
137    None
138}
139
140fn split_comment(line: &str) -> (&str, &str) {
141    let mut scanner = Scanner::new(line);
142    while let Some((index, character)) = scanner.next() {
143        if scanner.is_code() && character == ';' {
144            return line.split_at(index);
145        }
146    }
147    (line, "")
148}
149
150fn split_alternatives(text: &str) -> Vec<String> {
151    let mut scanner = Scanner::new(text);
152    let mut start = 0;
153    let mut alternatives = Vec::new();
154    while let Some((index, character)) = scanner.next() {
155        if scanner.is_code() && character == '|' {
156            alternatives.push(text[start..index].to_string());
157            start = index + character.len_utf8();
158        }
159    }
160    alternatives.push(text[start..].to_string());
161    alternatives
162}
163
164#[derive(Clone, Copy, Debug, PartialEq, Eq)]
165enum ScanState {
166    Code,
167    SingleQuote,
168    DoubleQuote,
169    NonTerminal,
170}
171
172#[derive(Clone, Debug)]
173struct Scanner<'text> {
174    text: &'text str,
175    cursor: usize,
176    state: ScanState,
177}
178
179impl<'text> Scanner<'text> {
180    const fn new(text: &'text str) -> Self {
181        Self {
182            text,
183            cursor: 0,
184            state: ScanState::Code,
185        }
186    }
187
188    const fn is_code(&self) -> bool {
189        matches!(self.state, ScanState::Code)
190    }
191
192    fn next(&mut self) -> Option<(usize, char)> {
193        let rest = self.text.get(self.cursor..)?;
194        let mut chars = rest.char_indices();
195        let (_, character) = chars.next()?;
196        let index = self.cursor;
197        self.cursor += character.len_utf8();
198
199        match (self.state, character) {
200            (ScanState::Code, '\'') => self.state = ScanState::SingleQuote,
201            (ScanState::Code, '"') => self.state = ScanState::DoubleQuote,
202            (ScanState::Code, '<') => self.state = ScanState::NonTerminal,
203            (ScanState::SingleQuote, '\'') | (ScanState::DoubleQuote, '"') => {
204                self.state = ScanState::Code;
205            }
206            (ScanState::NonTerminal, '>') => self.state = ScanState::Code,
207            _ => {}
208        }
209
210        Some((index, character))
211    }
212}
meta_language/grammar/import/bnf.rs

meta_language/grammar/import/
bnf.rs
