The Synthesizer Generator: A System for Constructing Language-Based Editors

Thomas W. Reps and Tim Teitelbaum
University of Wisconsin

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.