meta_language/grammar/emit/
gbnf.rs

1use std::collections::{BTreeMap, BTreeSet};
2use std::fmt::Write as _;
3
4use crate::grammar::{CharClassItem, Grammar, GrammarExpr, GrammarFormat, GrammarRule};
5
6use super::{
7    EmitReport, GBNF_RULE_TEMPLATE, GrammarEmitError, finish_lines, render_rule_line,
8    unsupported_error,
9};
10
11const ANY_CHAR_CLASS: &str = r"[\x00-\U0010FFFF]";
12
13/// Emits GGML BNF text for grammar-constrained LLM decoding.
14///
15/// The output is deterministic, starts with the mandatory GBNF `root` rule, and
16/// uses GBNF's native alternation, grouping, character classes, and counted
17/// repetition operators. The IR's `AnyChar` wildcard is emitted as the documented
18/// full Unicode scalar range class `[\x00-\U0010FFFF]`.
19///
20/// # Errors
21///
22/// Returns [`GrammarEmitError`] when the grammar contains a construct GBNF
23/// cannot faithfully represent, such as general PEG lookahead predicates, empty
24/// character classes, descending ranges, invalid repeat bounds, or a configured
25/// start rule that is not present in the grammar.
26///
27/// Rule documentation is written as `#` comment lines above the rule, as the
28/// GBNF importer reads it, with a lossy note when it would not read back
29/// verbatim.
30pub fn emit_gbnf(grammar: &Grammar) -> Result<(String, EmitReport), GrammarEmitError> {
31    if grammar.rules().is_empty() {
32        return Ok((String::new(), EmitReport::default()));
33    }
34
35    let start_index = start_rule_index(grammar).ok_or_else(|| {
36        unsupported_error(
37            GrammarFormat::Gbnf,
38            "configured start rule is not present in the grammar",
39        )
40    })?;
41    let start_name = grammar.rules()[start_index].name();
42
43    let mut report = EmitReport::default();
44    let names = NamePlan::new(grammar, start_name, &mut report);
45    let mut emitter = GbnfEmitter { report, names };
46    let mut lines = Vec::new();
47
48    let start_rule = &grammar.rules()[start_index];
49    lines.extend(doc_comments(start_rule, &mut emitter.report));
50    let start_body = emitter.emit_expr(start_rule.expr(), Precedence::Choice)?;
51    lines.push(render_rule_line(GBNF_RULE_TEMPLATE, "root", &start_body));
52
53    for (index, rule) in grammar.rules().iter().enumerate() {
54        if index == start_index {
55            continue;
56        }
57        lines.extend(doc_comments(rule, &mut emitter.report));
58        let name = emitter.names.name_for(rule.name());
59        let body = emitter.emit_expr(rule.expr(), Precedence::Choice)?;
60        lines.push(render_rule_line(GBNF_RULE_TEMPLATE, &name, &body));
61    }
62
63    Ok((finish_lines(&lines), emitter.report))
64}
65
66/// The `#` comment lines the GBNF importer reads back as the rule's
67/// documentation: each documentation line, prefixed with `# ` unless it already
68/// is a comment.
69fn doc_comments(rule: &GrammarRule, report: &mut EmitReport) -> Vec<String> {
70    let Some(doc) = rule.doc() else {
71        return Vec::new();
72    };
73    let lines: Vec<String> = doc
74        .split('\n')
75        .map(|line| {
76            if line.starts_with('#') {
77                line.to_string()
78            } else {
79                format!("# {line}")
80            }
81        })
82        .collect();
83    let reimported = lines
84        .iter()
85        .map(|line| line.trim())
86        .collect::<Vec<_>>()
87        .join("\n");
88    if lines.iter().any(|line| line.contains('\r')) || reimported != doc {
89        report.add_lossy(format!(
90            "GBNF re-imports the documentation of rule {:?} as {reimported:?}",
91            rule.name()
92        ));
93    }
94    lines
95}
96
97#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
98enum Precedence {
99    Choice = 0,
100    Sequence = 1,
101    Postfix = 2,
102    Atom = 3,
103}
104
105#[derive(Clone, Debug)]
106struct GbnfEmitter {
107    report: EmitReport,
108    names: NamePlan,
109}
110
111impl GbnfEmitter {
112    fn emit_expr(
113        &mut self,
114        expr: &GrammarExpr,
115        parent: Precedence,
116    ) -> Result<String, GrammarEmitError> {
117        let (text, precedence) = match expr {
118            GrammarExpr::Empty => (quote_terminal(""), Precedence::Atom),
119            GrammarExpr::Terminal(value) => (quote_terminal(value), Precedence::Atom),
120            GrammarExpr::TerminalInsensitive(value) => {
121                self.report.add_lossy(format!(
122                    "GBNF expands case-insensitive terminal {value:?} to character classes"
123                ));
124                (emit_case_insensitive_terminal(value), Precedence::Sequence)
125            }
126            GrammarExpr::CharRange(start, end) => {
127                (emit_char_range(*start, *end)?, Precedence::Atom)
128            }
129            GrammarExpr::CharClass { negated, items } => {
130                (emit_char_class(*negated, items)?, Precedence::Atom)
131            }
132            GrammarExpr::AnyChar => (ANY_CHAR_CLASS.to_string(), Precedence::Atom),
133            GrammarExpr::NonTerminal(name) => (self.names.name_for(name), Precedence::Atom),
134            GrammarExpr::Choice {
135                ordered,
136                alternatives,
137            } => (
138                self.emit_choice(*ordered, alternatives)?,
139                Precedence::Choice,
140            ),
141            GrammarExpr::Sequence(items) => (self.emit_sequence(items)?, Precedence::Sequence),
142            GrammarExpr::Optional(inner) => {
143                let inner = self.emit_expr(inner, Precedence::Choice)?;
144                (format!("({inner})?"), Precedence::Postfix)
145            }
146            GrammarExpr::ZeroOrMore(inner) => {
147                let inner = self.emit_expr(inner, Precedence::Choice)?;
148                (format!("({inner})*"), Precedence::Postfix)
149            }
150            GrammarExpr::OneOrMore(inner) => {
151                let inner = self.emit_expr(inner, Precedence::Choice)?;
152                (format!("({inner})+"), Precedence::Postfix)
153            }
154            GrammarExpr::Repeat { expr, min, max } => {
155                (self.emit_repeat(expr, *min, *max)?, Precedence::Postfix)
156            }
157            GrammarExpr::And(_) => {
158                return Err(unsupported_error(GrammarFormat::Gbnf, "positive-predicate"));
159            }
160            GrammarExpr::Not(_) => {
161                return Err(unsupported_error(GrammarFormat::Gbnf, "negative-predicate"));
162            }
163            GrammarExpr::Feature(feature) => {
164                return Err(unsupported_error(GrammarFormat::Gbnf, feature.head()));
165            }
166            GrammarExpr::Capture { label, expr } => {
167                report_capture_loss(&mut self.report, label.as_ref());
168                return self.emit_expr(expr, parent);
169            }
170        };
171
172        if precedence < parent {
173            Ok(format!("({text})"))
174        } else {
175            Ok(text)
176        }
177    }
178
179    fn emit_choice(
180        &mut self,
181        ordered: bool,
182        alternatives: &[GrammarExpr],
183    ) -> Result<String, GrammarEmitError> {
184        if alternatives.is_empty() {
185            return Err(unsupported_error(GrammarFormat::Gbnf, "empty Choice"));
186        }
187        if ordered {
188            self.report
189                .add_lossy("GBNF treats ordered choice as unordered choice");
190        }
191
192        alternatives
193            .iter()
194            .map(|alternative| self.emit_expr(alternative, Precedence::Choice))
195            .collect::<Result<Vec<_>, _>>()
196            .map(|items| items.join(" | "))
197    }
198
199    fn emit_sequence(&mut self, items: &[GrammarExpr]) -> Result<String, GrammarEmitError> {
200        let mut emitted = Vec::new();
201        let mut index = 0;
202        while index < items.len() {
203            if let Some(class_items) = negated_class_peephole(items, index) {
204                emitted.push(emit_char_class(true, &class_items)?);
205                index += 2;
206                continue;
207            }
208
209            let text = self.emit_expr(&items[index], Precedence::Sequence)?;
210            if !text.is_empty() {
211                emitted.push(text);
212            }
213            index += 1;
214        }
215
216        if emitted.is_empty() {
217            Ok(quote_terminal(""))
218        } else {
219            Ok(emitted.join(" "))
220        }
221    }
222
223    fn emit_repeat(
224        &mut self,
225        expr: &GrammarExpr,
226        min: usize,
227        max: Option<usize>,
228    ) -> Result<String, GrammarEmitError> {
229        if max.is_some_and(|max| max < min) {
230            return Err(unsupported_error(
231                GrammarFormat::Gbnf,
232                format!("Repeat with min {min} greater than max {max:?}"),
233            ));
234        }
235
236        let inner = self.emit_expr(expr, Precedence::Choice)?;
237        let suffix = match max {
238            Some(max) if min == max => format!("{{{min}}}"),
239            Some(max) => format!("{{{min},{max}}}"),
240            None => format!("{{{min},}}"),
241        };
242        Ok(format!("({inner}){suffix}"))
243    }
244}
245
246#[derive(Clone, Debug)]
247struct NamePlan {
248    names: BTreeMap<String, String>,
249}
250
251impl NamePlan {
252    fn new(grammar: &Grammar, start_name: &str, report: &mut EmitReport) -> Self {
253        let defined_names = grammar
254            .rules()
255            .iter()
256            .map(|rule| rule.name().to_string())
257            .collect::<BTreeSet<_>>();
258        let mut symbols = Vec::new();
259        let mut seen = BTreeSet::new();
260        for rule in grammar.rules() {
261            push_unique_symbol(&mut symbols, &mut seen, rule.name());
262        }
263        for reference in grammar.referenced_nonterminals() {
264            push_unique_symbol(&mut symbols, &mut seen, &reference);
265        }
266
267        let mut used = BTreeSet::from(["root".to_string()]);
268        let mut names = BTreeMap::new();
269        names.insert(start_name.to_string(), "root".to_string());
270
271        for symbol in symbols {
272            if symbol == start_name {
273                continue;
274            }
275            let base = sanitize_identifier(&symbol);
276            let emitted = unique_identifier(&base, &mut used);
277            if emitted != symbol {
278                report_name_change(report, &defined_names, &symbol, &emitted);
279            }
280            names.insert(symbol, emitted);
281        }
282
283        Self { names }
284    }
285
286    fn name_for(&self, source: &str) -> String {
287        self.names
288            .get(source)
289            .map_or_else(|| source.to_string(), Clone::clone)
290    }
291}
292
293fn push_unique_symbol(symbols: &mut Vec<String>, seen: &mut BTreeSet<String>, symbol: &str) {
294    if seen.insert(symbol.to_string()) {
295        symbols.push(symbol.to_string());
296    }
297}
298
299fn report_name_change(
300    report: &mut EmitReport,
301    defined_names: &BTreeSet<String>,
302    source: &str,
303    emitted: &str,
304) {
305    let kind = if defined_names.contains(source) {
306        "rule"
307    } else {
308        "non-terminal reference"
309    };
310    report.add_lossy(format!("GBNF renamed {kind} {source:?} to {emitted:?}"));
311}
312
313fn unique_identifier(base: &str, used: &mut BTreeSet<String>) -> String {
314    if used.insert(base.to_string()) {
315        return base.to_string();
316    }
317
318    for suffix in 1_usize.. {
319        let candidate = format!("{base}-{suffix}");
320        if used.insert(candidate.clone()) {
321            return candidate;
322        }
323    }
324    unreachable!("unbounded suffix search must eventually find a free identifier")
325}
326
327fn sanitize_identifier(source: &str) -> String {
328    let mut output = String::new();
329    let mut previous_hyphen = false;
330    for character in source.chars() {
331        let sanitized = if character.is_ascii_alphanumeric() {
332            character
333        } else {
334            '-'
335        };
336        if sanitized == '-' {
337            if !previous_hyphen {
338                output.push(sanitized);
339                previous_hyphen = true;
340            }
341        } else {
342            output.push(sanitized);
343            previous_hyphen = false;
344        }
345    }
346
347    let mut output = output.trim_matches('-').to_string();
348    if output.is_empty() {
349        output.push_str("ml");
350    }
351    if !output.starts_with(|character: char| character.is_ascii_alphabetic()) {
352        output.insert_str(0, "ml-");
353    }
354    output
355}
356
357fn start_rule_index(grammar: &Grammar) -> Option<usize> {
358    grammar.start().map_or(Some(0), |start| {
359        grammar.rules().iter().position(|rule| rule.name() == start)
360    })
361}
362
363fn negated_class_peephole(items: &[GrammarExpr], index: usize) -> Option<Vec<CharClassItem>> {
364    let GrammarExpr::Not(inner) = items.get(index)? else {
365        return None;
366    };
367    if !matches!(items.get(index + 1), Some(GrammarExpr::AnyChar)) {
368        return None;
369    }
370    predicate_negated_class_items(inner)
371}
372
373fn predicate_negated_class_items(expr: &GrammarExpr) -> Option<Vec<CharClassItem>> {
374    match expr {
375        GrammarExpr::CharClass {
376            negated: false,
377            items,
378        } => Some(items.clone()),
379        GrammarExpr::Terminal(value) => {
380            let mut chars = value.chars();
381            let character = chars.next()?;
382            chars
383                .next()
384                .is_none()
385                .then_some(vec![CharClassItem::Char(character)])
386        }
387        _ => None,
388    }
389}
390
391fn emit_case_insensitive_terminal(value: &str) -> String {
392    if value.is_empty() {
393        return quote_terminal("");
394    }
395
396    value
397        .chars()
398        .map(emit_case_insensitive_char)
399        .collect::<String>()
400}
401
402fn emit_case_insensitive_char(character: char) -> String {
403    if character.is_ascii_alphabetic() {
404        let upper = character.to_ascii_uppercase();
405        let lower = character.to_ascii_lowercase();
406        let mut output = String::new();
407        output.push('[');
408        push_escaped_class_char(&mut output, upper);
409        push_escaped_class_char(&mut output, lower);
410        output.push(']');
411        output
412    } else {
413        quote_terminal(&character.to_string())
414    }
415}
416
417fn emit_char_range(start: char, end: char) -> Result<String, GrammarEmitError> {
418    validate_range("CharRange", start, end)?;
419    Ok(format!(
420        "[{}-{}]",
421        escaped_class_char(start),
422        escaped_class_char(end)
423    ))
424}
425
426fn emit_char_class(negated: bool, items: &[CharClassItem]) -> Result<String, GrammarEmitError> {
427    if items.is_empty() {
428        return Err(unsupported_error(GrammarFormat::Gbnf, "empty CharClass"));
429    }
430
431    let mut output = String::new();
432    output.push('[');
433    if negated {
434        output.push('^');
435    }
436    for item in items {
437        output.push_str(&emit_char_class_item(item)?);
438    }
439    output.push(']');
440    Ok(output)
441}
442
443fn emit_char_class_item(item: &CharClassItem) -> Result<String, GrammarEmitError> {
444    match item {
445        CharClassItem::Char(value) => Ok(escaped_class_char(*value)),
446        CharClassItem::Range(start, end) => {
447            validate_range("CharClass range", *start, *end)?;
448            Ok(format!(
449                "{}-{}",
450                escaped_class_char(*start),
451                escaped_class_char(*end)
452            ))
453        }
454    }
455}
456
457fn validate_range(construct: &str, start: char, end: char) -> Result<(), GrammarEmitError> {
458    if start > end {
459        return Err(unsupported_error(
460            GrammarFormat::Gbnf,
461            format!(
462                "{construct} has descending bounds U+{:04X}..=U+{:04X}",
463                start as u32, end as u32
464            ),
465        ));
466    }
467    Ok(())
468}
469
470fn report_capture_loss(report: &mut EmitReport, label: Option<&String>) {
471    if let Some(label) = label {
472        report.add_lossy(format!("GBNF dropped capture label {label:?}"));
473    } else {
474        report.add_lossy("GBNF dropped anonymous capture");
475    }
476}
477
478fn quote_terminal(value: &str) -> String {
479    let mut output = String::with_capacity(value.len() + 2);
480    output.push('"');
481    for character in value.chars() {
482        push_escaped_string_char(&mut output, character);
483    }
484    output.push('"');
485    output
486}
487
488fn escaped_class_char(character: char) -> String {
489    let mut output = String::new();
490    push_escaped_class_char(&mut output, character);
491    output
492}
493
494fn push_escaped_string_char(output: &mut String, character: char) {
495    match character {
496        '"' => output.push_str("\\\""),
497        '\\' => output.push_str("\\\\"),
498        '\n' => output.push_str("\\n"),
499        '\r' => output.push_str("\\r"),
500        '\t' => output.push_str("\\t"),
501        '\u{08}' => output.push_str("\\b"),
502        '\u{0c}' => output.push_str("\\f"),
503        character if character.is_control() => push_hex_escape(output, character),
504        character => output.push(character),
505    }
506}
507
508fn push_escaped_class_char(output: &mut String, character: char) {
509    match character {
510        '\\' => output.push_str("\\\\"),
511        '[' => output.push_str("\\["),
512        ']' => output.push_str("\\]"),
513        '-' => output.push_str("\\-"),
514        '^' => output.push_str("\\^"),
515        '\n' => output.push_str("\\n"),
516        '\r' => output.push_str("\\r"),
517        '\t' => output.push_str("\\t"),
518        '\u{08}' => output.push_str("\\b"),
519        '\u{0c}' => output.push_str("\\f"),
520        character if character.is_control() => push_hex_escape(output, character),
521        character => output.push(character),
522    }
523}
524
525fn push_hex_escape(output: &mut String, character: char) {
526    let code = character as u32;
527    if code <= 0xff {
528        let _ = write!(output, "\\x{code:02X}");
529    } else if code <= 0xffff {
530        let _ = write!(output, "\\u{code:04X}");
531    } else {
532        let _ = write!(output, "\\U{code:08X}");
533    }
534}
meta_language/grammar/emit/gbnf.rs

meta_language/grammar/emit/
gbnf.rs
