《程序设计语言编译方法》

第一章引言1

1.1计算机的语言层次与翻译1

1.2编译的阶段（phase）2

1.3编译的遍（pass）4

1.4 SIMPLE编译的结构设计5

第二章编译基础6

2.1字母表、串和语言6

2.2文法的引例7

2.3文法的形式定义8

2.4文法的分类9

2.5正规文法和有穷自动机10

2.5.1正规集与正规文法10

2.5.2有穷自动机11

2.5.3正规文法与有穷自动机14

2.5.4 正规文法和正规式15

2.6 正规式、NFA和DFA之间的等价变换16

2.6.1从正规式构造NFA16

2.6.2 NFA的确定化18

2.6.3 DFA的最小化19

2.7上下文无关文法与下推自动机21

2.7.1上下文无关文法21

2.7.2上下文无关文法的变换23

2.7.3语法树与文法的二义性24

2.7.4 下推自动机26

习题28

第三章程序设计语言的构造基础与定义32

3.1程序设计语言的构造基础32

3.1.1对象的名字、属性与汇聚32

3.1.2 数据型对象及其存贮表示33

3.1.3 运行时的存贮管理36

3.1.4 运算及运算的复合36

3.1.5 运算的顺序控制37

3.1.6参数传递37

3.2程序设计语言的定义40

3.2.1程序语言的语法定义40

3.2.2 程序语言的语义定义45

3.3 SIMPLE语言的主要成分47

习题47

第四章词法分析51

4.1单词的种类与机内表示法51

4.1.1单词的分类51

4.1.2单词的机内表示法51

4.2扫描器的任务与设计考虑53

4.3扫描器的设计54

4.3.1扫描器的界面与数据结构54

4.3.2 扫描器的数据流图55

4.3.3 扫描器的详细设计57

4.4扫描器的其他设计技术62

4.4.1有穷自动机技术62

4.4.2正规式技术64

4.5某些高级语言的词法分析问题65

4.6词法分析阶段的错误处理66

4.7扫描器的自动生成原理67

4.7.1 LEX语言的基本语句与功能67

4.7.2 LEX编译器原理69

习题70

第五章语法分析72

5.1自顶向下分析法72

5.1.1自顶向下分析法中的问题研究72

5.1.2 左递归与回溯问题74

5.1.3 LL(1)文法的定义75

5.1.4 LL(1)文法的判别78

5.1.5 LL(1)文法的讨论79

5.2递归下降法80

5.3 LL(1)分析法83

5.4自底向上分析法86

5.4.1自底向上分析法中的问题研究86

5.4.2 句柄的定义与识别方法88

5.5算符优先分析技术90

5.5.1算符优先文法91

5.5.2算符优先矩阵93

5.5.3算符优先分析法的实现问题96

5.5.4 算符优先分析的数据流图与模块结构图98

5.5.5算符优先分析技术的改进101

5.6 LR分析技术102

5.6.1概述102

5.6.2 LR(0)分析表的构造方法103

5.6.3 SLR(1)分析表的构造方法107

5.6.4 LR(1)分析表的构造方法109

5.6.5 LALR分析表的构造方法114

5.6.6 二义文法的LR分析法120

5.6.7 LR分析器总控程序122

5.7语法分析中的错误处理123

5.8各种语法分析技术的比较124

5.9语法分析器自动生成的原理126

5.9.1文法定义语言的功能126

5.9.2其他文法类分析表的自动生成问题128

习题129

第六章语法制导翻译技术133

6.1语法制导翻译概述133

6.2中间代码134

6.3自底向上的语法制导翻译135

6.3.1自底向上翻译的特点135

6.3.2说明语句的翻译136

6.3.3简单赋值句的翻译139

6.3.4布尔表达式的翻译140

6.3.5 IF语句的翻译146

6.3.6 REPEAT语句的翻译148

6.3.7 FOR循环语句的翻译148

6.4自顶向下的语法制导翻译149

6.4.1递归下降的语法制导翻译150

6.4.2 LL(1)语法制导翻译153

6.5属性文法与属性翻译156

6.5.1属性文法与L_属性文法156

6.5.2属性计值规则的改造与属性翻译158

6.6 SIMPLE语言的语法制导翻译程序的设计163

6.7某些复杂语言成分的翻译172

6.7.1分程序结构的符号表172

6.7.2数组变量说明的翻译174

6.7.3过程语句的翻译176

6.7.4 过程调用语句和返回语句的翻译176

6.7.5 复杂赋值句的翻译178

6.7.6 CASE语句的翻译181

6.7.7 输入输出语句的翻译182

6.8 P－代码183

习题186

第七章运行时的存贮分配190

7.1数据区的内容191

7.2静态存贮分配191

7.3栈式存贮分配194

7.3.1栈式存贮管理和过程数据区格式194

7.3.2运行时地址的计算198

7.3.3过程调用与返回语句的目标代码199

7.3.4 过程的目标代码结构和运行栈的管理201

7.3.5 递归过程的调用204

7.4堆式存贮分配206

7.4.1堆空间的分配管理206

7.4.2堆空间的释放与敛集208

习题210

第八章程序控制流与数据流分析213

8.1程序控制流图与循环分析213

8.1.1基本块与程序控制流图的构造213

8.1.2查找循环结构215

8.2到达－定值数据流分析217

8.2.1引用与定值（ud）链217

8.2.2到达－定值数据流方程218

8.3活跃变量分析219

8.3.1活跃变量的教据流方程219

8.3.2定值－引用（du）链及其数据流方程220

8.4可用表达式分析220

8.5非常忙表达式分析222

8.6模块间数据流分析222

第九章代码优化224

9.1局部优化224

9.1.1局部优化的种类224

9.1.2适合于优化的中间代码225

9.2合并已知量226

9.3利用公共子表达式和消除无用赋值232

9.4循环优化技术238

9.4.1代码外提239

9.4.2强度削弱和变换循环变量240

9.4.3循环展开和循环合并242

习题243

第十章目标代码生成245

10.1 目标机245

10.2各类四元式的翻译方法246

10.3寄存器分配与基本块代码的生成248

10.3.1引用信息与活跃信息248

10.3.2寄存器的分配问题249

10.3.3基本块的代码生成算法250

10.4 DAG的目标代码生成252

10.5 SIMPLE目标代码生成器的设计256

10.6目标代码的其他优化技术259

10.6.1窥孔优化259

10.6.2 区域内寄存器的分配259

习题260

第十一章运行准备262

11.1装配程序262

11.1.1绝对装配程序262

11.1.2重定位装配程序263

11.2外部访问的辨认265

11.3连接程序（LINKER）266

11.4库管理270

11.5存贮分配271

习题272

部分习题参考答案274

参考文献298