COMPILER CONSTR UCTION - Carnegie Mellon University

1 COMPILER CONSTRUCTION. William M. Waite Department of Electrical Engineering University of Colorado Boulder, Colorado 80309. USA. email: Gerhard Goos Institut Programmstrukturen und Datenorganisation Fakult at f ur Informatik Universit at Karlsruhe D-76128 Karlsruhe Germany email: COMPILER Construction, a modern text written by two leaders in the in the eld, demonstrates how a COMPILER is built. Describing the necessary tools and how to create and use them, the authors compose the task into mod- ules, placing equal emphasis on the action and data aspects of compilation. Attribute grammars are used extensively to provide a uniform treatment of semantic analysis, competent code generation and assembly. The authors also explain how intermediate representations can be chosen automatically on the basis of attribute dependence.

2 Thus, all aspects of the subject are presented in terms of a uniform model subject to automation. This ap- proach imparts a vivid understanding of the compilation and the decisions that must be made when designing a COMPILER . From the back page of the printed book. All known errors from the rst and second printing (1994 and 1995) have been xed. While every precaution has been taken in preparation of this book, the authors assume no responsibility for errors or omissions, or damages resulting from the use of the information contained here. c 1984{1994 by Springer-Verlag, Berlin, New York Inc. ISBN 0-387-90821-8 and ISBN 3-540-90821. c 1995 by William M. Waite and Gerhard Goos. All rights reserved. No part of this book may be translated, reproduced, archived or sold in any form without written permission from one of the authors.}

3 The content of COMPILER Construction is made available via the Web by permission of the authors as a service to the community and only for educational purposes. The book may be accessed freely via Web browsers. The URL is Karlsruhe, 22nd February 1996. To all who know more than one language Preface Compilers and operating systems constitute the basic interfaces between a programmer and the machine for which he is developing software. In this book we are concerned with the construction of the former. Our intent is to provide the reader with a rm theoretical basis for COMPILER construction and sound engineering principles for selecting alternate methods, implementing them, and integrating them into a reliable, economically viable product.

4 The emphasis is upon a clean decomposition employing modules that can be re-used for many com- pilers, separation of concerns to facilitate team programming, and exibility to accommodate hardware and system constraints. A reader should be able to understand the questions he must ask when designing a COMPILER for language X on machine Y, what tradeo s are possible, and what performance might be obtained. He should not feel that any part of the design rests on whim; each decision must be based upon speci c, identi able characteristics of the source and target languages or upon design goals of the COMPILER . The vast majority of computer professionals will never write a COMPILER . Nevertheless, study of COMPILER technology provides important bene ts for almost everyone in the eld.

5 It focuses attention on the basic relationships between languages and machines. Un- derstanding of these relationships eases the inevitable transitions to new hardware and programming languages and improves a person's ability to make appropriate tradeo s in design and implementation. It illustrates application of software engineering techniques to the solution of a signi cant problem. The problem is understandable to most users of computers, and involves both combinatorial and data processing aspects. Many of the techniques used to construct a COMPILER are useful in a wide variety of appli- cations involving symbolic data. In particular, every man-machine interface constitutes a form of programming language and the handling of input involves these techniques.

6 We believe that software tools will be used increasingly to support many aspects of COMPILER construction. Much of Chapters 7 and 8 is therefore devoted to parser gen- erators and analyzers for attribute grammars. The details of this discussion are only interesting to those who must construct such tools; the general outlines must be known to all who use them. We also realize that construction of compilers by hand will remain an important alternative, and thus we have presented manual methods even for those situations where tool use is recommended. Virtually every problem in COMPILER construction has a vast number of possible solutions. We have restricted our discussion to the methods that are most useful today, and make no attempt to give a comprehensive survey.

7 Thus, for example, we treat only the LL and LR. parsing techniques and provide references to the literature for other approaches. Because we do not constantly remind the reader that alternative solutions are available, we may sometimes appear overly dogmatic although that is not our intent. i ii Preface Chapters 5 and 8, and Appendix B, state most theoretical results without proof. Although this makes the book unsuitable for those whose primary interest is the theory underlying a COMPILER , we felt that emphasis on proofs would be misplaced. Many excellent theoretical texts already exist; our concern is reduction to practice. A COMPILER design is carried out in the context of a particular language/machine pair. Although the principles of COMPILER construction are largely independent of this context, the detailed design decisions are not.

8 In order to maintain a consistent context for our major examples, we therefore need to choose a particular source language and target machine. The source language that we shall use is de ned in Appendix A. We chose not to use an existing language for several reasons, the most important being that a new language enabled us to control complexity: Features illustrating signi cant questions in COMPILER design could be included while avoiding features that led to burdensome but obvious detail. It also allows us to illustrate how a COMPILER writer derives information about a language, and provides an example of an informal but relatively precise language de nition. We chose the machine language of the IBM 370 and its imitators as our target.

9 This architecture is widely used, and in many respects it is a di cult one to deal with. The problems are representative of many computers, the important exceptions being those (such as the Intel 8086) without a set of general registers. As we discuss code generation and assembly strategies we shall point out simpli cations for more uniform architectures like those of the DEC PDP11 and Motorola 68000. We assume that the reader has a minimum of one year of experience with a block- structured language, and some familiarity with computer organization. Chapters 5 and 8. use notation from logic and set theory, but the material itself is straightforward. Several important algorithms are based upon results from graph theory summarized in Appendix B.

10 This book is based upon many COMPILER projects and upon the lectures given by the authors at the Universit at Karlsruhe and the University of Colorado. For self-study, we recommend that a reader with very little background begin with Section , Chapters 2. and 3, Section and Appendix A. His objective should be to thoroughly understand the relationships between typical programming languages and typical machines, relationships that de ne the task of the COMPILER . It is useful to examine the machine code produced by existing compilers while studying this material. The remainder of Chapter 1 and all of Chapter 4 give an overview of the organization of a COMPILER and the properties of its major data structures, while Chapter 14 shows how three production compilers have been structured.