3 ms·

What might be an example of a syntax that can't be expressed (parsed) with a Pratt parser?

• vidarh 10y ago
  The right question is probably what syntax can't be expressed cleanly with a Pratt parser. Operator precedence parsing in general can be extended to parse anything relatively easily by introducing different kinds of operators with special treatment, but if your grammar can't be cleanly expressed in a way that naturally results in a sensible parse-tree by applying operator precedence (e.g. asterisk should bind tighter than "+" so that "5 * 2 + 1" is parsed (+ (* 5 2) 1) rather than (* 5 (+ 2 1))) you can end up with ugly special casing. An example that makes it more complicated (not impossible): In Ruby "x" depends on context. It can be a method call or a local variable reference. If "x" has been assigned to prior to the reference, it's a local variable. Except if it has a parameter list. "x 1" is a method call. Except if it's within a literal hash. "{ foo: x 1 }" is a syntax error - the parser wants a "," after "x". Even with Ruby I handle a substantial part of the syntax in my compiler with an operator precedence parser where the operator precedence parser class itself is about ~170 lines of Ruby (excluding the table of operator priorities which adds another 145 lines). But on top of that I so far have ended up with about the same again to "massage" the resulting parse tree into something that's nicer to work with. The challenge with these types of parsers, though, is generally more often that they are harder for people to reason about. If I express the rules I started with (for "+" vs asterisk) in a BNF-type syntax, I could do it like this: expr = plusexpr plusexpr = mulexpr ("+" plusexpr)* mulexpr = simple ("*" mulexpr)* simple = number|identifier It's quite clear if you've seen some variant of BNF before that "1 + 2 + 3" will go expr -> plusexpr -> mulexpr -> simple, return 1, then fail to find asterisk , find "+", parse a second "plusexpr" find 2 + 3, then exit with (+ 1 (+ 2 3)). And that "1 * 2 + 3" meanwhile will go expr -> plusxpr -> mulexpr -> simple, find "1", then find asterisk parse a second "mulexpr" which will find "2", return up to plusexpr, find "+" and eventually "3", and result in (+ (* 1 2) 3). But the grammar above, in terms of an operator precedence parser might be expressed by a table like this: +, INFIX, 10 *, INFIX, 20 The rest is "obscured" in the parser function. As long as it's this simple you can probably guess what's going on (the last number is the priority, and the values are arbitrary - only their relative size and whether high or low values are treated as binding tigher or loser by the parser matters), but when you e.g. add things like different types of brackets and parentheses, function calls, operators with different priorities if used as a prefix vs. infix etc. it can easily become hard to understand intuitively from the table of operators how the priorities interact. EDIT: Modified due to HN handling of asterisk...
  • zengid 10y ago
    I agree with you that operator precedence parsers are somewhat opaque in terms of how they function (at least I can say Pratt parsers are, of which I am most familiar). One has to juggle a lot of mechanics in their head. Also, they have to be able to imagine the recursive nature of the expression parsing without a nice BNF style definition that resides in one location as you mentioned.