The Synthesizer Generator: A System for Constructing
Language-Based Editors
Thomas W. Reps and Tim Teitelbaum
This book is a detailed account of the Synthesizer Generator, a system
for creating specialized editors that are customized for editing
particular languages. The book is intended for those with an interest
in software tools and in methods for building interactive systems. It
is a must for people who are using the Synthesizer Generator to build
editors because it provides extensive discussions of how to write
editor specifications. The book should also be valuable for people
who are building specialized editors ``by hand,'' without using an
editor-generating tool.
The need to manage the development of large software systems is one of
the most pressing problems faced by computer programmers. An
important aspect of this problem is the design of new tools to aid
interactive program development. The Synthesizer Generator permits
one to create specialized editors that are tailored for editing a
particular language. In program editors built with the Synthesizer
Generator, knowledge about the language is used to continuously assess
whether a program contains errors and to determine where such errors
occur. The information is then displayed on the terminal screen to
provide feedback to the programmer as the program is developed and
modified.
The knowledge incorporated in editors generated with the Synthesizer
Generator takes several forms. One form is knowledge of the
language's syntax, which is used to detect and prevent syntax errors.
Other forms of language knowledge encompass translation,
transformation, and analysis of an object being edited. Knowledge of
such aspects can be harnessed to check objects for inconsistencies, to
prompt the user of the editor with legal alternatives, or to impose
constraints on how the user can proceed.
The feature that makes the Synthesizer Generator unique is its use of
an immediate-computation paradigm to perform analysis,
translation, and error reporting while an object is being edited. In
the immediate mode of computation, each modification to data has
instantaneous effect, as in an electronic spreadsheet. For example,
with program editors generated using the Synthesizer Generator, each
modification to a program causes all affected analysis, error
messages, and generated code to be immediately updated. Errors are
detected as soon as they occur, and the delay for compilation that is
necessary with traditional program-development tools is eliminated.
The Synthesizer Generator creates a language-specific editor from a
specification of a language's abstract syntax, context-sensitive
relationships, display format, concrete input syntax, and
transformation rules for restructuring objects. The treatment of
language syntax by the Synthesizer Generator is of particular
importance. The editor-designer's specification of the language's
syntax addresses not only context-free syntax but also such
context-sensitive conditions as the absence of type mismatches; as the
user creates and modifies objects, the generated editor incrementally
checks for violations of context conditions that have been specified.
The Synthesizer Generator is of utility in a wide range of
applications, including program editors, document-preparation systems,
and verification tools. It has been used to create program editors
for several different programming languages, including ones with such
varying features as context-sensitive ``pretty-printing,'' incremental
code generation, detection of program anomalies, and detection of type
violations. It has been used to create editors for text and
mathematical formulas; in these editors, formatting is performed
interactively on a character-by-character basis so that at all times
the screen resembles the final page layout. It has also been used to
create editors that verify the correctness of mathematical proofs (for
several different varieties of logic).
The Synthesizer Generator's specification language (called SSL, for
Synthesizer Specification Language) is based on the notion of an
attribute grammar, which is a very general notation for
expressing syntax-directed translations. A number of innovations in
SSL make SSL specifications different from specifications written for
other systems based on attribute grammars. The primary innovations
are the way SSL merges the concepts of abstract-syntax definitions and
user-defined attribute types, the introduction of notation that
permits specifications to be factored into separate modules, and the
manner in which the parser is incorporated into the system.
The Synthesizer Generator has been under development since 1981. It
is implemented in C and runs under the UNIX operating system. The
system has been licensed to hundreds of sites; further information
about the availability of the Synthesizer Generator appears at the end
of this volume.
One goal of the book is to present the Synthesizer Generator's
specification language. The aim is to describe exactly what is
necessary to specify a language-based editor using SSL. However, the
book is more than just a user guide for the system; we also discuss
issues that motivated the decisions we made when designing the system.
A second goal of the book is to demonstrate the Synthesizer
Generator's versatility. We have brought together a collection of
examples that demonstrate the widespread applicability of attribute
grammars in language-based editors.
A third goal is to describe how to make effective use of the system.
In Chapter 8, devoted to practical advice for editor-designers, we
provide recommendations about how to start developing a new editor, as
well as how to organize an editor specification so as to make it
easier to re-use parts of editor specifications in subsequent editors.
We also present case studies of how to specify commonly arising editor
features.
A fourth goal is to provide an introduction to the implementation of
the Synthesizer Generator. In the final two chapters of the book, we
describe a number of the algorithms that are used in the system's
implementation.
The book is organized as follows: Chapters 2, 3, and 4 provide a
tutorial introduction to the Synthesizer Generator; in them, we
briefly examine each of the system's major features. In Chapter 2, we
use a sample editing session to illustrate the capabilities of editors
generated using the Synthesizer Generator. In Chapter 3, we discuss
the model of editing upon which the Synthesizer Generator is based.
In Chapter 4, we begin discussing the Synthesizer Specification
Language, the Synthesizer Generator's specification language; we
present the SSL specification used to generate the editor examined in
Chapter 2 and describe how each of that editor's major components is
specified.
Chapters 5, 6, 7, and 8 provide a more detailed treatment of
``programming'' in SSL. Chapter 5 is concerned with lists and
optional elements, and discusses the issues that arise when writing
the parts of editor specifications that concern them. Chapter 6 is
devoted to the problem of how to create a harmonious integration of
structural and textual perspectives in editors. Chapter 7 discusses
how to specify static inferences via attribution. Chapter 8 is
devoted to practical advice on a range of topics.
In Chapters 9 and 10 we discuss additional examples that illustrate
the power and versatility of the Synthesizer Generator. Chapter 9 is
concerned with ways to extend language-based editors with execution
facilities. Chapter 10 discusses the use of the Synthesizer Generator
to build editors for creating and manipulating proofs in a formal
system of logic.
Chapters 11 and 12 discuss technical matters about the system.
Chapter 11 provides an introduction to the implementation of the
Synthesizer Generator, including a discussion of some of the
algorithms that are used in the system. Chapter 12 concerns one of
the algorithms used in the system for incremental attribute
evaluation.
The four appendices contain miscellaneous documentation of SSL and the
Synthesizer Generator. Appendix A contains a context-free grammar for
SSL. Appendix B, presented in the standard format for UNIX-manual
entries, documents how to build an editor with the Synthesizer
Generator by invoking the sgen command. Appendix C, excerpted
from The Synthesizer Generator Reference Manual, documents some
of the commands available in editors generated with the Synthesizer
Generator. Appendix D describes workstation-specific information
required for running an editor.
Reps, T. and Teitelbaum, T., The Synthesizer Generator: A
System for Constructing Language-Based Editors. Springer-Verlag,
New York, NY, 1988.
University of Wisconsin