Re: References to object oriented design of compilers?

newton@cs.utexas.edu (Peter Newton):
> Does anybody know of any publications on the subject of object-oriented
> design applied to compilers?


The idea that every rule in the abstract syntax becomes a class is a
classic one, but doesn't seem to be documented anywhere. It is used in
the original Smalltalk-80 compiler, which dates from at least 1980. The
spin that Douglas Jones puts on it is a lot more sophisticated than the
one that most people use. The Smalltalk compiler has a recursive descent
parser that produces ASTs, and then implements various operations on the
ASTs for code optimization and code generation. We reused the parser in
TS, but translated the ASTs into an RTL.


A common problem with this approach is that the classes representing AST
nodes get cluttered with a lot of code that is very specialized. In
Smalltalk, for example, there is code for pretty printing, flow analysis,
and so on. One way to move this code out of the main AST classes and into
applications is to use a design technique called a Visitor, or tree
walker, or tree node enumerator. This technique is a form of double
dispatching. The idea is to give each node a "handle:" method, which a
node of type Foo implements as:


handle: aVisitor
      ^aVisitor handleFoo: self


The Visitor object then implements a handleX: method for each AST node
class X.


Thus, an operation on an AST is represented by a Visitor object, and you
apply an operation to an AST by traversing it, sending the handle: message
to each node with the Visitor as an argument.


A description of the basic design pattern of representing each rule in a
grammar with a class is going to be in my upcoming book on object-oriented
design patterns with Erich Gamma, Richard Helm, and John Vlissides called
"Design patterns: Micro-Architectures for Reusable Object-Oriented
Design". The only paper that I can think might describe it is a paper
about T-Gen by Justin Graver, which I think was published in Software
Practice and Experience. T-Gen is a parser generator for Smalltalk.
--

Return to the comp.compilers page.
Search the comp.compilers archives again.