本书全面、深入地探讨了编译器设计方面的重要主题，包括词法分析、语法分析、语法制导定义和语法制导翻译、运行时刻环境、目标代码生成、代码优化技术、并行性检测以及过程间分析技术，并在相关章节中给出大量实例。

本书是编译领域无可替代的经典著作，被广大计算机专业人士誉为“龙书”。本书上一版自1986年出版以来，被世界各地的著名高等院校和研究机构（包括美国哥伦比亚大学、斯坦福大学、哈佛大学、普林斯顿大学、贝尔实验室）作为本科生和研究生的编译原理课程的教材。该书对我国高等计算机教育领域也产生了重大影响。
第2版对每一章都进行了全面的修订，以反映自上一版出版二十多年来软件工程、程序设计语言和计算机体系结构方面的发展对编译技术的影响。
本书全面介绍了编译器的设计，并强调编译技术在软件设计和开发中的广泛应用，每章中都包含大量的习题和丰富的参考文献。本书适合作为高等院校计算机专业本科生和研究生的编译原理与技术课程的教材，也可供广大计算机技术人员参考。
作者简介
Alfred V．Aho
美国哥伦比亚大学教授，美国国家工程院院士，ACM和IEEE会士，曾获得IEEE的冯·诺伊曼奖。著有多部算法、数据结构、编译器、数据库系统及计算机科学基础方面的著作。
Monica S．Lam
斯坦福大学计算机科学系教授，曾任Tensilica的首席科学家，也是Moka5的首任CEO。曾经主持SUIF项目，该项目产生了最流行的研究用编译器之一。
Ravi Sethi
Avaya实验室总裁，曾任贝尔实验室高级副总裁和Lucent Technologies通信软件的CTO。他曾在宾夕法尼亚州立大学、亚利桑那州立大学和普林斯顿大学任教，是ACM会士。
Jeffrey D．Ullman
斯坦福大学计算机科学系教授和Gradiance CEO。他的研究兴趣包括数据库理论、数据库集成、数据挖掘和利用信息基础设施教学等。他是美国国家工程院院士、IEEE会士，获得过ACM的Karlstrom杰出教育奖和Knuth奖。

计算机\编译

本书是编译领域无可替代的经典著作，被广大计算机专业人士誉为“龙书”。本书上一版自1986年出版以来，被世界各地的著名高等院校和研究机构（包括美国哥伦比亚大学、斯坦福大学、哈佛大学、普林斯顿大学、贝尔实验室）作为本科生和研究生的编译原理课程的教材。该书对我国高等计算机教育领域也产生了重大影响。　　第2版对每一章都进行了全面的修订，以反映自上一版出版20多年来软件工程。程序设计语言和计算机体系结构方面的发展对编译技术的影响。本书全面介绍了编译器的设计，并强调编译技术在软件设计和开发中的广泛应用。每章中都包含大量的习题和丰富的参考文献。　　本书适合作为高等院校计算机专业本科生和研究生的编译原理与技术课程的教材，也可供广大计算机技术人员参考。

（美）Alfred V. Aho; Monica S. Lam; Ravi Sethi; Jeffrey D. Ullman 著：Alfred V．Aho，美国歌伦比亚大学教授，美国国家工程院院士，ACM和IEEE会士，曾获得IEEE的冯·诺伊曼奖。著有多部算法、数据结构、编译器、数据库系统及计算机科学基础方面的著作。 Monica S．Lam，斯坦福大学计算机科学系教授，曾任Tensilica的首席科学家，也是Moka5的首任CEO。曾经主持SUIF项目，该项目产生了最流行的研究用编译器之一。 Ravi Sethi，Avaya实验室总裁，曾任贝尔实验室高级副总裁和Lucent Technologies通信软件的CTO。他曾在宾夕法尼亚州立大学，亚利桑那州立大学和普林斯顿大学任教，是ACM会士。 Jefirey D．Ullman斯坦福大学计算机科学系教授和Gradiance CEO。他的研究兴趣包括数据库理论、数据库集成、数据挖掘和利用信息基础设施教学等。他是美国国家工程学院院士、IEEE会士，获得过ACM的Karlstrom杰出教育奖和Knuth奖。

