Parsing – Simplest Example to Explain Parse Trees vs Abstract Syntax Trees

It is up to the visitor implementation to decide whether to visit child nodes and in which order. That's the whole point of the visitor pattern.

In order to adapt the visitor for more situations it is helpful (and quite common) to use generics like this (it's Java):

public interface ExpressionNodeVisitor<R, P> {
    R visitNumber(NumberNode number, P p);
    R visitBinary(BinaryNode expression, P p);
    // ...
}

And an accept method would look like this:

public interface ExpressionNode extends Node {
    <R, P> R accept(ExpressionNodeVisitor<R, P> visitor, P p);
    // ...
}

This allows to pass additional parameters to visitor and retrieve a result from it. So, the expression evaluation can be implemented like this:

public class EvaluatingVisitor
    implements ExpressionNodeVisitor<Double, Void> {
    public Double visitNumber(NumberNode number, Void p) {
        // Parse the number and return it.
        return Double.valueOf(number.getText());
    }
    public Double visitBinary(BinaryNode binary, Void p) {
        switch (binary.getOperator()) {
        case '+':
            return binary.getLeftOperand().accept(this, p)
                + binary.getRightOperand().accept(this, p);
        // More cases for other operators here.
        }
    }
}

The accept method parameter isn't used in the above example, but just believe me: it is quite useful to have one. For example, it can be a Logger instance to report errors to.

It's not a choice between flex/bison or nothing. There are several options out there. I used antlr for a recent project and found it very nice to work with. Some things you might not have considered:

• Lexers aren't that difficult, but parsers have a considerable number of gotchas you won't even realize until they hit you. Widely used tools have already solved a bunch of problems you don't even know exist yet.
• Your parser will still need to be just as strict as a compiler. The difference will be you can use a simpler grammar in some places, but that will probably be offset by needing to use more complex grammar in other places. For example, code beautifiers often want to preserve an intentional newline that a regular compiler just lumps into "whitespace." If your language has a preprocessor, a beautifier will have to incorporate that into the grammar, whereas a compiler's parser won't.
• Grammars are extremely difficult to debug. Tools like antlr have devoted considerable effort to producing useful error messages. Even if you do go with a custom parser, you may still find it useful to use an existing parser generator to debug your grammar.