Pretty Printing Java With Visitor

The following exchange is from the JavaCompilerCompiler email list ...

What is the Visitor OO Pattern?

I wrote a PrettyPrinter last week, and it works by getting JavaCC to generate a parser for the Java1.1 grammar. On top of this, it uses a facility in JavaCC called JJTree, which generates a "syntax tree structure" as the parser goes through the input file. (In fact I wrote the PrettyPrinter mainly to learn about JavaCC/Tree.)

You end up with a big tree of nodes that represents the syntactic structure of the program just read in. The "leaf" nodes of the tree are the symbols you see in the source code, like "public" "count", "==", and inner nodes represent increasingly more abstract notions: Expression, Statement, MethodBody?, ClassDeclaration?, all the way up to the root, called CompilationUnit?.

Problem: my PrettyPrinter works by having each Node in the tree have a "PrettyPrint" method. This is fine except, if I now wanted to do a "Javadoc" application; the nodes have to be ripped open, rewritten, recompiled etc, etc, and the whole thing gets really here-comes-another-wheel hairy, and then you get confused between each operation and what methods belong to which etc. Actually it's already like this, confusing or not caring about the difference between strictly "Node" methods and attributes and the PPrinter methods.

So I looked in "DesignPatterns" on the advice of someone on the ball in the JavaCC mailing list, and there's a pattern right at the end of the book, page 331, called "Visitor". This seems exactly right: You have two things, the syntax tree, and the Visitor, and there's I guess an interface they've got to meet.

Here's a partial, part-baked understanding that I made earlier:

