Linux Today: Linux News On Internet Time.

Validation in Dijkstra's shunting yard algorithm

Nov 01, 2010, 11:02 (0 Talkback[s])

[ Thanks to Erik for this link. ]

"In a previous blog post, I argued that it is perfectly possible to extend Dijkstra's shunting yard algorithm to parse function calls and object-oriented expressions. It actually does not take that much effort to extend the algorithm to do so. This means that you could happily build an entire compiler or scripting engine with the algorithm, that would be able to accept typical modern programming language source code, such as C, Javascript, Php, Perl, Java, and so on. Dijkstra's algorithm simplifies compiler construction by doing away with AST trees. In this approach they become obsolete. Dijkstra's algorithm immediately generates intermediate language, that can easily be translated into executable bytecode or CPU-specific machine language.

"Unfortunately, the algorithm will still happily parse invalid source code. In my impression, it would be wrong to burden Dijkstra's algorithm with attempts to validate the source code. It would complicate the algorithm to no end, while it would be quite hard to implement complete validation of the source code. Therefore, I believe that we should rather use a validator program that precedes Dijkstra's algorithm, and that fails when the source code supplied is invalid. From there, Dijkstra's algorithm would be guaranteed to parse only valid source code, and does no longer need to perform validations by itself."

Complete Story

Related Stories: