编译原理 英文版 第2版

本书是编译领域无可替代的经典著作，被广大计算机专业人士誉为“龙书”。自本书上一版于1986年出版以来，被世界各地的著名高等院校和研究机构（包括美国哥伦比亚大学、斯坦福大学、哈佛大学、普林斯顿大学、贝尔实验室）作为本科生和研究生的编译原理课程的教材。该书对我国计算机教育领域也具有重大影响。

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

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 1