编译原理（第四版）

《编译原理(第四版)》主要介绍设计和构造编译程序的基本原理和方法．内容包括适应高级程序设计语言翻译的形式语言理论和自动机理论、常用的词法分析方法、各种经典的语法分析技术、语法制导翻译方法、存储组织与管理方法、造查表方法、代码优化和代码生成方法、编译自动化和并行编译程序，以及词法分析器生成工具LEX和语法分析器生成工具YACC等。本书特别注重理论与实践的沟通，基本概念清晰，循序渐进，深入浅出。各章附有难度不一的习题。 本书可作为高等院校计算机专业的教材，也可供相关教师、研究生和科技工作者学习和参考。

1975年毕业留校筹建武汉大学计算机科学系，1978年晋升为武汉大学计算机科学系讲师，在计算机软件教研室从事教学和科研工作； 1987年4月任武汉大学计科系副主任；1989年晋升为计算机科学系副教授； 1993年破格晋升为计算机科学系教授； 1997年1月任武汉大学计算机学院副院长； 1997年9月任武汉大学计算机学院院长， 1997-2001年兼任软件工程国家重点实验室主任； 1999年4月-2001年1月兼任武汉大学校长助理； 1999年评为博士生导师； 2001年1月—2013年3月任（四校合并后）武汉大学计算机学院院长。

第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) 第10章符号表的组织和查找(180) 10.1符号表的一般组织形式(180) 10.2符号表中的数据(181) 10.3符号表的构造与查找(181) 10.3.1线性查找(182) 10.3.2折半法(182) 10.3.3杂凑技术(183) 10.4分程序结构的符号表(185) 10.5小结(187) 习题十(188) 第11章优化(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) 第12章代码生成(208) 12.1假想的计算机模型(208) 12.2从四元式生成代码(209) 12.3从三元式生成代码(210) 12.4从树形表示生成代码(213) 12.5从逆波兰表示生成代码(215) 12.6寄存器的分配(215) 12.7小结(216) 习题十二(216) 第13章词法分析程序生成工具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) 第14章语法分析程序生成工具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)