meta_language/grammar/emit/
bnf.rs

1use crate::grammar::{CharClassItem, Grammar, GrammarExpr, GrammarFormat};
2
3use super::{
4    expanded_chars, finish_lines, ordered_rules, render_rule_line, unsupported_error, EmitReport,
5    GrammarEmitError, HelperRules, BNF_RULE_TEMPLATE,
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(quote_terminal(value)),
68            GrammarExpr::TerminalInsensitive(value) => {
69                self.report.add_lossy(format!(
70                    "BNF cannot preserve case-insensitive terminal {value:?}"
71                ));
72                Ok(quote_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::Capture { label, expr } => {
92                report_capture_loss(&mut self.report, GrammarFormat::Bnf, label.as_ref());
93                self.emit_expr(expr, context)
94            }
95        }
96    }
97
98    fn emit_choice(
99        &mut self,
100        ordered: bool,
101        alternatives: &[GrammarExpr],
102        context: BnfContext,
103    ) -> Result<String, GrammarEmitError> {
104        if ordered {
105            self.report
106                .add_lossy("BNF treats ordered choice as unordered choice");
107        }
108        if context == BnfContext::SequenceItem {
109            return self.emit_choice_helper(&GrammarExpr::Choice {
110                ordered,
111                alternatives: alternatives.to_vec(),
112            });
113        }
114
115        alternatives
116            .iter()
117            .map(|alternative| self.emit_expr(alternative, BnfContext::Production))
118            .collect::<Result<Vec<_>, _>>()
119            .map(|items| items.join(" | "))
120    }
121
122    fn emit_sequence(&mut self, items: &[GrammarExpr]) -> Result<String, GrammarEmitError> {
123        let mut emitted = Vec::new();
124        for item in items {
125            let text = self.emit_expr(item, BnfContext::SequenceItem)?;
126            if !text.is_empty() {
127                emitted.push(text);
128            }
129        }
130        Ok(emitted.join(" "))
131    }
132
133    fn emit_repeat(
134        &mut self,
135        expr: &GrammarExpr,
136        min: usize,
137        max: Option<usize>,
138    ) -> Result<String, GrammarEmitError> {
139        if max.is_some_and(|max| max < min) {
140            return Err(unsupported_error(
141                GrammarFormat::Bnf,
142                format!("Repeat with min {min} greater than max {max:?}"),
143            ));
144        }
145
146        let mut parts = Vec::new();
147        for _ in 0..min {
148            parts.push(self.emit_expr(expr, BnfContext::SequenceItem)?);
149        }
150
151        match max {
152            Some(max) => {
153                for _ in min..max {
154                    parts.push(self.emit_optional_helper(expr)?);
155                }
156            }
157            None => parts.push(self.emit_star_helper(expr)?),
158        }
159
160        Ok(parts
161            .into_iter()
162            .filter(|part| !part.is_empty())
163            .collect::<Vec<_>>()
164            .join(" "))
165    }
166
167    fn emit_choice_helper(&mut self, expr: &GrammarExpr) -> Result<String, GrammarEmitError> {
168        let (name, is_new) = self.helpers.reserve("choice", format!("{expr:?}"));
169        if is_new {
170            let body = self.emit_expr(expr, BnfContext::Production)?;
171            self.helpers.push(name.clone(), body);
172        }
173        Ok(nonterminal(&name))
174    }
175
176    fn emit_optional_helper(&mut self, expr: &GrammarExpr) -> Result<String, GrammarEmitError> {
177        if matches!(expr, GrammarExpr::Empty) {
178            return Ok(String::new());
179        }
180
181        let (name, is_new) = self.helpers.reserve("opt", format!("{expr:?}"));
182        if is_new {
183            let body = format!("{} |", self.emit_expr(expr, BnfContext::Production)?);
184            self.helpers.push(name.clone(), body);
185        }
186        Ok(nonterminal(&name))
187    }
188
189    fn emit_star_helper(&mut self, expr: &GrammarExpr) -> Result<String, GrammarEmitError> {
190        if matches!(expr, GrammarExpr::Empty) {
191            return Ok(String::new());
192        }
193
194        let (name, is_new) = self.helpers.reserve("star", format!("{expr:?}"));
195        if is_new {
196            let item = self.emit_expr(expr, BnfContext::SequenceItem)?;
197            let body = if item.is_empty() {
198                String::new()
199            } else {
200                format!("{item} {} |", nonterminal(&name))
201            };
202            self.helpers.push(name.clone(), body);
203        }
204        Ok(nonterminal(&name))
205    }
206
207    fn emit_plus_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("plus", 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} {} | {item}", nonterminal(&name))
219            };
220            self.helpers.push(name.clone(), body);
221        }
222        Ok(nonterminal(&name))
223    }
224
225    fn emit_range_helper(&mut self, start: char, end: char) -> Result<String, GrammarEmitError> {
226        let (name, is_new) = self
227            .helpers
228            .reserve("range", format!("{}:{}", start as u32, end as u32));
229        if is_new {
230            let body = expand_range(start, end)?
231                .into_iter()
232                .map(|character| quote_terminal(&character.to_string()))
233                .collect::<Vec<_>>()
234                .join(" | ");
235            self.helpers.push(name.clone(), body);
236        }
237        Ok(nonterminal(&name))
238    }
239
240    fn emit_char_class_helper(
241        &mut self,
242        negated: bool,
243        items: &[CharClassItem],
244    ) -> Result<String, GrammarEmitError> {
245        if negated {
246            return Err(unsupported_error(GrammarFormat::Bnf, "negated CharClass"));
247        }
248
249        let (name, is_new) = self.helpers.reserve("class", format!("{items:?}"));
250        if is_new {
251            let chars = expand_class_items(items)?;
252            if chars.is_empty() {
253                return Err(unsupported_error(GrammarFormat::Bnf, "empty CharClass"));
254            }
255            let body = chars
256                .into_iter()
257                .map(|character| quote_terminal(&character.to_string()))
258                .collect::<Vec<_>>()
259                .join(" | ");
260            self.helpers.push(name.clone(), body);
261        }
262        Ok(nonterminal(&name))
263    }
264}
265
266fn expand_range(start: char, end: char) -> Result<Vec<char>, GrammarEmitError> {
267    expanded_chars(
268        GrammarFormat::Bnf,
269        "CharRange",
270        start,
271        end,
272        MAX_BNF_EXPANSION,
273    )
274}
275
276fn expand_class_items(items: &[CharClassItem]) -> Result<Vec<char>, GrammarEmitError> {
277    let mut chars = Vec::new();
278    for item in items {
279        match item {
280            CharClassItem::Char(value) => chars.push(*value),
281            CharClassItem::Range(start, end) => chars.extend(expand_range(*start, *end)?),
282        }
283        if chars.len() > MAX_BNF_EXPANSION as usize {
284            return Err(unsupported_error(
285                GrammarFormat::Bnf,
286                format!("CharClass expands to more than {MAX_BNF_EXPANSION} characters"),
287            ));
288        }
289    }
290    Ok(chars)
291}
292
293fn report_capture_loss(report: &mut EmitReport, format: GrammarFormat, label: Option<&String>) {
294    if let Some(label) = label {
295        report.add_lossy(format!("{format} dropped capture label {label:?}"));
296    } else {
297        report.add_lossy(format!("{format} dropped anonymous capture"));
298    }
299}
300
301fn nonterminal(name: &str) -> String {
302    format!("<{name}>")
303}
304
305fn quote_terminal(value: &str) -> String {
306    let mut output = String::with_capacity(value.len() + 2);
307    output.push('"');
308    for character in value.chars() {
309        match character {
310            '"' => output.push_str("\\\""),
311            '\\' => output.push_str("\\\\"),
312            other => output.push(other),
313        }
314    }
315    output.push('"');
316    output
317}
meta_language/grammar/emit/bnf.rs

meta_language/grammar/emit/
bnf.rs
