Java – Tree Transformations Using Visitor Pattern

abstract-syntax-treejavapythontreevisitor-pattern

(Disclaimer: these examples are given in the context of building a compiler, but this question is all about the Visitor pattern and does not require any knowledge of compiler theory.) I'm going through Andrew Appel's Modern Compiler Implementation in Java to try to teach myself compiler theory (so no, this isn't homework) and I'm having trouble understanding how he wants to use the Visitor pattern to transform an AST to an IR tree. (Note: I'm doing this in Python so I can learn Python also, which is why the upcoming examples are not in Java.) As I understand it, the visit and accept methods in the Visitor pattern are void-typed by design, so if I have something like

class PlusExp(Exp):
    def __init__(self, exp_left, exp_right):
        self.exp_left = exp_left
        self.exp_right = exp_right

    def accept(self, v):
        v.visit_plus_exp(self)

then I would like to be able to write a visitor method like

def visit_plus_exp(self, plus_exp):
    return BINOP(BinOp.PLUS, 
                 plus_exp.exp_left.accept(self), 
                 plus_exp.exp_right.accept(self))

which would translate the two child expressions into IR and then link them up with the BINOP representing the plus expression. Of course, this isn't possible unless I modify all the accept functions to return extra info, and that is also messy because sometimes you just want a print visitor that doesn't return anything. Yet, this text insists that a visitor is the right way to go, and in Java at that, which means it can be done without the flexibility of Python. I can't think of any solutions that aren't incredibly hacky – can anyone enlighten me as to the intended design?

Best Answer

A SAX parser is a kind of visitor. To avoid adding a return value to the method, you can use a stack:

class Visitor {
    Stack<Node> stack = new Stack<Node>();

//    . . .

    void visitPlus(PlusExp pe) {
        pe.left.accept(this);
        pe.right.accept(this);
        Node b = stack.pop();
        Node a = stack.pop();
        stack.push(new BinOp(BinOp.PLUS, a, b));
    }

Related Solutions

Python – Calling a function of a module by using its name (a string)

Assuming module foo with method bar:

import foo
method_to_call = getattr(foo, 'bar')
result = method_to_call()

You could shorten lines 2 and 3 to:

result = getattr(foo, 'bar')()

if that makes more sense for your use case.

You can use getattr in this fashion on class instance bound methods, module-level methods, class methods... the list goes on.

Python – the difference between re.search and re.match

re.match is anchored at the beginning of the string. That has nothing to do with newlines, so it is not the same as using ^ in the pattern.

As the re.match documentation says:

If zero or more characters at the beginning of string match the regular expression pattern, return a corresponding MatchObject instance. Return None if the string does not match the pattern; note that this is different from a zero-length match.

Note: If you want to locate a match anywhere in string, use search() instead.

re.search searches the entire string, as the documentation says:

Scan through string looking for a location where the regular expression pattern produces a match, and return a corresponding MatchObject instance. Return None if no position in the string matches the pattern; note that this is different from finding a zero-length match at some point in the string.

So if you need to match at the beginning of the string, or to match the entire string use match. It is faster. Otherwise use search.

The documentation has a specific section for match vs. search that also covers multiline strings:

Python offers two different primitive operations based on regular expressions: match checks for a match only at the beginning of the string, while search checks for a match anywhere in the string (this is what Perl does by default).

Note that match may differ from search even when using a regular expression beginning with '^': '^' matches only at the start of the string, or in MULTILINE mode also immediately following a newline. The “match” operation succeeds only if the pattern matches at the start of the string regardless of mode, or at the starting position given by the optional pos argument regardless of whether a newline precedes it.

Now, enough talk. Time to see some example code:

# example code:
string_with_newlines = """something
someotherthing"""

import re

print re.match('some', string_with_newlines) # matches
print re.match('someother', 
               string_with_newlines) # won't match
print re.match('^someother', string_with_newlines, 
               re.MULTILINE) # also won't match
print re.search('someother', 
                string_with_newlines) # finds something
print re.search('^someother', string_with_newlines, 
                re.MULTILINE) # also finds something

m = re.compile('thing$', re.MULTILINE)

print m.match(string_with_newlines) # no match
print m.match(string_with_newlines, pos=4) # matches
print m.search(string_with_newlines, 
               re.MULTILINE) # also matches

Best Answer

Related Solutions

Python – Calling a function of a module by using its name (a string)

Python – the difference between re.search and re.match

Related Topic