Compilers : Principles, Techniques, and Tools

by Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D.

• ISBN13: 9780201100884
• ISBN10: 0201100886
• Format: Hardcover
• Copyright: 1986-01-01
• Publisher: Addison Wesley

Summary

This book provides the foundation for understanding the theory and pracitce of compilers. Revised and updated, it reflects the current state of compilation. Every chapter has been completely revised to reflect developments in software engineering, programming languages, and computer architecture that have occurred since 1986, when the last edition published.& The authors, recognizing that few readers will ever go on to construct a compiler, retain their focus on the broader set of problems faced in software design and software development. Computer scientists, developers, &and aspiring students that want to learn how to build, maintain, and execute a compiler for a major programming language.

Table of Contents

Chapter 1 Introduction to Compiling	1	(24)
1.1 Compilers	1	(3)
1.2 Analysis of the source program	4	(6)
1.3 The phases of a compiler	10	(6)
1.4 Cousins of the compiler	16	(4)
1.5 The grouping of phases	20	(2)
1.6 Compiler-construction tools	22	(1)
Bibliographic notes	23	(2)
Chapter 2 A Simple One-Pass Compiler	25	(58)
2.1 Overview	25	(1)
2.2 Syntax definition	26	(7)
2.3 Syntax-directed translation	33	(7)
2.4 Parsing	40	(8)
2.5 A translator for simple expressions	48	(6)
2.6 Lexical analysis	54	(6)
2.7 Incorporating a symbol table	60	(2)
2.8 Abstract stack machines	62	(7)
2.9 Putting the techniques together	69	(9)
Exercises	78	(3)
Bibliographic notes	81	(2)
Chapter 3 Lexical Analysis	83	(76)
3.1 The role of the lexical analyzer	84	(4)
3.2 Input buffering	88	(4)
3.3 Specification of tokens	92	(6)
3.4 Recognition of tokens	98	(7)
3.5 A language for specifying lexical analyzers	105	(8)
3.6 Finite automata	113	(8)
3.7 From a regular expression to an NFA	121	(7)
3.8 Design of a lexical analyzer generator	128	(6)
3.9 Optimization of DFA-based pattern matchers	134	(12)
Exercises	146	(11)
Bibliographic notes	157	(2)
Chapter 4 Syntax Analysis	159	(120)
4.1 The role of the parser	160	(5)
4.2 Context-free grammars	165	(7)
4.3 Writing a grammar	172	(9)
4.4 Top-down parsing	181	(14)
4.5 Bottom-up parsing	195	(8)
4.6 Operator-precedence parsing	203	(12)
4.7 LR parsers	215	(32)
4.8 Using ambiguous grammars	247	(10)
4.9 Parser generators	257	(10)
Exercises	267	(10)
Bibliographic notes	277	(2)
Chapter 5 Syntax-Directed Translation	279	(64)
5.1 Syntax-directed definitions	280	(7)
5.2 Construction of syntax trees	287	(6)
5.3 Bottom-up evaluation of S-attributed definitions	293	(3)
5.4 L-attributed definitions	296	(6)
5.5 Top-down translation	302	(6)
5.6 Bottom-up evaluation of inherited attributes	308	(8)
5.7 Recursive evaluators	316	(4)
5.8 Space for attribute values at compile time	320	(3)
5.9 Assigning space at compiler-construction time	323	(6)
5.10 Analysis of syntax-directed definitions	329	(7)
Exercises	336	(4)
Bibliographic notes	340	(3)
Chapter 6 Type Checking	343	(46)
6.1 Type systems	344	(4)
6.2 Specification of a simple type checker	348	(4)
6.3 Equivalence of type expressions	352	(7)
6.4 Type conversions	359	(2)
6.5 Overloading of functions and operators	361	(3)
6.6 Polymorphic functions	364	(12)
6.7 An algorithm for unification	376	(5)
Exercises	381	(5)
Bibliographic notes	386	(3)
Chapter 7 Run-Time Environments	389	(74)
7.1 Source language issues	389	(7)
7.2 Storage organization	396	(5)
7.3 Storage-allocation strategies	401	(10)
7.4 Access to nonlocal names	411	(13)
7.5 Parameter passing	424	(5)
7.6 Symbol tables	429	(11)
7.7 Language facilities for dynamic storage allocation	440	(2)
7.8 Dynamic storage allocation techniques	442	(4)
7.9 Storage allocation in Fortran	446	(9)
Exercises	455	(6)
Bibliographic notes	461	(2)
Chapter 8 Intermediate Code Generation	463	(50)
8.1 Intermediate languages	464	(9)
8.2 Declarations	473	(5)
8.3 Assignment statements	478	(10)
8.4 Boolean expressions	488	(9)
8.5 Case statements	497	(3)
8.6 Backpatching	500	(6)
8.7 Procedure calls	506	(2)
Exercises	508	(3)
Bibliographic notes	511	(2)
Chapter 9 Code Generation	513	(72)
9.1 Issues in the design of a code generator	514	(5)
9.2 The target machine	519	(3)
9.3 Run-time storage management	522	(6)
9.4 Basic blocks and flow graphs	528	(6)
9.5 Next-use information	534	(1)
9.6 A simple code generator	535	(6)
9.7 Register allocation and assignment	541	(5)
9.8 The dag representation of basic blocks	546	(8)
9.9 Peephole optimization	554	(3)
9.10 Generating code from dags	557	(10)
9.11 Dynamic programming code-generation algorithm	567	(5)
9.12 Code-generator generators	572	(8)
Exercises	580	(3)
Bibliographic notes	583	(2)
Chapter 10 Code Optimization	585	(138)
10.1 Introduction	586	(6)
10.2 The principal sources of optimization	592	(6)
10.3 Optimization of basic blocks	598	(4)
10.4 Loops in flow graphs	602	(6)
10.5 Introduction to global data-flow analysis	608	(16)
10.6 Iterative solution of data-flow equations	624	(9)
10.7 Code-improving transformations	633	(15)
10.8 Dealing with aliases	648	(12)
10.9 Data-flow analysis of structured flow graphs	660	(11)
10.10 Efficient data-flow algorithms	671	(9)
10.11 A tool for data-flow analysis	680	(14)
10.12 Estimation of types	694	(9)
10.13 Symbolic debugging of optimized code	703	(8)
Exercises	711	(7)
Bibliographic notes	718	(5)
Chapter 11 Want to Write a Compiler?	723	(10)
11.1 Planning a compiler	723	(2)
11.2 Approaches to compiler development	725	(4)
11.3 The compiler-development environment	729	(2)
11.4 Testing and maintenance	731	(2)
Chapter 12 A Look at Some Compilers	733	(12)
12.1 EQN, a preprocessor for typesetting mathematics	733	(1)
12.2 Compilers for Pascal	734	(1)
12.3 The C compilers	735	(2)
12.4 The Fortran H compilers	737	(3)
12.5 The Bliss/11 compiler	740	(2)
12.6 Modula-2 optimizing compiler	742	(3)
Appendix A Compiler Project	745	(7)
A.1 Introduction	745	(1)
A.2 A Pascal subset	745	(1)
A.3 Program structure	745	(3)
A.4 Lexical conventions	748	(1)
A.5 Suggested exercises	749	(1)
A.6 Evolution of the interpreter	750	(1)
A.7 Extensions	751	(1)
Bibliography	752	(28)
Index	780