Previous    Next

VISITORS

Each abstract syntax class of Program 4.5 has a constructor for building syntax trees, and an eval method for returning the value of the represented expression. This is an object-oriented style of programming. Let us consider an alternative.

Exp class for Program 4.4.
public abstract class Exp {
 public abstract int eval();
}
public class PlusExp extends Exp {
 private Exp e1,e2;
 public PlusExp(Exp a1, Exp a2) { e1=a1; e2=a2; }
 public int eval() {
 return e1.eval()+e2.eval();
 }
}
public class MinusExp extends Exp {
 private Exp e1,e2;
 public MinusExp(Exp a1, Exp a2) { e1=a1; e2=a2; }
 public int eval() {
 return e1.eval()-e2.eval();
 }
}
public class TimesExp extends Exp {
 private Exp e1,e2;
 public TimesExp(Exp a1, Exp a2) { e1=a1; e2=a2; }
 public int eval() {
 return e1.eval()*e2.eval();
 }
}
public class DivideExp extends Exp {
 private Exp e1,e2;
 public DivideExp(Exp a1, Exp a2) { e1=a1; e2=a2; }
 public int eval() {
 return e1.eval()/e2.eval();
 }
}
public class Identifier extends Exp {
 private String f0;
 public Identifier(String n0) { f0 = n0; }
 public int eval() {
 return lookup(f0);
 }
}
public class IntegerLiteral extends Exp {
 private String f0;
 public IntegerLiteral(String n0) { f0 = n0; }
 public int eval() {
 return Integer.parseInt(f0);
 }
}



Java End example

Suppose the code for evaluating expressions is written separately from the abstract syntax classes. We might do that by examining the syntax-tree data structure by using instanceof and by fetching public class variables that represent subtrees. This is a syntax separate from interpretations style of programming. The choice of style affects the modularity of the compiler. In a situation such as this, we have several kinds of objects: compound statements, assignment statements, print statements, and so on. And we also may have several different interpretations of these objects: type-check, translate to Pentium code, translate to Sparc code, optimize, interpret, and so on. Each interpretation must be applied to each kind; if we add a new kind, we must implement each interpretation for it; and if we add a new interpretation, we must implement it for each kind. Image 4.6 illustrates the orthogonality of kinds and interpretations - for compilers, and for graphic user interfaces, where the kinds are different widgets and gadgets, and the interpretations are move, hide, and redisplay commands.

Java Click To expand
Image 4.6: Orthogonal directions of modularity.

If the syntax separate from interpretations style is used, then it is easy and modular to add a new interpretation: One new function is written, with clauses for the different kinds all grouped logically together. On the other hand, it will not be modular to add a new kind, since a new clause must be added to every interpretation function. With the object-oriented style, each interpretation is just a method in all the classes. It is easy and modular to add a new kind: All the interpretations of that kind are grouped together as methods of the new class. But it is not modular to add a new interpretation: A new method must be added to every class. For graphic user interfaces, each app will want to make its own kinds of widgets; it is impossible to predetermine one set of widgets for everyone to use. On the other hand, the set of common operations (interpretations) is fixed: The window manager demands that each widget support only a certain interface. Thus, the object-oriented style works well, and the syntax separate from interpretations style would not be as modular. For coding languages, on the other hand, it works very well to fix a syntax and then provide many interpretations of that syntax. If we have a compiler where one interpretation is translate to Pentium andwewishtoport that compiler to the Sparc, then not only must we add operations for generating Sparc code but we might also want to remove (in this configuration) the Pentium code-generation functions. This would be very inconvenient in the object-oriented style, requiring each class to be edited. In the syntax separate from interpretations style, such a change is modular: We remove a Pentiumrelated module and add a Sparc module. We prefer a syntax-separate-from-interpretations style. Fortunately, we can use this style without employing instanceof expressions for accessing syntax trees. Instead, we can use a technique known as the Visitor pattern. A visitor implements an interpretation; it is an object which contains a visit method for each syntax-tree class. Each syntax-tree class should contain an accept method. An accept method serves as a hook for all interpretations. It is called by a visitor and it has just one task: It passes control back to an appropriate method of the visitor. Thus, control goes back and forth between a visitor and the syntax-tree classes. Intuitively, the visitor calls the accept method of a node and asks "what is your class?" The accept method answers by calling the corresponding visit method of the visitor. Code for the running example, using visitors, is given in Programs 4.7 and 4.8. Every visitor implements the interface Visitor. Notice that each accept method takes a visitor as an argument, and that each visit method takes a syntax-tree-node object as an argument.

