1. 42
  1.  

  2. 4

    This is the first clear explanation I’ve seen of Pratt parsing. I’ve been in sore need of an explanation for a project I’m working on. Thank you!

    A few typos to report:

    • approach is roghtly the one
    • And lo, we have a fully functioning minimal Prat parser: And lo, we have a fully functioning minimal Prat parser:
    1. 4

      I added a link to this article in my survey, along with a note about what makes Pratt parsing different than other recursive algorithms:

      http://www.oilshell.org/blog/2017/03/31.html#2020

      Maybe that helps? There are also 4 other intros I linked, but I guess they weren’t that clear.

      1. 1

        Ah, I wasn’t aware or I forgot about your index. Now that I see it, the algorithm is really simple and easy to understand. I had a mental block before this and I’ve seen at least a few of the articles I see in your index. I’m not sure what it was about this article that made it clear to me (maybe it was the static types). But now it would be hard to see what made the others less clear.

    2. 2

      I’ve been using this post to implement a parser in rust last night, and it works beautifully. Thanks for the amazing writeup.

      1. 1

        I was following along with this explanation very well at first, but hit a wall at the section From Precedence to Binding Power. That section makes several mental leaps that took me a long time to puzzle through. These are the parts that confused me, including some suggestions for explaining them better. Hopefully my suggestions will also help other readers who are confused, even if they are not incorporated into the article.

        Premature introduction of two binding powers per operator

        Why assign an operator two binding powers, one for the left and one for the right sides? I naturally think of “addition” of having a single precedence that can be compared to the single precedence of “multiplication”. That is, why start with the second model below instead of the first model?

        expr:   A   +   B   *   C
        power:      3       5
        
        expr:   A   +   B   *   C
        power:    3   3   5   5
        

        You later motivate the second model by using different numbers on the left and right, but I think before the reader sees the motivation for using two numbers, you should diagram the expression using the first model. Then you can point out and explain the surprising operation of splitting the numbers in two.

        Meanings of “fold” and “reduce”

        What do “fold” and “reduce” mean in this context? I can see they have something to do with parenthesization, but I don’t think “folding” just means “parenthesizing”. Folding sounds more technical, like some well-defined operation that can be performed on a node.

        Also, what’s the difference between folding and reducing? I know that in the context of building a result value through iteration over a collection, like [1, 2, 3].reduce(0, (sum, n) => sum + n), “fold” and “reduce” mean the same thing – is it the same here?

        No specific suggestions here – I still don’t know the answers to these questions.

        Justifications for two binding powers per operator

        Associativity

        When you motivate the splitting of binding powers with this example:

        expr:      A       +       B       +       C
        power:  0      3      3.1      3      3.1     0
        

        And use those binding powers to get to (A + B) + C, my reaction is “what’s the point?” The result would be exactly the same if you parsed it as A + (B + C), because addition is associative. In the end, you’re making Atoms and Cons cells, so won’t the expression just end up as (+ A B C), making the order of parentheses irrelevant?

        Only after a lot of thinking did I realize that the order of binding would be important for non-associative operators. A - B - C would be a much better example for introducing split binding powers.

        Parse order limitations

        Even after thinking of that example, I still wondered why we need these binding powers to tell us to fold from left to right. The program is processing the token stream from left to right anyway, so it feels like it could do that automatically.

        It’s great that you introduce the function composition operator ., because it can show that that assumption is wrong. However, I think you should help the reader by pointing this out explicitly, making it clear why you bothered to mention this operator: it’s the reason we can’t ignore binding powers and always fold from left to right.

        Holding arguments tighter than their neighbors

        It took many rereads to notice the importance of this sentence and understand what it meant:

        Here, the first (and only the first) + holds both of its arguments tighter than the neighbors, so we can reduce it:

        “Binding tighter than neighbors” is a new and unexpected concept. I think it’s worth expanding it with examples, like this:

        We define the next operator that should be folded [whatever “fold” means] by that operator holding its neighbors with a higher binding power than the other neighbors of those neighbors. For example, when considering whether to fold the first +:

        • + binds with the previous A with a power of 3
          • The other neighbor of A, the start of the string, binds with power 0. So the + is stronger.
        • + binds with the following B with a power of 3.1
          • The other neighbor of B, another +, binds with power 3. So this + is stronger.

        As you can see, the first + binds tighter than its neighbors. And when considering whether to fold the second +:

        • + binds with the previous B with a power of 3
          • The other neighbor of B, another +, binds with power 3. So this + is weaker, and should be folded later.
        • + binds with the following C with a power of 3.1
          • The other neighbor of C, the end of the string, binds with power 0. So the + is stronger.

        Since the first + has a stronger claim one of the neighbors, the second + should be folded after it.

        Those examples would change slightly if you used - instead of +, as I suggested earlier.

        Function name expr_bp

        The next section, Minimal Pratt Parser had a slightly confusing part too: the function name expr_bp in the first version of the parsing code. When looking at expr, expr_bp, and tests, I couldn’t guess what the “bp” stood for.

        After a minute more of reading, I understood that it stood for “binding power”. I assume you didn’t name that function expr_binding_power because you wanted to shorten its later recursive calls, so I suggest adding this comment above the function definition: // expression using binding power.