From Pratt to DijkstraApr 15, 2020

This is a sequel to the previous post about Pratt parsing. Here, well study the relationship between top-down operator precedence (Pratt parsing) and the more famous shunting yard algorithm. Spoiler: they are the same algorithm, the difference is implementation style with recursion (Pratt) or a manual stack (Dijkstra).

Unlike the previous educational post, this one is going to be an excruciatingly boring pile of technicalities well just slowly and mechanically refactor our way to victory. Specifically,

1. We start with refactoring Pratt parser to minimize control flow variations.
2. Then, having arrived at the code with only one `return` and only one recursive call, we replace recursion with an explicit stack.
3. Finally, we streamline control in the iterative version.
4. At this point, we have a bona fide shunting yard algorithm.

To further reveal the connection, we further verify that the original recursive and the iterative formulation produce syntax nodes in the same order.

Really, the most exciting bit about this post is the conclusion, and you already know it :)

Starting Point

Last time, weve ended up with the following code:

First, to not completely drown in minutia, well simplify it by removing support for indexing operator `[]` and ternary operator `?:`. We will keep parenthesis, left and right associative operators, and the unary minus (which is somewhat tricky to handle in shunting yard). So this is our starting point:

What I like about this code is how up-front it is about all special cases and control flow. This is a shameless green code! However, it is clear that we have a bunch of duplication between prefix, infix and postfix operators. Our first step would be to simplify the control flow to its core.

Minimization

First, lets merge postfix and infix cases, as they are almost the same. The idea is to change priorities for `!` from `(11, ())` to `(11, 100)`, where `100` is a special, very strong priority, which means that the right hand side of a binary operator is empty. Well handle this in a pretty crude way right now, but all the hacks would go away once we refactor the rest.

Yup, we just check for hard-coded `100` constant and use a bunch of unwraps all over the place. But the code is already smaller.

Lets apply the same treatment for prefix operators. Well need to move their handing into the loop, and we also need to make `lhs` optional, which is now not a big deal, as the function as a whole returns an `Option`. On a happier note, this will allow us to remove the `if 100` wart. Whats more problematic is handing priorities: minus has different binding powers depending on whether it is in an infix or a prefix position. We solve this problem by just adding an `prefix: bool` argument to the `binding_power` function.

Keen readers might have noticed that we use `99` and not `100` here for no operand case. This is not important yet, but will be during the next step.

Weve unified prefix, infix and postfix operators. The next logical step is to treat atoms as nullary operators! That is, well parse `92` into `(92)` S-expression, with `None` for both `lhs` and `rhs`. We get this by using `(99, 100)` binding power. At this stage, we can get rid of distinction between atom tokens and operator tokens, and make the lexer return underlying `char`s directly. Well also get rid of `S::Atom`, which gives us this somewhat large change:

This is the stage where it becomes important that fake binding power of unary `-` is `99`. After parsing first constant in `1 - 2` the `r_bp` is `100`, and we need to avoid eating the following minus.

The only thing left outside the main loop are parenthesis. We can deal with them using `(99, 0)` priority after `(` we enter a new context where all operators are allowed.

Or, after some control flow cleanup:

This is still recognizably a Pratt parse, with its characteristic shape

What well do next is mechanical replacement of recursion with a manual stack.

From Recursion to Stack

This is a general transformation and (I think) it can be done mechanically. The interesting bits during transformation are recursive calls themselves and returns. The underlying goal of the preceding refactorings was to reduce the number of recursive invocations to one. We still have two `return` statements there, so lets condense that to just one as well:

Next, we should reify locals which are live across the recursive call into a data structure. If there were more than one recursive call, wed have to reify control-flow as enum as well, but weve prudently removed all but one recursive invocation.

So lets start with introducing a `Frame` struct, without actually adding a stack just yet.

And now, lets add a `stack: Vec<Frame>`. This is the point where the magic happens. Well still keep the `top` local variable: representing a stack as `(T, Vec<T>)` and not as just `Vec<T>` gives us compile-time guarantee of non-emptiness. We replace the `expr_bp(lexer, r_bp)` recursive call with pushing to the stack. All operations after the call are moved after `return`. `return` itself is replaced with popping off the stack.

Tada! No recursion anymore, and still passes the tests! Lets cleanup this further though. First, lets treat `)` more like a usual operator. The correct binding powers here are the opposite of `(`: `(0, 100)`:

Finally, lets note that `continue` inside the `match` is somewhat wasteful when we hit it, well re-`peek` the same token again. So lets repeat just the match until we know we can make progress. This also allows replacing `peek() / next()` pair with just `next()`.

And guess what? This is the shunting yard algorithm, with its characteristic shape of

To drive the point home, lets print the tokens we pop off the stack, to verify that we get reverse Polish notation without any kind of additional tree rearrangement, just like in the original algorithm description:

We actually could have done it with the original recursive formulation as well. Placing `print` statements at all points where we construct an `S` node prints expression in a reverse polish notation, proving that the recursive algorithm does the same steps and in the same order as the shunting yard.

Q.E.D.

The code from this and the previous article is available here: https://github.com/matklad/minipratt.