meta_language/grammar/emit/
gbnf.rs

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

meta_language/grammar/emit/
gbnf.rs
