meta_language/grammar/import/
bnf.rs

1//! Hand-written classic BNF importer, a port of `importBnf` in
2//! `js/src/grammar-importers/bnf-ebnf.js`.
3
4use super::common::{
5    Cursor, alternatives_choice, choice, grammar_from_rules, is_line_terminator, is_space,
6    json_quote, sequence, split_lines, strip_line_comment, terminal_or_empty, trim,
7};
8use super::{GrammarImportError, parse_error};
9use crate::grammar::{Grammar, GrammarExpr, GrammarFormat, GrammarRule};
10
11const FORMAT: GrammarFormat = GrammarFormat::Bnf;
12
13/// Parses classic angle-bracket Backus-Naur Form text into the grammar IR.
14///
15/// Each line holds one `<name> ::= alternatives` production; a later
16/// production for the same name adds alternatives to it. Terminals are single-
17/// or double-quoted without escape sequences, and `;` starts a line comment.
18///
19/// # Errors
20///
21/// Returns [`GrammarImportError`] when the BNF text cannot be parsed or when
22/// a non-terminal reference does not resolve to a rule.
23pub fn import_bnf(text: &str) -> Result<Grammar, GrammarImportError> {
24    let mut rules: Vec<GrammarRule> = Vec::new();
25    for raw_line in split_lines(text) {
26        let line = trim(strip_line_comment(raw_line, ';', false));
27        if line.is_empty() {
28            continue;
29        }
30        let Some((name, rhs)) = split_production(line) else {
31            return Err(parse_error(
32                FORMAT,
33                format!("invalid production {}", json_quote(line)),
34            ));
35        };
36        let expr = parse_alternatives(rhs)?;
37        if let Some(existing) = rules.iter_mut().find(|rule| rule.name == name) {
38            let previous = std::mem::replace(&mut existing.expr, GrammarExpr::Empty);
39            existing.expr = choice(vec![previous, expr], false);
40        } else {
41            rules.push(GrammarRule::new(name, expr));
42        }
43    }
44    grammar_from_rules(FORMAT, rules, &[])
45}
46
47/// Splits `<name> ::= rhs`, as the JavaScript pattern
48/// `^<([^<>]+)>\s*::=\s*(.*)$` does, returning the trimmed name.
49fn split_production(line: &str) -> Option<(&str, &str)> {
50    let rest = line.strip_prefix('<')?;
51    let close = rest.find(['<', '>'])?;
52    if close == 0 || !rest[close..].starts_with('>') {
53        return None;
54    }
55    let after = rest[close + 1..]
56        .trim_start_matches(is_space)
57        .strip_prefix("::=")?;
58    let rhs = after.trim_start_matches(is_space);
59    (!rhs.contains(is_line_terminator)).then(|| (trim(&rest[..close]), rhs))
60}
61
62fn parse_alternatives(source: &str) -> Result<GrammarExpr, GrammarImportError> {
63    let mut cursor = Cursor::new(source, FORMAT);
64    let mut alternatives = Vec::new();
65    loop {
66        let mut items = Vec::new();
67        loop {
68            cursor.skip_space()?;
69            if matches!(cursor.peek(), None | Some('|')) {
70                break;
71            }
72            items.push(atom(&mut cursor)?);
73        }
74        alternatives.push(sequence(items));
75        if !cursor.try_consume("|")? {
76            break;
77        }
78    }
79    cursor.skip_space()?;
80    if !cursor.eof() {
81        return Err(cursor.error("unexpected BNF input"));
82    }
83    Ok(alternatives_choice(alternatives))
84}
85
86fn atom(cursor: &mut Cursor<'_>) -> Result<GrammarExpr, GrammarImportError> {
87    cursor.skip_space()?;
88    // Classic BNF terminals have no escape sequences.
89    if matches!(cursor.peek(), Some('"' | '\'')) {
90        return cursor.quoted(None).map(terminal_or_empty);
91    }
92    if cursor.try_consume("<")? {
93        let Some(end) = cursor.rest().find('>') else {
94            return Err(cursor.error("unterminated non-terminal"));
95        };
96        let name = trim(&cursor.rest()[..end]);
97        cursor.advance(end + 1);
98        if name.is_empty() {
99            return Err(cursor.error("empty non-terminal"));
100        }
101        return Ok(GrammarExpr::NonTerminal(name.to_string()));
102    }
103    Err(cursor.error("expected literal or non-terminal"))
104}
meta_language/grammar/import/bnf.rs

meta_language/grammar/import/
bnf.rs
