编译原理（第二版）

第1章引论

1.1翻译程序

1.1.1程序设计语言

1.1.2翻译程序

1.2编译程序的工作过程

1.3编译程序的结构

1.4编译程序的组织方式

1.5编译程序的自展.移植与自动化

1.5.1高级语言的自编译性

1.5.2编译程序的自展技术

1.5.3编译程序的移植

1.5.4编译程序的自动化

1.6翻译程序编写系统

1.7并行编译程序

1.8小结

习题一

第2章形式语言概论

2.1字母表和符号串

2.2文法及其分类

2.2.1文法

2.2.2文法分类

2.2.3文法举例

2.3语言和语法树

2.3.1推导和规范推导

2.3.2句型.句子和语言

2.3.3语法树

2.3.4产生式树

2.4关于文法和语言的几点说明

2.5分析方法简介

2.5.1自上而下分析方法

2.5.2确定的自上而下分析方法

2.5.3自下而上分析方法

2.6小结

习题二

第3章有穷自动机

3.1有穷自动机的形式定义

3.1.1状态转换表

3.1.2状态转换图

3.1.3自动机的等价性

3.1.4非确定有穷自动机

3.2NDFA到DFA的转换

3.2.1空移环路的寻找和消除

3.2.2消除空移

3.2.3确定化--子集法

3.2.4确定化--造表法

3.2.5NDFA的确定化

3.2.6消除不可达状态

3.2.7DFA的化简

3.2.8从化简后的DFA到程序表示

3.3正规文法与有穷自动机

3.3.1从正规文法到FA

3.3.2从FA到正规文法

3.4正规表达式与FA

3.4.1正规表达式的定义

3.4.2正规表达式与FA的对应性

3.4.3正规表达式到NDFA的转换

3.4.4NDFA到正规表达式的转换

3.4.5从正规文法到正规表达式

3.5DFA在计算机中的表示

3.5.1矩阵表示法

3.5.2表结构

3.6小结

习题三

第4章词法分析

4.1词法分析器与单词符号

4.1.1词法分析器

4.1.2单词符号

4.2扫描程序的设计

4.2.1预处理

4.2.2状态转换图

4.2.3根据状态图设计词法分析程序

4.3标识符的处理

4.3.1类型的机内表示

4.3.2标识符的语义表示

4.3.3符号表(标识符表)

4.3.4标识符处理的基本思想

4.4设计词法分析程序的直接方法

4.4.1由正规文法设计词法分析程序

4.4.2由正规表达式设计词法分析程序

4.5小结

习题四

第5章自上而下语法分析

5.1消除左递归方法

5.1.1文法的左递归性

5.1.2用扩展的BNF表示法消除左递归

5.1.3直接改写法

5.1.4消除左递归算法

5.2LL(k)文法

5.2.1LL(1)文法的判断条件

5.2.2集合F)RST.FOLLOW与SELECT的构造

5.3确定的LL(1)分析器的构造

5.3.1构造分析表M的算法

5.3.2LL(1)分析器的总控算法

5.4递归下降分析程序及其设计

5.4.1框图设计

5.4.2程序设计

5.5带回溯的自上而下分析法

5.5.l文法在内存中的存放形式

5.5.2其它信息的存放

5.5.3带回溯的自上而下分析算法

5.6小结

习题五

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

6.1自下而上分析

6.2短语和句柄

6.3移进·归约方法

6.4有关文法的一些关系

6.4.1关系

6.4.2布尔矩阵和关系

6.4.3Warshall算法

6.4.4关系F1RST与LAST

6.5简单优先分析方法

6.5.1优先关系

6.5.2简单优先关系的形式化构造方法

6.5.3简单优先文法及其分析算法

6.5.4简单优先分析方法的局限性

6.6算符优先分析方法

6.6.1算符优先文法

6.6.2OPG优先关系的构造

6.6.3素短语及句型的分析

6.6.4算符优先分析算法

6.7优先函数及其构造

6.7.1优先函数

6.7.2Bell方法

6.7.3Floyd方法

6.7.4两种方法的比较

6.7.5运用优先函数进行分析

6.8两种优先分析方法的比较

6.9小结

习题六

第7章自-F而上的LR(k)分析方法

7.1LR(k)文法和LR(k)分析器

