Code for the Shunting Yard Algorithm, and More

2017-04-22

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 constructs like a[i], f(x, y), and C's ternary operator. I "switched" from precedence climbing to Pratt parsing specifically to handle these constructs cleanly.

Jean-Marc Bourguet answered my questions with example code:

C89 expressions parsed with the shunting yard algorithm in Python
shunting_yard.py (~270 lines)

And the repo has comparisons with more algorithms:

bourguet/operator_precedence_parsing on Github

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.

Unix V6 Source

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:

V6/usr/source/c/c05.c - opdope table
V6/usr/source/c/c01.c - algorithm using a stack

What do you think of this code?

I've added this post to the index of expression parsing posts.