3 ms·

My blog links to some runnable Python code for this algorithm, with tests: Code for the Shunting Yard Algorithm http://www.oilshell.org/blog/2017/04/22.html ht

by chubot 8y ago

My blog links to some runnable Python code for this algorithm, with tests: Code for the Shunting Yard Algorithm http://www.oilshell.org/blog/2017/04/22.html http://www.oilshell.org/blog/2017/04/22.html https://github.com/bourguet/operator_precedence_parsing https://github.com/bourguet/operator_precedence_parsing It seems like there are 2 common algorithms for expressions: the shunting yard algorithm and Pratt parsing [1]. As best as I can tell, which one you use is a coin toss. I haven't been able to figure out any real difference. They're both nicer than grammar-based approaches when you have many levels of precedence, like C. But it doesn't seem like there is any strict relationship between the two algorithms, which is interesting. I guess there are other places where that happens, like there being at least two unrelated algorithms for topological sort. Trivia: The original C compilers used the shunting yard algorithm. IIRC the source made reference to Dijikstra. [1] http://www.oilshell.org/blog/2017/03/31.html http://www.oilshell.org/blog/2017/03/31.html

userbinator 8y ago
I haven't been able to figure out any real difference. The biggest difference is that Pratt/precedence climbing does not require manipulating an extra stack, but instead uses the normal procedure stack in the same manner as recursive descent. This leads to somewhat simpler code. I've seen far more uses of recursive descent/Pratt than shunting-yard.
- chubot 8y ago
  I understand that, but I think it's mostly a matter of opinion ("somewhat simpler"). It seems like the code comes out the same length either way, and they're both linear time algorithms. I can't imagine any case where a user will care -- it's an internal detail. Whereas there are places where a user would notice if you used a CFG vs. a PEG. A long time ago, people might have been concerned about the recursive calls of Pratt parsing, but it seems like a non-issue now. I do think Pratt parsing is easier to understand, but that might be because I encountered it first.
  - vidarh 8y ago
    I first tried shunting yard without knowing what it was by mechanically translating the stack usage from a Pratt parser, so I agree. The reason was that I'd extended it to handle a lot more unusual constructs, and at that point the recursive version got much harder to read. It was part of a (ill advised, probably) attempt at using it to parse an entire C-like language, control structures at all. It worked, but it was painful to figure out all the precedence rules, and e.g. if I remember correct modelling if () {} else {} as operator "if" with operands (condition if-block else-expression). The changes to allow weird prefix operators like that with multiple operands were otherwise reasonably straightforward, though, it was the precedence table that got really hard to reason about. [I wish I still had the source; it was a fun, though very much dated, project, that allowed arbitrary inline M68k assembler in expressions (e.g. you could write "if D0.W == $1000 { }" to compare the lower 16-bit word of data register 0 to hex 1000), with "mentioning" the registers making the register allocator treat them as off limits for that scope]
    - chubot 8y ago
      I don't think Shunting Yard and Pratt are equivalent in that way -- i.e. replacing procedure calls with an explicit stack. When I wrote "Pratt Parsing and Precedence Climbing Are the Same Algorithm", multiple people replied and suggested that the Shunting Yard algorithm is also the same, with the equivalence you suggest. In particular the author of the repo Jean-Marc Bourguet also thought that. Then he implemented it and realized it wasn't true. See this section of the README: https://github.com/bourguet/operator_precedence_parsing https://github.com/bourguet/operator_precedence_parsing I had the mistaken impression that they were "just" replacing an explicit stack with the call stack of the implementation language but that was not clear enough from Andy's code. It was not clear because that's not the case. Compare Pratt's algorithm with recursive_operator_precedence.py, which is a recursive implementation of operator precedence, to see the difference. Pratt and operator climbing are really top down techniques: they call semantic actions as soon as possible, they don't delay the call until the whole handle is seen as operator precedence does. My current characterization is that they are to LL parsing and recursive descent what operator precedence is to LR and shift-reduce I think we had a discussion about an analogy LL vs. LR. Those are obviously not equivalent algorithms -- despite both being linear time, they recognize different languages. I think in the Shunting Yard algorithm, when you parse 1 + 2 / 3, the 2 / 3 tree is made first. I guess that is somewhat true of Pratt parsing too for natural reasons of tree building. You build the tree when you bubble out of the recursion. But it DECIDES that it has "led" for + before it decides it has "led" for /. So in summary, Shunting Yard "decides" 2 / 3 first, where as Pratt parsing "decides" 1+... first. That's what I think anyway. I think you could probably make this rigorous, but I'm not sure. I think of Pratt Parsing as LL(2) parsing for an operator grammar, although that's not technically correct because the precedence table is an extra piece of info outside the "grammar". You either lookahead 1 or 2 tokens, for null and led respectively. So basically I think you could translate Pratt parsing to use an explicit stack -- but then you'd still be using Pratt parsing. The Shunting Yard algorithm is something else.

