meta_language/grammar/import/
pest.rs

1//! Hand-written pest PEG importer, a port of
2//! `js/src/grammar-importers/pest.js`.
3
4use super::common::{
5    Cursor, canonical_repeat, choice, decimal, default_escapes, grammar_from_rules, is_space,
6    sequence,
7};
8use super::{GrammarImportError, parse_error, unsupported_error};
9use crate::grammar::{Grammar, GrammarExpr, GrammarFormat, GrammarRule, RuleKind};
10
11const FORMAT: GrammarFormat = GrammarFormat::Peg;
12
13/// The pest built-in rules a grammar may reference without defining them.
14const PEST_BUILTINS: &[&str] = &[
15    "ANY",
16    "SOI",
17    "EOI",
18    "ASCII_DIGIT",
19    "ASCII_NONZERO_DIGIT",
20    "ASCII_BIN_DIGIT",
21    "ASCII_OCT_DIGIT",
22    "ASCII_HEX_DIGIT",
23    "ASCII_ALPHA_LOWER",
24    "ASCII_ALPHA_UPPER",
25    "ASCII_ALPHA",
26    "ASCII_ALPHANUMERIC",
27    "ASCII",
28    "NEWLINE",
29    "UNICODE",
30    "LETTER",
31    "CASED_LETTER",
32    "UPPERCASE_LETTER",
33    "LOWERCASE_LETTER",
34    "TITLECASE_LETTER",
35    "MODIFIER_LETTER",
36    "OTHER_LETTER",
37    "MARK",
38    "NUMBER",
39    "PUNCTUATION",
40    "SEPARATOR",
41    "SYMBOL",
42    "CONTROL",
43    "XID_START",
44    "XID_CONTINUE",
45];
46
47/// Parses PEG `.pest` grammar text into the grammar IR.
48///
49/// Rules are `name = modifier? { expression }` with the modifiers `_`
50/// (silent), `@` (atomic), `$` (token), and `!` (normal). Expressions use
51/// ordered choice `|`, sequence `~`, the predicates `&` and `!`, the postfix
52/// operators `?`, `*`, `+`, and counted repetition `{n}`, `{n,}`, `{,m}`,
53/// `{n,m}`, over strings, `^"…"` case-insensitive strings, `'a'..'z'` ranges,
54/// and rule references, where `ANY` matches any character. `//` and `/* */`
55/// comments are skipped.
56///
57/// # Errors
58///
59/// Returns [`GrammarImportError`] when the pest grammar cannot be parsed, when
60/// a parsed construct (such as `PUSH(…)` or `PEEK[…]`) cannot be represented
61/// in the grammar IR, or when a non-terminal reference does not resolve to a
62/// local rule or pest built-in.
63pub fn import_pest(text: &str) -> Result<Grammar, GrammarImportError> {
64    let mut parser = PestParser {
65        cursor: Cursor::with_comments(text, FORMAT),
66    };
67    let rules = parser.rules()?;
68    grammar_from_rules(FORMAT, rules, PEST_BUILTINS)
69}
70
71struct PestParser<'source> {
72    cursor: Cursor<'source>,
73}
74
75impl PestParser<'_> {
76    fn rules(&mut self) -> Result<Vec<GrammarRule>, GrammarImportError> {
77        let mut rules: Vec<GrammarRule> = Vec::new();
78        loop {
79            self.cursor.skip_space()?;
80            if self.cursor.eof() {
81                return Ok(rules);
82            }
83            let name = self.cursor.identifier()?;
84            if rules.iter().any(|rule| rule.name == name) {
85                return Err(parse_error(FORMAT, format!("duplicate rule {name}")));
86            }
87            self.cursor.consume("=")?;
88            self.cursor.skip_space()?;
89            let kind = match self.cursor.peek() {
90                Some(modifier @ ('_' | '@' | '$' | '!')) => {
91                    self.cursor.take();
92                    match modifier {
93                        '_' => RuleKind::Silent,
94                        '@' => RuleKind::Atomic,
95                        '$' => RuleKind::Token,
96                        _ => RuleKind::Normal,
97                    }
98                }
99                _ => RuleKind::Normal,
100            };
101            self.cursor.consume("{")?;
102            let expr = self.alternation()?;
103            self.cursor.consume("}")?;
104            rules.push(GrammarRule::new(name, expr).with_kind(kind));
105        }
106    }
107
108    fn alternation(&mut self) -> Result<GrammarExpr, GrammarImportError> {
109        let mut alternatives = vec![self.sequence()?];
110        while self.cursor.try_consume("|")? {
111            alternatives.push(self.sequence()?);
112        }
113        Ok(choice(alternatives, true))
114    }
115
116    fn sequence(&mut self) -> Result<GrammarExpr, GrammarImportError> {
117        let mut items = vec![self.prefix()?];
118        while self.cursor.try_consume("~")? {
119            items.push(self.prefix()?);
120        }
121        Ok(sequence(items))
122    }
123
124    fn prefix(&mut self) -> Result<GrammarExpr, GrammarImportError> {
125        if self.cursor.try_consume("&")? {
126            return self.prefix().map(GrammarExpr::and);
127        }
128        if self.cursor.try_consume("!")? {
129            return self.prefix().map(GrammarExpr::not);
130        }
131        self.postfix()
132    }
133
134    fn postfix(&mut self) -> Result<GrammarExpr, GrammarImportError> {
135        let expr = self.atom()?;
136        if self.cursor.try_consume("?")? {
137            return Ok(GrammarExpr::optional(expr));
138        }
139        if self.cursor.try_consume("*")? {
140            return Ok(GrammarExpr::zero_or_more(expr));
141        }
142        if self.cursor.try_consume("+")? {
143            return Ok(GrammarExpr::one_or_more(expr));
144        }
145        self.cursor.skip_space()?;
146        match counted_repetition(self.cursor.rest()) {
147            Some((length, min, max)) => {
148                self.cursor.advance(length);
149                canonical_repeat(FORMAT, expr, min, max)
150            }
151            None => Ok(expr),
152        }
153    }
154
155    fn atom(&mut self) -> Result<GrammarExpr, GrammarImportError> {
156        self.cursor.skip_space()?;
157        if self.cursor.try_consume("(")? {
158            let expr = self.alternation()?;
159            self.cursor.consume(")")?;
160            return Ok(expr);
161        }
162        match self.cursor.peek() {
163            Some('^') => {
164                self.cursor.advance(1);
165                if self.cursor.peek() != Some('"') {
166                    return Err(self
167                        .cursor
168                        .error("case-insensitive marker must precede a string"));
169                }
170                return Ok(GrammarExpr::TerminalInsensitive(
171                    self.cursor.quoted(Some(default_escapes))?,
172                ));
173            }
174            Some('"') => {
175                return Ok(GrammarExpr::Terminal(
176                    self.cursor.quoted(Some(default_escapes))?,
177                ));
178            }
179            Some('\'') => {
180                let start = self.cursor.quoted(Some(default_escapes))?;
181                self.cursor.consume("..")?;
182                let end = self.cursor.quoted(Some(default_escapes))?;
183                return match (single_char(&start), single_char(&end)) {
184                    (Some(start), Some(end)) => Ok(GrammarExpr::CharRange(start, end)),
185                    _ => Err(parse_error(
186                        FORMAT,
187                        "character range endpoints must be one character",
188                    )),
189                };
190            }
191            _ => {}
192        }
193        let name = self.cursor.identifier()?;
194        self.cursor.skip_space()?;
195        let next = self.cursor.peek();
196        if name == "PUSH" && next == Some('(') {
197            return Err(unsupported_error(FORMAT, "Push"));
198        }
199        if name == "PEEK" && next == Some('[') {
200            return Err(unsupported_error(FORMAT, "PeekSlice"));
201        }
202        Ok(if name == "ANY" {
203            GrammarExpr::AnyChar
204        } else {
205            GrammarExpr::NonTerminal(name)
206        })
207    }
208}
209
210fn single_char(text: &str) -> Option<char> {
211    let mut characters = text.chars();
212    let character = characters.next()?;
213    characters.next().is_none().then_some(character)
214}
215
216/// Matches `{n}`, `{n,}`, `{,m}`, or `{n,m}` at the start of `text`, as the
217/// JavaScript pattern `^\{\s*(\d*)\s*(?:,\s*(\d*)\s*)?\}` does, returning the
218/// matched length and the bounds. `{}` and `{ }` are not counted repetition.
219fn counted_repetition(text: &str) -> Option<(usize, u64, Option<u64>)> {
220    let digits = |text: &str| -> usize {
221        text.find(|character: char| !character.is_ascii_digit())
222            .unwrap_or(text.len())
223    };
224    let spaces = |text: &str, from: usize| -> usize {
225        from + text[from..]
226            .find(|character: char| !is_space(character))
227            .unwrap_or(text.len() - from)
228    };
229    let mut index = spaces(text, text.strip_prefix('{').map(|_| 1)?);
230    let low_end = index + digits(&text[index..]);
231    let low = &text[index..low_end];
232    index = spaces(text, low_end);
233    let mut high = None;
234    if text[index..].starts_with(',') {
235        index = spaces(text, index + 1);
236        let high_end = index + digits(&text[index..]);
237        high = Some(&text[index..high_end]);
238        index = spaces(text, high_end);
239    }
240    if !text[index..].starts_with('}') || (low.is_empty() && high.is_none()) {
241        return None;
242    }
243    let min = decimal(low);
244    let max = match high {
245        None => Some(min),
246        Some("") => None,
247        Some(high) => Some(decimal(high)),
248    };
249    Some((index + 1, min, max))
250}
meta_language/grammar/import/pest.rs

meta_language/grammar/import/
pest.rs
