meta_language/grammar/import/
abnf.rs

1//! Hand-written RFC 5234 ABNF importer, a port of
2//! `js/src/grammar-importers/abnf.js`.
3
4use super::common::{
5    Cursor, canonical_repeat, choice, collect_references, decimal, default_escapes,
6    grammar_from_rules, is_line_terminator, is_space, json_quote, sequence, split_lines,
7    strip_line_comment, trim,
8};
9use super::{GrammarImportError, parse_error, unsupported_error};
10use crate::grammar::{CharClassItem, Grammar, GrammarExpr, GrammarFormat, GrammarRule};
11
12const FORMAT: GrammarFormat = GrammarFormat::Abnf;
13
14/// Parses Augmented Backus-Naur Form text into the grammar IR.
15///
16/// Rule names are case-insensitive: `=/` extends the rule of the same name,
17/// references take the defining rule's spelling, and RFC 5234 core rules such
18/// as `ALPHA` and `DIGIT` are appended when referenced but not defined.
19///
20/// # Errors
21///
22/// Returns [`GrammarImportError`] when the ABNF text cannot be parsed, when a
23/// parsed construct cannot be represented, or when a non-terminal reference
24/// does not resolve to an imported or RFC 5234 core rule.
25pub fn import_abnf(text: &str) -> Result<Grammar, GrammarImportError> {
26    let mut rules: Vec<GrammarRule> = Vec::new();
27    for line in logical_lines(text)? {
28        let Some((name, incremental, rhs)) = split_rule(&line) else {
29            return Err(parse_error(
30                FORMAT,
31                format!("invalid rule {}", json_quote(&line)),
32            ));
33        };
34        let expr = AbnfParser::new(rhs).parse()?;
35        let existing = rules
36            .iter_mut()
37            .find(|rule| rule.name.eq_ignore_ascii_case(name));
38        match (incremental, existing) {
39            (true, Some(existing)) => {
40                let previous = std::mem::replace(&mut existing.expr, GrammarExpr::Empty);
41                existing.expr = choice(vec![previous, expr], false);
42            }
43            (true, None) => {
44                return Err(parse_error(
45                    FORMAT,
46                    format!("incremental alternative for undefined rule {name}"),
47                ));
48            }
49            (false, Some(_)) => {
50                return Err(parse_error(FORMAT, format!("duplicate rule {name}")));
51            }
52            (false, None) => rules.push(GrammarRule::new(name, expr)),
53        }
54    }
55
56    canonicalize_references(&mut rules);
57    inject_core_rules(&mut rules);
58    grammar_from_rules(FORMAT, rules, &[])
59}
60
61/// Joins indented continuation lines onto their rule after dropping `;`
62/// comments and blank lines.
63fn logical_lines(source: &str) -> Result<Vec<String>, GrammarImportError> {
64    let mut lines: Vec<String> = Vec::new();
65    for physical in split_lines(source) {
66        let line = strip_line_comment(physical, ';', true).trim_end_matches(is_space);
67        if line.is_empty() {
68            continue;
69        }
70        if line.starts_with([' ', '\t']) {
71            let Some(previous) = lines.last_mut() else {
72                return Err(parse_error(FORMAT, "continuation without a rule"));
73            };
74            previous.push(' ');
75            previous.push_str(trim(line));
76        } else {
77            lines.push(line.to_string());
78        }
79    }
80    Ok(lines)
81}
82
83/// Splits `name = rhs` or `name =/ rhs`, as the JavaScript pattern
84/// `^([A-Za-z][A-Za-z0-9-]*)\s*(=\/|=)\s*(.*)$` does.
85fn split_rule(line: &str) -> Option<(&str, bool, &str)> {
86    if !line.starts_with(|character: char| character.is_ascii_alphabetic()) {
87        return None;
88    }
89    let name_end = line
90        .find(|character: char| !(character.is_ascii_alphanumeric() || character == '-'))
91        .unwrap_or(line.len());
92    let (name, rest) = line.split_at(name_end);
93    let rest = rest.trim_start_matches(is_space).strip_prefix('=')?;
94    let (incremental, rest) = rest
95        .strip_prefix('/')
96        .map_or((false, rest), |rest| (true, rest));
97    let rhs = rest.trim_start_matches(is_space);
98    (!rhs.contains(is_line_terminator)).then_some((name, incremental, rhs))
99}
100
101struct AbnfParser<'source> {
102    cursor: Cursor<'source>,
103}
104
105impl<'source> AbnfParser<'source> {
106    const fn new(source: &'source str) -> Self {
107        Self {
108            cursor: Cursor::new(source, FORMAT),
109        }
110    }
111
112    fn parse(mut self) -> Result<GrammarExpr, GrammarImportError> {
113        let expr = self.alternation(None)?;
114        self.cursor.skip_space()?;
115        if !self.cursor.eof() {
116            return Err(self.cursor.error("unexpected ABNF input"));
117        }
118        Ok(expr)
119    }
120
121    fn alternation(&mut self, close: Option<char>) -> Result<GrammarExpr, GrammarImportError> {
122        let mut alternatives = vec![self.concatenation(close)?];
123        while self.cursor.try_consume("/")? {
124            alternatives.push(self.concatenation(close)?);
125        }
126        Ok(choice(alternatives, false))
127    }
128
129    fn concatenation(&mut self, close: Option<char>) -> Result<GrammarExpr, GrammarImportError> {
130        let mut items = Vec::new();
131        loop {
132            self.cursor.skip_space()?;
133            let next = self.cursor.peek();
134            if next.is_none() || next == Some('/') || (close.is_some() && next == close) {
135                break;
136            }
137            items.push(self.repetition()?);
138        }
139        Ok(sequence(items))
140    }
141
142    /// Reads an optional `n`, `n*m`, `n*`, `*m`, or `*` repeat prefix, then
143    /// the repeated element.
144    fn repetition(&mut self) -> Result<GrammarExpr, GrammarImportError> {
145        self.cursor.skip_space()?;
146        let rest = self.cursor.rest();
147        let low = leading(rest, |character| character.is_ascii_digit());
148        let bounds = if let Some(after) = rest[low.len()..].strip_prefix('*') {
149            let high = leading(after, |character| character.is_ascii_digit());
150            self.cursor.advance(low.len() + 1 + high.len());
151            Some((decimal(low), (!high.is_empty()).then(|| decimal(high))))
152        } else if low.is_empty() {
153            None
154        } else {
155            self.cursor.advance(low.len());
156            Some((decimal(low), Some(decimal(low))))
157        };
158        let atom = self.atom()?;
159        match bounds {
160            Some((min, max)) => canonical_repeat(FORMAT, atom, min, max),
161            None => Ok(atom),
162        }
163    }
164
165    fn atom(&mut self) -> Result<GrammarExpr, GrammarImportError> {
166        self.cursor.skip_space()?;
167        if self.cursor.eof() {
168            return Err(self.cursor.error("expected ABNF element"));
169        }
170        if self.cursor.try_consume("(")? {
171            let expr = self.alternation(Some(')'))?;
172            self.cursor.consume(")")?;
173            return Ok(expr);
174        }
175        if self.cursor.try_consume("[")? {
176            let expr = self.alternation(Some(']'))?;
177            self.cursor.consume("]")?;
178            return Ok(GrammarExpr::optional(expr));
179        }
180        match self.cursor.peek() {
181            Some('"') => Ok(GrammarExpr::TerminalInsensitive(
182                self.cursor.quoted(Some(default_escapes))?,
183            )),
184            Some('<') => Err(unsupported_error(FORMAT, "prose-val")),
185            Some('%') => self.percent_value(),
186            _ => Ok(GrammarExpr::NonTerminal(self.cursor.identifier_with(
187                |character| character.is_ascii_alphabetic(),
188                |character| character.is_ascii_alphanumeric() || character == '-',
189            )?)),
190        }
191    }
192
193    /// Reads `%s"…"`, `%i"…"`, or a `%b`, `%d`, or `%x` numeric value, range,
194    /// or dotted series.
195    fn percent_value(&mut self) -> Result<GrammarExpr, GrammarImportError> {
196        self.cursor.consume("%")?;
197        let kind = self.cursor.take().map(|kind| kind.to_ascii_lowercase());
198        if matches!(kind, Some('s' | 'i')) && self.cursor.peek() == Some('"') {
199            let value = self.cursor.quoted(Some(default_escapes))?;
200            return Ok(if kind == Some('s') {
201                GrammarExpr::Terminal(value)
202            } else {
203                GrammarExpr::TerminalInsensitive(value)
204            });
205        }
206        let radix = match kind {
207            Some('b') => 2,
208            Some('d') => 10,
209            Some('x') => 16,
210            _ => return Err(self.cursor.error("invalid percent value")),
211        };
212        let is_digit = |character: char| character.is_digit(radix);
213        let rest = self.cursor.rest();
214        let first = leading(rest, is_digit);
215        if first.is_empty() {
216            return Err(self.cursor.error("invalid numeric terminal"));
217        }
218        let after = &rest[first.len()..];
219        if let Some(end) = after
220            .strip_prefix('-')
221            .map(|after| leading(after, is_digit))
222            .filter(|end| !end.is_empty())
223        {
224            self.cursor.advance(first.len() + 1 + end.len());
225            return Ok(GrammarExpr::CharRange(
226                decode_code_point(first, radix)?,
227                decode_code_point(end, radix)?,
228            ));
229        }
230        let mut values = vec![first];
231        let mut length = first.len();
232        while let Some(value) = rest[length..]
233            .strip_prefix('.')
234            .map(|after| leading(after, is_digit))
235            .filter(|value| !value.is_empty())
236        {
237            values.push(value);
238            length += 1 + value.len();
239        }
240        self.cursor.advance(length);
241        let mut literal = String::new();
242        for value in values {
243            literal.push(decode_code_point(value, radix)?);
244        }
245        Ok(GrammarExpr::Terminal(literal))
246    }
247}
248
249/// The longest prefix of `text` whose characters all satisfy `predicate`.
250fn leading(text: &str, predicate: impl Fn(char) -> bool) -> &str {
251    let end = text
252        .find(|character: char| !predicate(character))
253        .unwrap_or(text.len());
254    &text[..end]
255}
256
257fn decode_code_point(value: &str, radix: u32) -> Result<char, GrammarImportError> {
258    u32::from_str_radix(value, radix)
259        .ok()
260        .and_then(char::from_u32)
261        .ok_or_else(|| unsupported_error(FORMAT, format!("numeric terminal value {value}")))
262}
263
264/// Rewrites every reference to the spelling of the rule it names, ignoring
265/// ASCII case.
266fn canonicalize_references(rules: &mut [GrammarRule]) {
267    let names = rules
268        .iter()
269        .map(|rule| rule.name.clone())
270        .collect::<Vec<_>>();
271    for rule in rules {
272        for_each_reference(&mut rule.expr, &mut |name| {
273            if let Some(canonical) = names
274                .iter()
275                .find(|candidate| candidate.eq_ignore_ascii_case(name))
276            {
277                name.clone_from(canonical);
278            }
279        });
280    }
281}
282
283fn for_each_reference(expr: &mut GrammarExpr, visit: &mut impl FnMut(&mut String)) {
284    match expr {
285        GrammarExpr::NonTerminal(name) => visit(name),
286        GrammarExpr::Choice {
287            alternatives: items,
288            ..
289        }
290        | GrammarExpr::Sequence(items) => {
291            for item in items {
292                for_each_reference(item, visit);
293            }
294        }
295        GrammarExpr::Optional(expr)
296        | GrammarExpr::ZeroOrMore(expr)
297        | GrammarExpr::OneOrMore(expr)
298        | GrammarExpr::And(expr)
299        | GrammarExpr::Not(expr)
300        | GrammarExpr::Capture { expr, .. }
301        | GrammarExpr::Repeat { expr, .. } => for_each_reference(expr, visit),
302        GrammarExpr::Feature(feature) => {
303            feature.map_expressions(&mut |inner| for_each_reference(inner, visit));
304        }
305        GrammarExpr::Empty
306        | GrammarExpr::Terminal(_)
307        | GrammarExpr::TerminalInsensitive(_)
308        | GrammarExpr::CharRange(_, _)
309        | GrammarExpr::CharClass { .. }
310        | GrammarExpr::AnyChar => {}
311    }
312}
313
314/// Appends the RFC 5234 core rules the grammar references, in order of first
315/// reference, under the spelling used by the reference.
316fn inject_core_rules(rules: &mut Vec<GrammarRule>) {
317    loop {
318        let mut referenced = Vec::new();
319        for rule in rules.iter() {
320            collect_references(&rule.expr, &mut referenced);
321        }
322        let mut added = false;
323        for name in referenced {
324            if rules.iter().any(|rule| rule.name == name) {
325                continue;
326            }
327            if let Some(expr) = core_expression(&name) {
328                rules.push(GrammarRule::new(name, expr));
329                added = true;
330            }
331        }
332        if !added {
333            return;
334        }
335    }
336}
337
338fn core_expression(name: &str) -> Option<GrammarExpr> {
339    let wsp =
340        || GrammarExpr::char_class(false, [CharClassItem::Char(' '), CharClassItem::Char('\t')]);
341    let terminal = |value: &str| GrammarExpr::Terminal(value.to_string());
342    Some(match name.to_ascii_uppercase().as_str() {
343        "ALPHA" => GrammarExpr::char_class(
344            false,
345            [
346                CharClassItem::Range('A', 'Z'),
347                CharClassItem::Range('a', 'z'),
348            ],
349        ),
350        "BIT" => GrammarExpr::CharRange('0', '1'),
351        "CHAR" => GrammarExpr::CharRange('\u{01}', '\u{7f}'),
352        "CR" => terminal("\r"),
353        "CRLF" => sequence(vec![terminal("\r"), terminal("\n")]),
354        "CTL" => choice(
355            vec![
356                GrammarExpr::CharRange('\u{00}', '\u{1f}'),
357                GrammarExpr::CharRange('\u{7f}', '\u{7f}'),
358            ],
359            false,
360        ),
361        "DIGIT" => GrammarExpr::CharRange('0', '9'),
362        "DQUOTE" => terminal("\""),
363        "HEXDIG" => GrammarExpr::char_class(
364            false,
365            [
366                CharClassItem::Range('0', '9'),
367                CharClassItem::Range('A', 'F'),
368                CharClassItem::Range('a', 'f'),
369            ],
370        ),
371        "HTAB" => terminal("\t"),
372        "LF" => terminal("\n"),
373        "OCTET" => GrammarExpr::CharRange('\u{00}', '\u{ff}'),
374        "SP" => terminal(" "),
375        "VCHAR" => GrammarExpr::CharRange('!', '~'),
376        "WSP" => wsp(),
377        "LWSP" => GrammarExpr::zero_or_more(choice(
378            vec![wsp(), sequence(vec![terminal("\r\n"), wsp()])],
379            false,
380        )),
381        _ => return None,
382    })
383}
meta_language/grammar/import/abnf.rs

meta_language/grammar/import/
abnf.rs
