4 ms·

Pratt parsing is essentially hand-written LR. It's certainly bottom-up in the same way, despite Pratt's paper title. (I went into more depth on this a few year

by Rusky 2y ago

Pratt parsing is essentially hand-written LR. It's certainly bottom-up in the same way, despite Pratt's paper title. (I went into more depth on this a few years ago: https://www.abubalay.com/blog/2021/12/31/lr-control-flow https://www.abubalay.com/blog/2021/12/31/lr-control-flow)

chubot 2y ago
Hm I wouldn't call it bottom up -- I would say it's top down, but you consult a table of integers to decide where to recurse. I would even call it a variant of recursive descent, which is top-down. In plain recursive descent, you often choose where to recurse based on the first token (e.g. if while for). In Pratt, you choose based on a table indexed by the second operater token. You can have an an entire arbitrary length subexpression before the "second token", but it is still resolved "eagerly". e.g. consulting the loop here - https://github.com/andychu/pratt-parsing-demo/blob/master/tdop.py#L212 https://github.com/andychu/pratt-parsing-demo/blob/master/td... I skimmed over your post, but I don't really see the bottom-up argument. I guess I could concede that it's neither top down nor bottom up, but I don't see the argument for being bottom up. And maybe this is just a taxonomy thing, which doesn't matter in practice. It could be understood both ways -- I don't think Vaughan Pratt was mistaken when he understood it a certain way :) --- "where to recurse" is basically choosing the parent's production before its children -- that's most similar to top down If you choose the child's production before its parent, then that's LR / bottom-up (using Haberman's explanation - https://blog.reverberate.org/2013/07/ll-and-lr-parsing-demystified.html https://blog.reverberate.org/2013/07/ll-and-lr-parsing-demys...) May also be relevant: https://www.oilshell.org/blog/2017/03/31.html https://www.oilshell.org/blog/2017/03/31.html https://www.oilshell.org/blog/2017/04/22.html https://www.oilshell.org/blog/2017/04/22.html https://matklad.github.io/2020/04/15/from-pratt-to-dijkstra.html https://matklad.github.io/2020/04/15/from-pratt-to-dijkstra.... I believe some people claimed that Dijikstra is bottom-up and Pratt is top down. That has a certain nice symmetry to it, but I'm not sure it's true :) Dijikstra does use an explicit stack and Pratt uses the call stack -- maybe that is how I'd put it.
- Rusky 2y ago
  The fact that you parse an entire subtree before you know the kind of its parent is exactly what makes it bottom-up. Pratt is certainly easy to integrate into an otherwise-top-down parser, because you can enter it from the top and it can enter its "leaves" from the top, but internally it is absolutely bottom-up, and you can generalize this to any recursive ascent parser. To make this more explicit: The first thing a Pratt parser does before entering the loop is based on the lookahead token's "nud." This corresponds to an LR automaton in its initial state shifting that token and advancing into the leaf-most rule(s). The "nud" typically switches back to top-down internally, where pure bottom-up would not, but the choice of "nud" is necessarily made in a bottom-up way. Once "nud" returns, or the LR automaton reduces back to the initial state, the next thing it does is based on the operator token's "led." This corresponds to the LR automaton shifting that token and advancing into the parent rule determined by the operator. This resolution is just as "eager" in LR, where it is represented by the new state containing only items from the chosen rule. This is the hallmark of bottom-up parsing: as you progress through the children, you narrow down the possibilities for the parent. Finally, note that none of this has anything to do with the use of function calls vs a table of integers and explicit stack. Both top-down and bottom-up parsers can be implemented using either recursion or a table and stack.
  - chubot 2y ago
    OK interesting, yeah I do see that if you consider how these expressions are parsed 1 + 1 * 42 1 + 1 + 1 * 42 1 + 1 + 1 + ... * 42 Or simply right associative operators. I'm not sure how much the classification matters, similar to how I've concluded that pratt parsing vs. shunting yard doesn't seem to "matter" (both work) But I have heard the "complaint" that pratt parsing is hard to understand, so maybe explaining it as a bottom up could help. The arbitrary length subexpression prefix is really the problem that LR solves compared to LL (historically Python used LL parsing, and param=value and lvalue=rvalue are "overparsed" for this reason)
    - Rusky 2y ago
      Yeah- I tend to think of the whole vague collection of LR + shunting yard + Pratt as one single approach in my head, with the same capabilities in terms of parsing. Sometimes working through a particular problem, or conflict, or example is easier from one than the others, but knowing how they correspond (which is similar to how iteration and recursion correspond) means you can translate those ideas across.

by Rusky 2y ago

chubot 2y ago

Hm I wouldn't call it bottom up -- I would say it's top down, but you consult a table of integers to decide where to recurse. I would even call it a variant of recursive descent, which is top-down. In plain recursive descent, you often choose where to recurse based on the first token (e.g. if while for). In Pratt, you choose based on a table indexed by the second operater token. You can have an an entire arbitrary length subexpression before the "second token", but it is still resolved "eagerly". e.g. consulting the loop here - https://github.com/andychu/pratt-parsing-demo/blob/master/tdop.py#L212 https://github.com/andychu/pratt-parsing-demo/blob/master/td... I skimmed over your post, but I don't really see the bottom-up argument. I guess I could concede that it's neither top down nor bottom up, but I don't see the argument for being bottom up. And maybe this is just a taxonomy thing, which doesn't matter in practice. It could be understood both ways -- I don't think Vaughan Pratt was mistaken when he understood it a certain way :) --- "where to recurse" is basically choosing the parent's production before its children -- that's most similar to top down If you choose the child's production before its parent, then that's LR / bottom-up (using Haberman's explanation - https://blog.reverberate.org/2013/07/ll-and-lr-parsing-demystified.html https://blog.reverberate.org/2013/07/ll-and-lr-parsing-demys...) May also be relevant: https://www.oilshell.org/blog/2017/03/31.html https://www.oilshell.org/blog/2017/03/31.html https://www.oilshell.org/blog/2017/04/22.html https://www.oilshell.org/blog/2017/04/22.html https://matklad.github.io/2020/04/15/from-pratt-to-dijkstra.html https://matklad.github.io/2020/04/15/from-pratt-to-dijkstra.... I believe some people claimed that Dijikstra is bottom-up and Pratt is top down. That has a certain nice symmetry to it, but I'm not sure it's true :) Dijikstra does use an explicit stack and Pratt uses the call stack -- maybe that is how I'd put it.

Rusky 2y ago
The fact that you parse an entire subtree before you know the kind of its parent is exactly what makes it bottom-up. Pratt is certainly easy to integrate into an otherwise-top-down parser, because you can enter it from the top and it can enter its "leaves" from the top, but internally it is absolutely bottom-up, and you can generalize this to any recursive ascent parser. To make this more explicit: The first thing a Pratt parser does before entering the loop is based on the lookahead token's "nud." This corresponds to an LR automaton in its initial state shifting that token and advancing into the leaf-most rule(s). The "nud" typically switches back to top-down internally, where pure bottom-up would not, but the choice of "nud" is necessarily made in a bottom-up way. Once "nud" returns, or the LR automaton reduces back to the initial state, the next thing it does is based on the operator token's "led." This corresponds to the LR automaton shifting that token and advancing into the parent rule determined by the operator. This resolution is just as "eager" in LR, where it is represented by the new state containing only items from the chosen rule. This is the hallmark of bottom-up parsing: as you progress through the children, you narrow down the possibilities for the parent. Finally, note that none of this has anything to do with the use of function calls vs a table of integers and explicit stack. Both top-down and bottom-up parsers can be implemented using either recursion or a table and stack.
- chubot 2y ago
  OK interesting, yeah I do see that if you consider how these expressions are parsed 1 + 1 * 42 1 + 1 + 1 * 42 1 + 1 + 1 + ... * 42 Or simply right associative operators. I'm not sure how much the classification matters, similar to how I've concluded that pratt parsing vs. shunting yard doesn't seem to "matter" (both work) But I have heard the "complaint" that pratt parsing is hard to understand, so maybe explaining it as a bottom up could help. The arbitrary length subexpression prefix is really the problem that LR solves compared to LL (historically Python used LL parsing, and param=value and lvalue=rvalue are "overparsed" for this reason)
  - Rusky 2y ago
    Yeah- I tend to think of the whole vague collection of LR + shunting yard + Pratt as one single approach in my head, with the same capabilities in terms of parsing. Sometimes working through a particular problem, or conflict, or example is easier from one than the others, but knowing how they correspond (which is similar to how iteration and recursion correspond) means you can translate those ideas across.