Emond Papegaaij - The Tree Processing Language

author:Emond Papegaaij
title:The Tree Processing Language
keywords:tree processing, ANTLR, TPL, visitor pattern
committee:dr.ir. T.C. Ruys (1st supervisor)
ir. Philip K.F. Hölzenspies
prof.dr.ir. A. Rensink
graduation date:7 March 2007 (mark: 9/10)


Tree structures are commonly used in many applications. One of these is a compiler, in which the tree is called an abstract syntax tree (AST). Different techniques have been developed for building and working with ASTs. However, many of these techniques are limited in their applicability, require major effort to implement or introduce maintenance problems in an evolving application.

This thesis introduces the Tree Processing Language (TPL), a language for defining the structure of a tree and adding functionality to this tree. The compiler TPLc is used to produce the actual class hierarchy implementing the specified tree. TPL provides a clear separation between the structure of a tree, a tree definition, and behaviour of a tree, logic specifications. Different aspects of the behaviour of a tree can be provided in separate logic specifications, allowing a clear separation of concerns.

TPLc generates a heterogeneous tree structure with strictly typed children. Functionality in a logic specification is specified using the inheritance pattern. To allow different inheritance trees in different logic specifications, the inheritance pattern is enhanced with multiple inheritance. For languages that do not support multiple inheritance, the inheritance pattern with composition is developed. To prove the applicability of TPL, TPLc is itself written in TPL. When compared with an implementation in Java, this implementation provides a better separation of concerns and is easier to maintain.