meta_language/grammar/emit/
mod.rs

1//! Emitters for external grammar definition formats.
2
3use std::collections::{BTreeMap, BTreeSet};
4use std::error::Error;
5use std::fmt;
6
7use crate::grammar::{Grammar, GrammarExpr, GrammarFormat, GrammarRule};
8use crate::translation_rules::TranslationTemplate;
9
10mod abnf;
11mod bnf;
12mod ebnf;
13mod gbnf;
14mod javascript;
15mod pest;
16mod rust;
17mod tree_sitter;
18
19pub use abnf::emit_abnf;
20pub use bnf::emit_bnf;
21pub use ebnf::emit_ebnf;
22pub use gbnf::emit_gbnf;
23pub use javascript::{emit_javascript_parser, emit_peggy, JsParserArtifacts};
24pub use pest::emit_pest;
25pub use rust::{emit_rust_parser, render_rust_type, RustParserArtifacts};
26pub use tree_sitter::{emit_tree_sitter_grammar_js, emit_tree_sitter_grammar_js_with_report};
27
28pub(super) const BNF_RULE_TEMPLATE: &str = "<{name}> ::= {body}";
29pub(super) const EBNF_RULE_TEMPLATE: &str = "{name} = {body} ;";
30pub(super) const ABNF_RULE_TEMPLATE: &str = "{name} = {body}";
31pub(super) const GBNF_RULE_TEMPLATE: &str = "{name} ::= {body}";
32pub(super) const PEST_RULE_TEMPLATE: &str = "{name} = {modifier}{{ {body} }}";
33
34/// Error raised while emitting an external grammar notation.
35#[derive(Clone, Debug, PartialEq, Eq)]
36pub enum GrammarEmitError {
37    /// The target notation cannot represent this construct at all.
38    Unsupported {
39        /// Grammar format being emitted.
40        format: GrammarFormat,
41        /// Construct name or summary.
42        construct: String,
43    },
44}
45
46impl fmt::Display for GrammarEmitError {
47    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
48        match self {
49            Self::Unsupported { format, construct } => {
50                write!(
51                    formatter,
52                    "{format} emit unsupported construct: {construct}"
53                )
54            }
55        }
56    }
57}
58
59impl Error for GrammarEmitError {}
60
61/// Non-fatal fidelity notes collected while emitting a grammar.
62#[derive(Clone, Debug, Default, PartialEq, Eq)]
63pub struct EmitReport {
64    /// Fidelity-reducing conversions, such as dropped labels or case flags.
65    pub lossy: Vec<String>,
66}
67
68impl EmitReport {
69    pub(super) fn add_lossy(&mut self, note: impl Into<String>) {
70        self.lossy.push(note.into());
71    }
72}
73
74pub(super) fn unsupported_error(
75    format: GrammarFormat,
76    construct: impl Into<String>,
77) -> GrammarEmitError {
78    GrammarEmitError::Unsupported {
79        format,
80        construct: construct.into(),
81    }
82}
83
84pub(super) fn render_rule_line(template: &str, name: &str, body: &str) -> String {
85    let template = TranslationTemplate::new(template);
86    render_template_source(template.source(), name, "", body)
87}
88
89pub(super) fn render_rule_line_with_modifier(
90    template: &str,
91    name: &str,
92    modifier: &str,
93    body: &str,
94) -> String {
95    let template = TranslationTemplate::new(template);
96    render_template_source(template.source(), name, modifier, body)
97}
98
99fn render_template_source(source: &str, name: &str, modifier: &str, body: &str) -> String {
100    let mut output = String::new();
101    let mut chars = source.chars().peekable();
102    while let Some(character) = chars.next() {
103        match character {
104            '{' if chars.peek() == Some(&'{') => {
105                chars.next();
106                output.push('{');
107            }
108            '{' => render_placeholder(&mut output, &mut chars, name, modifier, body),
109            '}' if chars.peek() == Some(&'}') => {
110                chars.next();
111                output.push('}');
112            }
113            other => output.push(other),
114        }
115    }
116    output
117}
118
119fn render_placeholder<I>(
120    output: &mut String,
121    chars: &mut std::iter::Peekable<I>,
122    name: &str,
123    modifier: &str,
124    body: &str,
125) where
126    I: Iterator<Item = char>,
127{
128    let mut placeholder = String::new();
129    let mut closed = false;
130    for next in chars.by_ref() {
131        if next == '}' {
132            closed = true;
133            break;
134        }
135        placeholder.push(next);
136    }
137
138    if !closed {
139        output.push('{');
140        output.push_str(&placeholder);
141        return;
142    }
143
144    match placeholder.trim() {
145        "name" => output.push_str(name),
146        "modifier" => output.push_str(modifier),
147        "body" => output.push_str(body),
148        _ => {
149            output.push('{');
150            output.push_str(&placeholder);
151            output.push('}');
152        }
153    }
154}
155
156pub(super) fn ordered_rules(grammar: &Grammar) -> Vec<&GrammarRule> {
157    let rules = grammar.rules();
158    let Some(start) = grammar.start() else {
159        return rules.iter().collect();
160    };
161    let Some(start_index) = rules.iter().position(|rule| rule.name() == start) else {
162        return rules.iter().collect();
163    };
164
165    let mut ordered = Vec::with_capacity(rules.len());
166    ordered.push(&rules[start_index]);
167    ordered.extend(rules[..start_index].iter());
168    ordered.extend(rules[start_index + 1..].iter());
169    ordered
170}
171
172pub(super) fn peg_choice_alternatives(
173    ordered: bool,
174    alternatives: &[GrammarExpr],
175) -> Vec<&GrammarExpr> {
176    let mut indexed = alternatives.iter().enumerate().collect::<Vec<_>>();
177    if !ordered && has_literal_prefix_conflict(alternatives) {
178        indexed.sort_by(|(left_index, left), (right_index, right)| {
179            expr_required_width(right)
180                .cmp(&expr_required_width(left))
181                .then_with(|| left_index.cmp(right_index))
182        });
183    }
184    indexed
185        .into_iter()
186        .map(|(_index, alternative)| alternative)
187        .collect()
188}
189
190fn expr_required_width(expr: &GrammarExpr) -> usize {
191    match expr {
192        GrammarExpr::Empty
193        | GrammarExpr::And(_)
194        | GrammarExpr::Not(_)
195        | GrammarExpr::Optional(_)
196        | GrammarExpr::ZeroOrMore(_) => 0,
197        GrammarExpr::Terminal(value) | GrammarExpr::TerminalInsensitive(value) => value.len(),
198        GrammarExpr::CharRange(_, _)
199        | GrammarExpr::CharClass { .. }
200        | GrammarExpr::AnyChar
201        | GrammarExpr::NonTerminal(_) => 1,
202        GrammarExpr::Choice { alternatives, .. } => alternatives
203            .iter()
204            .map(expr_required_width)
205            .max()
206            .unwrap_or(0),
207        GrammarExpr::Sequence(items) => items
208            .iter()
209            .map(expr_required_width)
210            .fold(0_usize, usize::saturating_add),
211        GrammarExpr::OneOrMore(inner) | GrammarExpr::Capture { expr: inner, .. } => {
212            expr_required_width(inner)
213        }
214        GrammarExpr::Repeat { expr, min, .. } => expr_required_width(expr).saturating_mul(*min),
215    }
216}
217
218fn has_literal_prefix_conflict(alternatives: &[GrammarExpr]) -> bool {
219    let yields = alternatives
220        .iter()
221        .filter_map(literal_yield)
222        .collect::<Vec<_>>();
223    yields.iter().enumerate().any(|(index, left)| {
224        yields
225            .iter()
226            .skip(index + 1)
227            .any(|right| literal_prefix_conflict(left, right))
228    })
229}
230
231fn literal_prefix_conflict(left: &str, right: &str) -> bool {
232    if left.is_empty() || right.is_empty() || left == right {
233        return false;
234    }
235    left.starts_with(right) || right.starts_with(left)
236}
237
238fn literal_yield(expr: &GrammarExpr) -> Option<String> {
239    match expr {
240        GrammarExpr::Empty => Some(String::new()),
241        GrammarExpr::Terminal(value) | GrammarExpr::TerminalInsensitive(value) => {
242            Some(value.clone())
243        }
244        GrammarExpr::Sequence(items) => {
245            let mut output = String::new();
246            for item in items {
247                output.push_str(&literal_yield(item)?);
248            }
249            Some(output)
250        }
251        GrammarExpr::Capture { expr, .. } => literal_yield(expr),
252        GrammarExpr::CharRange(_, _)
253        | GrammarExpr::CharClass { .. }
254        | GrammarExpr::AnyChar
255        | GrammarExpr::NonTerminal(_)
256        | GrammarExpr::Choice { .. }
257        | GrammarExpr::Optional(_)
258        | GrammarExpr::ZeroOrMore(_)
259        | GrammarExpr::OneOrMore(_)
260        | GrammarExpr::Repeat { .. }
261        | GrammarExpr::And(_)
262        | GrammarExpr::Not(_) => None,
263    }
264}
265
266pub(super) fn finish_lines(lines: &[String]) -> String {
267    if lines.is_empty() {
268        String::new()
269    } else {
270        let mut output = lines.join("\n");
271        output.push('\n');
272        output
273    }
274}
275
276pub(super) fn expanded_chars(
277    format: GrammarFormat,
278    construct: &str,
279    start: char,
280    end: char,
281    max_chars: u32,
282) -> Result<Vec<char>, GrammarEmitError> {
283    let start = start as u32;
284    let end = end as u32;
285    if start > end {
286        return Err(unsupported_error(
287            format,
288            format!("{construct} has descending bounds U+{start:04X}..=U+{end:04X}"),
289        ));
290    }
291    let span = end - start + 1;
292    if span > max_chars {
293        return Err(unsupported_error(
294            format,
295            format!("{construct} expands to {span} characters"),
296        ));
297    }
298    Ok((start..=end).filter_map(char::from_u32).collect())
299}
300
301#[derive(Clone, Debug, PartialEq, Eq)]
302pub(super) struct HelperRule {
303    pub(super) name: String,
304    pub(super) body: String,
305}
306
307#[derive(Clone, Debug)]
308pub(super) struct HelperRules {
309    used_names: BTreeSet<String>,
310    names_by_key: BTreeMap<String, String>,
311    entries: Vec<HelperRule>,
312    next_id: usize,
313}
314
315impl HelperRules {
316    pub(super) fn new(grammar: &Grammar) -> Self {
317        Self {
318            used_names: grammar
319                .rules()
320                .iter()
321                .map(|rule| rule.name().to_string())
322                .collect(),
323            names_by_key: BTreeMap::new(),
324            entries: Vec::new(),
325            next_id: 0,
326        }
327    }
328
329    pub(super) fn reserve(&mut self, kind: &str, key: impl Into<String>) -> (String, bool) {
330        let key = format!("{kind}:{}", key.into());
331        if let Some(name) = self.names_by_key.get(&key) {
332            return (name.clone(), false);
333        }
334
335        let name = self.next_name(kind);
336        self.names_by_key.insert(key, name.clone());
337        (name, true)
338    }
339
340    pub(super) fn push(&mut self, name: String, body: String) {
341        self.entries.push(HelperRule { name, body });
342    }
343
344    pub(super) fn entries(&self) -> &[HelperRule] {
345        &self.entries
346    }
347
348    fn next_name(&mut self, kind: &str) -> String {
349        loop {
350            let name = format!("ml{kind}{}", self.next_id);
351            self.next_id += 1;
352            if self.used_names.insert(name.clone()) {
353                return name;
354            }
355        }
356    }
357}
meta_language/grammar/emit/mod.rs

meta_language/grammar/emit/
mod.rs
