Chapter Program Representation
Strategies for Program Transformation
Abstract
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.
Preprint
