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:

  1. regardless of the type of the grammar used for building the AST (LR, LL*, or even no formal grammar as with Perl 5);

  2. regardless of the parser-generator used for building the AST (bison, antlr, or my own hand-written code); and

  3. 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?

  • 3
    Gene's comment is still valid here: the question you are asking is too vague to be meaningfully answerable. If you need clarification on something Gene said in his comment, focus on that thing specifically in your question. Or, simply ask Gene what he meant. – Robert Harvey Jan 9 '16 at 3:26
  • 2
    I want to move to a new town. Please tell me what that new town cannot provide me. – Robert Harvey Jan 9 '16 at 3:41
  • 4
    It's a question alright. But how do you answer it in any meaningful way? – Robert Harvey Jan 9 '16 at 3:43
  • 2
    An AST can represent an arbitrary amount of information about the source file, up to an including "all of it". As such, the answer is clearly "yes". The only real question is how much of the information in the original source is needed to translate a particular language. Usually you preserve more than is strictly necessary for translation, to support producing better error messages. – Jerry Coffin Jan 9 '16 at 17:22
  • 2
    @Harry That's a tautology, not a fallacy. Part of the point is the only way to answer your question is with tautologies like that. It is possible to do X with an AST as long as X only requires stuff contained in the AST. So the only things you can't do with an AST are the ones that require information the AST does not preserve. Any answer more useful/interesting than that would require more specific definitions; otherwise you could just redefine your ASTs so that they do include whitespace or whatever. – Ixrec Jan 9 '16 at 20:53

Theoretically, yes, assuming you have an AST for a Turing Complete language. It may mean interpreting a+b as something not meaning "add the variables referenced by these two identifiers together", or building your own compiler in the source language to implement the feature, or something else particularly impractical. But once you can model one Turing Complete language, you can do whatever you want.

Practically though, no. If your source language (and AST) has no concept of functions, then it may be tricky to implement them as a feature just by AST translations. Could you do it in the source language? Sure. Could you add AST nodes to support it? Sure. Those are pretty easy.

But changing the meaning of the syntax nodes in any coherent way gets a lot more (order of magnitude+) difficult.

| improve this answer | |
  • If my "source language (and AST) has no concept of functions", then why would I want to "implement them as a feature"? – Harry Jan 9 '16 at 4:09
  • 2
    @harry - damned if I know, you're the one that asked the question. – Telastyn Jan 9 '16 at 4:36
  • 1
    It's like asking a waiter at the restaurant "Can I have ketchup with my steak", then the waiter replies "No, you cannot have ketchup with your steak" and then you yell at him "Why would I want to have ketchup with my steak?" Well, you asked about having ketchup with your steak, so, it's reasonable assumption that you weren't just compiling a database of possible condiments but actually wanted to have ketchup with your steak. – Jörg W Mittag Jan 9 '16 at 6:53
  • 1
    @Telastyn, the question now is - why do we need functions for Turing completeness. – Basilevs Jan 9 '16 at 9:55
  • 5
    @Harry - some examples of things that an AST by itself won't allow me to do - and that is my answer - If you have an AST of a Turing Complete language, there is nothing that the AST by itself won't allow you to do. You can translate that to do literally any compute-able problem (with enough processing of it). – Telastyn Jan 9 '16 at 13:30

Not the answer you're looking for? Browse other questions tagged or ask your own question.