---

Validation in Dijkstra’s shunting yard algorithm

[ 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