blog | oilshell.org
I wrote that Pratt Parsing and Precedence Climbing Are the Same Algorithm, but I didn't explain the relation to Dijkstra's Shunting Yard Algorithm.
That's because I didn't implement it, and I wasn't sure how you handle
f(x, y), and C's ternary operator. I "switched" from
precedence climbing to Pratt parsing specifically to handle these constructs
Jean-Marc Bourguet answered my questions with example code:
And the repo has comparisons with more algorithms:
I won't attempt to summarize it, because I'm not familiar with everything, and because I'm in Twitter mode. But it's one of the most thorough treatments of expression parsing I've seen — particularly because I prefer running and tested code to pseudocode.
Leave a comment if you have questions.
The POSIX shell spec says that shell arithmetic is C arithmetic, So it's natural to wonder what the creators of C used. They didn't use grammars to specify their language. The code came first and grammars came later.
Here is one of the clearer versions I found, from Unix V6:
What do you think of this code?
I've added this post to the index of expression parsing posts.