meta_language/grammar/import/
ebnf.rs

1//! Hand-written ISO-style EBNF importer, a port of `importEbnf` in
2//! `js/src/grammar-importers/bnf-ebnf.js`.
3
4use super::common::{Cursor, alternatives_choice, grammar_from_rules, sequence, terminal_or_empty};
5use super::{GrammarImportError, parse_error, unsupported_error};
6use crate::grammar::{Grammar, GrammarExpr, GrammarFormat, GrammarRule};
7
8const FORMAT: GrammarFormat = GrammarFormat::Ebnf;
9
10/// Parses Extended Backus-Naur Form text into the grammar IR.
11///
12/// The parser accepts the ISO-style `name = expression ;` spelling used by the
13/// issue fixtures and the `::=` spelling. Concatenation (`,` or juxtaposition)
14/// binds tighter than alternation (`|`); `( )`, `[ ]`, and `{ }` group,
15/// make optional, and repeat; a postfix `?`, `*`, or `+` follows an element.
16/// ISO `(* ... *)` comments outside string literals are skipped, as in the
17/// JavaScript importer.
18///
19/// # Errors
20///
21/// Returns [`GrammarImportError`] when the EBNF text cannot be parsed, when a
22/// parsed construct cannot be represented, or when a non-terminal reference does
23/// not resolve to a rule in the imported grammar.
24pub fn import_ebnf(text: &str) -> Result<Grammar, GrammarImportError> {
25    let source = remove_comments(text)?;
26    let mut cursor = Cursor::new(&source, FORMAT);
27    let mut rules: Vec<GrammarRule> = Vec::new();
28    loop {
29        cursor.skip_space()?;
30        if cursor.eof() {
31            break;
32        }
33        let name = cursor.identifier()?;
34        if rules.iter().any(|rule| rule.name == name) {
35            return Err(parse_error(FORMAT, format!("duplicate rule {name}")));
36        }
37        if !cursor.try_consume("::=")? {
38            cursor.consume("=")?;
39        }
40        let expr = alternation(&mut cursor, ';')?;
41        cursor.consume(";")?;
42        rules.push(GrammarRule::new(name, expr));
43    }
44    grammar_from_rules(FORMAT, rules, &[])
45}
46
47fn alternation(cursor: &mut Cursor<'_>, close: char) -> Result<GrammarExpr, GrammarImportError> {
48    let mut alternatives = vec![concatenation(cursor, close)?];
49    while cursor.try_consume("|")? {
50        alternatives.push(concatenation(cursor, close)?);
51    }
52    Ok(alternatives_choice(alternatives))
53}
54
55fn concatenation(cursor: &mut Cursor<'_>, close: char) -> Result<GrammarExpr, GrammarImportError> {
56    let mut items = Vec::new();
57    loop {
58        cursor.skip_space()?;
59        match cursor.peek() {
60            None | Some('|' | ')' | ']' | '}') => break,
61            Some(character) if character == close => break,
62            Some(',') => cursor.advance(1),
63            Some(_) => items.push(postfix(cursor)?),
64        }
65    }
66    Ok(sequence(items))
67}
68
69fn postfix(cursor: &mut Cursor<'_>) -> Result<GrammarExpr, GrammarImportError> {
70    let expr = atom(cursor)?;
71    Ok(if cursor.try_consume("?")? {
72        GrammarExpr::optional(expr)
73    } else if cursor.try_consume("*")? {
74        GrammarExpr::zero_or_more(expr)
75    } else if cursor.try_consume("+")? {
76        GrammarExpr::one_or_more(expr)
77    } else {
78        expr
79    })
80}
81
82fn atom(cursor: &mut Cursor<'_>) -> Result<GrammarExpr, GrammarImportError> {
83    cursor.skip_space()?;
84    if matches!(cursor.peek(), Some('"' | '\'')) {
85        return cursor.quoted(Some(decode_escape)).map(terminal_or_empty);
86    }
87    for (open, close) in [("(", ')'), ("[", ']'), ("{", '}')] {
88        if cursor.try_consume(open)? {
89            let expr = alternation(cursor, close)?;
90            cursor.consume(&close.to_string())?;
91            return Ok(match close {
92                ']' => GrammarExpr::optional(expr),
93                '}' => GrammarExpr::zero_or_more(expr),
94                _ => expr,
95            });
96        }
97    }
98    match cursor.peek() {
99        Some('?') => Err(unsupported_error(FORMAT, "special sequence")),
100        Some('#') => Err(unsupported_error(FORMAT, "inline regex")),
101        _ => Ok(GrammarExpr::NonTerminal(cursor.identifier()?)),
102    }
103}
104
105/// Decodes the escapes `\t \b \n \r \f \/ \\` and an escaped quote inside a
106/// quoted terminal, rejecting any other escape.
107fn decode_escape(
108    escaped: char,
109    quote: char,
110    format: GrammarFormat,
111) -> Result<String, GrammarImportError> {
112    let decoded = match escaped {
113        _ if escaped == quote => quote,
114        't' => '\t',
115        'b' => '\u{8}',
116        'n' => '\n',
117        'r' => '\r',
118        'f' => '\u{c}',
119        '/' => '/',
120        '\\' => '\\',
121        _ => {
122            return Err(parse_error(
123                format,
124                format!("unsupported string escape \\{escaped}"),
125            ));
126        }
127    };
128    Ok(decoded.to_string())
129}
130
131/// Replaces every `(* ... *)` comment outside a string literal with one space.
132fn remove_comments(source: &str) -> Result<String, GrammarImportError> {
133    let mut result = String::with_capacity(source.len());
134    let mut quote = None;
135    let mut index = 0;
136    while let Some(character) = source[index..].chars().next() {
137        if let Some(open) = quote {
138            result.push(character);
139            index += character.len_utf8();
140            if character == '\\'
141                && let Some(next) = source[index..].chars().next()
142            {
143                result.push(next);
144                index += next.len_utf8();
145            } else if character == open {
146                quote = None;
147            }
148            continue;
149        }
150        if matches!(character, '"' | '\'') {
151            quote = Some(character);
152        } else if source[index..].starts_with("(*") {
153            let Some(end) = source[index + 2..].find("*)") else {
154                return Err(parse_error(FORMAT, "unterminated comment"));
155            };
156            result.push(' ');
157            index += 2 + end + 2;
158            continue;
159        }
160        result.push(character);
161        index += character.len_utf8();
162    }
163    if quote.is_some() {
164        return Err(parse_error(FORMAT, "unterminated string literal"));
165    }
166    Ok(result)
167}
meta_language/grammar/import/ebnf.rs

meta_language/grammar/import/
ebnf.rs
