Note: In my ignorance of the difference between Programmers vs StackOverflow sites (which I know now), I had posted this question on StackOverflow earlier. What I'm looking for is some elaboration, for example, on the comment by Gene.
Once I am able to build an abstract syntax tree (AST) for an input, then:
regardless of the type of the grammar used for building the AST (LR, LL*, or even no formal grammar as with Perl 5);
regardless of the parser-generator used for building the AST (
antlr, or my own hand-written code); and
regardless of the number of passes I do over my input for building the AST;
... is it true that I can implement any feature of any language ever created just by visiting the AST
N number of times?
I'm not worried about the complexity of the resulting code, or its performance, I just need to know whether an AST is sufficient to allow the building of a translator (a compiler or an interpreter) regardless of the feature I am trying to build.
I am not looking for an exhaustive list of what cannot be done with an AST, just 1 example should suffice. If an AST is a sufficiently fundamental (and thus versatile/powerful) structure to allow the building of just about any translator, then a I'd like to see a confirmation of this fact. Getting the source of the book or a URL (if one exists) would be an additional bonus.
Just as an AST, being a tree, would be more powerful data structure than (and, thus, can also emulate) a flat or linear intermediate representation (IR) such as the Three-Address Code as covered in the Dragon book, so also an abstract syntax graph (ASG, if you will), being a graph, would be more powerful than an AST. Thus, elaborating further on my original post: Is there any translator feature known to mankind as of this writing that cannot be implemented by an AST and requires the use of an ASG?