During the design of my parser generator Mage, I encountered a problem with correctly generating parsers for expressions.
Let's say we have this definition for an expression in BNF:
expr ::= int_expr
| ref_expr
| add_expr
| sub_expr
| mul_expr
| div_expr
It should parse things like 1 + 2, 1 + 2 * 3 and 1 / 2 * 3 - 4 + 5.
The closest equivalent grammar in Mage would be:
pub expr
= try add_expr
| try sub_expr
| try mul_expr
| try div_expr
| int_expr
| ref_expr
Note that the try keyword in this example attempts to parse whatever comes next to it, and cleanly resets the stream to right before the try-expression was executed. Without it, add_expr might parse a single int_expr and advance the stream, but when it fails to parse the + the stream may remain after the int_expr.
Going further, here are some sample implementations of int_expr and ref_expr. We don't need them to be complete; we want them to be just useful enough to experiment with them.
pub int_expr
= [0-9]+
pub ref_expr
= [a-z]+
Finishing off our tiny grammar, we define four binary expressions:
pub add_expr
= expr '+' expr
pub sub_expr
= expr '-' expr
pub mul_expr
= expr '*' expr
pub div_expr
= expr '/' expr
Two Problems
We can immediately experience a first problem. This grammar appears to be a valid Mage grammar, but it wil execute forever. Say we give it simply foo as input. It will attempt to parse expr, then try add_expr, followed by expr and add_expr, going deeper and deeper and never coming to a halt.
Moreover, given the input 1 + 2 * 3, this grammar doesn't inform Mage whether we prefer (1 + 2) * 3 or 1 + (2 * 3). Which one is correct?
A Textbook Solution
We always need to parse something, right? Even if it is a small, tiny little atom. Let's therefore first define what can be safely parsed without any ugly infinite loops:
pub atom
= int_expr
| ref_expr
Parsing atom should never result in the infinite loop we saw earlier. Indeed, it can correctly parse 12345 and foobar.
Next, the textbook approach to avoid this infinite loop is to narrow down the possibilities that can be consumed while it descends into expr.
We define factor as the thing that is parsed within a multiplication, and term the thing that is parsed within addition or subtraction. After all choices have been exhausted, we delegate term to factor, which in turn delegates to atom.
pub term
| try add_expr
| try sub_expr
| factor
pub add_expr
= factor '+' term
pub sub_expr
= factor '-' term
pub factor
= try mul_expr
| try div_expr
| atom
pub mul_expr
= atom '*' factor
pub div_expr
= atom '/' factor
pub expr
= term
Note that a factor is closer to the 'ground' than a term, in the sense that it is closer to atomic formulae. This gives it a higher binding power than term.
When we e.g. parse 1 + 2 * 3, we first parse add_expr, which succeeds parsing a 1 and a +. We then continue parsing a term that delegates to factor, which in turn succeeds parsing mul_expr.
Pratt Parsing
We could abstract the previous technique to automatically transform Mage grammars so that they once again become executable, but this transformation is far from trivial. There's also the concern for speed: these try expressions can become overly expensive.
The question is: how do we generalize this approach and make it efficient? That's where Pratt parsing comes in.
The most popular article about Pratt parsing seems to be the one by Bob Nystrom, the guy who wrote the famous book Crafting Interpreters. I personally prefer the article by Alex Kladov, one of the maintainers of rust-analyzer.
A Pratt parser is more of a technique than an algorithm. The defining ingredient of a Pratt parser is precedence, or as Kladov calls it, binding power. Sub-expressions with a higher precedence appear deeper in the AST than sub-expressions with a lower precedence.
This code comes straight from Kladov's article:
fn expr_bp(lexer: &mut Lexer, min_bp: u8) -> S {
let mut lhs = match lexer.next() {
Token::Atom(it) => S::Atom(it),
Token::Op('(') => {
let lhs = expr_bp(lexer, 0);
assert_eq!(lexer.next(), Token::Op(')'));
lhs
}
Token::Op(op) => {
let ((), r_bp) = prefix_binding_power(op);
let rhs = expr_bp(lexer, r_bp);
S::Cons(op, vec![rhs])
}
t => panic!("bad token: {:?}", t),
};
loop {
let op = match lexer.peek() {
Token::Eof => break,
Token::Op(op) => op,
t => panic!("bad token: {:?}", t),
};
if let Some((l_bp, ())) = postfix_binding_power(op) {
if l_bp < min_bp {
break;
}
lexer.next();
lhs = if op == '[' {
let rhs = expr_bp(lexer, 0);
assert_eq!(lexer.next(), Token::Op(']'));
S::Cons(op, vec![lhs, rhs])
} else {
S::Cons(op, vec![lhs])
};
continue;
}
if let Some((l_bp, r_bp)) = infix_binding_power(op) {
if l_bp < min_bp {
break;
}
lexer.next();
lhs = if op == '?' {
let mhs = expr_bp(lexer, 0);
assert_eq!(lexer.next(), Token::Op(':'));
let rhs = expr_bp(lexer, r_bp);
S::Cons(op, vec![lhs, mhs, rhs])
} else {
let rhs = expr_bp(lexer, r_bp);
S::Cons(op, vec![lhs, rhs])
};
continue;
}
break;
}
lhs
}
In this Gist, I re-implement the algorithm in Python with a few changes.
First, my implementation uses .tell() and .seek() to save and restore the position of the stream right before an operator is going to be parsed. That way, functions like parse_postfix_operator can become as complex as needed without being required to 'clean up'.
Second, the functions parse_prefix_operator, parse_infix_operator and parse_postfix_operator return an anonymous function that builds the actual AST node from information they get from the main loop in parse_expr_bp. This way they aren't limited in what they can parse. Indeed: the entire ternary operator block, a special case in Kladov's code, becomes just another operator in my code. It just so happens to parse more than only the operator, namely an expression and a colon, as if the ? and : were two parentheses.
The above two adjustments allow us to write any expression as an operator, just like our Mage metagrammar allows.
The next challenge therefore isn't with our operators, but with which expressions are allowed.
Detecting Pratt Expressions
A point I made in the previous section gives us a powerful hint: anything between 'parentheses' (whatever they may be) can be plainly parsed as a top-level expression. See for yourself:
pub index_expr
= expr '[' expr ']'
The precedence of [ matters, but whatever comes after the [ is just part of the operator and doesn't influence precedence at all.
This means that the only place where precedence matters is at the beginning and end of an expression of a Mage rule. We get in Mage pseudo-code:
pub prefix_expr
= operator expr
pub postfix_expr
= expr operator
pub infix_expr
= expr operator expr
pub atom_expr
= any_non_expr
Remember, however, that a Mage grammar may contain any valid rule and that the developer might not have declared their Pratt-compatible rules as expr. Therefore we need to find some algorithm to scan the grammar for these rules. Luckily for us, Mage already has some machinery in place that will help us.
Mage can produce a call graph of an entire grammar, making it easy to spot those rules that indirectly call themselves. Those rules will form a cycle, and so we are tempted to perform a topological sort on this call graph.
One component coming out of this topological sort will look like this:
As expected from a single component, every rule is reachable by every other rule.
But hold on, what if we have a grammar like this:
pub one
= '1' two | 'x'
pub two
= '2' three | 'x'
pub three
= '3' four | 'x'
pub four
= '4' one | 'x'
The only component will look like this:
But this example isn't a Pratt expression! Clearly, a Pratt expression is more than a recursive call. A Pratt expression demands choice. Moreover, as we've seen, prefix and postfix require one recursive call at the respective edges while infix requires exactly two.
We come to the following definition:
A Pratt expression is an expression where at least one of the edges of the expression recursively call themselves, and during that call there is a possible choice to at least one other Pratt expression.
If we didn't have a choice somewhere, there is no need for a Pratt parser.
This detection mechanism will be implemented in an upcoming version of Mage. I will write a follow-up on the actual implementation of the parser, so stay tuned!
Top comments (0)