meta_language/grammar/emit/
lark.rs

1//! Lark grammar emitter.
2
3use std::collections::BTreeSet;
4use std::fmt::Write as _;
5
6use super::structural::{
7    NamePlan, Precedence, Rendered, check_repeat_bounds, collect_references, doc_lines,
8    join_choice, join_sequence, negated_lookahead_set, snake_case, wrap,
9};
10use super::{EmitReport, GrammarEmitError, finish_lines, unsupported_error};
11use crate::grammar::{
12    CharClassItem, Grammar, GrammarExpr, GrammarFormat, GrammarRule, RuleKind, import_lark,
13};
14
15const FORMAT: GrammarFormat = GrammarFormat::Lark;
16const LABEL: &str = "Lark";
17
18/// Documentation `import_lark` attaches to rules created from `%ignore`.
19const IGNORE_DOC: &str = "%ignore";
20
21/// Emits a Lark grammar.
22///
23/// Normal rules become lower-case Lark rules, silent rules become inlined
24/// `?rule`s, and token and atomic rules become upper-case terminals. Rule
25/// names are adjusted deterministically to Lark's case conventions; every
26/// rename is recorded in [`EmitReport::lossy`] as
27/// `Lark renamed rule "a" to "b"`. Silent rules documented exactly as
28/// `%ignore`, which is how `import_lark` represents `%ignore` directives, are
29/// written back as `%ignore` directives; no other `%ignore` is emitted.
30///
31/// Character classes, ranges and any-character are written as regex
32/// terminals, case-insensitive literals as `(?i:...)` regexes, counted
33/// repetition as `~ n..m`, and captures labelled `regex` over a literal as
34/// the regex they were imported from. Ordered choice is written as Lark
35/// alternation; lookahead and other captures have no Lark form and are
36/// dropped, except that a negative lookahead over a character set followed by
37/// any character becomes a complemented character class. Every lowering and
38/// drop is recorded in the report, so `import_lark` of the output reproduces
39/// the grammar modulo the recorded notes, and emitting the re-imported
40/// grammar reproduces the same text.
41///
42/// Rule documentation is written as `//` comments above each rule; trailing
43/// `inline` and `priority N` documentation parts, as produced by
44/// `import_lark`, are written back as the `?` prefix and `.N` priority.
45///
46/// # Errors
47///
48/// Returns [`GrammarEmitError::Unsupported`] for empty non-negated character
49/// classes, descending character ranges, repetitions whose maximum is below
50/// their minimum, and regexes that Lark cannot delimit.
51pub fn emit_lark(grammar: &Grammar) -> Result<(String, EmitReport), GrammarEmitError> {
52    LarkEmitter::new(grammar).emit()
53}
54
55#[derive(Debug)]
56struct LarkEmitter<'grammar> {
57    grammar: &'grammar Grammar,
58    names: NamePlan,
59    ignored: BTreeSet<usize>,
60    report: EmitReport,
61    foreign: bool,
62    rule: String,
63}
64
65impl<'grammar> LarkEmitter<'grammar> {
66    fn new(grammar: &'grammar Grammar) -> Self {
67        let rules = grammar.rules();
68        let mut ignored = rules
69            .iter()
70            .enumerate()
71            .filter(|(_index, rule)| {
72                rule.kind == RuleKind::Silent && rule.doc() == Some(IGNORE_DOC)
73            })
74            .map(|(index, _rule)| index)
75            .collect::<BTreeSet<_>>();
76        if ignored.len() == rules.len() {
77            ignored.clear();
78        }
79        let foreign = grammar.source_format() != Some(FORMAT);
80        let mut report = EmitReport::default();
81        let mut candidates = rules
82            .iter()
83            .map(|rule| rule_candidate(rule, foreign, &mut report))
84            .collect::<Vec<_>>();
85        for (position, &index) in ignored.iter().enumerate() {
86            candidates[index] = if position == 0 {
87                "_ignore".to_string()
88            } else {
89                format!("_ignore_{}", position + 1)
90            };
91        }
92        let names = NamePlan::new(
93            grammar,
94            LABEL,
95            &candidates,
96            &ignored,
97            reference_candidate,
98            &mut report,
99        );
100        Self {
101            grammar,
102            names,
103            ignored,
104            report,
105            foreign,
106            rule: String::new(),
107        }
108    }
109
110    fn emit(mut self) -> Result<(String, EmitReport), GrammarEmitError> {
111        let (order, effective) = self.emission_order();
112        self.note_start(effective);
113        let mut lines = Vec::new();
114        for index in order {
115            self.emit_rule(index, &mut lines)?;
116        }
117        Ok((finish_lines(&lines), self.report))
118    }
119
120    /// Orders rules so that `import_lark` picks the same start rule and
121    /// returns that rule. The importer starts at `start` when it exists,
122    /// wherever it sits, so source order is kept then; otherwise the start
123    /// rule moves first. `%ignore` directives come last because the importer
124    /// appends them.
125    fn emission_order(&self) -> (Vec<usize>, Option<usize>) {
126        let rules = self.grammar.rules();
127        let regular = (0..rules.len())
128            .filter(|index| !self.ignored.contains(index))
129            .collect::<Vec<_>>();
130        let named_start = regular
131            .iter()
132            .copied()
133            .find(|&index| self.names.rule_name(index) == "start");
134        let mut order = Vec::with_capacity(rules.len());
135        let effective = if named_start.is_some() {
136            order.extend(regular.iter().copied());
137            named_start
138        } else {
139            let effective = self
140                .grammar
141                .start()
142                .and_then(|start| {
143                    regular
144                        .iter()
145                        .copied()
146                        .find(|&index| rules[index].name == start)
147                })
148                .or_else(|| regular.first().copied());
149            order.extend(effective);
150            order.extend(
151                regular
152                    .iter()
153                    .copied()
154                    .filter(|&index| Some(index) != effective),
155            );
156            effective
157        };
158        order.extend(self.ignored.iter().copied());
159        (order, effective)
160    }
161
162    fn note_start(&mut self, effective: Option<usize>) {
163        let (Some(start), Some(effective)) = (self.grammar.start(), effective) else {
164            return;
165        };
166        let expected = self.names.resolve(start).to_string();
167        let actual = self.names.rule_name(effective).to_string();
168        if expected != actual {
169            self.report.add_lossy(format!(
170                "Lark re-imports start rule as {actual:?} instead of {expected:?}, \
171                 because Lark starts at `start` or the first rule"
172            ));
173        }
174    }
175
176    fn emit_rule(&mut self, index: usize, lines: &mut Vec<String>) -> Result<(), GrammarEmitError> {
177        let rule = &self.grammar.rules()[index];
178        let name = self.names.rule_name(index).to_string();
179        self.rule.clone_from(&name);
180        let body = self.render(rule.expr())?.0;
181
182        if self.ignored.contains(&index) {
183            if body.is_empty() {
184                return Err(unsupported_error(FORMAT, "empty %ignore expression"));
185            }
186            lines.push(format!("%ignore {body}"));
187            return Ok(());
188        }
189
190        let silent = rule.kind == RuleKind::Silent;
191        let doc = plan_doc(rule.doc(), silent);
192        if doc.reimported.as_deref() != rule.doc() {
193            self.report.add_lossy(format!(
194                "Lark re-imports the documentation of rule {name:?} as {:?}",
195                doc.reimported
196            ));
197        }
198        lines.extend(doc.comments);
199
200        let mut line = String::new();
201        if silent {
202            line.push('?');
203        }
204        line.push_str(&name);
205        if let Some(priority) = doc.priority {
206            let _ = write!(line, ".{priority}");
207        }
208        line.push(':');
209        if !body.is_empty() {
210            line.push(' ');
211            line.push_str(&body);
212        }
213        lines.push(line);
214
215        if rule.kind == RuleKind::Atomic {
216            self.report.add_lossy(format!(
217                "Lark emitted atomic rule {:?} as terminal {name:?}, which re-imports as a token rule",
218                rule.name
219            ));
220        }
221        if self.foreign && is_terminal_name(&name) {
222            self.note_terminal_references(rule, &name);
223        }
224        Ok(())
225    }
226
227    fn note_terminal_references(&mut self, rule: &GrammarRule, name: &str) {
228        let mut references = Vec::new();
229        collect_references(rule.expr(), &mut references);
230        for reference in references {
231            let emitted = self.names.resolve(reference).to_string();
232            if self.grammar.rule(reference).is_some() && !is_terminal_name(&emitted) {
233                self.report.add_lossy(format!(
234                    "Lark terminal {name:?} references rule {emitted:?}, which Lark rejects"
235                ));
236            }
237        }
238    }
239
240    fn note(&mut self, message: &str) {
241        let note = format!("Lark {message} in rule {:?}", self.rule);
242        self.report.add_lossy(note);
243    }
244
245    fn render(&mut self, expr: &GrammarExpr) -> Result<Rendered, GrammarEmitError> {
246        Ok(match expr {
247            GrammarExpr::Empty => (String::new(), Precedence::Sequence),
248            GrammarExpr::Terminal(value) => {
249                if value.is_empty() {
250                    self.note("keeps an empty literal, which Lark rejects,");
251                }
252                (quote(value), Precedence::Atom)
253            }
254            GrammarExpr::TerminalInsensitive(value) => {
255                self.note(&format!(
256                    "emitted case-insensitive literal {value:?} as a (?i:...) regex"
257                ));
258                (
259                    format!("/(?i:{})/", regex_literal_text(value)),
260                    Precedence::Atom,
261                )
262            }
263            GrammarExpr::CharRange(start, end) => {
264                if start > end {
265                    return Err(unsupported_error(
266                        FORMAT,
267                        format!("descending character range {start:?}..{end:?}"),
268                    ));
269                }
270                self.note("emitted character range as a regex character class");
271                render_class(false, &[CharClassItem::Range(*start, *end)])
272            }
273            GrammarExpr::CharClass { negated, items } => self.render_class(*negated, items)?,
274            GrammarExpr::AnyChar => {
275                self.note("emitted any character as a regex character class");
276                render_class(false, &[any_char_range()])
277            }
278            GrammarExpr::NonTerminal(name) => {
279                (self.names.resolve(name).to_string(), Precedence::Atom)
280            }
281            GrammarExpr::Choice {
282                ordered,
283                alternatives,
284            } => {
285                if *ordered && alternatives.len() > 1 {
286                    self.note("treats ordered choice as unordered choice");
287                }
288                let rendered = alternatives
289                    .iter()
290                    .map(|alternative| self.render(alternative))
291                    .collect::<Result<Vec<_>, _>>()?;
292                join_choice(rendered)
293            }
294            GrammarExpr::Sequence(items) => self.render_sequence(items)?,
295            GrammarExpr::Optional(inner) => {
296                let (text, _precedence) = self.render(inner)?;
297                (format!("[{text}]"), Precedence::Atom)
298            }
299            GrammarExpr::ZeroOrMore(inner) => self.render_postfix(inner, "*")?,
300            GrammarExpr::OneOrMore(inner) => self.render_postfix(inner, "+")?,
301            GrammarExpr::Repeat { expr, min, max } => self.render_repeat(expr, *min, *max)?,
302            GrammarExpr::And(_) => {
303                self.note("dropped positive lookahead");
304                (String::new(), Precedence::Sequence)
305            }
306            GrammarExpr::Not(_) => {
307                self.note("dropped negative lookahead");
308                (String::new(), Precedence::Sequence)
309            }
310            GrammarExpr::Capture { label, expr } => self.render_capture(label.as_deref(), expr)?,
311            GrammarExpr::Feature(feature) => {
312                return Err(unsupported_error(GrammarFormat::Lark, feature.head()));
313            }
314        })
315    }
316
317    fn render_sequence(&mut self, items: &[GrammarExpr]) -> Result<Rendered, GrammarEmitError> {
318        let mut rendered = Vec::with_capacity(items.len());
319        let mut index = 0;
320        while index < items.len() {
321            if let Some((negated, class)) = negated_lookahead_set(items, index) {
322                self.note(
323                    "lowered negative lookahead followed by any character to a complemented character class",
324                );
325                rendered.push(render_class(negated, &class));
326                index += 2;
327                continue;
328            }
329            rendered.push(self.render(&items[index])?);
330            index += 1;
331        }
332        Ok(join_sequence(rendered))
333    }
334
335    fn render_postfix(
336        &mut self,
337        inner: &GrammarExpr,
338        operator: &str,
339    ) -> Result<Rendered, GrammarEmitError> {
340        let operand = self.render(inner)?;
341        Ok((
342            format!("{}{operator}", wrap(operand, Precedence::Atom)),
343            Precedence::Postfix,
344        ))
345    }
346
347    fn render_repeat(
348        &mut self,
349        inner: &GrammarExpr,
350        min: usize,
351        max: Option<usize>,
352    ) -> Result<Rendered, GrammarEmitError> {
353        check_repeat_bounds(FORMAT, min, max)?;
354        let operand = wrap(self.render(inner)?, Precedence::Atom);
355        Ok(match (min, max) {
356            (_, Some(max)) if max == min => (format!("{operand} ~ {min}"), Precedence::Postfix),
357            (_, Some(max)) => (format!("{operand} ~ {min}..{max}"), Precedence::Postfix),
358            (0, None) => {
359                self.note("emitted unbounded repetition {0,} as `*`");
360                (format!("{operand}*"), Precedence::Postfix)
361            }
362            (1, None) => {
363                self.note("emitted unbounded repetition {1,} as `+`");
364                (format!("{operand}+"), Precedence::Postfix)
365            }
366            (min, None) => {
367                self.note(&format!(
368                    "emitted unbounded repetition {{{min},}} as `~ {min}` followed by `*`"
369                ));
370                (
371                    format!("{operand} ~ {min} {operand}*"),
372                    Precedence::Sequence,
373                )
374            }
375        })
376    }
377
378    fn render_capture(
379        &mut self,
380        label: Option<&str>,
381        inner: &GrammarExpr,
382    ) -> Result<Rendered, GrammarEmitError> {
383        if label == Some("regex")
384            && let GrammarExpr::Terminal(pattern) = inner
385        {
386            return self.render_regex(pattern);
387        }
388        match label {
389            Some(label) => self.note(&format!("dropped capture label {label:?}")),
390            None => self.note("dropped anonymous capture"),
391        }
392        self.render(inner)
393    }
394
395    fn render_regex(&mut self, pattern: &str) -> Result<Rendered, GrammarEmitError> {
396        if pattern.is_empty() {
397            self.note("emitted an empty regex as /(?:)/");
398            return Ok(("/(?:)/".to_string(), Precedence::Atom));
399        }
400        let body = delimit_regex(pattern)?;
401        if body != pattern {
402            self.note(&format!("escaped regex /{pattern}/ as /{body}/"));
403        }
404        if is_class_shaped(&body) {
405            let probe = format!("probe: /{body}/\n");
406            if let Err(error) = import_lark(&probe) {
407                return Err(unsupported_error(
408                    FORMAT,
409                    format!("regex /{body}/ does not re-import as a character class: {error}"),
410                ));
411            }
412            self.note(&format!("regex /{body}/ re-imports as a character class"));
413        }
414        Ok((format!("/{body}/"), Precedence::Atom))
415    }
416
417    fn render_class(
418        &mut self,
419        negated: bool,
420        items: &[CharClassItem],
421    ) -> Result<Rendered, GrammarEmitError> {
422        if items.is_empty() {
423            if negated {
424                self.note("emitted an empty negated character class as any character");
425                return Ok(render_class(false, &[any_char_range()]));
426            }
427            return Err(unsupported_error(FORMAT, "empty character class"));
428        }
429        if let Some(CharClassItem::Range(start, end)) = items
430            .iter()
431            .find(|item| matches!(item, CharClassItem::Range(start, end) if start > end))
432        {
433            return Err(unsupported_error(
434                FORMAT,
435                format!("descending character class range {start:?}-{end:?}"),
436            ));
437        }
438        Ok(render_class(negated, items))
439    }
440}
441
442const fn any_char_range() -> CharClassItem {
443    CharClassItem::Range('\0', char::MAX)
444}
445
446fn is_terminal_name(name: &str) -> bool {
447    name.starts_with(|c: char| c.is_ascii_uppercase())
448}
449
450/// Returns Lark's conventional spelling of a rule or terminal name.
451fn rule_candidate(rule: &GrammarRule, foreign: bool, report: &mut EmitReport) -> String {
452    match rule.kind {
453        RuleKind::Token | RuleKind::Atomic => terminal_candidate(&rule.name),
454        RuleKind::Normal if is_filtered_terminal_name(&rule.name) => {
455            if foreign {
456                report.add_lossy(format!(
457                    "Lark keeps rule {:?} as a filtered terminal name, which re-imports as a normal rule",
458                    rule.name
459                ));
460            }
461            rule.name.clone()
462        }
463        RuleKind::Normal | RuleKind::Silent => lower_candidate(&rule.name),
464    }
465}
466
467/// Returns a valid spelling for a reference without a rule, keeping its case.
468fn reference_candidate(name: &str) -> String {
469    if is_filtered_terminal_name(name) {
470        name.to_string()
471    } else if is_terminal_name(name) {
472        terminal_candidate(name)
473    } else {
474        lower_candidate(name)
475    }
476}
477
478/// Recognizes `_NAME`, the spelling Lark uses for filtered terminals.
479fn is_filtered_terminal_name(name: &str) -> bool {
480    let mut chars = name.chars();
481    chars.next() == Some('_')
482        && chars.next().is_some_and(|c| c.is_ascii_uppercase())
483        && chars.all(|c| c.is_ascii_uppercase() || c.is_ascii_digit() || c == '_')
484}
485
486fn lower_candidate(name: &str) -> String {
487    let output = snake_case(name);
488    let mut chars = output.chars();
489    let valid = match chars.next() {
490        Some('_') => chars.next().is_some_and(|c| c.is_ascii_lowercase()),
491        Some(first) => first.is_ascii_lowercase(),
492        None => false,
493    };
494    if valid {
495        output
496    } else if output.starts_with('_') {
497        format!("r{output}")
498    } else {
499        format!("r_{output}")
500    }
501}
502
503fn terminal_candidate(name: &str) -> String {
504    let mut chars = name.chars();
505    if chars.next().is_some_and(|c| c.is_ascii_uppercase())
506        && chars.all(|c| c.is_ascii_uppercase() || c.is_ascii_digit() || c == '_')
507    {
508        return name.to_string();
509    }
510    let output = snake_case(name).to_ascii_uppercase();
511    if output.starts_with(|c: char| c.is_ascii_uppercase()) {
512        output
513    } else if output.starts_with('_') {
514        format!("T{output}")
515    } else {
516        format!("T_{output}")
517    }
518}
519
520/// Quotes a Lark string literal.
521fn quote(value: &str) -> String {
522    let mut output = String::from("\"");
523    for character in value.chars() {
524        match character {
525            '"' => output.push_str("\\\""),
526            '\\' => output.push_str("\\\\"),
527            character => push_plain_char(&mut output, character),
528        }
529    }
530    output.push('"');
531    output
532}
533
534/// Escapes regex metacharacters so a regex matches `value` literally.
535fn regex_literal_text(value: &str) -> String {
536    let mut output = String::new();
537    for character in value.chars() {
538        if character.is_ascii_punctuation() {
539            output.push('\\');
540            output.push(character);
541        } else {
542            push_plain_char(&mut output, character);
543        }
544    }
545    output
546}
547
548/// Renders a regex character class terminal.
549fn render_class(negated: bool, items: &[CharClassItem]) -> Rendered {
550    let mut output = String::from(if negated { "/[^" } else { "/[" });
551    for item in items {
552        match item {
553            CharClassItem::Char(character) => push_class_char(&mut output, *character),
554            CharClassItem::Range(start, end) => {
555                push_class_char(&mut output, *start);
556                output.push('-');
557                push_class_char(&mut output, *end);
558            }
559        }
560    }
561    output.push_str("]/");
562    (output, Precedence::Atom)
563}
564
565fn push_class_char(output: &mut String, character: char) {
566    match character {
567        '\\' | ']' | '[' | '-' | '^' | '/' => {
568            output.push('\\');
569            output.push(character);
570        }
571        character => push_plain_char(output, character),
572    }
573}
574
575/// Pushes a character, escaping line breaks, tabs, controls, whitespace
576/// other than space, and characters outside the Basic Multilingual Plane.
577fn push_plain_char(output: &mut String, character: char) {
578    let code = u32::from(character);
579    match character {
580        '\n' => output.push_str("\\n"),
581        '\r' => output.push_str("\\r"),
582        '\t' => output.push_str("\\t"),
583        character
584            if character.is_control()
585                || (character.is_whitespace() && character != ' ')
586                || code > 0xFFFF =>
587        {
588            let _ = match code {
589                0..=0xFF => write!(output, "\\x{code:02X}"),
590                0x100..=0xFFFF => write!(output, "\\u{code:04X}"),
591                _ => write!(output, "\\U{code:08X}"),
592            };
593        }
594        character => output.push(character),
595    }
596}
597
598/// Escapes unescaped `/` and raw line breaks so the pattern fits in `/.../`.
599fn delimit_regex(pattern: &str) -> Result<String, GrammarEmitError> {
600    let mut output = String::new();
601    let mut chars = pattern.chars();
602    while let Some(character) = chars.next() {
603        match character {
604            '\\' => match chars.next() {
605                Some('\n') => output.push_str("\\n"),
606                Some('\r') => output.push_str("\\r"),
607                Some(next) => {
608                    output.push('\\');
609                    output.push(next);
610                }
611                None => {
612                    return Err(unsupported_error(
613                        FORMAT,
614                        format!("regex /{pattern}/ ends with a lone backslash"),
615                    ));
616                }
617            },
618            '/' => output.push_str("\\/"),
619            '\n' => output.push_str("\\n"),
620            '\r' => output.push_str("\\r"),
621            character => output.push(character),
622        }
623    }
624    Ok(output)
625}
626
627/// Mirrors the importer's test for regexes it lowers to character classes.
628fn is_class_shaped(body: &str) -> bool {
629    if body.len() < 2 || !body.starts_with('[') || !body.ends_with(']') {
630        return false;
631    }
632    let inner = &body[1..body.len() - 1];
633    let mut escaped = false;
634    for character in inner.chars() {
635        if escaped {
636            escaped = false;
637        } else if character == '\\' {
638            escaped = true;
639        } else if character == ']' {
640            return false;
641        }
642    }
643    true
644}
645
646/// Comments, priority and re-imported documentation for one rule.
647#[derive(Debug)]
648struct DocPlan {
649    comments: Vec<String>,
650    priority: Option<usize>,
651    reimported: Option<String>,
652}
653
654/// Plans how rule documentation is written so that `import_lark` reads the
655/// same documentation back whenever it consists of comments, `inline` and
656/// `priority N`, as `import_lark` produces it.
657fn plan_doc(doc: Option<&str>, silent: bool) -> DocPlan {
658    let mut text = doc.unwrap_or("");
659    let mut priority = None;
660    if let Some((rest, part)) = split_last_part(text)
661        && let Some(digits) = part.strip_prefix("priority ")
662        && let Ok(value) = digits.parse::<usize>()
663        && value.to_string() == digits
664    {
665        priority = Some(value);
666        text = rest;
667    }
668    if silent && let Some((rest, "inline")) = split_last_part(text) {
669        text = rest;
670    }
671
672    let trimmed = text.trim();
673    let comments = if trimmed.starts_with("//") && !trimmed.contains(['\n', '\r']) {
674        vec![trimmed.to_string()]
675    } else {
676        doc_lines(text)
677            .map(|line| {
678                if line.starts_with("//") {
679                    line.to_string()
680                } else {
681                    format!("// {line}")
682                }
683            })
684            .collect()
685    };
686
687    let mut parts = comments.clone();
688    if silent {
689        parts.push("inline".to_string());
690    }
691    if let Some(priority) = priority {
692        parts.push(format!("priority {priority}"));
693    }
694    DocPlan {
695        comments,
696        priority,
697        reimported: (!parts.is_empty()).then(|| parts.join("; ")),
698    }
699}
700
701/// Splits the last `; `-separated part off documentation.
702fn split_last_part(text: &str) -> Option<(&str, &str)> {
703    if text.is_empty() {
704        return None;
705    }
706    Some(text.rfind("; ").map_or(("", text), |position| {
707        (&text[..position], &text[position + 2..])
708    }))
709}
meta_language/grammar/emit/lark.rs

meta_language/grammar/emit/
lark.rs
