TOtodsacerdoti·Jul 21, 2024Submission
Operator_precedence_parsing: C89 expressions parsed with the shunting yard algo
10 points · Open discussionbourguet
operator_precedence_parsing
Python2019–2024
bourguet / operator_precedence_parsing
operator_precedence_parsing
C89 expressions parsed with the shunting yard algorithm in Python
2Distinct people
3Mentions
0Explicit recommenders
88GitHub stars
What to know before exploring
What it is
C89 expressions parsed with the shunting yard algorithm in Python
GitHub
Where it is used
No documented product use has been verified yet.
What people are saying
No recommendation phrase was found in the indexed comments.
No classified warning is attached to this page. Read the discussions before treating silence as approval.
Also in these discussions
No other repository is repeatedly linked in the same discussions.
This week on Hacker News
Nov 7–Nov 14 UTC · Direct repository links and separately labeled related project stories. Indexed through 11/14/2026, 5:04:57 PM UTC.
No direct repository links were found in the indexed HN discussions over the past seven days. Older discussions are available below.
Mentions over time
HN mentions by year3 dated mentions
Observed mentions: 2019-02-19 01:41:03 UTC to 2024-07-21 02:02:33 UTC.
Counts come from the repository’s dated source evidence. Index cutoff: 2026-11-02 08:16:59 UTC.
View mention counts and date ranges
| Period | Start (UTC) | End (exclusive, UTC) | Mentions | Submissions | Comments |
|---|---|---|---|---|---|
| 2019 | 2019-01-01 00:00:00 UTC | 2020-01-01 00:00:00 UTC | 2 | 0 | 2 |
| 2020 | 2020-01-01 00:00:00 UTC | 2021-01-01 00:00:00 UTC | 0 | 0 | 0 |
| 2021 | 2021-01-01 00:00:00 UTC | 2022-01-01 00:00:00 UTC | 0 | 0 | 0 |
| 2022 | 2022-01-01 00:00:00 UTC | 2023-01-01 00:00:00 UTC | 0 | 0 | 0 |
| 2023 | 2023-01-01 00:00:00 UTC | 2024-01-01 00:00:00 UTC | 0 | 0 | 0 |
| 2024 | 2024-01-01 00:00:00 UTC | 2025-01-01 00:00:00 UTC | 1 | 1 | 0 |
What Hacker News says
3 sourcesI 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
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
Read the rest
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.
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
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 sou
Read the rest
rce made reference to Dijikstra.
[1] http://www.oilshell.org/blog/2017/03/31.html