meta_language/grammar/emit/
ebnf.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, EBNF_RULE_TEMPLATE,
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::Capture { label, expr } => {
111                report_capture_loss(&mut self.report, GrammarFormat::Ebnf, label.as_ref());
112                return self.emit_expr(expr, parent);
113            }
114        };
115
116        if precedence < parent && !text.is_empty() {
117            Ok(format!("({text})"))
118        } else {
119            Ok(text)
120        }
121    }
122
123    fn emit_choice(
124        &mut self,
125        ordered: bool,
126        alternatives: &[GrammarExpr],
127    ) -> Result<String, GrammarEmitError> {
128        if ordered {
129            self.report
130                .add_lossy("EBNF treats ordered choice as unordered choice");
131        }
132        alternatives
133            .iter()
134            .map(|alternative| self.emit_expr(alternative, Precedence::Choice))
135            .collect::<Result<Vec<_>, _>>()
136            .map(|items| items.join(" | "))
137    }
138
139    fn emit_sequence(&mut self, items: &[GrammarExpr]) -> Result<String, GrammarEmitError> {
140        let mut emitted = Vec::new();
141        for item in items {
142            let text = self.emit_expr(item, Precedence::Sequence)?;
143            if !text.is_empty() {
144                emitted.push(text);
145            }
146        }
147        Ok(emitted.join(" , "))
148    }
149
150    fn emit_repeat_sequence(
151        &mut self,
152        expr: &GrammarExpr,
153        min: usize,
154        max: Option<usize>,
155    ) -> Result<String, GrammarEmitError> {
156        if max.is_some_and(|max| max < min) {
157            return Err(unsupported_error(
158                GrammarFormat::Ebnf,
159                format!("Repeat with min {min} greater than max {max:?}"),
160            ));
161        }
162
163        let mut parts = Vec::new();
164        for _ in 0..min {
165            let part = self.emit_expr(expr, Precedence::Sequence)?;
166            if !part.is_empty() {
167                parts.push(part);
168            }
169        }
170
171        if let Some(max) = max {
172            for _ in min..max {
173                let inner = self.emit_expr(expr, Precedence::Choice)?;
174                if !inner.is_empty() {
175                    parts.push(format!("[ {inner} ]"));
176                }
177            }
178        } else {
179            let inner = self.emit_expr(expr, Precedence::Choice)?;
180            if !inner.is_empty() {
181                parts.push(format!("{{ {inner} }}"));
182            }
183        }
184
185        Ok(parts.join(" , "))
186    }
187
188    fn emit_range_helper(&mut self, start: char, end: char) -> Result<String, GrammarEmitError> {
189        let (name, is_new) = self
190            .helpers
191            .reserve("range", format!("{}:{}", start as u32, end as u32));
192        if is_new {
193            let body = expand_range(start, end)?
194                .into_iter()
195                .map(|character| quote_terminal(&character.to_string()))
196                .collect::<Vec<_>>()
197                .join(" | ");
198            self.helpers.push(name.clone(), body);
199        }
200        Ok(name)
201    }
202
203    fn emit_char_class_helper(
204        &mut self,
205        negated: bool,
206        items: &[CharClassItem],
207    ) -> Result<String, GrammarEmitError> {
208        if negated {
209            return Err(unsupported_error(GrammarFormat::Ebnf, "negated CharClass"));
210        }
211
212        let (name, is_new) = self.helpers.reserve("class", format!("{items:?}"));
213        if is_new {
214            let chars = expand_class_items(items)?;
215            if chars.is_empty() {
216                return Err(unsupported_error(GrammarFormat::Ebnf, "empty CharClass"));
217            }
218            let body = chars
219                .into_iter()
220                .map(|character| quote_terminal(&character.to_string()))
221                .collect::<Vec<_>>()
222                .join(" | ");
223            self.helpers.push(name.clone(), body);
224        }
225        Ok(name)
226    }
227}
228
229fn expand_range(start: char, end: char) -> Result<Vec<char>, GrammarEmitError> {
230    expanded_chars(
231        GrammarFormat::Ebnf,
232        "CharRange",
233        start,
234        end,
235        MAX_EBNF_EXPANSION,
236    )
237}
238
239fn expand_class_items(items: &[CharClassItem]) -> Result<Vec<char>, GrammarEmitError> {
240    let mut chars = Vec::new();
241    for item in items {
242        match item {
243            CharClassItem::Char(value) => chars.push(*value),
244            CharClassItem::Range(start, end) => chars.extend(expand_range(*start, *end)?),
245        }
246        if chars.len() > MAX_EBNF_EXPANSION as usize {
247            return Err(unsupported_error(
248                GrammarFormat::Ebnf,
249                format!("CharClass expands to more than {MAX_EBNF_EXPANSION} characters"),
250            ));
251        }
252    }
253    Ok(chars)
254}
255
256fn report_capture_loss(report: &mut EmitReport, format: GrammarFormat, label: Option<&String>) {
257    if let Some(label) = label {
258        report.add_lossy(format!("{format} dropped capture label {label:?}"));
259    } else {
260        report.add_lossy(format!("{format} dropped anonymous capture"));
261    }
262}
263
264fn quote_terminal(value: &str) -> String {
265    let quote = if value.contains('"') && !value.contains('\'') {
266        '\''
267    } else {
268        '"'
269    };
270    let escaped = value.replace(quote, &quote.to_string().repeat(2));
271    format!("{quote}{escaped}{quote}")
272}
meta_language/grammar/emit/ebnf.rs

meta_language/grammar/emit/
ebnf.rs
