Question about custom visitors

[Elvis Stansvik]

Hi all,

Me and my partner are now at the translation phase of our school compiler project. That is, we're about to translate the AST given to us by SableCC into a more primitive intermediate representation (IR) that is closer to the target machine language.

In the type-checking phase, we used the technique with a map to store the types of expression nodes, and then did the type-checking in the out*-methods, on our way back up the AST so to speak. E.g. as a simple example, our type-checking for == looks like:

public void outAEqualExpression(final AEqualExpression expression) {

        final Type left = types.get(expression.getLeft());

        final Type right = types.get(expression.getRight());

        final int line = expression.getEqual().getLine();

        final int column = expression.getEqual().getPos();

        if (!left.isEqualComparableTo(right)) {

            error(INVALID_BINARY_OP.on(line, column, "==", left, right));

        }

        types.put(expression, BuiltInType.Boolean);

}

Where "types" is our Node -> Type map. We have to use this technique since in SableCC we have no control over the generated AST node classes (except indirectly through the grammar of course), and can't make a completely custom visitor that would return a Type. If we could, the above check would be something like:

   if (!expression.getLeft().visit().isEqualComparableTo(expression.getRight().visit())) {

       ...

   }

Which is more commonly seen in compilers, AFAICS.

Now, for the AST -> IR translation phase we're kind of in the same boat: We need the translation of subexpressions/statements ready and waiting on our way back up to the tree. So I guess the natural thing is to use the same tecnique: Store the translation in a Node -> IRNode map.

But before we start I thought I'd ask here on the list: Has anyone else been in a similar situation? If so, how did you handle this? Just using the map technique, or did you hack the SableCC code generation so that you could make completely custom visitors (including control of the method return type)?

Wow, mail got longer than I intended, sorry about that :)

Anyway, quite interested in anyone who has experience with SableCC AST -> IR translation.

Best regards,

Elvis Stansvik

[Javier Abdul Córdoba Gándara]

Hello Elvis, what I normally do is to modify the class Node, root of all nodes in the AST. There I put additional attributes and methods to be inherited for all nodes (as the type, but can be whatever).

Regards,

Abdul

--
-- You received this message because you are subscribed to the SableCC group. To post to this group, send email to sab...@googlegroups.com. To unsubscribe from this group, send email to sablecc+u...@googlegroups.com. For more options, visit this group at https://groups.google.com/d/forum/sablecc?hl=en
---
You received this message because you are subscribed to the Google Groups "SableCC" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sablecc+u...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Etienne Gagnon]

Hi Elvis,

There is an easier way to type-check expressions. As you probably know, type-checking an expression is equivalent to abstractly evaluating the expression. In other words, you evaluate the expression, but instead of computing a value, you compute a type.

I invite you to look at how I implemented expression evalulation in the mino interpreter:
https://github.com/egagnon/mino/blob/master/src/mino/walker/InterpreterEngine.java

Here are some key parts:

public class InterpreterEngine
        extends Walker {

    // instance variable to hold the result of last expression evaluation
    private Instance expEval;

    // method to visit a node
    public void visit(
            Node node) {

        node.apply(this);
    }

    // method to evaluate a node and get the result
    private Instance getExpEval(
            Node node) {

        visit(node);
        Instance expEval = this.expEval;
        this.expEval = null;
        return expEval;
    }

    // typical binary expression operation (add)
    @Override
    public void caseAddExp_Add(
            NAddExp_Add node) {

        // compute the left expression and get the result
        Instance left = getExpEval(node.get_AddExp());

        // compute the right expression and get the result
        Instance right = getExpEval(node.get_LeftUnaryExp());

	// check for error situations
        if (left == null) {
            throw new InterpreterException("left argument of + method is null",
                    node.get_Plus());
        }
        else if (right == null) {
            throw new InterpreterException(
                    "right argument of + method is null", node.get_Plus());
        }
        else {
            // everything is OK, compute the result...

            MethodInfo invokedMethod = left.getClassInfo().getMethodTable()
                    .getMethodInfo(node.get_Plus());
            Frame frame = new Frame(this.currentFrame, left, invokedMethod);
            frame.setParam(right);

            // ... and store it in expEval
            this.expEval = execute(invokedMethod, frame, node.get_Plus());
        }
    }

As you see, this avoids having to use a hash table to store intermediate values.

The trick:

1. You override the "caseXXX()" methods instead of the "outXXX()" methods.
2. You explicitly and sequentially trigger the evaluation of subnodes, storing the subnode results in local variables (e.g. left and right above).
3. You compute the new result (for current node).
4. You store the result in the result instance variable so that an ancestor can retrieve it.
   

You can use this trick for evaluating expressions, type-checking them, and even to generate an intermediate representation.

Have fun!

Etienne

Etienne Gagnon, Ph.D.
http://sablecc.org

Le 2014-04-01 10:22, Elvis Stansvik a écrit :

Hi all,

Me and my partner are now at the translation phase of our school compiler project. That is, we're about to translate the AST given to us by SableCC into a more primitive intermediate representation (IR) that is closer to the target machine language.

In the type-checking phase, we used the technique with a map to store the types of expression nodes, and then did the type-checking in the out*-methods, on our way back up the AST so to speak. E.g. as a simple example, our type-checking for == looks like:

[...]

Where "types" is our Node -> Type map. We have to use this technique since in SableCC we have no control over the generated AST node classes (except indirectly through the grammar of course), and can't make a completely custom visitor that would return a Type. If we could, the above check would be something like:

   if (!expression.getLeft().visit().isEqualComparableTo(expression.getRight().visit())) {

       ...

   }

Which is more commonly seen in compilers, AFAICS.

Now, for the AST -> IR translation phase we're kind of in the same boat: We need the translation of subexpressions/statements ready and waiting on our way back up to the tree. So I guess the natural thing is to use the same tecnique: Store the translation in a Node -> IRNode map.

But before we start I thought I'd ask here on the list: Has anyone else been in a similar situation? If so, how did you handle this? Just using the map technique, or did you hack the SableCC code generation so that you could make completely custom visitors (including control of the method return type)?

Wow, mail got longer than I intended, sorry about that :)

Anyway, quite interested in anyone who has experience with SableCC AST -> IR translation.

Best regards,

Elvis Stansvik

[Elvis Stansvik]

Ah, that's a clever way I hadn't thought about, using a local variable like that. And should be more memory efficient.

We're completely done with the type-checking, and it goes through our schools test system. So we probably won't re-write the type-checking right now (it's at [1] btw). But maybe we can use this technique for the translation to IR then. Will discuss it with my partner later this week.

Thanks!

Elvis

[1] https://github.com/estan/mjc/blob/master/src/main/java/mjc/analysis/TypeChecker.java

[Elvis Stansvik]

2014-04-01 19:50 GMT+02:00 Javier Abdul Córdoba Gándara <abdulc...@gmail.com>:

Hello Elvis, what I normally do is to modify the class Node, root of all nodes in the AST. There I put additional attributes and methods to be inherited for all nodes (as the type, but can be whatever).

Hm. So you go in and modify the generated code? Our build system is set up so that it regenerates the code at build time. I was thinking more if people customized the generated code through the .txt templates SableCC uses. Anyway, thanks for your input, good to know there's more than one way to do it :)

Elvis

[Elvis Stansvik]

I should clarify; with "local variable" I meant the this.expEval/expEval you have in getExpEval.

Elvis

[Javier Abdul Córdoba Gándara]

Nice one Etienne! My students are just working in the type checker right now, I will direct them to this code.

-- 

Abdul