The Visitor (the PrettyPrinter operation) has a method for every nodetype, and calls "Accept(thePrettyPrinter)" on each node of the tree structure (each node?). The node (say it's the IfStatement? node) then calls back to the Visitor, with the call "yoo-hoo, VisitIfStatement?", and allows the Visitor to know the details of what this (IfStatement?) node is, somehow. Either by passing itself kit-and-kaboodle or by sending the pertinent details. *Something like this*.

I thought someone might know about this. Anyway, if I can understand this, then I can produce a "JavaAST component" that with suitable documentation and a clean interface, can accept all manner of yet-to-be-dreamt-of operations. One such that does need overhauling is Javadoc. Another is, or just hauling, is HyperJava?.

It says, and I've understood this, that the Visitor Pattern idea is no good if the design elements of the tree structure keeps being modified, but Java 1.1 and language grammars in general are quite stable, geologically speaking. -- Sandy (mailto:sandy@almide.demon.co.uk)

Sorry, this doesn't answer your question about what the Visitor OO pattern is, but, on the topic of the visitor design pattern for use with syntax trees, as a research project this summer I've been working on a syntax tree automatic generator, along the same lines as jjTree.

The difference is that this generator is designed for use with the visitor pattern. Given a .jj file, it will generate classes for each production (with a method to accept visitors), an annotated version of the input file which will now build the tree, and a generic Visitor superclass which simply traverses the tree. IMHO, it's very easy to use. All you need to know is how to program using the visitor pattern (which, once you know how, very much simplifies and organizes AST programming).

I'll post a message to this mailing list once the program is ready for public use/testing, which will be fairly soon, probably some time in September. -- Kevin (mailto:taokr@cs.purdue.edu, http://www.cs.purdue.edu/homes/taokr)

Ok, so in a month's time, or so, you're saying there will be a new Tree-thingy that allows it to accept independent stand-alone Tree "operations" modules, otherwise known as "visitors". So I can re-write my existing PrettyPrinter as a separate entity from the AST - as a "PrettyPrint" visitor.

This is most excellent. This business of learning JavaCC the hard way has been very rewarding; I've had huge glimpses of insight into Object Oriented doodah over the last month. More than all 3 years at college anyway! -- Sandy

Readers are encouraged to explore the JavaTreeBuilder? at ...

as of Dec 2004 this is a BrokenLink -- JeffHayes

This tool is an alternative to JJTree that has been explicitly designed? with the VisitorPattern in mind.

I've used the VisitorPattern, but I'm not sure what your question is. I was able to figure it out from the book (although I agree it's the least obvious pattern there). You have a class called Visitor, with a method for each type of node. Each node class has a single routine like: 

    void accept( Visitor visitor ) {
        visitor.visit( this );
    }
Inside the body of that routine, the static type of "this" is known, so the right version of visitor.visit() gets called via overloading. You then have a subclass of Visitor called PrettyPrintVisitor?, which overrides each of the visit() routines: 
    void visit( IfStatementNode? node ) {
        // do some stuff.
        node.getCondition().accept( this );
        node.getTrueStatement().accept( this );
        node.getFalseStatement().accept( this );
    }
In the body of this routine, we know both the type of the node and the type of the visitor so we can do the needful.

I've shown the tree traversal code as part of the visit() statement. It can also be in the accept() method of the IfStatementNode? class, or in a base class of PrettyPrintVisitor?.

I hope this helps. -- DaveHarris

(looks like my original post got stomped)

I found the VisitorPattern useful on a project where I implemented an HTML viewer and minimalist browser. Being able to take the tree representing the structure of the HTML file and to apply various Visitor objects on it greatly simplified the implementation (e.g., rendering, creating a form and posting it, extracting HTML element values).

One problem I found was that, even though I tried to document the pattern, I had trouble getting the person to whom the code was eventually given to understand how the DoubleDispatch-like mechanism of the VisitorPattern worked, or to understand how it simplified the implementation (this was written in two or three weeks).

I noticed that the person eventually got his own copy of DesignPatterns, which I had attributed in the source code...

-- OliverSeiler

SableCC seems to be better than JavaCC and it uses the visitor pattern. Here is the link to the site: http://www.sablecc.org/.

as of Dec 2004 this is a BrokenLink - JeffHayes

I followed it to http://www.sable.mcgill.ca/projects/ but there is no further clue about what happened to it.

Bala(mailto:nospam@yahoo.com) (Replace nospam by bparanj)

Whenever i use JavaCompilerCompiler, or write any kind of parsing code, for that matter, i use a form in which the parser communicates the document to the backed via a VisitorPattern-type interface. In fact, it's rather like a BuilderPattern.

With JavaCC, one writes productions that look a bit like this (with annotations for those not familiar with JavaCC syntax): 

 House() // production name
 {} // ignore these braces for now!
 {
 (Room() | Corridor() | Staircase())*
 }


 Room()
 {}
 {
 "Room" // consume a literal
 // the <XXX> syntax means 'consume token of type XXX'
 <DISTANCE> // width
 <DISTANCE> // length
 <FLOOR_NUMBER> // floor level
 }


 // etc - productions for Corridor and Staircase
One of the problems a programmer faces is getting the parsed data from the parser to the rest of the application. One way is to use JjTree? and then let the rest of the application play with the tree. However, there is an alternative which is often as powerful, and more space-efficient. This is to define a visitor interface for the parsed document; in this case it might look like this: 

 public interface HouseVisitor
 {
 public void houseStart() ;
 public void houseEnd() ;
 public void room( double width, double length, int floor ) ;
 public void corridor( ... ) ;
 public void staircase( ... ) ;
 }
The grammar can now be annoted with actions to send messages to the visitor: 

 // make HouseVisitor v a member variable in the parser, or else pass it down to the productions


 House() {}
 {
 { // braces denote an inline code block
 v.houseStart() ;
 }
 (Room() | Corridor() | Staircase())*
 {
  v.houseEnd() ;
 }
 }


 Room()
 { // this leading brace pair is a place to put variable declarations
 Token widthTok, lengthTok, floorTok ;
 }
 {
 "Room"
 widthTok = <DISTANCE> // width
 lengthTok = <DISTANCE> // length
 floorTok = <FLOOR_NUMBER> // floor level
 {
 // Token.image is the string value of a token
 double width = Double.parseDouble( widthTok.image ) ;
 double length= Double.parseDouble( lengthTok.image ) ;
 int floor = Integer.parseInt( floorTok.image ) ;
 v.room( width, length, floor ) ;
 }
 }


 // etc
The parser is thus decoupled from the actual application logic. This isn't a proper visitor, as the interface does not take whole objects, but the guts of eviscerated objects. In this respect, it is more like a builder, and i use it so: i write model classes which basically hold onto the values produced by the parser, and write a builder implementation of the interface which builds model objects from the method calls it receives. The model objects then have accept methods which use the interface as a normal visitor.

In this way, any visitor written to visit the model (such as a PrettyPrinter) can also be plugged straight in to the parser, so avoiding any actual construction of model objects. Which can be handy.

Has anyone else noticed the family resemblance between VisitorAndBuilder??

PS there's a working example of this here:

http://users.ox.ac.uk/~univ0938/parse-visit-build.zip

It's a parser for a very simple VRML-like language (six productions in the grammar!). There's no documentation or tests or anything, but it should build out of the box if you define 'javacc' as a command which runs JavaCC.

-- TomAnderson

EditText of this page (last edited May 14, 2008) or FindPage with title or text search