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

meta_language/grammar/emit/
mod.rs
