编译原理（第四版）

第1章引论(1)

1.1程序设计语言与翻译程序(1)
1.1.1程序设计语言(1)
1.1.2翻译程序(1)
1.2编译程序的工作过程(2)
1.3编译程序的结构(4)
1.4编译程序的组织方式(5)
1.5编译程序的自展、移植与自动化(6)
1.5.1 语言的自编译性(6)
1.5.2编译程序的自展技术(6)
1.5.3编译程序的移植(7)
1.5.4编译程序的自动化(7)
1.6翻译程序编写系统(8)
1.7并行编译程序(9)
1.8小结(10)
习题一(10)
第2章形式语言理论(12)
2.1字母表和符号串(12)
2.2文法及其分类(13)
2.2.1文法(13)
2.2.2文法分类(14)
2.2.3文法举例(15)
2.3语言和语法树(16)
2.3.1推导和规范推导(16)
2.3.2句型、句子和语言(17)
2.3.3语法树(18)
2.3.4产生式树(19)
2.4关于文法和语言的几点说明(20)
2.5分析方法简介(21)
2.5.1自上而下分析方法(22)
2.5.2确定的自上而下分析方法(23)
2.5.3自下而上分析方法(24)
2.6小结(25)
习题二(26)

第3章有穷自动机(28)
3.1有穷自动机的形式定义(28)
3.1.1状态转换表(28)
3.1.2状态转换图(29)
3.1.3自动机的等价性(29)
3.1.4非确定有穷自动机(30)
3.2NFA到DFA的转换(31)
3.2.1空移环路的寻找和消除(31)
3.2.2消除空移(32)
3.2.3确定化——子集法(32)
3.2.4确定化——造表法(33)
3.2.5εNFA的确定化(35)
3.2.6消除不可达状态(36)
3.2.7DFA的化简(37)
3.2.8从化简后的DFA到程序表示(37)
3.3正规表达式与FA(38)
3.3.1正规表达式的定义(38)
3.3.2正规表达式与FA的对应性(40)
3.3.3正规表达式到NFA的转换(40)
3.3.4NFA到正规表达式的转换(41)
3.4DFA在计算机中的表示(42)
3.4.1矩阵表示法(42)
3.4.2表结构(43)
3.5小结(43)
习题三(44)
第4章词法分析(46)
4.1词法分析程序与单词符号(46)
4.1.1词法分析程序(46)
4.1.2单词符号(46)
4.2扫描程序的设计(47)
4.2.1预处理(47)
4.2.2状态转换图(48)
4.2.3根据状态图设计词法分析程序(49)
4.3标识符的处理(50)
4.3.1类型的机内表示(50)
4.3.2标识符的语义表示(51)
4.3.3符号表（标识符表）(51)
4.3.4标识符处理的基本思想(51)
4.4设计词法分析程序的直接方法(52)
4.4.1由正规文法设计词法分析程序(52)
4.4.2由正规表达式设计词法分析程序(53)
4.4.3由状态图到词法分析程序的流程图(54)
4.4.4词法分析程序的自动构造(54)
4.5小结(54)
习题四(55)
第5章自上而下语法分析(56)
5.1消除左递归方法(56)
5.1.1文法的左递归性(56)
5.1.2用扩展的BNF表示法消除左递归(56)
5.1.3直接改写法(57)
5.1.4消除左递归算法(58)
5.2LL(k)文法(59)
5.2.1LL(1)文法的判断条件(59)
5.2.2集合FIRST、FOLLOW与SELECT的构造(59)
5.3确定的LL(1)分析程序的构造(61)
5.3.1构造分析表M的算法(61)
5.3.2LL(1)分析程序的总控算法(62)
5.4递归下降分析程序及其设计(64)
5.4.1框图设计(64)
5.4.2程序设计(65)
5.5带回溯的自上而下分析法(66)
5.5.1文法在内存中的存放形式(66)
5.5.2其他信息的存放(67)
5.5.3带回溯的自上而下分析算法(67)
5.6小结(71)
习题五(71)
第6章自下而上分析和优先分析方法(74)
6.1自下而上分析(74)
6.2短语和句柄(74)
6.3移进归约方法(76)
6.4有关文法的一些关系(77)
6.4.1关系(77)
6.4.2布尔矩阵和关系(78)
6.4.3Warshall算法(79)
6.4.4关系FIRST与LAST(80)
6.5简单优先分析方法(82)
6.5.1优先关系(82)
6.5.2简单优先关系的形式化构造方法(83)
6.5.3简单优先文法及其分析算法(87)
6.5.4简单优先分析方法的局限性(89)
6.6算符优先分析方法(90)
6.6.1算符优先文法(90)
6.6.2OPG优先关系的构造(90)
6.6.3素短语及句型的分析(92)
6.6.4算符优先分析算法(92)
6.7优先函数及其构造(94)
6.7.1优先函数(94)
6.7.2Bell方法(95)
6.7.3Floyd方法(96)
6.7.4Bell和Floyd两种方法的比较(97)
6.7.5运用优先函数进行分析(97)
6.8两种优先分析方法的比较(98)
6.9小结(98)
习题六(99)
第7章自下而上的LR(k)分析方法
(101)
7.1LR(k)文法和LR(k)分析程序(101)
7.2LR(0)分析表的构造(104)
7.2.1规范句型的活前缀(105)
7.2.2LR(0)项目(105)
7.2.3文法G的拓广文法(105)
7.2.4CLOSURE(I)函数(105)
7.2.5goto(I,X)函数(106)
7.2.6LR(0)项目集规范族(107)
7.2.7有效项目(108)
7.2.8举例(110)
7.2.9LR(0)文法(112)
7.2.10构造LR(0)分析表的算法(112)
7.3SLR分析表的构造(113)
7.4规范LR(1)分析表的构造(116)
7.5LALR分析表的构造(121)
7.6无二义性规则的使用(124)
7.7小结(126)
习题七(130)
第8章语法制导翻译法(131)
8.1一般原理和树变换(131)
8.1.1一般原理(131)
8.1.2树变换(133)
8.2简单SDTS和自上而下翻译器(135)
8.3简单后缀SDTS和自下而上翻译器(137)
8.3.1后缀翻译(138)
8.3.2IFTHENELSE控制语句(138)
8.3.3函数调用(139)
8.4抽象语法树的构造(140)
8.4.1自下而上构造AST(141)
8.4.2AST的拓广(142)
8.5属性文法(143)
8.5.1L属性文法(143)
8.5.2S属性文法(143)
8.6中间代码形式(144)
8.6.1逆波兰表示法(144)
8.6.2逆波兰表示法的推广(144)
8.6.3四元式(146)
8.6.4三元式(147)
8.7属性翻译文法的应用(147)
8.7.1综合属性与自下而上定值(147)
8.7.2继承属性和自上而下定值(148)
8.7.3布尔表达式到四元式的翻译(149)
8.7.4条件语句的翻译(150)
8.7.5迭代语句的翻译(151)
8.8小结(153)
习题八(154)
第9章运行时的存储组织与管理(156)
9.1存储分配基础知识(156)
9.1.1运行时刻的存储区域(156)
9.1.2过程活动与过程的活动记录(156)
9.1.3静态层次、静态外层和动态外层(157)
9.1.4名字的作用域和生存期(158)
9.1.5名字的静态属性和动态属性(159)
9.1.6常见数据类型的存储分配(159)
9.2典型的存储分配方案(160)
9.2.1静态存储分配方案(160)
9.2.2动态存储分配方案(161)
9.2.3存储分配时需考虑的问题(161)
9.3参数传递方式及其实现(162)
9.3.1传地址(162)
9.3.2传值(163)
9.3.3传结果(163)
9.3.4传名(163)
9.4栈式存储分配(164)
9.4.1概述(164)
9.4.2简单栈式存储分配(166)
9.4.3嵌套结构语言的栈式存储分配(167)
9.4.4过程调用时的存储管理(171)
9.4.5PL/0栈式存储分配(171)
9.5堆式存储分配方法(177)
9.6小结(177)
习题九(178)
0章符号表的组织和查找(180)
10.1符号表的一般组织形式(180)
10.2符号表中的数据(181)
10.3符号表的构造与查找(181)
10.3.1线性查找(182)
10.3. 半法(182)
10.3.3杂凑技术(183)
10.4分程序结构的符号表(185)
10.5小结(187)
习题十(188)
1章优化(189)
11.1控制流图(190)
11.2常见的冗余(193)
11.2.1公共子表达式(194)
11.2.2复制传播(195)
11.2.3活跃变量分析及死代码删除(196)
11.3循环优化(197)
11.3.1代码外提(197)
11.3.2归纳变量与强度削弱(200)
11.3.3循环展开(202)
11.3.4指令调度(204)
习题十一(205)
2章代码生成(208)
12.1假想的计算机模型(208)
12.2从四元式生成代码(209)
12.3从三元式生成代码(210)
12.4从树形表示生成代码(213)
12.5从逆波兰表示生成代码(215)
12.6寄存器的分配(215)
12.7小结(216)
习题十二(216)
3章词法分析程序生成工具LEX(217)
13.1LEX简介(217)
13.2LEX源文件的格式(219)
13.2.1模式(219)
13.2.2定义部分(221)
13.2.3规则部分(222)
13.2.4用户代码部分(223)
13.3LEX的工作原理(223)
13.4yylex()函数的匹配原则(224)
13.5识别模式后处理(224)
13.6条件模式(227)
13.7FLEX的命令选项(228)
13.8举例(228)
习题十三(229)
4章语法分析程序生成工具YACC(231)
14.1YACC简介(231)
14.2YACC源文件的格式(234)
14.2.1单词和非终结符(234)
14.2.2定义部分(235)
14.2.3语法规则部分(241)
14.3语义定义(241)
14.3.1单词语义值的计算(242)
14.3.2非终结符语义值的计算(243)
14.3.3在规则中部的语义动作(244)
14.4归约归约冲突和上下文相关性的处理(246)
14.5出错处理和恢复(248)
14.6输出分析程序的调试(250)
14.7YACC和LEX的接口(250)
14.8BYACC的命令选项(251)
14.9举例(252)
习题十四(257)
参考文献(259)