Transcript visitorPattern

The Visitor Design Pattern
and Java Tree Builder
Cheng-Chia Chen
1
The Visitor Pattern
• A design pattern enabling the definitions of new
operations on an object structure without the requirement
to change the classes of the objects.
• Separate (the specification of) extrinsic operations on an
object structure from the structure of objects.
2
UML Representation of Visitor Pattern
3
Visitor Structure
Element
Visitor
visitA () = 0;
visitB () = 0;
accept ()
ConcreteVisitor
ElementA
ElementB
accept (); A_method ();
accept (); B_method ();
visitA ();
visitB ();
• Different elements have different concrete interfaces
• Element abstract base class adds accept interface
• Double hand-shake between concrete element and visitor allows
visitor to call the appropriate concrete element method
4
Visitor Interactions
ElementA
ElementB
ConcreteVisitor
accept ();
visitA ();
A_method ();
accept ();
visitB ();
B_method ();
5
Example : integer List
public abstract class List { }
public class NullList extends List
{}
class ConsList extends List {
int head;
List tail;
}
6
Operation : summing an integer list
• First Approach: Instanceof and Type Casts
List l; // The List-object
int sum = 0;
boolean proceed = true;
while (proceed) {
if (l instanceof NullList)
proceed = false;
else if (l instanceof ConsList) {
sum = sum + ((ConsList) l).head;
l = ((ConsList) l).tail;
// Notice the two type casts!
}}
Advantage: The code is written without touching the classes NullList
and ConsList.
Drawback: The code constantly uses type casts and instanceof to
determine what class of object it is considering.
7
2nd approach : attach a method to each class
• The first approach is not object-oriented!
• To access parts of an object, the classical approach is to
use dedicated methods which both access and act on the
subobjects.
abstract class List {
int sum(); }
• We can now compute the sum of all components of a
given List-object l by writing l.sum().
8
2nd approach (continued)
class NullList extends List {
public int sum() { return 0; } }
class ConsList extends List {
int head; List tail;
public int sum() { return head + tail.sum(); }
}
Advantage: The type casts and instanceof operations have
disappeared, and the code can be written in a systematic way.
Disadvantage: For each new operation (say, multiply all
integers, count #integers, print all integers,…) on Listobjects, new dedicated methods have to be written, and
all classes must be recompiled.
9
Third Approach: The Visitor Pattern
The Idea:
• Divide the code into an object structure and a Visitor
• Insert an accept method in each class. Each accept
method takes a Visitor as argument.
• A Visitor contains a method visit(C x) for each possible
object class C. (overloading!).
abstract List {
void accept(Visitor v);
}
interface Visitor {
void visit(NullList x);
void visit(ConsList x); }
10
Third Approach (continued)
• The purpose of the accept methods is to invoke the visit
method in the Visitor which can handle the current object.
class NullList extends List {
public void accept(Visitor v) { v.visit(this); } //1
}
class ConsList extends List {
int head; List tail;
public void accept(Visitor v) { v.visit(this); } //2
}
Note: 1 and 2 are the same and can be lifted to parent List.
class List {
public void accept(Visitor v) // default accept implem.
{ v.visit(this); } }
11
Third Approach : (continued)
• The control flow goes back and forth between the visit methods in
the Visitor and the accept methods in the object structure.
class SumVisitor implements Visitor {
int sum = 0;
public void visit(NullList x) {}
public void visit(ConsList x) {
sum = sum + x.head;
x.tail.accept(this);
}}
.....
SumVisitor sv = new SumVisitor();
l.accept(sv);
System.out.println(sv.sum);
• Notice: The visit methods describe both (1) actions, and (2) access
of subobjects. (2) can in fact be determined by object class instead of
visitor.
12
Third Approach : (Continued)
• Extend your List applications to permit
– multiplying all integers in a list or
– counting the number of integers in a list
– printing out all integers, ….
• Each can be implemented by defining a new visitor.
– without the need to change code of List (and NullList and ConsList …).
 main advantage of the visitor pattern.
class ProductVisitor implements Visitor {
int prod = 1;
public void visit(NullList x) {}
public void visit(ConsList x) {
prod = prod * x.head;
x.tail.accept(this);
}}
13
class CountVisitor implements Visitor {
int count = 0;
public void visit(NullList x) {}
public void visit(ConsList x) {
count++;
x.tail.accept(this);
}}
class PrintVisitor implements Visitor {
String result = “”;
public void visit(NullList x) {}
public void visit(ConsList x) {
if( “”.equals(result) ){ result = result + x.head; }
else { result = rersult + “ ,” + x.head ;}
x.tail.accept(this);
}}…
CountVisitor cv = new CountVisitor();
PrintVisitor pv = new CountVisitor();
cv.accept(l); System.out.println(cv.count);
pv.accept(l); System.out.println(“[“ + pv.result +”]”);
14
Comarision
• The Visitor pattern combines the advantages of the two other
approaches.
Frequent
Frequent
type casts?
recompilation?
Instanceof and type casts
Yes
No
Dedicated methods
No
Yes
The Visitor pattern
No
No
• The advantage of Visitors: New methods without recompilation!
• Requirement for using Visitors: All classes must have an accept
method.
• Tools that use the Visitor pattern:
– JJTree (from Sun Microsystems) and the Java Tree Builder (from Purdue
University), both frontends for The Java Compiler Compiler from Sun
Microsystems.
-SableCC
15
Visitor: Summary
• Visitor makes adding new operations easy.
– Simply write a new visitor.
•
A visitor gathers related operations.
– It also separates unrelated ones.
•
Adding new classes to the object structure is hard.
– Key consideration: are you most likely to change the algorithm applied
over an object structure, or are you most like to change the classes of
objects that make up the structure.
– As to compiler design, it requires many operations on syntax tree, which
is the main object structure of compiler and is relatively stable.
•
•
Visitors can accumulate state/information.
Visitor can break encapsulation.
– Visitor’s approach assumes that the interface of the data structure
classes is powerful enough to let visitors do their job. As a result, the
pattern often forces you to provide public operations that access internal
state, which may compromise its encapsulation.
16
The Java Tree Builder (JTB)
• Developed at Purdue University.
– http://www.cs.purdue.edu/jtb/
• A frontend for The Java Compiler Compiler.
• Supports the building of syntax trees which can be
traversed using visitors.
• JTB transforms a bare JavaCC grammar into three
components:
– a JavaCC grammar with embedded Java code for building a
syntax tree;
– one class for every form of syntax tree node; and
– a default visitor which can do a depth-first traversal of a syntax
tree.
17
JTB (continued)
• The produced JavaCC grammar can then be processed
by the Java Compiler Compiler to give a parser which
produces syntax trees.
• The produced syntax trees can now be traversed by a
Java program by writing subclasses of the default visitor.
Program
Parser
SyntaxTree
with accept
methods
JavaCC
Bare JavaCC
Grammar
SyntaxTree
Node Classes
JTB
Default Visitor
JavaCC Grammar with
embeded code
MyApplicationVisitor
18
Using JTB
• jtb myGrammar.jj // will generates many files:
– jtb.out.jj -- the original grammar file with syntaxTree building code
inserted.
– /syntaxtree/**.java -- a class for each production
– /visitor/**
–
Visitor.java, DepthFirstVisitor -- the interface and implemenation
–
ObjectVisitor.java, ObjectDepthFirstVisitor.java
–
-- the visitor interface (& implementation) with return value and
argument
• javacc jtb.out.jj // generates a parser with a specified name
• javac Main.java // Main.java contains a call of the parser and calls
to visitors
• java Main < prog.f // builds a syntax tree for prog.f, and executes
the visitors
19
Example:
• A visitor which operates on syntax trees for Java programs. The
program prints the right-hand side of every assignment.
public class VprintAssignRHS extends DepthFirstVisitor {
void visit(Assignment n) {
PrettyPrinter v = new PrettyPrinter();
n.f2.accept(v); v.out.println();
n.f2.accept(this);
}}
• When this visitor is passed to the root of the syntax tree, the depthfirst traversal will begin, and when Assignment nodes are reached,
the method visit in VprintAssignRHS is executed.
• Notice the use of PrettyPrinter. It is a visitor which pretty prints Java
1.1 programs.
• JTB is bootstrapped (JTB written using JTB)
20
Details
• jtb.out.jj, the original grammar file, now with syntax tree
building actions inserted
• The subdirectory/package syntaxtree which contains a
java class for each production in the grammar
• The subdirectory/package visitor which contains
Visitor.java, the default visitor interface, also
– DepthFirstVisitor.java, a default implementation which visits each
node of the tree in depth-first order.
• ObjectVisitor.java, another default visitor interface that
supports return value and argument.
– ObjectDepthFirst.java is a defualt implemetation of
ObjectVisitor.java.
21
General Instructions
• To generate your parser, simply run JavaCC
using jtb.out.jj as the grammar file.
• Let's take a look at all the files and directories
JTB generates.
22
The grammar file
• Named jtb.out.jj
• This file is the same as the input grammar file except that
it now contains code for building the syntax tree during
parse.
• Typically, this file can be left alone after generation.
• The only thing that needs to be done to it is to run it
through JavaCC to generate your parser
23
The syntax tree node classes
• This directory contains syntax tree node classes
generated based on the productions in your JavaCC
grammar.
• Each production will have its own class. If your
grammar contains 42 productions, this directory will
contain 42 classes (plus the special automatically
generated nodes--these will be discussed later), with
names corresponding to the left-hand side names of the
productions.
• Like jtb.out.jj, after generation these files don't
need to be edited. Generate them once, compile them
once, and forget about them
24
Example
• Let's examine one of the classes generated from
a production. Take, for example, the following
production
void ImportDeclaration() :
{}
{
"import" Name() [ "." "*" ] ";“
}
25
What gets produced?
Part 1
// Generated by JTB 1.1.2 //
package syntaxtree;
/**
* Grammar production:
All parts of a production
* f0 -> "import"
are represented in the tree,
* f1 -> Name()
including tokens.
* f2 -> [ "." "*" ]
* f3 -> ";"
*/
public class ImportDeclaration implements Node {
public NodeToken f0;
public Name f1;
public NodeOptional f2;
public NodeToken f3;
26
The Syntax Tree Classes
• Notice the package "syntaxtree".
• The purpose of separating the generated tree node
classes into their own package is that it greatly simplifies
file organization, particularly when the grammar contains
a large number of productions.
• It’s often not necessary to pay the syntax classes any
more attention. All of the work is to done to the visitor
classes.
• Note that this class implements an interface named
Node.
27
Automatically-Generated Tree Node Interface and Classes
Node
All tree nodes implement this
Nodelistinterface
List interface that NodeList, NodeListOptional, and
NodeSeqeunce implement
Nodechoice
Represents ( A | B )
Nodelist
Represents ( A ) +
NodeListOptional
Represents ( A ) *
NodeOptional
Represents [ A ] or ( A )?
NodeSequence
Represents nexted sequence like
[ "extends" Name() ]
NodeToken
Represents a token string
28
Node
• The interface Node is implemented by all syntax tree nodes.
Node looks like this:
public
interface Node extends java.io.Serializable {
public void accept(visitor.Visitor v);
public Object accept(visitor.ObjectVisitor v,
Object argu);
}
29
Nodes and Accept
• All tree node classes implement the accept()
method.
– In the case of all the automatically-generated classes,
the accept() method simply calls the corresponding
visit(XXXX n) (where XXXX is the name of the
production) method of the visitor passed to it.
– Note that the visit() methods are overloaded, i.e. the
distinguishing feature is the argument each takes, as
opposed to its name.
30
Two New Features
• Two features presented in JTB 1.2 may be
helpful
–
The first is that Node extends java.io.Serializable,
meaning that you can now serialize your trees (or
subtrees) to an output stream and read them back in.
– Secondly, there is one accept() method that can take
an extra argument and return a value.
31
What gets produced?
Part 1
// Generated by JTB 1.1.2 //
package syntaxtree;
/**
* Grammar production:
All parts of a production
* f0 -> "import"
* f1 -> Name()
are represented in the tree,
* f2 -> [ "." "*" ]
including tokens.
* f3 -> ";"
*/
public class ImportDeclaration implements Node {
public NodeToken f0;
public Name f1;
public NodeOptional f2;
public NodeToken f3;
32
NodeListInterface
• The interface NodeListInterface is implemented by
NodeList, NodeListOptional, and
NodeSequence. NodeListInterface looks like this:
public interface NodeListInterface
extends Node {
public void addNode(Node n);
public Node elementAt(int i);
public java.util.Enumeration
elements();
public int size();
}
33
Details
• Interface not generally needed but can be useful
when writing code which only deals with the
Vector-like functionality of any of the three
classes listed above.
– addNode() is used by the tree-building code to add
nodes to the list.
– elements() is similar to the method of the same name
in Vector, returning an Enumeration of the elements
in the list.
– elementAt() returns the node at the ith position in the
list (starting at 0, naturally).
– size() returns the number of elements in the list
34
NodeChoice
• NodeChoice is the class which JTB uses to represent
choice points in a grammar. An example of this would
be
( "abstract" | "final" | "public" )
• JTB would represent the production
void ResultType() :
{}
{
"void" | Type() }
– as a class ResultType with a single child of type NodeChoice.
35
Details
• The type stored by this NodeChoice would not
be determined until the file was actually parsed.
• The node stored by a NodeChoice would then be
accessible through the choice field.
• Since the choice is of type Node, typecasts are
sometimes necessary to access the fields of the
node stored in a NodeChoice.
36
Implementation
public class NodeChoice implements Node {
public NodeChoice(Node node, int
whichChoice);
public void accept(visitor.Visitor v);
public Object
accept(visitor.ObjectVisitor v,
Object argu);
public Node choice;
public int which;
}
37
Which One?
• Another feature of NodeChoice is the field which
for determining which of the choices was
selected
• The which field is used to see which choice
was used
–
If the first choice is selected, which equals 0
(following the old programming custom to start
counting at 0).
– If the second choice is taken, which equals 1. The
third choice would be 2, etc.
– Note that your code could potentially break if the
order of the choices is changed in the grammar.
38
NodeList
• NodeList is the class used by JTB to represent
lists. An example of a list would be
( "[" Expression() "]" )+
• JTB would represent the javacc production :
void ArrayDimensions() :
{}
{ ( "[" Expression() "]" )+ ( "[" "]" )* }
– as a class ArrayDimensions() with children NodeList
and NodeListOptional respectively.
39
Details
• NodeLists use java.lang.Vectors to store the lists
of nodes.
• Like NodeChoice, typecasts may occasionally
be necessary to access fields of nodes contained
in the list.
40
Implementation
public class NodeList implements NodeListInterface {
public NodeList();
public void addNode(Node n);
public Enumeration elements();
public Node elementAt(int i);
public int size();
public void accept(visitor.Visitor v);
public Object accept(visitor.ObjectVisitor v,
Object argu);
public Vector nodes;
}
41
NodeToken
• This class is used by JTB to store all tokens into
the tree, including JavaCC "special tokens" (if the
-tk command-line option is used).
• In addition, each NodeToken contains
information about each token, including its
starting and ending column and line numbers.
42
Implementation
public class NodeToken implements Node {
public NodeToken(String s);
public NodeToken(String s, int kind, int beginLine,
int beginColumn, int endLine, int
endColumn);
public String toString();
public void accept(visitor.Visitor v);
public Object accept(visitor.ObjectVisitor v, Object
argu);
// -1 for these ints means no position info is
available.
// …
}
43
Continued
public class NodeToken implements Node {
// ….
public String tokenImage;
public int beginLine, beginColumn, endLine,
endColumn;
// -1 if not available.
// Equal to the JavaCC token "kind" integer.
public int kind;
// Special Token methods below
public NodeToken getSpecialAt(int i);
public int numSpecials();
public void addSpecial(NodeToken s);
public void trimSpecials();
public String withSpecials();
public Vector specialTokens;
}
44
Token Details
• The tokens are simply stored as strings.
• The field tokenImage can be accessed directly, and the
toString() method returns the same string.
• Also available is the kind integer.
• JavaCC assigns each type of token a unique integer to
identify it.
• This integer is now available in each JTB
NodeToken. For more information on using the kind
integer, see the JavaCC documentation.
45
Member Variables of
Generated Classes
• Next comes the member variables of the
ImportDeclaration class.
• These are generated based on the RHS of the
production. Their type depends on the various items in
the RHS and their names begin with f0 and work their
way up.
• Why are they public?
– Visitors which must access these fields reside in a different
package than the syntax tree nodes
– Package visibility cannot be used.
– Breaking encapsulation was a necessary evil in this case.
46
What gets produced?
Part 2
public ImportDeclaration(NodeToken n0,
Name n1, NodeOptional n2, NodeToken n3)
{
f0 = n0;
f1 = n1;
f2 = n2;
f3 = n3;
}
public ImportDeclaration(Name n0, NodeOptional n1) {
f0 = new NodeToken("import");
f1 = n0;
f2 = n1;
f3 = new NodeToken(";");
}
47
Constructors
• The next portion of the generated class is the standard
constructor. It is called from the tree-building actions in
the annotated grammar so you will probably not need to
use it.
• Following the first constructor is a convenience
constructor with the constant tokens of the production
already filled-in by the appropriate NodeToken. This
constructor's purpose is to help in manual construction of
syntax trees.
48
What gets produced?
Part 3
public void accept(visitor.Visitor v)
{
v.visit(this);
}
public Object
accept(visitor.ObjectVisitor
v, Object argu) {
return v.visit(this,argu);
}
}
49
The Accept Methods
•
•
After the constructor are the accept() methods.
These methods are the way in which visitors
interact with the class.
void accept(visitor.Visitor v)
–
works with Visitor
Object accept(visitor.ObjectVisitor v,
Object argu)
–
works with ObjectVisitor
50
References
• Java Tree Builder Documentation
• Why Visitors?
• Erich Gamma, Richard Helm, Ralph Johnson, and John
Vlissides.
Design Patterns: Elements of Reusable Object-Oriented
Software.
Addison-Wesley, 1995
51