meta_language/grammar/emit/
ebnf.rs

1use crate::grammar::{CharClassItem, Grammar, GrammarExpr, GrammarFormat};
2
3use super::{
4    EBNF_RULE_TEMPLATE, EmitReport, GrammarEmitError, HelperRules, expanded_chars, finish_lines,
5    ordered_rules, render_rule_line, unsupported_error,
6};
7
8const MAX_EBNF_EXPANSION: u32 = 256;
9
10/// Emits ISO/IEC 14977-style Extended Backus-Naur Form text from the grammar IR.
11///
12/// EBNF has native optional and repetition operators, but ISO EBNF does not have
13/// character ranges or character classes, so those constructs are expanded
14/// through deterministic helper productions.
15///
16/// # Errors
17///
18/// Returns [`GrammarEmitError`] when the grammar contains a construct ISO EBNF
19/// cannot represent, such as PEG predicates, negated character classes, or a
20/// character range too large to expand safely.
21pub fn emit_ebnf(grammar: &Grammar) -> Result<(String, EmitReport), GrammarEmitError> {
22    let mut emitter = EbnfEmitter::new(grammar);
23    let mut lines = Vec::new();
24
25    for rule in ordered_rules(grammar) {
26        let body = emitter.emit_expr(rule.expr(), Precedence::Choice)?;
27        lines.push(render_rule_line(EBNF_RULE_TEMPLATE, rule.name(), &body));
28    }
29    for helper in emitter.helpers.entries() {
30        lines.push(render_rule_line(
31            EBNF_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, PartialOrd, Ord)]
41enum Precedence {
42    Choice = 0,
43    Sequence = 1,
44    Atom = 2,
45}
46
47#[derive(Clone, Debug)]
48struct EbnfEmitter {
49    report: EmitReport,
50    helpers: HelperRules,
51}
52
53impl EbnfEmitter {
54    fn new(grammar: &Grammar) -> Self {
55        Self {
56            report: EmitReport::default(),
57            helpers: HelperRules::new(grammar),
58        }
59    }
60
61    fn emit_expr(
62        &mut self,
63        expr: &GrammarExpr,
64        parent: Precedence,
65    ) -> Result<String, GrammarEmitError> {
66        let (text, precedence) = match expr {
67            GrammarExpr::Empty => (String::new(), Precedence::Atom),
68            GrammarExpr::Terminal(value) => (quote_terminal(value), Precedence::Atom),
69            GrammarExpr::TerminalInsensitive(value) => {
70                self.report.add_lossy(format!(
71                    "EBNF cannot preserve case-insensitive terminal {value:?}"
72                ));
73                (quote_terminal(value), Precedence::Atom)
74            }
75            GrammarExpr::CharRange(start, end) => {
76                (self.emit_range_helper(*start, *end)?, Precedence::Atom)
77            }
78            GrammarExpr::CharClass { negated, items } => (
79                self.emit_char_class_helper(*negated, items)?,
80                Precedence::Atom,
81            ),
82            GrammarExpr::AnyChar => ("? any character ?".to_string(), Precedence::Atom),
83            GrammarExpr::NonTerminal(name) => (name.clone(), Precedence::Atom),
84            GrammarExpr::Choice {
85                ordered,
86                alternatives,
87            } => (
88                self.emit_choice(*ordered, alternatives)?,
89                Precedence::Choice,
90            ),
91            GrammarExpr::Sequence(items) => (self.emit_sequence(items)?, Precedence::Sequence),
92            GrammarExpr::Optional(inner) => {
93                let inner = self.emit_expr(inner, Precedence::Choice)?;
94                (format!("[ {inner} ]"), Precedence::Atom)
95            }
96            GrammarExpr::ZeroOrMore(inner) => {
97                let inner = self.emit_expr(inner, Precedence::Choice)?;
98                (format!("{{ {inner} }}"), Precedence::Atom)
99            }
100            GrammarExpr::OneOrMore(inner) => (
101                self.emit_repeat_sequence(inner, 1, None)?,
102                Precedence::Sequence,
103            ),
104            GrammarExpr::Repeat { expr, min, max } => (
105                self.emit_repeat_sequence(expr, *min, *max)?,
106                Precedence::Sequence,
107            ),
108            GrammarExpr::And(_) => return Err(unsupported_error(GrammarFormat::Ebnf, "And")),
109            GrammarExpr::Not(_) => return Err(unsupported_error(GrammarFormat::Ebnf, "Not")),
110            GrammarExpr::Feature(feature) => {
111                return Err(unsupported_error(GrammarFormat::Ebnf, feature.head()));
112            }
113            GrammarExpr::Capture { label, expr } => {
114                report_capture_loss(&mut self.report, GrammarFormat::Ebnf, label.as_ref());
115                return self.emit_expr(expr, parent);
116            }
117        };
118
119        if precedence < parent && !text.is_empty() {
120            Ok(format!("({text})"))
121        } else {
122            Ok(text)
123        }
124    }
125
126    fn emit_choice(
127        &mut self,
128        ordered: bool,
129        alternatives: &[GrammarExpr],
130    ) -> Result<String, GrammarEmitError> {
131        if ordered {
132            self.report
133                .add_lossy("EBNF treats ordered choice as unordered choice");
134        }
135        alternatives
136            .iter()
137            .map(|alternative| self.emit_expr(alternative, Precedence::Choice))
138            .collect::<Result<Vec<_>, _>>()
139            .map(|items| items.join(" | "))
140    }
141
142    fn emit_sequence(&mut self, items: &[GrammarExpr]) -> Result<String, GrammarEmitError> {
143        let mut emitted = Vec::new();
144        for item in items {
145            let text = self.emit_expr(item, Precedence::Sequence)?;
146            if !text.is_empty() {
147                emitted.push(text);
148            }
149        }
150        Ok(emitted.join(" , "))
151    }
152
153    fn emit_repeat_sequence(
154        &mut self,
155        expr: &GrammarExpr,
156        min: usize,
157        max: Option<usize>,
158    ) -> Result<String, GrammarEmitError> {
159        if max.is_some_and(|max| max < min) {
160            return Err(unsupported_error(
161                GrammarFormat::Ebnf,
162                format!("Repeat with min {min} greater than max {max:?}"),
163            ));
164        }
165
166        let mut parts = Vec::new();
167        for _ in 0..min {
168            let part = self.emit_expr(expr, Precedence::Sequence)?;
169            if !part.is_empty() {
170                parts.push(part);
171            }
172        }
173
174        if let Some(max) = max {
175            for _ in min..max {
176                let inner = self.emit_expr(expr, Precedence::Choice)?;
177                if !inner.is_empty() {
178                    parts.push(format!("[ {inner} ]"));
179                }
180            }
181        } else {
182            let inner = self.emit_expr(expr, Precedence::Choice)?;
183            if !inner.is_empty() {
184                parts.push(format!("{{ {inner} }}"));
185            }
186        }
187
188        Ok(parts.join(" , "))
189    }
190
191    fn emit_range_helper(&mut self, start: char, end: char) -> Result<String, GrammarEmitError> {
192        let (name, is_new) = self
193            .helpers
194            .reserve("range", format!("{}:{}", start as u32, end as u32));
195        if is_new {
196            let body = expand_range(start, end)?
197                .into_iter()
198                .map(|character| quote_terminal(&character.to_string()))
199                .collect::<Vec<_>>()
200                .join(" | ");
201            self.helpers.push(name.clone(), body);
202        }
203        Ok(name)
204    }
205
206    fn emit_char_class_helper(
207        &mut self,
208        negated: bool,
209        items: &[CharClassItem],
210    ) -> Result<String, GrammarEmitError> {
211        if negated {
212            return Err(unsupported_error(GrammarFormat::Ebnf, "negated CharClass"));
213        }
214
215        let (name, is_new) = self.helpers.reserve("class", format!("{items:?}"));
216        if is_new {
217            let chars = expand_class_items(items)?;
218            if chars.is_empty() {
219                return Err(unsupported_error(GrammarFormat::Ebnf, "empty CharClass"));
220            }
221            let body = chars
222                .into_iter()
223                .map(|character| quote_terminal(&character.to_string()))
224                .collect::<Vec<_>>()
225                .join(" | ");
226            self.helpers.push(name.clone(), body);
227        }
228        Ok(name)
229    }
230}
231
232fn expand_range(start: char, end: char) -> Result<Vec<char>, GrammarEmitError> {
233    expanded_chars(
234        GrammarFormat::Ebnf,
235        "CharRange",
236        start,
237        end,
238        MAX_EBNF_EXPANSION,
239    )
240}
241
242fn expand_class_items(items: &[CharClassItem]) -> Result<Vec<char>, GrammarEmitError> {
243    let mut chars = Vec::new();
244    for item in items {
245        match item {
246            CharClassItem::Char(value) => chars.push(*value),
247            CharClassItem::Range(start, end) => chars.extend(expand_range(*start, *end)?),
248        }
249        if chars.len() > MAX_EBNF_EXPANSION as usize {
250            return Err(unsupported_error(
251                GrammarFormat::Ebnf,
252                format!("CharClass expands to more than {MAX_EBNF_EXPANSION} characters"),
253            ));
254        }
255    }
256    Ok(chars)
257}
258
259fn report_capture_loss(report: &mut EmitReport, format: GrammarFormat, label: Option<&String>) {
260    if let Some(label) = label {
261        report.add_lossy(format!("{format} dropped capture label {label:?}"));
262    } else {
263        report.add_lossy(format!("{format} dropped anonymous capture"));
264    }
265}
266
267fn quote_terminal(value: &str) -> String {
268    let quote = if value.contains('"') && !value.contains('\'') {
269        '\''
270    } else {
271        '"'
272    };
273    let mut output = String::with_capacity(value.len() + 2);
274    output.push(quote);
275    for character in value.chars() {
276        match character {
277            '\\' => output.push_str("\\\\"),
278            '\n' => output.push_str("\\n"),
279            '\r' => output.push_str("\\r"),
280            '\t' => output.push_str("\\t"),
281            other if other == quote => {
282                output.push('\\');
283                output.push(other);
284            }
285            other => output.push(other),
286        }
287    }
288    output.push(quote);
289    output
290}
meta_language/grammar/emit/ebnf.rs

meta_language/grammar/emit/
ebnf.rs
