A.W. Appel, J. Palsberg - Modern Compiler Implementation in Java (Second Edition) (798439), страница 19

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 19)

But it is not modular to add a new interpretation: A new methodmust be added to every class.For graphic user interfaces, each application will want to make its own kinds of widgets; it isimpossible to predetermine one set of widgets for everyone to use. On the other hand, the setof common operations (interpretations) is fixed: The window manager demands that eachwidget support only a certain interface. Thus, the object-oriented style works well, and thesyntax separate from interpretations style would not be as modular.For programming languages, on the other hand, it works very well to fix a syntax and thenprovide many interpretations of that syntax.

If we have a compiler where one interpretation istranslate to Pentium andwewishtoport that compiler to the Sparc, then not only must we addoperations 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 objectoriented style, requiring each class to be edited. In the syntax separate from interpretationsstyle, such a change is modular: We remove a Pentiumrelated module and add a Sparcmodule.We prefer a syntax-separate-from-interpretations style. Fortunately, we can use this stylewithout employing instanceof expressions for accessing syntax trees. Instead, we can use a88technique known as the Visitor pattern.

A visitor implements an interpretation; it is an objectwhich contains a visit method for each syntax-tree class. Each syntax-tree class shouldcontain an accept method. An accept method serves as a hook for all interpretations. It iscalled by a visitor and it has just one task: It passes control back to an appropriate method ofthe 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?" Theaccept method answers by calling the corresponding visit method of the visitor. Code forthe running example, using visitors, is given in Programs 4.7 and 4.8.

Every visitorimplements the interface Visitor. Notice that each accept method takes a visitor as anargument, and that each visit method takes a syntax-tree-node object as an argument.PROGRAM 4.7: 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);}}89PROGRAM 4.8: 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);}}In Programs 4.7 and 4.8, the visit and accept methods all return int.

Suppose we wantinstead to return String. In that case, we can add an appropriate accept method to eachsyntax tree class, and we can write a new visitor class in which all visit methods returnString.The main difference between the object-oriented style and the syntaxseparate-frominterpretations style is that, for example, the interpreter code in Program 4.5 is in the evalmethods 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 andrecompiling existing classes, provided that each of the appropriate classes has an acceptmethod. The following table summarizes some advantages of the Visitor pattern:Frequent type casts? Frequent recompilation?Instanceof and type castsDedicated methodsThe Visitor patternYesNoNoNoYesNo90ABSTRACT SYNTAX FOR MiniJavaFigure 4.9 shows classes for the abstract syntax of MiniJava.

The meaning of each constructorin the abstract syntax should be clear after a careful study of Appendix A, but there are a fewpoints that merit explanation.Only the constructors are shown in Figure 4.9; the object field variables correspond exactly tothe names of the constructor arguments. Each of the six list classes is implemented in thesame 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 interfaceVisitor is shown in Program 4.10.PROGRAM 4.10: MiniJava visitorpublic 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);91publicpublicpublicpublicpublicvoidvoidvoidvoidvoidvisit(This n);visit(NewArray n);visit(NewObject n);visit(Not n);visit(Identifier n);}We can construct a syntax tree by using nested new expressions.

For example, we can build asyntax 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 buildingsyntax trees, and code for template visitors. For JavaCC, a companion tool called the JavaTree Builder (JTB) enables the generation of similar code. The advantage of using such toolsis that once the grammar is written, one can go straight on to writing visitors that operate onsyntax trees.

The disadvantage is that the syntax trees supported by the generated code may beless abstract than one could desire.PROGRAM ABSTRACT SYNTAXAdd semantic actions to your parser to produce abstract syntax for the MiniJava language.Syntax-tree classes are available in $MINIJAVA/chap4, together with a PrettyPrintVisitor.If you use JavaCC, you can use JTB to generate the needed code automatically.

Similarly,with SableCC, the needed code can be generated automatically.FURTHER READINGMany compilers mix recursive-descent parsing code with semantic-action code, as shown inProgram 4.1; Gries [1971] and Fraser and Hanson [1995] are ancient and modern examples.Machine-generated parsers with semantic actions (in special-purpose "semantic-action minilanguages") attached to the grammar productions were tried out in 1960s [Feldman and Gries1968]; Yacc [Johnson 1975] was one of the first to permit semantic action fragments to bewritten in a conventional, general-purpose programming language.The notion of abstract syntax is due to McCarthy [1963], who designed the abstract syntax forLisp [McCarthy et al.

Характеристики

Список файлов книги