《编译程序构造》求取 ⇩

第一章引论1

1．1翻译程序1

1．2为什么需要编译程序3

1．2．1模块性4

1．2．2静态解释与动态解释5

1．2．3机器无关性6

1．2．4程序语言特征8

1．3编译程序的开销8

1．4编译过程简介9

1．5翻译程序的观点15

1．6小结16

第二章形式语言理论介绍18

2．1语言成分18

2．1．1符号与字母表19

2．1．2串20

2．2产生式文法和语言21

2．2．1产生式规则、文法21

2．2．2文法分类23

2．2．3文法分类的意义28

2．2．4句型、句子和语言29

2．2．5推导树和产生式树30

2．2．6文法的一些特性38

2．2．7规范推导40

2．2．8二义性44

2．3分析方法介绍46

2．3．1自上而下分析46

2．3．2确定的自上而下分析器49

2．3．3确定的自下而上分析器53

练习56

第三章有穷自动机62

3．1概述62

3．2FSA的形式定义66

3．2．1状态转换表67

3．2．2状态转换图68

3．2．3构形和移动68

3．2．4自动机的等价性69

3．2．5非确定的有穷自动机70

3．3NDFSA到DFSA的转换72

3．3．1空移环路的寻找和删除73

3．3．2消除空移74

3．3．3从NDFSA到DFSA（确定化）80

3．3．4消除不可达状态83

3．3．5确定的有穷自动机的化简84

3．3．6小结88

3．4正规文法与有穷自动机88

3．4．1从正规文法到FSA89

3．4．2从FSA到正规文法90

3．5正规表达式与FSA91

3．5．1正规表达式的定义91

3．5．2正规表达式的CFG93

3．5．3正规表达式与FSA的对应性94

3．5．4从正规文法到正规表达式102

3．6DFSA在计算机中的表示106

3．7词法分析109

3．7．1词法分析概述109

3．7．2单词符号110

3．7．3扫描程序的设计111

3．7．4与设计扫描程序相关的几个问题119

练习120

第四章语法分析——自上而下分析125

4．1非确定的下推自动机126

4．1．1PDA的形式定义126

4．1．2 PDA的构形和移动129

4．1．3上下文无关语言与PDA132

4．2LL（k）文法136

4．2．1有关LL（1）文法的转换技术137

4．2．2 LL（1）文法的判断条件141

4．3确定的LL（1）分析器的构造145

4．3．1构造分析表M的算法146

4．3．2LL（1）分析器的总控算法148

4．4 LL（k）文法的几个结论150

4．5递归下降分析程序及其设计150

练习154

第五章自下而上分析和优先分析方法157

5．1概述157

5．2短语和句柄91

5．3非确定的自下而上分析器161

5．3．1拓广的PDA与上下文无关语言的等价性163

5．4有关文法的一些关系167

5．4．1关系167

5．4．2布尔矩阵和关系170

5．4．3Warshall算法173

5．5简单优先分析方法173

5．5．1优先关系173

5．5．2优先关系的形式定义及构造176

5．5．3简单优先文法及其分析算法178

5．5．4优先函数及其构造181

5．6算符优先分析方法184

5．6．1算符优先文法184

5．6．2OPG优先关系的构造186

5．6．3素短语及句型的分析187

练习189

第六章自下而上的LR（k）分析方法192

6．1 LR（k）分析法概述192

6．2 LR（k）文法和LR（k）分析器193

6．3 LR（0）项目集规范族199

6．4有效项目205

6．5 SLR分析表的构造207

6．6规范LR分析表的构造211

6．7 LALR分析表的构造220

6．8无二义性规则的使用226

6．9有关LR分析的几个结论229

练习229

第七章语法制导翻译法231

7．1一般原理231

7．1．1树变换236

7．2简单SDTS和自上而下翻译器238

7．3简单后缀SDTS和自下而翻译器243

7．4抽象语法树的构造248

7．4．1自下而上构造AST251

7．4．2AST的拓广252

7．5属性文法253

7．6中间代码形式255

7．6．1逆波兰表示255

7．6．2逆波兰表示式的推广256

7．6．3四元式258

7．6．4三元式260

7．7属性翻译文法的应用262

7．7．1综合属性与自下而上定值262

7．7．2继承属性和自上而下定值263

7．7．3迭代语句的翻译265

练习269

第八章运行时的存贮组织与管理271

8．1数据区和属性字272

8．2基本数据类型的存贮分配275

8．3数组的存贮分配275

8．3．1单块存贮方式275

8．3．2信息向量与数组分配程序278

8．3．3多块存贮方式280

8．4记录结构的存贮分配280

8．5参数传递方式及其实现282

8．5．1换名283

8．5．2传值284

8．5．3传地址284

8．5．4传结果285

8．5．5数组名字用作实参286

8．5．6过程名字用作实参286

8．6栈式存贮分配法与ALGOL存贮管理286

8．6．1概述286

8．6．2现行DISPLAY和现行数据区288

8．6．3标识符的作用域290

8．6．4分程序的进口和出口工作291

8．6．5过程调用时的存贮管理295

8．7FORTRAN存贮管理298

8．8堆式存贮分配方法介绍299

8．9临时工作单元的存贮分配300

练习305

第九章符号表的组织与查找308

9．1符号表的一般组织形式308

9．2符号表中的数据309

9．3符号表的构造与查找311

9．3．1线性查找311

9．3．2折半法313

9．3．3杂凑技术314

9．4分程序结构的符号表318

练习321

第十章优化323

10．1优化概述323

10．2优化举例324

10．3使用变量的定义点进行优化328

10．3．1变量的定义点328

10．3．2循环中不变式的外提330

10．3．3运算强度削弱330

10．3．4公共子表达式的消除330

10．3．5常量合并332

10．4窥孔优化334

10．5小结334

练习335

第十一章代码生成337

11．1假想的计算机模型338

11．2从四元式生成代码339

11．3从三元式生成代码341

11．4从树型表示生成代码345

11．5从逆波兰表示生成代码348

11．6寄存器的分配350

练习352

第十二章翻译程序编写系统介绍353

参考文献355