by chubot 8y ago

userbinator 8y ago

I haven't been able to figure out any real difference. The biggest difference is that Pratt/precedence climbing does not require manipulating an extra stack, but instead uses the normal procedure stack in the same manner as recursive descent. This leads to somewhat simpler code. I've seen far more uses of recursive descent/Pratt than shunting-yard.

chubot 8y ago
I understand that, but I think it's mostly a matter of opinion ("somewhat simpler"). It seems like the code comes out the same length either way, and they're both linear time algorithms. I can't imagine any case where a user will care -- it's an internal detail. Whereas there are places where a user would notice if you used a CFG vs. a PEG. A long time ago, people might have been concerned about the recursive calls of Pratt parsing, but it seems like a non-issue now. I do think Pratt parsing is easier to understand, but that might be because I encountered it first.
- vidarh 8y ago
  I first tried shunting yard without knowing what it was by mechanically translating the stack usage from a Pratt parser, so I agree. The reason was that I'd extended it to handle a lot more unusual constructs, and at that point the recursive version got much harder to read. It was part of a (ill advised, probably) attempt at using it to parse an entire C-like language, control structures at all. It worked, but it was painful to figure out all the precedence rules, and e.g. if I remember correct modelling if () {} else {} as operator "if" with operands (condition if-block else-expression). The changes to allow weird prefix operators like that with multiple operands were otherwise reasonably straightforward, though, it was the precedence table that got really hard to reason about. [I wish I still had the source; it was a fun, though very much dated, project, that allowed arbitrary inline M68k assembler in expressions (e.g. you could write "if D0.W == $1000 { }" to compare the lower 16-bit word of data register 0 to hex 1000), with "mentioning" the registers making the register allocator treat them as off limits for that scope]
  - chubot 8y ago
    I don't think Shunting Yard and Pratt are equivalent in that way -- i.e. replacing procedure calls with an explicit stack. When I wrote "Pratt Parsing and Precedence Climbing Are the Same Algorithm", multiple people replied and suggested that the Shunting Yard algorithm is also the same, with the equivalence you suggest. In particular the author of the repo Jean-Marc Bourguet also thought that. Then he implemented it and realized it wasn't true. See this section of the README: https://github.com/bourguet/operator_precedence_parsing https://github.com/bourguet/operator_precedence_parsing I had the mistaken impression that they were "just" replacing an explicit stack with the call stack of the implementation language but that was not clear enough from Andy's code. It was not clear because that's not the case. Compare Pratt's algorithm with recursive_operator_precedence.py, which is a recursive implementation of operator precedence, to see the difference. Pratt and operator climbing are really top down techniques: they call semantic actions as soon as possible, they don't delay the call until the whole handle is seen as operator precedence does. My current characterization is that they are to LL parsing and recursive descent what operator precedence is to LR and shift-reduce I think we had a discussion about an analogy LL vs. LR. Those are obviously not equivalent algorithms -- despite both being linear time, they recognize different languages. I think in the Shunting Yard algorithm, when you parse 1 + 2 / 3, the 2 / 3 tree is made first. I guess that is somewhat true of Pratt parsing too for natural reasons of tree building. You build the tree when you bubble out of the recursion. But it DECIDES that it has "led" for + before it decides it has "led" for /. So in summary, Shunting Yard "decides" 2 / 3 first, where as Pratt parsing "decides" 1+... first. That's what I think anyway. I think you could probably make this rigorous, but I'm not sure. I think of Pratt Parsing as LL(2) parsing for an operator grammar, although that's not technically correct because the precedence table is an extra piece of info outside the "grammar". You either lookahead 1 or 2 tokens, for null and led respectively. So basically I think you could translate Pratt parsing to use an explicit stack -- but then you'd still be using Pratt parsing. The Shunting Yard algorithm is something else.