7.2LR(0)分析表的构造

7.2.1规范句型的活前缀

7.2.2LR(p)项目

7.2.3文法G的拓广文法

7.2.4CL()SURE(1)函数

7.2.5goto(I.X)函数

7.2.6LR(0)项目集规范族

7.2.7有效项目

7.2.8举例

7.2.9LR(0)文法

7.2.10构造LR(0)分析表的算法

7.2.11构造LR(0)分析表的步骤小结

7.3SLR分析表的构造

7.4规范LR(1)分析表的构造

7.5LALR分析表的构造

7.6无二义性规则的使用

7.7小结

7.7.1LR分析程序

7.7.2LR分析表的自动构造

7.7.3文法间的关系

7.7.4LR文法举例

7.7.5有关LR文法的几个结论

习题七

第8章语法制导翻译法

8.1一般原理和树变换

8.1.1一般原理

8.1.2树变换

8.2简单SDTS和自上而下翻译器

8.3简单后缀SDTS和自下而上翻译器

8.3.1后缀翻译

8.3.2IF-THEN-ELSE控制语句

8.3.3函数调用

8.4抽象语法树的构造

8.4.1自下而上构造AST

8.4.2AST的拓广

8.5属性文法

8.5.1L属性文法

8.5.2S属性文法

8.6中间代码形式

8.6.1逆波兰表示法

8.6.2逆波兰表示法的推广

8.6.3四元式

8.6.4三元式

8.7属性翻译文法的应用

8.7.1综合属性与自下而上定值

8.7.2继承属性和自上而下定值

8.7.3布尔表达式到四元式的翻译

8.7.4条件语句的翻译

8.7.5迭代语句的翻译

8.8小结

习题八

第9章运行时的存储组织与管理

9.1数据区和属性字

9.2基本数据类型的存储分配

9.3数组的存储分配

9.3.1单块存储方式

9.3.2信息向量与数组分配程序

9.3.3多块存储方式

9.4记录结构的存储分配

9.5参数传递方式及其实现

9.5.1换名

9.5.2传值

9.5.3传地址

9.5.4传结果

9.5.5数组名用做实参

9.5.6过程名用做实参

9.6栈式存储分配方法

9.6.1概述

9.6.2现行DISPLAY和现行数据区

9.6.3标识符的作用域

9.6.4分程序的人口和出口工作

9.6.5过程调用时的存储管理

9.7堆式存储分配方法

9.8临时工作单元的存储分配

9.9小结

习题九

第10章符号表的组织和查找

10.1符号表的一般组织形式

10.2符号表中的数据

10.3符号表的构造与查找

10.2.1线性查找

10.3.2折半法

10.3.3杂凑技术

10.4分程序结构的符号表

10.5小结

习题十

第11章优化

11.1基本块及其求法

11.2优化举例

11.3利用变量的定义点进行优化

11.3.1变量的定义点

11.3.2循环中不变式的外提

11.3.3运算强度削弱

11.3.4公共表达式的消除

11.3.5常量合并

11.4循环优化

11.5借助DAG进行优化

11.6并行分支的优化

11.7窥孔优化

11.8小结

习题十一

第12章代码生成

12.1假想的计算机模型

12.2从四元式生成代码

12.3从三元式生成代码

12.4从树型表示生成代码

12.5从逆波兰表示生成代码

12.6寄存器的分配

12.7小结

习题十二

第13章词法分析器生成工具LEX

13.1LEX简介

13.2LEX源文件的格式

13.2.1模式

13.2.2定义部分

13.2.3规则部分

13.2.4用户代码部分

13.3LEX的工作原理

13.4yylex()函数的匹配原则

13.5识别模式后处理

13.6条件模式

13.7FLEX的命令选项

13.8举例

习题十三

第14章语法分析器生成工具YACC

14.1YACC简介

14.2YACC源文件的格式

14.2.1单词和非终结符

14.2.2定义部分

14.2.3语法规则部分

14.3语义定义

14.3.1单词语义值的汁算

14.3.2非终结符语义值的计算

14.3.3在规则中部的语义动作

14.4归约-归约冲突和上下文相关性的处理

14.5出错处理和恢复

14.6输出分析器的调试

14.7YACC和LEX的接口

14.8BYACC的命令选项

14.9举例

习题十四

参考文献