Chapter Program Representation

Strategies for Program Transformation

Program transformation systems need some kind of representation for program that can be manipulated. Programmers write programs as texts using text editors. Some programming environments provide more graphical (visual) interfaces for programmers to specify certain domain-specific ingredients (e.g., user interface components). But ultimately, such environments have a textual interface for specifying the details. Even if programs are written in a `structured format' such as XML, the representation used by programmers generally is text. So a program transformation system needs to manipulate programs in text format.

However, for all but the most trivial transformations, a structured rather than a textual representation is needed. To bridge the gap between textual and structured representation, parsers and unparsers are needed. Since the theory of formal languages, context-free and regular grammars, and parser construction are standard fair, we will not treat those subjects here. The purpose of this chapter is to introduce the terminology and formalisms used in the rest of this book. This includes formal syntax definition with the syntax definition formalism SDF, parsing, representation of trees as ATerms, mapping of parse trees to abstract syntax trees, and pretty-printing using the target-independent Box language. We illustrate these concepts with a syntax definition for a subset of the Tiger language used in the rest of this book.