Syntax classes with accept methods.
public abstract class Exp {
 public abstract int accept(Visitor v);
}
public class PlusExp extends Exp {
 public Exp e1,e2;
 public PlusExp(Exp a1, Exp a2) { e1=a1; e2=a2; }
 public int accept(Visitor v) {
 return v.visit(this);
 }
}
public class MinusExp extends Exp {
 public Exp e1,e2;
 public MinusExp(Exp a1, Exp a2) { e1=a1; e2=a2; }
 public int accept(Visitor v) {
 return v.visit(this);
 }
}
public class TimesExp extends Exp {
 public Exp e1,e2;
 public TimesExp(Exp a1, Exp a2) { e1=a1; e2=a2; }
 public int accept(Visitor v) {
 return v.visit(this);
 }
}
public class DivideExp extends Exp {
 public Exp e1,e2;
 public DivideExp(Exp a1, Exp a2) { e1=a1; e2=a2; }
 public int accept(Visitor v) {
 return v.visit(this);
 }
}
public class Identifier extends Exp {
 public String f0;
 public Identifier(String n0) { f0 = n0; }
 public int accept(Visitor v) {
 return v.visit(this);
 }
}
public class IntegerLiteral extends Exp {
 public String f0;
 public IntegerLiteral(String n0) { f0 = n0; }
 public int accept() {
 return v.visit(this);
 }
}



Java End example
An interpreter visitor.
public interface Visitor {
 public int visit(PlusExp n);
 public int visit(MinusExp n);
 public int visit(TimesExp n);
 public int visit(DivideExp n);
 public int visit(Identifier n);
 public int visit(IntegerLiteral n);
}
public class Interpreter implements Visitor {
 public int visit(PlusExp n) {
 return n.e1.accept(this)+n.e2.accept(this);
 }
 public int visit(MinusExp n) {
 return n.e1.accept(this)-n.e2.accept(this);
 }
 public int visit(TimesExp n) {
 return n.e1.accept(this)*n.e2.accept(this);
 }
 public int visit(DivideExp n) {
 return n.e1.accept(this)/n.e2.accept(this);
 }
 public int visit(Identifier n) {
 return lookup(n.f0);
 }
 public int visit(IntegerLiteral n) {
 return Integer.parseInt(n.f0);
 }
}



Java End example

In Programs 4.7 and 4.8, the visit and accept methods all return int. Suppose we want instead to return String. In that case, we can add an appropriate accept method to each syntax tree class, and we can write a new visitor class in which all visit methods return String. The main difference between the object-oriented style and the syntaxseparate-from-interpretations style is that, for example, the interpreter code in Program 4.5 is in the eval methods while in Program 4.8 it is in the Interpreter visitor. In summary, with the Visitor pattern we can add a new interpretation without editing and recompiling existing classes, provided that each of the appropriate classes has an accept method. The following table summarizes some advantages of the Visitor pattern:

 

Frequent type casts?

Frequent recompilation?


Instanceof and type casts

Yes

No

Dedicated methods

No

Yes

The Visitor pattern

No

No

ABSTRACT SYNTAX FOR MiniJava

Image 4.9 shows classes for the abstract syntax of MiniJava. The meaning of each constructor in the abstract syntax should be clear after a careful study of Appendix A, but there are a few points that merit explanation. Only the constructors are shown in Image 4.9; the object field variables correspond exactly to the names of the constructor arguments. Each of the six list classes is implemented in the same way, for example:

public class ExpList {
 private Vector list;
 public ExpList() {
 list = new Vector();
 }
 public void addElement(Exp n) {
 list.addElement(n);
 }
 public Exp elementAt(int i) {
 return (Exp)list.elementAt(i);
 }
 public int size() {
 return list.size();
 }
}


Each of the nonlist classes has an accept method for use with the visitor pattern. The interface Visitor is shown in Program 4.10.

MiniJava visitor
public interface Visitor {
 public void visit(Program n);
 public void visit(MainClass n);
 public void visit(ClassDeclSimple n);
 public void visit(ClassDeclExtends n);
 public void visit(VarDecl n);
 public void visit(MethodDecl n);
 public void visit(Formal n);
 public void visit(IntArrayType n);
 public void visit(BooleanType n);
 public void visit(IntegerType n);
 public void visit(IdentifierType n);
 public void visit(Block n);
 public void visit(If n);
 public void visit(While n);
 public void visit(Print n);
 public void visit(Assign n);
 public void visit(ArrayAssign n);
 public void visit(And n);
 public void visit(LessThan n);
 public void visit(Plus n);
 public void visit(Minus n);
 public void visit(Times n);
 public void visit(ArrayLookup n);
 public void visit(ArrayLength n);
 public void visit(Call n);
 public void visit(IntegerLiteral n);
 public void visit(True n);
 public void visit(False n);
 public void visit(IdentifierExp n);
 public void visit(This n);
 public void visit(NewArray n);
 public void visit(NewObject n);
 public void visit(Not n);
 public void visit(Identifier n);
}



Java End example

We can construct a syntax tree by using nested new expressions. For example, we can build a syntax tree for the MiniJava statement:

x = y.m(1,4+5);


using the following Java code:

ExpList el = new ExpList();
el.addElement(new IntegerLiteral(1));
el.addElement(new Plus(new IntegerLiteral(4),
 new IntegerLiteral(5)));
Statement s = new Assign(new Identifier("x"),
 new Call(new IdentifierExp("y"),
 new Identifier("m"),
 el));


SableCC enables automatic generation of code for syntax tree classes, code for building syntax trees, and code for template visitors. For JavaCC, a companion tool called the Java Tree Builder (JTB) enables the generation of similar code. The advantage of using such tools is that once the grammar is written, one can go straight on to writing visitors that operate on syntax trees. The disadvantage is that the syntax trees supported by the generated code may be less abstract than one could desire.


JaVaScreenshot Previous    Next
Comments