PEG and Pratt play well together
Tags: parsing, peg, dsl, compilers
Published: 2019-08-28 10:29:13


A popular PEG-based parsing is nice, easy and beautiful. All the way until you want to define binary expressions with precedence and associativity. Then it's quickly getting ugly.

```
expr = { [expr1] "*" [expr] => ... }
     / { [expr1] "/" [expr] => ... }
     / [expr1];
     
expr1 = { [atom] "+" [expr1] => ... }
      / { [atom] "-" [expr1] => ... }
      / [atom];
      
... and so on

```

Of course, there are ways of handling left-recursive grammars with PEG (Packrat, in particular), see [PEPM08 slides](http://alexwarth.com/papers/pepm08-slides.pdf) for a quick introduction into one of the most practical methods of doing so. Is it sufficient? Not quite, grammars are still clumsy, and good luck expressing associativity in any meaningful way. 

The grammar above is right-associative, and the easiest way to turn it left-associative is to annotate the AST you're constructing and transform it later, without touching the grammar itself. And it's an obviously ugly way of doing things.

Just as an illustration of how bad this accidental right-associativity is: an expression `x-1-1` will be parsed as `x-(1-1)`, which is clearly not what we want.

Now, there is one little trick that PEG implementation vendors don't want you to know about. It's called [Pratt parsing](http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-expression-parsing-made-easy/).

It's very easy to understand and even easier to implement. The whole algorithm can be described as follows:

The `prefix` parser:

* Try parsing an `atom`
* If successful, store as `Left`, otherwise return the failure
* Try parsing a `binary` operator, one at a time (e.g., "*", "/", "+", "-"...)
* If all attempts failed, return `Left`, otherwise check precedence for the 
successful operator; if it's less than the current precedence, apply corresponding `infix` parser, otherwise return `Left`


An `infix` parser:

* Try parsing right side with a current precedence (using a `prefix` parser),
  if right-associative, use current precedence minus one.
* If successful, return the current result (apply an AST constructor, whatever),
  otherwise, backtrack to the beginning of the current `prefix` entry.
 
Pity it all only makes sense for the binary expressions with precedence and associativity, and pretty much useless for the rest of your grammar. Luckily, this algorithm does not tell us anything about *how* we're parsing atoms and binary operators. Looks like an opportunity!

Turns out, Pratt algorithm is very easy to embed into pretty much any kind of Packrat or any other PEG implementation - you can still do all the memoisation you want, and the whole Pratt is just another parsing order operator inside your PEG.

The grammar above now turns into something much nicer:

```
binary expr = 
         (200) [expr] "*" [expr] => ...
       | (200) [expr] "/" [expr] => ...
       | (100) [expr] "+" [expr] => ...
       | (100) [expr] "-" [expr] => ...
       | [atom]
       ;

atom = { "(" [expr] ")" => ... }
     / ... all the other trivial entries ...
```

Here, `200` is the precedence of the `*` and `/` operations, and `100` is a precedence of `+` and `-`. We can have as many precedence levels as we want, suitable for any language imaginable.

We don't care any more about all the consequences of having a left-recursive grammar, and we get a default left associativity for free. Our infamous `x-1-1` is not translated into `x-0` any more, with no extra effort!

This approach is successfully used in my optimising [PEG parsing system](https://github.com/combinatorylogic/mbase/tree/master/src/l/lib/parsing) which is a central part of the [PFront language](https://combinatorylogic.github.io/mbase-docs/),  and I highly recommend anyone implementing a PEG parser to do the same. It'll make your life easier, I promise.