编译程序(compiler),又称编译器,是计算机的重要系统软件,是高级程序设计语言的支撑基础。本书主要介绍设计和构造编译程序的基本原理和方法。本书共分 14 章。第1章讲述编译程序的功能、结构、工作过程、组织方式、编译程序与高级语言的关系,以及编译自动化方面的基本知识。第2章介绍形式语言理论,我们仅仅给出了便于理解、有助于研究各种分析方法和设计构造编译程序的形式语言理论，并着重介绍了上下文无关文法。有穷自动机是描述词法的有效工具,也是进行词法分析的主要理论基础。因此,第3章专门讨论有穷自动机,它与正规文法、正规表达式之间的对应关系,以及它的确定化和*小化方面的知识，略去了图灵机及可计算性理论方面的内容。第4章讨论词法分析的功能和词法分析程序的设计方法。上下文无关文法可用于描述现今大多数高级程序设计语言的语法，也是语法分析的主要理论支柱。为此,在接下来的几章里,主要讨论了与上下文无关文法相关的各类语法分析方法。第5章介绍自上而下分析方法,句括 LL(k)文法、LL(1)分析方法和应用十分广泛的递归下降分析方法。第6章讨论自下而上分析方法的一般原理和优先分析方法,包括简单优先分析方法和算符优先分析方法。第7章专门讨论自下而上的LR(k)分析方法,包括 LR(O)、SLR(1)、规范 LR(1)及 LALR 分析表的构造算法第8章介绍语法制导翻译方法,主要讨论了 SDTS 的基本原理、属性翻译文法,以及它们在中间代码生成中的应用。第9章讨论运行时的存储组织与管理,其中考虑了一些重要的语言特征,如过程调用、参数传递、数组和记录的存取方式及多种存储分配技术。第10章讨论符号表的组织和存取符号表的各种方法。第11章介绍常用的优化方法。第12章简单讨论代码生成的原理。第13章、第14章中花了较大篇幅分别介绍了词法分析器生成工具 LEX 和语法分器生成工具 YACC,以便于本课程的教学实习和课程设计。我们认为某些形式语言理论和自动机理论对设计构造编译程序是极其有用的,但现有的不少形式语言理论及自动机理论与设计和构造编译程序的关系不大。本书试图在沟通设计和构造编译程序的理论与实践、原理与方法等方面做一点尝试。编译原理这门课程是计算机专业的主干课和必修课,也是计算机专业高年级课程中较难学习的一门课程,其先导课程是汇编语言程序设计、计算机组成原理、数据结构、高级语言程序设计和离散数学等。本课程的参考学时数为72,使用者可根据具体情况对教材内容进行取舍,例如,工科院校的学生可略过第7章、第8章并可精简第2章的内容,从而使授课学时数减至54。本次再版工作主要是针对《编译原理(第三版)》中的差错进行修正,对过时的章节进行删除,对必要的内容进行补充等。其中,第1~3章由袁梦霆负责修订,第 4~6 章由杜卓敏负责修订,第7~8章由何炎祥负责修订,第9~10章由伍春香负责修订,第11~14章基本没动。*后由何炎祥对全书进行了审定。同时,适当配套一些电子资源,包括 PPT 课件、习题答案、部分章节的相关视频。本书可作为高等院校计算机专业的教材，也可供教师、研究生及有关科技工作者学习和参本书成书过程中,得到了华中科技大学出版社的鼎力协助，此外,书中还引用了一些专家学者的研究成果,在此一并表示感谢。作 者2023 年5月于武昌珞珈山
第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.2IFTHENELSE控制语句(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)
精品教材 更多
