Expression tree and implementation of visitor pattern

Question

I have a hierarchical structure of objects to represent arithmetic expressions. Something like the following:

      TreeNode
     /        \
    /          \
   /            \ 
NumericNode    BinaryOpNode
              /  |    \    \
             /   |     \    \
            /    |      \    \   
      AddNode MulNode DivNode ...etc

I have the lexer and parser working. Now I'm trying to figure out the best way to do actions over the generated AST in a practical and easy to adapt manner. Right now I had implemented the Visitor Pattern with a Visitor and Visitable interface, but I'm not sure if I really need all the concrete classes to implement the Visitable interface.

Since i want to control the traverse order in the visitor, i find myself repeating a lot of code. For example, for a PrintInOrder Visitor i have methods like:

    public void visit(AddNode node) { 
       node.getLeft().accept(this);
       System.out.print(node + " ");
       node.getRight().accept(this);
    }

for every concrete node representing some arithmetic operation.

But i can achieve the same implementing Visitable in the super classes. For example the same PrintInOrder Visitor would look like:

    public void visit(BinaryOpNode node) { 
       node.getLeft().accept(this);
       System.out.print(node + " ");
       node.getRight().accept(this);
    }

However, I don't know what is the most common approach for this task.

Question 1: If I want my design to let me do almost whatever I want over the AST, I really need to visit all the concrete nodes and write all that repeated code?.

Question 2: Assuming a Visitor that could return some type, like:

public interface Visitor<T> {
    public T visit(AddNode node);
    public T visit(MulNode node);
        ...
}

This looks more versatile than the common void version. But it has useful benefits? And can be used in the same way as the void version?

Attila · Accepted Answer · 2014-01-04 18:01:13Z

3

Answer 1: You could use an abstract super class the visit method and any common functionality, that is going to be the same in each concrete class, so each concrete class can be derived from this abstract class and use the method without implementing it a redundant way.

Visitor pattern

As you can see on the figure you can implement the visitor logic in a seperate class. This way you can decouple the traversal order, and the implementation of visiting the nodes from the Node implementation. If you have your abstract syntax tree built up according to the arithmetic operation precedence you don't have to change the implementation for the different types of nodes. You can use the same ConcreteVisitor for each of them.

Answer 2: Yes, using generic classes are benefical many ways. This way you can do type cheking compile time. If you don't have this opportunity you may have bugs hidden, hard to find, but if you can check type validity compile time, you can make sure that you don't have this type of bugs in your system.

edited Jan 4, 2014 at 18:01

answered Jan 4, 2014 at 7:13

Attila

3,4263 gold badges37 silver badges48 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Wyvern666 Over a year ago

Please, can you give some pseudo-code example of the first answer?

drankin2112 · Accepted Answer · 2014-01-14 06:36:12Z

3

By far the best method that I've ever used to parse and interpret simple arithmetic expressions is to build a Pratt parser. The link below gives a great explaination of the process and the examples are even written in java.

Essentially you'll end up having separate mini parsers as functions of each operator that your app supports. All of your operators will be categorized as either prefix, infix, or postfix. Also, you'll assign a precedence value to each of those operators that you'll reference when evaluating each sub-expression.

I wrote an ECMAScript interpreter in C# that uses a recursive descendant parser for the language constructs and for evaluating control flow statements. And, it uses a Pratt parser to evaluate expressions. The Pratt parser gives you a way to deal with operator associativity and precedence.

I only used the Visitor pattern to generate pretty-print and no-whitespace formatted code from the AST itself. Everything else was done using inheritance and interfaces. If you really want to use the Visitor idea then a stack-based expression parser is what you'll want to make. The Pratt Parser just uses your application's call stack instead.

Being a java programmer, I think you'll find this article particularly helpful. Either way. Take care and good luck.

http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-expression-parsing-made-easy/

edited Jan 14, 2014 at 6:36

answered Jan 14, 2014 at 6:28

drankin2112

4,8021 gold badge18 silver badges20 bronze badges

3 Comments

Wyvern666 Over a year ago

Nice info. I started with the dragon book but i havent found anything about "pratt parsers" there, yet.

drankin2112 Over a year ago

don't forget to grab and study the source code for the author's bantam language. There's more info in there than the article mentions and it should basically clarify everything. It has all the expression classes and parselets.

Wyvern666 Over a year ago

Im happy with my clasical static approach, (i could do it with a explicit stack but mine is recursive). From what I've read the pratt parser is a good solution for a parser generator, it is easy to extend for user needs, i will take this in count for mi next stepts in parsing. Thanks.

Collectives™ on Stack Overflow

Expression tree and implementation of visitor pattern

2 Answers 2

1 Comment

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related