In this paper, we introduce SableCC, an object-oriented framework that generates compilers and interpreters in the Java programming language. This framework is based on two fundamental design decisions. Firstly, the framework uses object-oriented techniques to automatically build a strictly-typed abstract syntax tree that matches the grammar of the compiled language which simpli es debugging. Secondly, the framework generates treewalker classes using an extended version of the visitor design pattern which enables the implementation of actions on the nodes of the abstract syntax tree using inheritance. These two design decisions lead to a tool that supports a shorter development cycle for constructing compilers. To demonstrate the simplicity of the framework, we present all the steps of building an interpreter for a mini-BASIC language. This example could be easily modi ed to provide an embedded scripting language in an application. We also provide a brief description of larger systems that have been implemented using the SableCC tool. We conclude that the use of object-oriented techniques signi cantly reduces the length of the programmer written code, can shorten the development time and nally, makes the code easier to read and maintain. The number of computer languages in use today i s o verwhelming. Ranging from general purpose to highly specialized, they are present in almost all areas of computing. There are mainstream programming languages like C , F ortran, Pascal, but also many other languages used in domain-speci c applications. Computer languages can be used to describe many things, other than computer processing. HTML 12 or TeX 8 are used to describe formatted documents. A domain-speci c language like HL7 1 is used to exchange health care information uniformly across the world. It would impossible to list all the uses here, but it is worth noting that these languages are often embedded in larger systems. For example, many w ord processing applications have their own tiny macro language to allow the automation of commands. In component-based development e n vironments, small scripting languages are used to glue together components. In the 1950's, writing a compiler was very di cult. It took 18 sta -years to implement the rst FORTRAN compiler 2 . Since then, advances in the theory of compilers and the This work was partly supported NSERC. development of many compiler tools have simpli ed this task greatly. Writing a compiler is now a feasible task for any programmer with minimal knowledge of compiler techniques. This simplicity is achieved due to the use of compiler compilers. A compiler compiler is a program that translates a speci cation into a compiler for the programming language described in the speci cation. This relieves the programmer from the burden of writing the lexical and syntactical analysis code. Over the years, many compiler compilers have been developed. The scope of these tools varies. While some will build a complete compiler end-to-end from a speci cation, others will only build the front-end of a compiler lexer and or parser. It may seem, at rst glance, that an end-to-end compiler compiler will be more powerful. However, in practice, front-end compiler compilers are normally integrated with a general purpose programming language. This way, the implementation of complex data structures, optimizations, and code analyses is easier because it is done in the programmer's native programming language. Front-end compiler compilers exist for almost all major programming languages in use today. In the last few years, the Java T M 4 programming language has gained a remarkable popularity on the Internet. Although super cially Java has a syntax similar to C++, Java also has many additional features of modern high-level object-oriented programming languages. For example, Java has a garbage collector, a cleaner inheritance mechanism with classes and interfaces, and a rich standard cross-platform library with support for graphical user interfaces and network programming. One of the most interesting properties of Java is the portability of object code. Java source les are compiled to platform independent bytecode instructions. At runtime, these bytecodes are interpreted by a Java Virtual Machine 10 to perform the actual computation. We have developed SableCC, to generate compilers written in the Java programming language. SableCC sits in the middle between front-end and end-to-end compiler compilers. It not only generates a lexer and a parser, but it also builds a complete set of classes. Our main goal was to provide a framework that would simplify the development of easy to maintain compilers. To achieve this goal, the framework abides by the two following properties: All data structures are self-preserving. By preventing the programmer from corrupting data structures, the system helps reducing debugging time. This property is achieved by strictly typing the abstract syntax tree. The addition of new functionality should be feasible through the addition of programmer-de ned classes. This implies a clear separation between automatically generated classes and programmer written classes and thus, helps debugging. This is achieved by providing ready-to-be-inherited-from tree-walker classes. These classes implement the visitor design pattern to enable the use of inheritance as a means to add actions. We use the term actions to refer to the code written by a programmer to be executed on speci c nodes of the abstract syntax tree. This paper is organized as follows. In section 2 we give a high level description of SableCC. In section 3 we explain the relation between a grammar and a typed abstract syntax tree. In section 4 we explore the visitor design pattern and explain the few extensions that we have implemented in our framework. In section 5 we use SableCC to build an interpreter for a mini-BASIC language. In section 6 we brie y describe other compilers that were built using the SableCC tool. In section 7 we discuss related work, and in section 8 w e present our conclusions. SableCC represents the result of our research to develop a Java compiler compiler that meets new compiler implementation trends. More speci cally: Modern compilers usually implement many passes over the compiled program. One pass compilers like early PASCAL compilers are seldom used anymore. Many compilers work on AST Abstract Syntax Tree representation of programs. As a compiler evolves over time, new analyses and optimizations are added to the compiler. A compiler, like a n y other software, must be maintainable. To address these issues we have developed a new approach for compiler compiler tools. In our approach, the compiler compiler place in the development cycle has been reduced to merely build an initial object-oriented framework that is based solely on the lexical and grammatical de nition of the compiled language. This has the advantage of limiting framework modi cations to the case where the grammar of the compiled language is changed. On the other hand, the richness of the generated environment has been increased. So, in the generated framework: The parser automatically builds the AST of the compiled program. Each AST node is strictly typed, ensuring no corruption occurs in the tree. Each analysis is written in its own class. Writing a new analysis only requires extending a tree-walker class and providing methods to do the work at appropriate nodes. Storage of analysis information is kept in the analysis class itself, outside the de nition of node types. This ensures no modi cation to a node type is needed when a new analysis is added to or removed from the compiler. The framework makes extensive use of object-oriented design patterns to achieve modularity of code. The resulting compiler becomes a very maintainable compiler. In some cases we have opted for goodobject-oriented design over fast code. It is our belief that over time, new processors get faster and memory gets cheaper, but the same old code base is often used to generate new compilers. So good software engineering is important in the long term. We h a ve developed SableCC in the Java programming language. It runs on any platform supporting the Java Development Kit 1.1 or newer.
Another example of a compiler tool using OO ASTs is SableCC REF which is a Java-based system using an LL-parser generator.
SableCC, an object-oriented compiler framework
Proceedings. Technology of Object-Oriented Languages. TOOLS 26 (Cat. No.98EX176)
Proceedings. Technology of Object-Oriented Languages. TOOLS 26 (Cat. No.98EX176)
Computer Science