这是一本令人耳目一新的书。本书不仅对现代编译设计理论做了详尽的研究，而且对小语言的有效编译程序进行了全面的描述（并给出了源代码）。作者深信，如果不掌握编译理论，就不可能理解实际的编译程序设计；如果理论不付诸于实践就不会真正理解编译理论。对编译概念的教科书式的讲座形成了一个完整有效的编译程序，该编译程序由C语言编写并采用了各章所讲座的技巧。各章后面的练习旨在培养学生解决具体编程问题的能力。
This book is an introduction to the field of compiler construction. It combines a detailed study of the theory underlying the modern approach to compiler design, together with many practical examp1es, and a complete description, with source cede, of a compiler for a small language. It is specifically designed for use in an introductory course on compiler design or compiler construction at the advanced undergraduate level. However, it will also be of use to professionals joining or beginning a compiler writing project, as it aims to give the reader all the necessary too1s and practical experience to design and program an actua1 compiler.
A great many texts already exist for this fie1d. Why another one Because virtually all current texts confine themselves to the study of only one of the two important aspects of compiler construction. The first variety of text confines itself to a study of the theory and principles of compiler design, with only brief examples of the application of the theory. The second variety of text concentrates on the practical goal of producing an actual compiler, either for a real programming language or a pared-down version of one, with only small forays into the theory underlying the code to explain its origin and behavior. I have found both approaches lacking. To really understand the practical aspects of compiler design, one needs to have a good understanding of the theory, and to really appreciate the theory, one needs to see it in action in a real or near-real practical setting.
This text undertakes to provide the proper balance between theory and practice, and to provide enough actual implementation detail to give a real flavor for the techniques without overwhelming the reader. In this text, I provide a complete compiler for a small language written in C and developed using the different techniques studied in each chapter. In addition, detailed descriptions of coding techniques for additional language examples are given as the associated topics are studied. Finally, each chapter concludes with an extensive set of exercises, which are divided into two sections. The first contains those of the more pencil-and-paper variety involving little programming. The second contains those involving a significant amount of programming.
In writing such a text one must also take into account the different places that a compiler course occupies in different computer science curricula. In some programs, a course on automata theory is a prerequisite; in others, a course on programming languages is a prerequisite; while in yet others no prerequisites (other than data structures)are assumed. This text makes no assumptions about prerequisites beyond the usual data structures course and a familiarity with the C language, yet is arranged so that a prerequisite such as an automata theory course can be taken into account. Thus, it should be usable in a wide variety of programs.
A final problem in writing a compiler text is that instructors use many different classroom approaches to the practical application of theory. Some prefer to study the techniques using only a series of separate small examples, each targeting a specific concept. Some give an extensive compiler project, but make it more manageable with the use of Lex and Yacc as tools. Others ask their students to write all the code by hand (using, say, recursive descent for parsing) but may lighten the task by giving students the basic data structures and some sample code. This book should lend itself to all of these scenarios.
0veniew and 0rganization
In most cases each chapter is largely independent of the others, without artificially restricting the material in each. Cross-references in the text allow the reader or instructor to fill in any gaps that might arise even if a particular chapter or section is skipped.
Chapter 1 is a survey of the basic structure of a compiler and the techniques studied in later chapters. It also includes a section on porting and bootstrapping.
Chapter 2 studies the theory of finite automata and regular expressions, and then app1ies this theory to the construction of a scanner both by hand coding and using the scanner generation tool Lex.
Chapter 3 studies the theory of context-free grammars as it pertains to parsing, with particular emphasis on reso1ving ambiguity. It gives a detailed description of three common notations for such grammars, BNF, EBNF, and syntax diagrams. It also discusses the Chomsky hierarchy and the limits of the power of context-free grammars, and mentions some of the important computation-theoretic results concerning such grammars. A grammar for the sample language of the text is also provided.
Chapter 4 studies top-down parsing algorithms, in particular the methods of recursive-descent and LL(l) parsing. A recursive-descent parser for the sample language is also presented.
Chapter 5 continues the study of parsing algorithms, studying bottom-up parsing in detail, culminating in LALR(l) parsing tables and the use of the Yacc parser generator tool. A Yacc specification for the sample language is provided.
Chapter 6 is a comprehensive account of static semantic analysis, focusing on attribute grammars and syntax tree traversals. It gives extensive coverage to the construction of symbol tables and static type checking, the two primary examples of semantic analysis. A hash table implementation for a symbol table is also given and is used to implement a semantic analyzer for the sample language.
Chapter 7 discusses the common forms of runtime environments, from the fully static environment of Fortran through the many varieties of stack-based environments to the fully dynamic environments of Lisp-like languages. It also provides an implementation for a heap of dynamically allocated storage.
Chapter 8 discusses code generation both for intermediate code such as three-address code and P-code and for executable object code for a simple von Neumann architecture, for which a simulator is given. A complete code generator for the sample language is given. The chapter concludes with an introduction to code optimization techniques.
Three appendices augment the text. The first contains a detailed description of a language suitable for a class project, together with a list of partial projects that can be used as assignments. The remaining appendices give line-numbered listings of the source code for the sample compiler and the machine simulator, respective1y.
Use as a Text
This text can be used in a one-semester or two-semester introductory compiler course, either with or without the use of Lex and Yacc compiler construction tools. If an automata theory course is a prerequisite, then Sections 2.2., 2.3, and 2.4 in Chapter 2 and Sections 3.2 and 3.6 in Chapter 3 can be skipped or quickly reviewed. In a one-semester course this still makes for an extremely fast-paced course, if scanning, parsing, semantic analysis, and code generation are all to be covered.
One reasonable alternative is, after an overview of scanning, to simply provide a scanner and move quickly to parsing. (Even with standard techniques and the use of C, input routines can be subtly different for different operating systems and platforms.) Another alternative is to use Lex and Yacc to automate the construction of a scanner and a parser (I do find, however, that in doing this there is a risk that, in a first course, students may fail to understand the actual algorithms being used). If an instructor wishes to use only Lex and Yacc, then further material may be skipped: all sections of Chapter 4 except 4.4, and Section 2.5 of Chapter 2.
If an instructor wishes to concentrate on hand coding, then the sections on Lex and Yacc may be skipped (2.6, 5.5, 5.6, and 5.7). Indeed, it would be possible to skip all of Chapter 5 if bottom-up parsing is ignored.
Similar shortcuts may be taken with the later chapters, if necessary, in either a tools-based course or a hand-coding style course. For instance, not all the different styles of attribute analysis need to be studied (Section 6.2). Also, it is not essential to study in detail all the different runtime environments cataloged in Chapter 7. If the students are to take a further course that will cover code generation in detail, then Chapter 8 may be skipped.
In a two-quarter or two-semester course it should be possible to cover the entire book.
Internet Availability of Resources
All the code in Appendices B and C is available on the Web at locations pointed to from my home page (http://www.mathcs.sjsu.edu/faculty/louden/). Additional resources, such as errata lists and solutions to some of the exercises. may also be available from me. Please check my home page or contact me by e-mail at louden@cs.sjsu.edu.
Acknowledgments
My interest in compilers began in l984 with a summer course taught by Alan Demers. His insight and approach to the field have significantly influenced my own views. Indeed, the basic organization of the sample compiler in this text was suggested by that course, and the machine simulator of Appendix C is a descendant of the one he provided.
More directly, I would like to thank my colleagues Bill Giles and Sam Khuri at San Jose State for encouraging me in this project, reading and commenting on most of the text, and for using preliminary drafts in their classes. I would also like to thank the students at San Jose State University in both my own and other classes who provided useful input. Further, I would like to thank Mary T. Stone of PWS for gathering a great dea1 of information on compiler tools and for coordinating the very useful review process.
The following reviewers contributed many excellent suggestions, for which I am grateful:
Jeff Jenness Jerry Potter
Arkansas State University Kent State University
Joe Lambert Samuel A. Rebelsky
Penn State University Dartmouth College
Joan Lukas
University of Masschusetts, Boston
Of course I alone am responsible for any shortcomings of the text. I have tried to make this book as error-free as possible. Undoubtedly errors remain, and I would be happy to hear from any readers willing to point them out to me.
Finally, I would like to thank my wife Margreth for her understanding, patience, and support, and our son Andrew for encouraging me to finish this book.
K.C.L.
l INTRODUCTION
l.1 Why Compilers A Brief History
1.2 Programs Related to Compilers 4
l.3 The Translation Process 7
l.4 Major Data Structures in a Compiler l3
1.5 Other Issues in Compiler Structure 14
l.6 Bootstrapping and Porting 18
l.7 The TINY Sample Language and Compiler 22
1.8 C-Minus: A Language for a Compiler Project 26
Exercises 27 Notes and References 29
2 SCANNING 31
2.1 The Scanning Process 32
2.2 Regular Expressions 34
2.3 Finite Automata 47
2.4 From Regular Expressions to DFAs 64
2.5 Implementation of a TINY Scanner 75
2.6 Use of Lex to Generate a Scanner Automatically 81
Exercises 89
Programming Exercises 93
Notes and References 94
3 CONTEXT-FREE GRAMMARS AND PARSING 95
3.l The Parsing Process 96
3.2 Context-Free Grammars 97
3.3 Parse Trees and Abstract Syntax Trees 106
3.4 Ambiguity 114
3.5 Extended Notations: EBNF and Syntax Diagrams 123
3.6 Formal Properties of Context-Free Languages 128
3.7 Syntax of the TINY Language 133
Exercises 138 Notes and References 142
4 T0P-D0WN PARSING l43
4.1 Top-Down Parsing by Recursive-Descent l44
4.2 LL(1) Parsing 152
4.3 First and Follow Sets 168
4.4 A Recursive-Descent Parser for the TINY Language l80
4.5 Error Recovery in Top-Down Parsers l83
Exercises l89 Programming Exercises l93
Notes and References 196
5 BOTTOM-UP PARSING 197
5.1 Overview of Bottom-Up Parsing 198
5.2 Finite Automata of LR(0) Items and LR(0) Parsing 20l
5.3 SLR(1) Parsing 2l0
5.4 General LR(l) and LALR(l) Parsing 217
5.5 Yacc: An LALR(l) Parser Generator 226
5.6 Generation of a TINY Parser Using Yacc 243
5.7 Error Recovery in Bottom-Up Parsers 245
Exercises 250 Programming Exercises 254
Notes and References 256
6 SEMANTIC ANALYSIS 257
6.1 Attributes and Attribute Grammars 259
6.2 Algorithms for Attribute Computation 270
6.3 The Symbol Table 295
6.4 Data Types and Type Checking 313
6.5 A Semantic Analyzer for the TINY Language 334
Exercises 339 Programming Exercises 342
Notes and References 343
7 RUNTIME ENVIRONMENTS 345
7.l Memory Organization During Program Execution 346
7.2 Fully Static Runtime Environments 349
7.3 Stack-Based Runtime Environments 352
7.4 Dynamic Memory 373
7.5 Parameter Passing Mechanisms 381
7.6 A Runtime Environment for the TINY Language 386
Exercises 388 Programming Exercises 395
Notes and References 396
8 CODE GENERATION 397
8.1 Intermediate Code and Data Structures for Code Generation
8.2 Basic Code Generation Techniques
8.3 Code Generation of Data Structure References
8.4 Code Generation of Control Statements and Logical Expressions
8.5 Code Generation of Procedure and Function Calls
8.6 Code Generation in Commercial Compilers: Two Case Studies
8.7 TM: A Simple Target Machine
8.8 A Code Generator for the TINY Language
8.9 A Survey of Code Optimization Techniques
8.l0 Simple Optimizations for the TINY Code Generator
Exercises Programming Exercises
Notes and References
Appendix A C0MPILER PROJECT
A.l Lexical Conventions of C-
A.2 Syntax and Semantics of C-
A.3 Sample Programs in C-
A.4 A TINY Machine Runtime Environment for the C-- Language
A.5 Programming Projects Using C-- and TM
Appendix B: TINY COMPILER LISTING
Appendix C: TINY MACHINE SHMULATOR LISTING Bibliography 558
Index 562
