My own infix to prefix approach. What do you think?

[Les Bell]

(04-29-2014 01:28 PM)HP67 Wrote:  I meant it's the only thing Dijkstra has contributed that was actually useful.

Wow! -I guess you missed Dijkstra's shortest path algorithm, which is used in OSPF routing, his invention of semaphores, the "GO TO Considered Harmful" paper, his work on formal methods and his ACM Turing Award. The shunting algorithm is but a small part of his work and very far from the most useful.

(04-29-2014 01:28 PM)HP67 Wrote:  Really? I haven't seen anything formalized.

You mean, you haven't seen the Dragon Book ("Compilers: Principles, Techniques, & Tools", by Aho, Ullman, et. al.)? That book was significantly updated in the 20 years between the first and second edition, and there have been significant developments since then. You haven't seen YACC and LEX, the tools used in Kernighan and Pike's classic "The UNIX Programming Environment"? Nor BISON, the GNU equivalent?

I'm not going to respond in detail to the rest of your post; it simply reflects your view of coding as a craft.

I took it that Matt was thinking and learning about how basic language translation might be done, not looking for a specific algorithm. He's experimenting with his own ideas, and ANTLR (and similar tools) provide a "playpen" for that learning activity, along with guidance, in the form of the books I recommended. I expect Matt is already a competent coder, but now he's thinking about well-developed ideas in the realm of computer science.

The key point is that the shunting yard algorithm does one thing only - parse infix expressions and emit a prefix representation. However, before you can parse the expression, it has to be tokenized (and yes, I do know the difference between scanning and parsing, thank you!), and then once you've got your infix expression, now what?

If Matt is interested in implementing something useful with it, he'll need to extend it and place it in the context of additional features, which could be any or all of named variables (symbol tables), types, function definition, flow control, etc. The ANTLR approach makes this a natural extension.

However, if he's more interested in exploring the ideas involved, then learning (by example, with ANTLR) how a grammar defines a language and how a parser translates it would be a rewarding activity. Trying new ideas becomes a simple matter of editing the grammar, rather than rewriting reams of low-level code.

To paraphrase, I'll simply say that with the shunting yard algorithm, Matt has been given a fish; but ANTLR is a complete fishing rod, hooks, bait, pots, pans and a vegetable garden with all the things he'll need to cook that fish and any others he catches.