编译原理(第四版)

第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)