Mythic Logos

Version 4 has an error in it.

Try parsing 4^3^2. Parser 4 gives (4^3)^2 = 4096. Google gives 262144 as does Parser 5alpha. They parse it as 4^(3^2).

So how does Pratt parsing handle this? First, note that it is only an issue for operators with the same binding power. Different binding powers are there exactly to deal with implied associativity.

Parser 4 has this behavior because it keeps chugging along until the next token’s binding power is smaller than the previous one or the same. Thus, when it encounters something of its own level, it stops and deals with what it has already before moving on.

This is what we want for something like 7-3-4= (7-3)-4 not 7-(3-4). But as noted above, the power operator is not of that kind. So what do we do?

Well, when dealing with infix operators, we pass a binding power to the expression function to tell the stuff on the right when to stop. That stuff stops when the passed in power is greater than the right power. So we need to pass in a smaller power so that the process keeps going. That is, instead of passing a binding power of 20, we pass one of 19. Thus when it encounters one of its own, it compares 19 to 20 and decides to keep going.

See Wiki article on operator associativity.