meta_language/grammar/emit/
bnf.rs

1use crate::grammar::{CharClassItem, Grammar, GrammarExpr, GrammarFormat};
2
3use super::{
4    BNF_RULE_TEMPLATE, EmitReport, GrammarEmitError, HelperRules, expanded_chars, finish_lines,
5    ordered_rules, render_rule_line, unsupported_error,
6};
7
8const MAX_BNF_EXPANSION: u32 = 256;
9
10/// Emits classic Backus-Naur Form text from the grammar IR.
11///
12/// BNF has no native grouping, optional, repetition, character range, or
13/// character class operators, so this emitter synthesizes deterministic helper
14/// productions when a faithful expansion is possible.
15///
16/// # Errors
17///
18/// Returns [`GrammarEmitError`] when the grammar contains a construct BNF cannot
19/// represent, such as PEG predicates, negated character classes, `AnyChar`, or a
20/// character range too large to expand safely.
21pub fn emit_bnf(grammar: &Grammar) -> Result<(String, EmitReport), GrammarEmitError> {
22    let mut emitter = BnfEmitter::new(grammar);
23    let mut lines = Vec::new();
24
25    for rule in ordered_rules(grammar) {
26        let body = emitter.emit_expr(rule.expr(), BnfContext::Production)?;
27        lines.push(render_rule_line(BNF_RULE_TEMPLATE, rule.name(), &body));
28    }
29    for helper in emitter.helpers.entries() {
30        lines.push(render_rule_line(
31            BNF_RULE_TEMPLATE,
32            &helper.name,
33            &helper.body,
34        ));
35    }
36
37    Ok((finish_lines(&lines), emitter.report))
38}
39
40#[derive(Clone, Copy, Debug, PartialEq, Eq)]
41enum BnfContext {
42    Production,
43    SequenceItem,
44}
45
46#[derive(Clone, Debug)]
47struct BnfEmitter {
48    report: EmitReport,
49    helpers: HelperRules,
50}
51
52impl BnfEmitter {
53    fn new(grammar: &Grammar) -> Self {
54        Self {
55            report: EmitReport::default(),
56            helpers: HelperRules::new(grammar),
57        }
58    }
59
60    fn emit_expr(
61        &mut self,
62        expr: &GrammarExpr,
63        context: BnfContext,
64    ) -> Result<String, GrammarEmitError> {
65        match expr {
66            GrammarExpr::Empty => Ok(String::new()),
67            GrammarExpr::Terminal(value) => Ok(self.emit_terminal(value)),
68            GrammarExpr::TerminalInsensitive(value) => {
69                self.report.add_lossy(format!(
70                    "BNF cannot preserve case-insensitive terminal {value:?}"
71                ));
72                Ok(self.emit_terminal(value))
73            }
74            GrammarExpr::CharRange(start, end) => self.emit_range_helper(*start, *end),
75            GrammarExpr::CharClass { negated, items } => {
76                self.emit_char_class_helper(*negated, items)
77            }
78            GrammarExpr::AnyChar => Err(unsupported_error(GrammarFormat::Bnf, "AnyChar")),
79            GrammarExpr::NonTerminal(name) => Ok(nonterminal(name)),
80            GrammarExpr::Choice {
81                ordered,
82                alternatives,
83            } => self.emit_choice(*ordered, alternatives, context),
84            GrammarExpr::Sequence(items) => self.emit_sequence(items),
85            GrammarExpr::Optional(inner) => self.emit_optional_helper(inner),
86            GrammarExpr::ZeroOrMore(inner) => self.emit_star_helper(inner),
87            GrammarExpr::OneOrMore(inner) => self.emit_plus_helper(inner),
88            GrammarExpr::Repeat { expr, min, max } => self.emit_repeat(expr, *min, *max),
89            GrammarExpr::And(_) => Err(unsupported_error(GrammarFormat::Bnf, "And")),
90            GrammarExpr::Not(_) => Err(unsupported_error(GrammarFormat::Bnf, "Not")),
91            GrammarExpr::Feature(feature) => {
92                Err(unsupported_error(GrammarFormat::Bnf, feature.head()))
93            }
94            GrammarExpr::Capture { label, expr } => {
95                report_capture_loss(&mut self.report, GrammarFormat::Bnf, label.as_ref());
96                self.emit_expr(expr, context)
97            }
98        }
99    }
100
101    /// Classic BNF terminals have no escapes, so a terminal containing both
102    /// quote characters is emitted as a sequence of separately quoted runs.
103    fn emit_terminal(&mut self, value: &str) -> String {
104        let runs = quote_runs(value);
105        if runs.len() > 1 {
106            self.report.add_lossy(format!(
107                "BNF splits terminal {value:?} containing both quote characters"
108            ));
109        }
110        runs.iter()
111            .map(|run| quote_terminal(run))
112            .collect::<Vec<_>>()
113            .join(" ")
114    }
115
116    fn emit_choice(
117        &mut self,
118        ordered: bool,
119        alternatives: &[GrammarExpr],
120        context: BnfContext,
121    ) -> Result<String, GrammarEmitError> {
122        if ordered {
123            self.report
124                .add_lossy("BNF treats ordered choice as unordered choice");
125        }
126        if context == BnfContext::SequenceItem {
127            return self.emit_choice_helper(&GrammarExpr::Choice {
128                ordered,
129                alternatives: alternatives.to_vec(),
130            });
131        }
132
133        alternatives
134            .iter()
135            .map(|alternative| self.emit_expr(alternative, BnfContext::Production))
136            .collect::<Result<Vec<_>, _>>()
137            .map(|items| items.join(" | "))
138    }
139
140    fn emit_sequence(&mut self, items: &[GrammarExpr]) -> Result<String, GrammarEmitError> {
141        let mut emitted = Vec::new();
142        for item in items {
143            let text = self.emit_expr(item, BnfContext::SequenceItem)?;
144            if !text.is_empty() {
145                emitted.push(text);
146            }
147        }
148        Ok(emitted.join(" "))
149    }
150
151    fn emit_repeat(
152        &mut self,
153        expr: &GrammarExpr,
154        min: usize,
155        max: Option<usize>,
156    ) -> Result<String, GrammarEmitError> {
157        if max.is_some_and(|max| max < min) {
158            return Err(unsupported_error(
159                GrammarFormat::Bnf,
160                format!("Repeat with min {min} greater than max {max:?}"),
161            ));
162        }
163
164        let mut parts = Vec::new();
165        for _ in 0..min {
166            parts.push(self.emit_expr(expr, BnfContext::SequenceItem)?);
167        }
168
169        match max {
170            Some(max) => {
171                for _ in min..max {
172                    parts.push(self.emit_optional_helper(expr)?);
173                }
174            }
175            None => parts.push(self.emit_star_helper(expr)?),
176        }
177
178        Ok(parts
179            .into_iter()
180            .filter(|part| !part.is_empty())
181            .collect::<Vec<_>>()
182            .join(" "))
183    }
184
185    fn emit_choice_helper(&mut self, expr: &GrammarExpr) -> Result<String, GrammarEmitError> {
186        let (name, is_new) = self.helpers.reserve("choice", format!("{expr:?}"));
187        if is_new {
188            let body = self.emit_expr(expr, BnfContext::Production)?;
189            self.helpers.push(name.clone(), body);
190        }
191        Ok(nonterminal(&name))
192    }
193
194    fn emit_optional_helper(&mut self, expr: &GrammarExpr) -> Result<String, GrammarEmitError> {
195        if matches!(expr, GrammarExpr::Empty) {
196            return Ok(String::new());
197        }
198
199        let (name, is_new) = self.helpers.reserve("opt", format!("{expr:?}"));
200        if is_new {
201            let body = format!("{} |", self.emit_expr(expr, BnfContext::Production)?);
202            self.helpers.push(name.clone(), body);
203        }
204        Ok(nonterminal(&name))
205    }
206
207    fn emit_star_helper(&mut self, expr: &GrammarExpr) -> Result<String, GrammarEmitError> {
208        if matches!(expr, GrammarExpr::Empty) {
209            return Ok(String::new());
210        }
211
212        let (name, is_new) = self.helpers.reserve("star", format!("{expr:?}"));
213        if is_new {
214            let item = self.emit_expr(expr, BnfContext::SequenceItem)?;
215            let body = if item.is_empty() {
216                String::new()
217            } else {
218                format!("{item} {} |", nonterminal(&name))
219            };
220            self.helpers.push(name.clone(), body);
221        }
222        Ok(nonterminal(&name))
223    }
224
225    fn emit_plus_helper(&mut self, expr: &GrammarExpr) -> Result<String, GrammarEmitError> {
226        if matches!(expr, GrammarExpr::Empty) {
227            return Ok(String::new());
228        }
229
230        let (name, is_new) = self.helpers.reserve("plus", format!("{expr:?}"));
231        if is_new {
232            let item = self.emit_expr(expr, BnfContext::SequenceItem)?;
233            let body = if item.is_empty() {
234                String::new()
235            } else {
236                format!("{item} {} | {item}", nonterminal(&name))
237            };
238            self.helpers.push(name.clone(), body);
239        }
240        Ok(nonterminal(&name))
241    }
242
243    fn emit_range_helper(&mut self, start: char, end: char) -> Result<String, GrammarEmitError> {
244        let (name, is_new) = self
245            .helpers
246            .reserve("range", format!("{}:{}", start as u32, end as u32));
247        if is_new {
248            let body = expand_range(start, end)?
249                .into_iter()
250                .map(|character| quote_terminal(&character.to_string()))
251                .collect::<Vec<_>>()
252                .join(" | ");
253            self.helpers.push(name.clone(), body);
254        }
255        Ok(nonterminal(&name))
256    }
257
258    fn emit_char_class_helper(
259        &mut self,
260        negated: bool,
261        items: &[CharClassItem],
262    ) -> Result<String, GrammarEmitError> {
263        if negated {
264            return Err(unsupported_error(GrammarFormat::Bnf, "negated CharClass"));
265        }
266
267        let (name, is_new) = self.helpers.reserve("class", format!("{items:?}"));
268        if is_new {
269            let chars = expand_class_items(items)?;
270            if chars.is_empty() {
271                return Err(unsupported_error(GrammarFormat::Bnf, "empty CharClass"));
272            }
273            let body = chars
274                .into_iter()
275                .map(|character| quote_terminal(&character.to_string()))
276                .collect::<Vec<_>>()
277                .join(" | ");
278            self.helpers.push(name.clone(), body);
279        }
280        Ok(nonterminal(&name))
281    }
282}
283
284fn expand_range(start: char, end: char) -> Result<Vec<char>, GrammarEmitError> {
285    expanded_chars(
286        GrammarFormat::Bnf,
287        "CharRange",
288        start,
289        end,
290        MAX_BNF_EXPANSION,
291    )
292}
293
294fn expand_class_items(items: &[CharClassItem]) -> Result<Vec<char>, GrammarEmitError> {
295    let mut chars = Vec::new();
296    for item in items {
297        match item {
298            CharClassItem::Char(value) => chars.push(*value),
299            CharClassItem::Range(start, end) => chars.extend(expand_range(*start, *end)?),
300        }
301        if chars.len() > MAX_BNF_EXPANSION as usize {
302            return Err(unsupported_error(
303                GrammarFormat::Bnf,
304                format!("CharClass expands to more than {MAX_BNF_EXPANSION} characters"),
305            ));
306        }
307    }
308    Ok(chars)
309}
310
311fn report_capture_loss(report: &mut EmitReport, format: GrammarFormat, label: Option<&String>) {
312    if let Some(label) = label {
313        report.add_lossy(format!("{format} dropped capture label {label:?}"));
314    } else {
315        report.add_lossy(format!("{format} dropped anonymous capture"));
316    }
317}
318
319fn nonterminal(name: &str) -> String {
320    format!("<{name}>")
321}
322
323fn quote_runs(value: &str) -> Vec<String> {
324    let mut runs = Vec::new();
325    let mut run = String::new();
326    for character in value.chars() {
327        let conflicts =
328            (character == '"' && run.contains('\'')) || (character == '\'' && run.contains('"'));
329        if conflicts {
330            runs.push(std::mem::take(&mut run));
331        }
332        run.push(character);
333    }
334    runs.push(run);
335    runs
336}
337
338fn quote_terminal(value: &str) -> String {
339    let quote = if value.contains('"') { '\'' } else { '"' };
340    format!("{quote}{value}{quote}")
341}
meta_language/grammar/emit/bnf.rs

meta_language/grammar/emit/
bnf.rs