TableofContents
1Introduction1
1.1 Language Pro cessors . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Exercises for Section 1.1 . . . . . . . . . . . . . . . . . . . 3
1.2 The Structure of a Compiler . . . . . . . . . . . . . . . . . . . . . 4
1.2.1 Lexical Analysis . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.2 Syntax Analysis . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.3 Semantic Analysis . . . . . . . . . . . . . . . . . . . . . . 8
1.2.4 Intermediate Co de Generation . . . . . . . . . . . . . . . 9
1.2.5 Co de Optimization . . . . . . . . . . . . . . . . . . . . . . 10
1.2.6 Co de Generation . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.7 Symb ol-Table Management . . . . . . . . . . . . . . . . . 11
1.2.8 The Grouping of Phases into Passes . . . . . . . . . . . . 11
1.2.9 Compiler-Construction To ols . . . . . . . . . . . . . . . . 12
1.3 The Evolution of Programming Languages . . . . . . . . . . . . . 12
1.3.1 The Move to Higher-level Languages . . . . . . . . . . . . 13
1.3.2 Impacts on Compilers . . . . . . . . . . . . . . . . . . . . 14
1.3.3 Exercises for Section 1.3 . . . . . . . . . . . . . . . . . . . 14
1.4 The Science of Building a Compiler . . . . . . . . . . . . . . . . . 15
1.4.1 Mo deling in Compiler Design and Implementation . . . . 15
1.4.2 The Science of Co de Optimization . . . . . . . . . . . . . 15
1.5 Applications of Compiler Technology . . . . . . . . . . . . . . . . 17
1.5.1 Implementation of High-Level Programming Languages . 17
1.5.2 Optimizations for Computer Architectures . . . . . . . . . 19
1.5.3 Design of New Computer Architectures . . . . . . . . . . 21
1.5.4 Program Translations . . . . . . . . . . . . . . . . . . . . 22
1.5.5 Software Pro ductivity To ols . . . . . . . . . . . . . . . . . 23
1.6 Programming Language Basics . . . . . . . . . . . . . . . . . . . 25
1.6.1 The Static/Dynamic Distinction . . . . . . . . . . . . . . 25
1.6.2 Environments and States . . . . . . . . . . . . . . . . . . 26
1.6.3 Static Scop e and Blo ck Structure . . . . . . . . . . . . . . 28
1.6.4 Explicit Access Control . . . . . . . . . . . . . . . . . . . 31
1.6.5 Dynamic Scop e . . . . . . . . . . . . . . . . . . . . . . . . 31
1.6.6 Parameter Passing Mechanisms . . . . . . . . . . . . . . . 33
1.6.7 Aliasing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
1.6.8 Exercises for Section 1.6 . . . . . . . . . . . . . . . . . . . 35
1.7 Summary of Chapter 1 . . . . . . . . . . . . . . . . . . . . . . . . 36
1.8 References for Chapter 1 . . . . . . . . . . . . . . . . . . .38
2ASimpleSyntax-DirectedTranslator39
2.1 Intro duction . . . . . . . . . . . . . . . . . . . . . . 40
2.2 Syntax De nition . . . . . . . . . . . . . . . . . . . . . . 42
2.2.1 De nition of Grammars . . . . . . . . . . . . . . . . . . . 42
2.2.2 Derivations . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.2.3 Parse Trees . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.2.4 Ambiguity. . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.2.5 Asso ciativity of Op erators . . . . . . . . . . . . . . . . . . 48
2.2.6 Precedence of Op erators . . . . . . . . . . . . . . . . . . . 48
2.2.7 Exercises for Section 2.2 . . . . . . . . . . . . . . . . . . . 51
2.3 Syntax-Directed Translation . . . . . . . . . . . . . . . 52
2.3.1 Post x Notation . . . . . . . . . . . . . . . . . . . . . . . 53
2.3.2 Synthesized Attributes . . . . . . . . . . . . . . . . . . . . 54
2.3.3 Simple Syntax-Directed De nitions . . . . . . . . . . . . . 56
2.3.4 Tree Traversals . . . . . . . . . . . . . . . . . . . . . . . . 56
2.3.5 Translation Schemes . . . . . . . . . . . . . . . . . . . . . 57
2.3.6 Exercises for Section 2.3 . . . . . . . . . . . . . . . . . . . 60
2.4 Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . .60
2.4.1 Top-Down Parsing . . . . . . . . . . . . . . . . . . . . . . 61
2.4.2 Predictive Parsing . . . . . . . . . . . . . . . . . . . . . . 64
2.4.3 When to Use -Pro ductions . . . . . . . . . . . . . . . . . 65
2.4.4 Designing a Predictive Parser . . . . . . . . . . . . . . . . 66
2.4.5 Left Recursion . . . . . . . . . . . . . . . . . . . . . . . . 67
2.4.6 Exercises for Section 2.4 . . . . . . . . . . . . . . . . . . . 68
2.5 A Translator for Simple Expressions . . . . . . . . . . . . . . . . 68
2.5.1 Abstract and Concrete Syntax . . . . . . . . . . . . . . . 69
2.5.2 Adapting the Translation Scheme . . . . . . . . . . . . . . 70
2.5.3 Pro cedures for the Nonterminals . . . . . . . . . . . . . . 72
2.5.4 Simplifying the Translator . . . . . . . . . . . . . . . . . . 73
2.5.5 The Complete Program . . . . . . . . . . . . . . . . . . . 74
2.6 Lexical Analysis . . . . . . . . . . . . . . . . . . . . . .76
2.6.1 Removal of White Space and Comments . . . . . . . . . . 77
2.6.2 Reading Ahead . . . . . . . . . . . . . . . . . . . . . . . . 78
2.6.3 Constants . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
2.6.4 Recognizing Keywords and Identi ers . . . . . . . . . . . 79
2.6.5 A Lexical Analyzer . . . . . . . . . . . . . . . . . . . . . . 81
2.6.6 Exercises for Section 2.6 . . . . . . . . . . . . . . . . . . . 84
2.7 Symbol Tables . . . . . . . . . . . . . . . . . . . . . .85
2.7.1 Symbol Table Per Scop e . . . . . . . . . . . . . . . . . . . 86
2.7.2 The Use of Symbol Tables . . . . . . . . . . . . . . . . . . 89
2.8 Intermediate Co de Generation . . . . . . . . . . . . . . . . . . . 91
2.8.1 Two Kinds of Intermediate Representations . . . . . . . . 91
2.8.2 Construction of Syntax Trees . . . . . . . . . . . . . . . . 92
2.8.3 Static Checking . . . . . . . . . . . . . . . . . . . . . . . . 97
2.8.4 Three-Address Co de . . . . . . . . . . . . . . . . . . . . . 99
2.8.5 Exercises for Section 2.8 . . . . . . . . . . . . . . . . . . . 105
2.9 Summary of Chapter 2 . . . . . . . . . . . . . . . . . . .105
3LexicalAnalysis109
3.1 The Role of the Lexical Analyzer . . . . . . . . . . . . . . . . .109
3.1.1 Lexical Analysis Versus Parsing . . . . . . . . . . . . . . . 110
3.1.2 Tokens, Patterns, and Lexemes . . . . . . . . . . . . . . . 111
3.1.3 Attributes for Tokens . . . . . . . . . . . . . . . . . . . . 112
3.1.4 Lexical Errors . . . . . . . . . . . . . . . . . . . . . . . . . 113
3.1.5 Exercises for Section 3.1 . . . . . . . . . . . . . . . . . . . 114
3.2 Input Bu ering . . . . . . . . . . . . . . . . . . . . . . . .115
3.2.1 Bu er Pairs . . . . . . . . . . . . . . . . . . . . . . . . . . 115
3.2.2 Sentinels . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
3.3 Sp eci cation of Tokens . . . . . . . . . . . . . . . . . . 116
3.3.1 Strings and Languages . . . . . . . . . . . . . . . . . . . . 117
3.3.2 Op erations on Languages . . . . . . . . . . . . . . . . . . 119
3.3.3 Regular Expressions . . . . . . . . . . . . . . . . . . . . . 120
3.3.4 Regular De nitions . . . . . . . . . . . . . . . . . . . . . . 123
3.3.5 Extensions of Regular Expressions . . . . . . . . . . . . . 124
3.3.6 Exercises for Section 3.3 . . . . . . . . . . . . . . . . . . . 125
3.4 Recognition of Tokens . . . . . . . . . . . . . . . . . . 128
3.4.1 Transition Diagrams . . . . . . . . . . . . . . . . . . . . . 130
3.4.2 Recognition of Reserved Words and Identi ers . . . . . . 132
3.4.3 Completion of the Running Example . . . . . . . . . . . . 133
3.4.4 Architecture of a Transition-Diagram-Based Lexical An-alyzer . . . . . . . . . . .. . . . 134
3.4.5 Exercises for Section 3.4 . . . . . . . . . . . . . . . . . . . 136
3.5 The Lexical-Analyzer Generator Lex. . . . . . . . . . . . . . . . 140
3.5.1 Use of Lex. . . . . . . . . . . . . . . . . . . . . . . . . . . 140
3.5.2 Structure of LexPrograms . . . . . . . . . . . . . . . . . 141
3.5.3 Con ict Resolution in Lex. . . . . . . . . . . . . . . . . . 144
3.5.4 The Lo okahead Op erator . . . . . . . . . . . . . . . . . . 144
3.5.5 Exercises for Section 3.5 . . . . . . . . . . . . . . . . . . . 146
3.6 Finite Automata . . . . . . . . . . . . . . . . . . . . . . . . 147
3.6.1 Nondeterministic Finite Automata . . . . . . . . . . . . . 147
3.6.2 Transition Tables . . . . . . . . . . . . . . . . . . . . . . . 148
3.6.3 Acceptance of Input Strings by Automata . . . . . . . . . 149
3.6.4 Deterministic Finite Automata . . . . . . . . . . . . . . . 149
3.6.5 Exercises for Section 3.6 . . . . . . . . . . . . . . . . . . . 151
3.7 From Regular Expressions to Automata . . . . . . . . . . . . . . 152
3.7.1 Conversion of an NFA toa DFA . . . . . . . . . . . . . . 152
3.7.2 Simulation of an NFA . . . . . . . . . . . . . . . . . . . . 156
3.7.3 E ciency of NFA Simulation . . . . . . . . . . . . . . . . 157
3.7.4 Construction of an NFA from a Regular Expression . . . 159
3.7.5 E ciency of String-Pro cessing Algorithms . . . . . . . . . 163
3.7.6 Exercises for Section 3.7 . . . . . . . . . . . . . . . . . . . 166
3.8 Design of a Lexical-Analyzer Generator . . . . . . . . . . . . . . 166
3.8.1 The Structure of the Generated Analyzer . . . . . . . . . 167
3.8.2 Pattern Matching Based on NFA's . . . . . . . . . . . . . 168
3.8.3 DFA's for Lexical Analyzers . . . . . . . . . . . . . . . . . 170
3.8.4 Implementing the Lo okahead Op erator . . . . . . . . . . . 171
3.8.5 Exercises for Section 3.8 . . . . . . . . . . . . . . . . . . . 172
3.9 Optimization of DFA-Based Pattern Matchers . . . . . . . . . . . 173
3.9.1 Imp ortant States of an NFA. . . . . . . . . . . . . . . . . 173
3.9.2 Functions Computed From the Syntax Tree . . . . . . . . 175
3.9.3 Computing nul lable ,　rstpos, and lastpos . . . . . . . . . . 176
3.9.4 Computing fol lowpos . . . . . . . . . . . . . . . . . . . . . 177
3.9.5 Converting a Regular Expression Directly to a DFA . . . 179
3.9.6 Minimizing the Numb er of States of a DFA . . . . . . . . 180
3.9.7 State Minimization in Lexical Analyzers . . . . . . . . . . 184
3.9.8 Trading Time for Space in DFA Simulation . . . . . . . . 185
3.9.9 Exercises for Section 3.9 . . . . . . . . . . . . . . . . . . . 186
3.10 Summary of Chapter 3 . . . . . . . . . . . . . . . . 187
3.11 References for Chapter 3 . . . . . . . . . . . . . . . 189
4SyntaxAnalysis191
4.1 Intro duction . . . . . . . . . . . . . . . . . . . . . 192
4.1.1 The Role of the Parser . . . . . . . . . . . . . . . . . . . . 192
4.1.2 Representative Grammars . . . . . . . . . . . . . . . . . . 193
4.1.3 Syntax Error Handling . . . . . . . . . . . . . . . . . . . . 194
4.1.4 Error-Recovery Strategies . . . . . . . . . . . . . . . . . . 195
4.2 Context-Free Grammars . . . . . . . . . . . . . . . . . . . . . . . 197
4.2.1 The Formal De nition of a Context-Free Grammar . . . . 197
4.2.2 Notational Conventions . . . . . . . . . . . . . . . . . . . 198
4.2.3 Derivations . . . . . . . . . . . . . . . . . . . . . . . . . . 199
4.2.4 Parse Trees and Derivations . . . . . . . . . . . . . . . . . 201
4.2.5 Ambiguity. . . . . . . . . . . . . . . . . . . . . . . . . . . 203
4.2.6 Verifying the Language Generated by a Grammar . . . . 204
4.2.7 Context-Free Grammars Versus Regular Expressions . . . 205
4.2.8 Exercises for Section 4.2 . . . . . . . . . . . . . . . . . . . 206
4.3 Writing a Grammar . . . . . . . . . . . . . . . . . . . . . . . . . 209
4.3.1 Lexical Versus Syntactic Analysis . . . . . . . . . . . . . . 209
4.3.2 Eliminating Ambiguity. . . . . . . . . . . . . . . . . . . . 210
4.3.3 Elimination of Left Recursion . . . . . . . . . . . . . . . . 212
4.3.4 Left Factoring . . . . . . . . . . . . . . . . . . . . . . . . 214
4.3.5 Non-Context-Free Language Constructs . . . . . . . . . . 215
4.3.6 Exercises for Section 4.3 . . . . . . . . . . . . . . . . . . . 216
4.4 Top-Down Parsing . . . . . . . . . . . . . . . . . . . . 217
4.4.1 Recursive-Descent Parsing . . . . . . . . . . . . . . . . . . 219
4.4.2 FIRST and FOLLOW . . . . . . . . . . . . . . . . . . . . 220
4.4.3 LL(1) Grammars . . . . . . . . . . . . . . . . . . . . . . . 222
4.4.4 Nonrecursive Predictive Parsing . . . . . . . . . . . . . . . 226
4.4.5 Error Recovery in Predictive Parsing . . . . . . . . . . . . 228
4.4.6 Exercises for Section 4.4 . . . . . . . . . . . . . . . . . . . 231
4.5 Bottom-Up Parsing . . . . . . . . . . . . . . . . . . . . . 233
4.5.1 Reductions . . . . . . . . . . . . . . . . . . . . . . . . . . 234
4.5.2 Handle Pruning . . . . . . . . . . . . . . . . . . . . . . . . 235
4.5.3 Shift-Reduce Parsing . . . . . . . . . . . . . . . . . . . . . 236
4.5.4 Con icts During Shift-Reduce Parsing . . . . . . . . . . . 238
4.5.5 Exercises for Section 4.5 . . . . . . . . . . . . . . . . . . . 240
4.6 Intro duction to LR Parsing: Simple LR . . . . . . . . . . . . . . 241
4.6.1 Why LR Parsers . . . . . . . . . . . . . . . . . . . . . . . 241
4.6.2 Items and the LR(0) Automaton . . . . . . . . . . . . . . 242
4.6.3 The LR-Parsing Algorithm . . . . . . . . . . . . . . . . . 248
4.6.4 Constructing SLR-Parsing Tables . . . . . . . . . . . . . . 252
4.6.5 Viable Pre xes . . . . . . . . . . . . . . . . . . . . . . . . 256
4.6.6 Exercises for Section 4.6 . . . . . . . . . . . . . . . . . . . 257
4.7 More Powerful LR Parsers . . . . . . . . . . . . . . . 259
4.7.1 Canonical LR(1) Items . . . . . . . . . . . . . . . . . . . . 260
4.7.2 Constructing LR(1) Sets of Items . . . . . . . . . . . . . . 261
4.7.3 Canonical LR(1) Parsing Tables . . . . . . . . . . . . . . 265
4.7.4 Constructing LALR Parsing Tables . . . . . . . . . . . . . 266
4.7.5 E cient Construction of LALR Parsing Tables . . . . . . 270
4.7.6 Compaction of LR Parsing Tables . . . . . . . . . . . . . 275
4.7.7 Exercises for Section 4.7 . . . . . . . . . . . . . . . . . . . 277
4.8 Using Ambiguous Grammars . . . . . . . . . . . . . . . . . . . . 278
4.8.1 Precedence and Asso ciativity to Resolve Con icts . . . . 279
4.8.2 The \Dangling-Else" Ambiguity . . . . . . . . . . . . . . 281
4.8.3 Error Recovery in LR Parsing . . . . . . . . . . . . . . . . 283
4.8.4 Exercises for Section 4.8 . . . . . . . . . . . . . . . . . . . 285
4.9 Parser Generators . . . . . . . . . . . . . . . . . . . . . . 287
4.9.1 The Parser Generator Yacc. . . . . . . . . . . . . . . . . 287
4.9.2 Using Yaccwith Ambiguous Grammars . . . . . . . . . . 291
4.9.3 Creating YaccLexical Analyzers with Lex. . . . . . . . . 294
4.9.4 Error Recovery in Yacc. . . . . . . . . . . . . . . . . . . 295
4.9.5 Exercises for Section 4.9 . . . . . . . . . . . . . . . . . . . 297
4.10 Summary of Chapter 4 . . . . . . . . . . . . . . . . . . . .297
4.11 References for Chapter 4 . . . . . . . . . . . . . . . . . . . . 300
5Syntax-DirectedTranslation303
5.1 Syntax-Directed De nitions . . . . . . . . . . . . . . .304
5.1.1 Inherited and Synthesized Attributes . . . . . . . . . . . . 304
5.1.2 Evaluating an SDD at the No des of a Parse Tree . . . . . 306
5.1.3 Exercises for Section 5.1 . . . . . . . . . . . . . . . . . . . 309
5.2 Evaluation Orders for SDD's . . . . . . . . . . . . . . . . . . . . 310
5.2.1 Dep endency Graphs . . . . . . . . . . . . . . . . . . . . . 310
5.2.2 Ordering the Evaluation of Attributes . . . . . . . . . . . 312
5.2.3 S-Attributed De nitions . . . . . . . . . . . . . . . . . . . 312
5.2.4 L-Attributed De nitions . . . . . . . . . . . . . . . . . . . 313
5.2.5 Semantic Rules with Controlled Side E ects . . . . . . . . 314
5.2.6 Exercises for Section 5.2 . . . . . . . . . . . . . . . . . . . 317
5.3 Applications of Syntax-Directed Translation . . . . . . . . . . . . 318
5.3.1 Construction of Syntax Trees . . . . . . . . . . . . . . . . 318
5.3.2 The Structure of a Typ e . . . . . . . . . . . . . . . . . . . 321
5.3.3 Exercises for Section 5.3 . . . . . . . . . . . . . . . . . . . 323
5.4 Syntax-Directed Translation Schemes . . . . . . . . . . . . . . . . 324
5.4.1 Post x Translation Schemes . . . . . . . . . . . . . . . . . 324
5.4.2 Parser-Stack Implementation of Post x SDT's . . . . . . 325
5.4.3 SDT's With Actions Inside Pro ductions . . . . . . . . . . 327
5.4.4 Eliminating Left Recursion From SDT's . . . . . . . . . . 328
5.4.5 SDT's for L-Attributed De nitions . . . . . . . . . . . . . 331
5.4.6 Exercises for Section 5.4 . . . . . . . . . . . . . . . . . . . 336
5.5 Implementing L-Attributed SDD's . . . . . . . . . . . . . . . . . 337
5.5.1 Translation During Recursive-Descent Parsing . . . . . . 338
5.5.2 On-The-Fly Co de Generation . . . . . . . . . . . . . . . . 340
5.5.3 L-Attributed SDD's and LL Parsing . . . . . . . . . . . . 343
5.5.4 Bottom-Up Parsing of L-Attributed SDD's . . . . . . . . 348
5.5.5 Exercises for Section 5.5 . . . . . . . . . . . . . . . . . . . 352
5.6 Summary of Chapter 5 . . . . . . . . . . . . . . . . . . . .353
5.7 References for Chapter 5 . . . . . . . . . . . . . . . .354
6Intermediate-CodeGeneration357
6.1 Variants of Syntax Trees . . . . . . . . . . . . . . . . . 358
6.1.1 Directed Acyclic Graphs for Expressions . . . . . . . . . . 359
6.1.2 The Value-Numb er Metho d for Constructing DAG's . . . 360
6.1.3 Exercises for Section 6.1 . . . . . . . . . . . . . . . . . . . 362
6.2 Three-Address Co de . . . . . . . . . . . . . . . . . . . . 363
6.2.1 Addresses and Instructions . . . . . . . . . . . . . . . . . 364
6.2.2 Quadruples . . . . . . . . . . . . . . . . . . . . . . . . . . 366
6.2.3 Triples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367
6.2.4 Static Single-Assignment Form . . . . . . . . . . . . . . . 369
6.2.5 Exercises for Section 6.2 . . . . . . . . . . . . . . . . . . . 370
6.3 Typ es and Declarations . . . . . . . . . . . . . . . . .370
6.3.1 Typ e Expressions . . . . . . . . . . . . . . . . . . . . . . . 371
6.3.2 Typ e Equivalence . . . . . . . . . . . . . . . . . . . . . . . 372
6.3.3 Declarations . . . . . . . . . . . . . . . . . . . . . . . . . . 373
6.3.4 Storage Layout for Lo cal Names . . . . . . . . . . . . . . 373
6.3.5 Sequences of Declarations . . . . . . . . . . . . . . . . . . 376
6.3.6 Fields in Records and Classes . . . . . . . . . . . . . . . . 376
6.3.7 Exercises for Section 6.3 . . . . . . . . . . . . . . . . . . . 378
6.4 Translation of Expressions . . . . . . . . . . . . . . . . .378
6.4.1 Op erations Within Expressions . . . . . . . . . . . . . . . 378
6.4.2 Incremental Translation . . . . . . . . . . . . . . . . . . . 380
6.4.3 Addressing Array Elements . . . . . . . . . . . . . . . . . 381
6.4.4 Translation of Array References . . . . . . . . . . . . . . . 383
6.4.5 Exercises for Section 6.4 . . . . . . . . . . . . . . . . . . . 384
6.5 Typ e Checking . . . . . . . . . . . . . . . . . . . . . .386
6.5.1 Rules for Typ e Checking . . . . . . . . . . . . . . . . . . . 387
6.5.2 Typ e Conversions . . . . . . . . . . . . . . . . . . . . . . 388
6.5.3 Overloading of Functions and Op erators . . . . . . . . . . 390
6.5.4 Typ e Inference and Polymorphic Functions . . . . . . . . 391
6.5.5 An Algorithm for Uni cation . . . . . . . . . . . . . . . . 395
6.5.6 Exercises for Section 6.5 . . . . . . . . . . . . . . . . . . . 398
6.6 Control Flow . . . . . . . . . . . . . . . . . . . . . .399
6.6.1 Bo olean Expressions . . . . . . . . . . . . . . . . . . . . . 399
6.6.2 Short-Circuit Co de . . . . . . . . . . . . . . . . . . . . . . 400
6.6.3 Flow-of-Control Statements . . . . . . . . . . . . . . . . . 401
6.6.4 Control-Flow Translation of Bo olean Expressions . . . . . 403
6.6.5 Avoiding Redundant Gotos . . . . . . . . . . . . . . . . . 405
6.6.6 Bo olean Values and Jumping Co de . . . . . . . . . . . . . 408
6.6.7 Exercises for Section 6.6 . . . . . . . . . . . . . . . . . . . 408
6.7 Backpatching . . . . . . . . . . . . . . . . . . . . . 410
6.7.1 One-Pass Co de Generation Using Backpatching . . . . . . 410
6.7.2 Backpatching for Bo olean Expressions . . . . . . . . . . . 411
6.7.3 Flow-of-Control Statements . . . . . . . . . . . . . . . . . 413
6.7.4 Break-, Continue-, and Goto-Statements . . . . . . . . . . 416
6.7.5 Exercises for Section 6.7 . . . . . . . . . . . . . . . . . . . 417
6.8 Switch-Statements . . . . . . . . . . . . . . . . . . 418
6.8.1 Translation of Switch-Statements . . . . . . . . . . . . . . 419
6.8.2 Syntax-Directed Translation of Switch-Statements . . . . 420
6.8.3 Exercises for Section 6.8 . . . . . . . . . . . . . . . . . . . 421
6.9 Intermediate Co de for Pro cedures . . . . . . . . . . . .422
6.10 Summary of Chapter 6 . . . . . . . . . . . . . . . . . 424
6.11 References for Chapter 6 . . . . . . . . . . . . . . 425
7Run-TimeEnvironments427
7.1 Storage Organization . . . . . . . . . . . . . . . . .427
7.1.1 Static Versus Dynamic Storage Allo cation . . . . . . . . . 429
7.2 Stack Allo cation of Space . . . . . . . . . . . . . . . . .430
7.2.1 Activation Trees . . . . . . . . . . . . . . . . . . . . . . . 430
7.2.2 Activation Records . . . . . . . . . . . . . . . . . . . . . . 433
7.2.3 Calling Sequences . . . . . . . . . . . . . . . . . . . . . . 436
7.2.4 Variable-Length Data on the Stack . . . . . . . . . . . . . 438
7.2.5 Exercises for Section 7.2 . . . . . . . . . . . . . . . . . . . 440
7.3 Access to Nonlo cal Data on the Stack . . . . . . . . . . . . . . . 441
7.3.1 Data Access Without Nested Pro cedures . . . . . . . . . . 442
7.3.2 Issues With Nested Pro cedures . . . . . . . . . . . . . . . 442
7.3.3 A Language With Nested Pro cedure Declarations . . . . . 443
7.3.4 Nesting Depth . . . . . . . . . . . . . . . . . . . . . . . . 443
7.3.5 Access Links . . . . . . . . . . . . . . . . . . . . . . . . . 445
7.3.6 Manipulating Access Links . . . . . . . . . . . . . . . . . 447
7.3.7 Access Links for Pro cedure Parameters . . . . . . . . . . 448
7.3.8 Displays . . . . . . . . . . . . . . . . . . . . . . . . . . . . 449
7.3.9 Exercises for Section 7.3 . . . . . . . . . . . . . . . . . . . 451
7.4 Heap Management . . . . . . . . . . . . . . . . . . . . . . . . . . 452
7.4.1 The Memory Manager . . . . . . . . . . . . . . . . . . . . 453
7.4.2 The Memory Hierarchy of a Computer . . . . . . . . . . . 454
7.4.3 Lo cality in Programs . . . . . . . . . . . . . . . . . . . . . 455
7.4.4 Reducing Fragmentation . . . . . . . . . . . . . . . . . . . 457
7.4.5 Manual Deallo cation Requests . . . . . . . . . . . . . . . 460
7.4.6 Exercises for Section 7.4 . . . . . . . . . . . . . . . . . . . 463
7.5 Intro duction to Garbage Collection . . . . . . . . . . . 463
7.5.1 Design Goals for Garbage Collectors . . . . . . . . . . . . 464
7.5.2 Reachability. . . . . . . . . . . . . . . . . . . . . . . . . . 466
7.5.3 Reference Counting Garbage Collectors . . . . . . . . . . 468
7.5.4 Exercises for Section 7.5 . . . . . . . . . . . . . . . . . . . 470
7.6 Intro duction to Trace-Based Collection . . . . . . . 470
7.6.1 A Basic Mark-and-Sweep Collector . . . . . . . . . . . . . 471
7.6.2 Basic Abstraction . . . . . . . . . . . . . . . . . . . . . . 473
7.6.3 Optimizing Mark-and-Sweep . . . . . . . . . . . . . . . . 475
7.6.4 Mark-and-Compact Garbage Collectors . . . . . . . . . . 476
7.6.5 Copying collectors . . . . . . . . . . . . . . . . . . . . . . 478
7.6.6 Comparing Costs . . . . . . . . . . . . . . . . . . . . . . . 482
7.6.7 Exercises for Section 7.6 . . . . . . . . . . . . . . . . . . . 482
7.7 Short-Pause Garbage Collection . . . . . . . . . . . 483
7.7.1 Incremental Garbage Collection . . . . . . . . . . . . . . . 483
7.7.2 Incremental Reachability Analysis . . . . . . . . . . . . . 485
7.7.3 Partial-Collection Basics . . . . . . . . . . . . . . . . . . . 487
7.7.4 Generational Garbage Collection . . . . . . . . . . . . . . 488
7.7.5 The Train Algorithm . . . . . . . . . . . . . . . . . . . . . 490
7.7.6 Exercises for Section 7.7 . . . . . . . . . . . . . . . . . . . 493
7.8 Advanced Topics in Garbage Collection . . . . . . . . . . . . . . 494
7.8.1 Parallel and Concurrent Garbage Collection . . . . . . . . 495
7.8.2 Partial Ob ject Relo cation . . . . . . . . . . . . . . . . . . 497
7.8.3 Conservative Collection for Unsafe Languages . . . . . . . 498
7.8.4 Weak References . . . . . . . . . . . . . . . . . . . . . . . 498
7.8.5 Exercises for Section 7.8 . . . . . . . . . . . . . . . . . . . 499
7.9 Summary of Chapter 7 . . . . . . . . . . . . . . . 500
7.10 References for Chapter 7 . . . . . . . . . . . . . . 502
8CodeGeneration505
8.1 Issues in the Design of a Co de Generator . . . . . . . . . . . . . 506
8.1.1 Input to the Co de Generator . . . . . . . . . . . . . . . . 507
8.1.2 The Target Program . . . . . . . . . . . . . . . . . . . . . 507
8.1.3 Instruction Selection . . . . . . . . . . . . . . . . . . . . . 508
8.1.4 Register Allo cation . . . . . . . . . . . . . . . . . . . . . . 510
8.1.5 Evaluation Order . . . . . . . . . . . . . . . . . . . . . . . 511
8.2 The Target Language . . . . . . . . . . . . . . . . . . . . . . . . 512
8.2.1 A Simple Target Machine Mo del . . . . . . . . . . . . . . 512
8.2.2 Program and Instruction Costs . . . . . . . . . . . . . . . 515
8.2.3 Exercises for Section 8.2 . . . . . . . . . . . . . . . . . . . 516
8.3 Addresses in the Target Co de . . . . . . . . . . . . 518
8.3.1 Static Allo cation . . . . . . . . . . . . . . . . . . . . . . . 518
8.3.2 Stack Allo cation . . . . . . . . . . . . . . . . . . . . . . . 520
8.3.3 Run-Time Addresses for Names . . . . . . . . . . . . . . . 522
8.3.4 Exercises for Section 8.3 . . . . . . . . . . . . . . . . . . . 524
8.4 Basic Blo cks and Flow Graphs . . . . . . . . . . . . . . . . . . . 525
8.4.1 Basic Blo cks . . . . . . . . . . . . . . . . . . . . . . . . . 526
8.4.2 Next-Use Information . . . . . . . . . . . . . . . . . . . . 528
8.4.3 Flow Graphs . . . . . . . . . . . . . . . . . . . . . . . . . 529
8.4.4 Representation of Flow Graphs . . . . . . . . . . . . . . . 530
8.4.5 Lo ops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 531
8.4.6 Exercises for Section 8.4 . . . . . . . . . . . . . . . . . . . 531
8.5 Optimization of Basic Blo cks . . . . . . . . . . . . 533
8.5.1 The DAG Representation of Basic Blo cks . . . . . . . . . 533
8.5.2 Finding Lo cal Common Sub expressions . . . . . . . . . . 534
8.5.3 Dead Co de Elimination . . . . . . . . . . . . . . . . . . . 535
8.5.4 The Use of Algebraic Identities . . . . . . . . . . . . . . . 536
8.5.5 Representation of Array References . . . . . . . . . . . . . 537
8.5.6 Pointer Assignments and Pro cedure Calls . . . . . . . . . 539
8.5.7 Reassembling Basic Blo cks From DAG's . . . . . . . . . . 539
8.5.8 Exercises for Section 8.5 . . . . . . . . . . . . . . . . . . . 541
8.6 A Simple Co de Generator . . . . . . . . . . . 542
8.6.1 Register and Address Descriptors . . . . . . . . . . . . . . 543
8.6.2 The Co de-Generation Algorithm . . . . . . . . . . . . . . 544
8.6.3 Design of the Function getReg . . . . . . . . . . . . . . . . 547
8.6.4 Exercises for Section 8.6 . . . . . . . . . . . . . . . . . . . 548
8.7 Peephole Optimization . . . . . . . . . . . . . . . . . .549
8.7.1 Eliminating Redundant Loads and Stores . . . . . . . . . 550
8.7.2 Eliminating Unreachable Co de . . . . . . . . . . . . . . . 550
8.7.3 Flow-of-Control Optimizations . . . . . . . . . . . . . . . 551
8.7.4 Algebraic Simpli cation and Reduction in Strength . . . . 552
8.7.5 Use of Machine Idioms . . . . . . . . . . . . . . . . . . . . 552
8.7.6 Exercises for Section 8.7 . . . . . . . . . . . . . . . . . . . 553
8.8 Register Allo cation and Assignment . . . . . . . . . . . . . . . . 553
8.8.1 Global Register Allo cation . . . . . . . . . . . . . . . . . . 553
8.8.2 Usage Counts . . . . . . . . . . . . . . . . . . . . . . . . . 554
8.8.3 Register Assignment for Outer Lo ops . . . . . . . . . . . 556
8.8.4 Register Allo cation by Graph Coloring . . . . . . . . . . . 556
8.8.5 Exercises for Section 8.8 . . . . . . . . . . . . . . . . . . . 557
8.9 Instruction Selection by Tree Rewriting . . . . . . . . . . . . . . 558
8.9.1 Tree-Translation Schemes . . . . . . . . . . . . . . . . . . 558
8.9.2 Co de Generation by Tiling an Input Tree . . . . . . . . . 560
8.9.3 Pattern Matching by Parsing . . . . . . . . . . . . . . . . 563
8.9.4 Routines for Semantic Checking . . . . . . . . . . . . . . 565
8.9.5 General Tree Matching . . . . . . . . . . . . . . . . . . . . 565
8.9.6 Exercises for Section 8.9 . . . . . . . . . . . . . . . . . . . 567
8.10 Optimal Co de Generation for Expressions . . . . . . . . . . . . . 567
8.10.1 Ershov Numb ers . . . . . . . . . . . . . . . . . . . . . . . 567
8.10.2 Generating Co de From Lab eled Expression Trees . . . . . 568
8.10.3 Evaluating Expressions with an Insu cient Supply of Reg-
isters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 570
8.10.4 Exercises for Section 8.10 . . . . . . . . . . . . . . . . . . 572
8.11 Dynamic Programming Co de-Generation . . . . . . . . . . . . . . 573
8.11.1 Contiguous Evaluation . . . . . . . . . . . . . . . . . . . . 574
8.11.2 The Dynamic Programming Algorithm . . . . . . . . . . . 575
8.11.3 Exercises for Section 8.11 . . . . . . . . . . . . . . . . . . 577
8.12 Summary of Chapter 8 . . . . . . . . . . . . . 578
8.13 References for Chapter 8 . . . . . . . . . . . . 579
9Machine-IndependentOptimizations583
9.1 The Principal Sources of Optimization . . . . . . . . . . . . . . . 584
9.1.1 Causes of Redundancy . . . . . . . . . . . . . . . . . . . . 584
9.1.2 A Running Example: Quicksort . . . . . . . . . . . . . . . 585
9.1.3 Semantics-Preserving Transformations . . . . . . . . . . . 586
9.1.4 Global Common Sub expressions . . . . . . . . . . . . . . 588
9.1.5 Copy Propagation . . . . . . . . . . . . . . . . . . . . . . 590
9.1.6 Dead-Co de Elimination . . . . . . . . . . . . . . . . . . . 591
9.1.7 Co de Motion . . . . . . . . . . . . . . . . . . . . . . . . . 592
9.1.8 Induction Variables and Reduction in Strength . . . . . . 592
9.1.9 Exercises for Section 9.1 . . . . . . . . . . . . . . . . . . . 596
9.2 Intro duction to Data-Flow Analysis . . . . . . . . . . . . . . . . 597
9.2.1 The Data-Flow Abstraction . . . . . . . . . . . . . . . . . 597
9.2.2 The Data-Flow Analysis Schema . . . . . . . . . . . . . . 599
9.2.3 Data-Flow Schemas on Basic Blo cks . . . . . . . . . . . . 600
9.2.4 Reaching De nitions . . . . . . . . . . . . . . . . . . . . . 601
9.2.5 Live-Variable Analysis . . . . . . . . . . . . . . . . . . . . 608
9.2.6 Available Expressions . . . . . . . . . . . . . . . . . . . . 610
9.2.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 614
9.2.8 Exercises for Section 9.2 . . . . . . . . . . . . . . . . . . . 615
9.3 Foundations of Data-Flow Analysis . . . . . . . . . . . . . . . . . 618
9.3.1 Semilattices . . . . . . . . . . . . . . . . . . . . . . . . . . 618
9.3.2 Transfer Functions . . . . . . . . . . . . . . . . . . . . . . 623
9.3.3 The Iterative Algorithm for General Frameworks . . . . . 626
9.3.