目 录 前言. 3.7.2上下文无关文法中的 第1章编译程序概论. 规则. 1.1什么是编张程序 3.8练习. 4 1.2编译过程概述. 1.3编译程序的结构 6 第4查词法分析： 47 1.4编译阶段的组合.*. 词法分析程序的设计. 1.5编译技术和软件工具. 4.1.1 词法分析程序与语法 分析程序的接口方式.47 第2章PL/0编译程序的实现 4.1.2词法分析程序的输出.47 2.1PL/0语言描述. 4.1,3.将词法分析工作分离 2.1.1PL/0语言的语法描述图*.9 的考虑 48 2,1.2PL/0语言文法的EBNF 4.2单词的描述工具. 表示， 4.2.1正规文法， 2.2PL/0编译程序的结构 .12 4.2.2正规式.， 2.3PL/0编译程序的词法分析.14 423 正规文法到正规式.51 2:公终约品营代撕我一 4.3有穷自动机 52 PL/0编译程序的目标代码结构 4.3.1确定的有穷 19 自动机(DFA) 52 和代码生成 2.6PL/0编译程序的语法错误 4.3.2不确定的有穷 处理. 21 自动机(NFA) 2.7PL0编译程序的目标代码解释 4.3.3NFA-DFA的转换54 执行时的存储分配 24 4.3.4确定有穷自动机的化简57 2.8练习. 44正规式和有穷自动机的等 价性 .59 第3章文法和语言 4,5正规文法和有穷自动机间 文法的直观概念 的转地 4.62 3.2符号和符号甲 30 4.6词法分析程序的自动构造 3.3文法和语言的形式定义.3】 工具 6 3.4文法的类型. 35 4.6.11EX语日 上下文无关文法及其语法树.37 4.7练习. 66 3.6句型的分析 39 第5章自顶向下语法分析方法 .69 3.6.1自上而下的分析方法.·40 3.6.2自下而上的分析方法.40 5】确定的自顶向下分析思想 3.63 句型分析的有关问题.1 5.21L(1)文法的判别.73 37有关文法实用中的一些说明 43 5.3某些非LL.(1)文法到1L(1) 3.7.1有关文法的实用限制 文法的等价变换. .4.78
5.4不确定的自顶向下分析思想.5第8章语法制导国译和中间代码生成.155 5.5确定的自顶向下分析方法 87 8.1佩牲文法4,4，155 5.5.1递归子程序法 8.2语法制导翻译论.157 5.5.2预测分析方法： 87 中间代码 形式 ,15 5.6练可 8.31逆波兰记号.。 15 8,3.2 三元式和树形表示.160 第6章自底向上优先分析法. 94 8.3.3四元式4+4161 6.1自底向上优先分析法概述. .95 8.4简单赋值语句的翻译 16 6.2简单优先分析法 布尔表达式的翻译 621优先关系 851布尔表达式的翻译方法 164 6.2.2简单优先文法的定义.97 8.5.2控制语句中布尔表达式 6.2.3简单量先分折法 98 的翻译： 165 6.3算符优先分析法· 8.6控制结构的翻译· 169 6.3. 直观算符优先分析法 861条件转移 16 6.3.2 算符优先文法的定义 10 8.6.2开关语句 .171 6.3.3算符优先关系表的构造102 8.6.3for循环语句.173 6.3.4算符优先分析算法.109 8.6.4出口语句n: 4175 6.3.5优先函数. 111 &6.58o0语句 176 6.3.6 算符优先分析法的 86.6 过程调用的四元式产生.17 局限性 116 8.7 说明语句的译 17 6.4练可 8.7.1简单说明句的翻译.179 8.7.2过程中的说明.179 第7章LR分析法 11 8.8 数组和结构的翻译 180 71 LR分析概述 88.1 数组说明和数组元 7,2LR(0)分析 118 素的引用 .180 7.2.1可归前级和子前级 ++119 88.2结构（记录）说明和引 7.2.2识别活前数的有限 用的韩译.+*”186 自动机. 121 89 练习 44188 7.2.3 活前及其可归前缀的 般计算方法· 122 第9章符号表 7.2.4CR(0)项目集规范族 9.1符号表的作用和地位.190 ,125 9.2符号的主要属性及作用+.191 7.3S1R(1)分析 ,132 9.3 符号表的组织. 44.196 7.4LR(1)分析. 139 9.3. 符号表的总体组织 7.4.1LR(1)项目集族的 9.3.2符号表项的挂列 91 物浩， 44*44140 9.3.3关键字域的组织.·201 7.4.21.R1)分析表的构造.141 9.3.4其它城的组织. 44202 75【A1.R1)分析 14 9.3.5 于推链城的组织.209 7.6二义性文法在LR分析中 符号表的管理 21 的应用. .149 9.4.1符号表的初始化 210 7.7统习. +.151 9.4.2符号的登录. 9。.3符号的查找. ,212 ·N
9.4.4符号表中分程序结构 11.4.1些主的将念.258 层次的管理 .213 11.4.2 数据流方程的一般 9.5练习 ,.40n216 258 11.4.3到达一定值数据流 第10章 日振程序运行时的储组织21 方程4年4 ·259 10. 数据空间的 种不同使用方法和 11.4.4可用表达式及其数据 管理方法 流方程 26 10.1.1静态存储分配 11.4. 活跃变量数据流方程.26 10.1.2动态存储分配.219 11.4.6复写传播. 266 10.1.3 找式动态存储分配.219 11.5练习.+.+4. .267 10.1.4 堆式动态存储分配 .21g 10.2栈式存储分配的实现 220 第12章 代码生成 。270 10.2.1简单的栈式存储分配的 12.1代码生成概述 实现· ,220 12.2 一个计算机模型. 10.22嵌套过程语言的栈式 12.3 一个简单的代码生成程.·271 222 12.3.1寄存器分配的原则.271 10.2.3分程序结构的存储 12.3.2 待用信息链表法 管国 .226 12.3.3代码生成算法 10.3参数传 230 12.4代码生成研究现状. 27 10.3.1 传值 23 12.4.1中间语言的选择.*275 10.3.2 传地址 12.4.2代码生成的自动化 10.3.3过程参数. 232 277 10.4过程调用、过程进入和过程 12.5练习 ,278 +4+233 10.5练习 .234 第13章编译程序实现的途径 4279 译理序的书写语言与T 第11章代码优化. 236 4279 11.1优化技术简介* 236 132编译程序的自展技术 27 1.1.】化技术介 236 13.3交又编译与编译程序的移植.281 11.2局部优化 239 13.4编译程序的构造工具.282 11.2.1基本块的划分 13.4.1 基于L.ALR(1)的语法 11.2.2基本块的变换.239 分析程序的生成器 11.2.3基木块的DAG表示·240 YACO 282 1.2.DAG的应用. 213 13.4.2恭于1山(2)文法的编 11.2. )DAG构造算法讨论 24 译器的构壶工具 11.3控制流分析和循环优化 (SD呢.EBNF.LL(2)283 11.3.1程序流图与循环*.247 13.43词法分析程序的 11.3.2循环 .248 生成器1EX .286 11.3. 循环的查找 13.5练习. 448101**41中2287 11.3.4可归约流图 11.3.5循环优化 附录A PL/0编译程序文本 .4.288 11.4数据流的分析与全局优化.257
附录B词法分析程序生成器LEX的使 的写法 325 用方法 306 C.4. 语法规则的书写格式.325 B.1 LEX概述 306 C.4.2语义动作.326 B.2LEX源程序的格式 307 C.4.3YACC解决二义性和冲突 B.3LEX用的正规式 4+307 的方法 327 B.4LEX源程序中的动作.310 C.4.4 语法分析中的错误 B.5识别规则的二义性 312 处理. .328 B.6LEX源程序中的辅助定义 C,5程序段部分.*.329 都分 .312 C.5,1主程序，： ,:329 B.7怎样在UNX系统中使 C.5.2错误信息报告程序.329 用LEX 31 C.5.3 词法分析程序 B.8LEX源程序例子 314 C.5.4其它程序段 ”33 B.9再谈上下文相关性的处现.315 C.6YACC源程序例子说明 331 B.10LEX源程序格式总结.317 C.6.1YACC的源程序例1.332 C.6.2YACC的源程序例2.334 附录C 语法分析程序自动产生器YACC 的使用方法. 0.319 附录D编译原理实验要求.339 C.1YACC概述- +++319 C.2YACC源程序的一般格式.320 附录E编译原理铺助教学软件功能介绍 C.3YACC源程序说明部分的写法 .320 和使用说明 .340 C.3.1 头文件表. 32 E1功能介绍 340 C.3.2宏定义4.32 E,1,1THPL0CA1的功能·340 C3.3数据举型定义. 32 E.1,2TH-CCAIS的功能·340 C.3.4全局变量定义. 32 E.2使用说明. 341 C.3.5 语法开始符定义 32 E.2.1 THPL.0CA1使用说明.31 C.3.6语义值类型定义* 32 E.2.2TH-CCAIS使用说明·342 C.3.7终结符定义.323 E.2.3其它补充说明.350 C.3.8运算符优先级及结合 定义 323 参考文献 35 C.A YACC源程序中语法规则部分
第1章编译程序概论 1.1什么是编译程序 编译程序是现代计算机系统的基本组成部分之一，而且多数计算机系统都含有不止 一个高级语言的编译程序，对有些高级语言甚至配置了几个不同性能的编译程序。从功 上看，一个编译程序就是一个语言翻译程序。它把一种语言（称作源语言）书写的程序翻译 成另一种语言（称作目标语言）的等价的程序。比如，汇编程序是一个翻译程序，它把汇编 语言程序翻译成机器语言程序，如果源语言是像FORTRAN,PASCAL或C那样的高级 语言，目标语言是像汇编语言或机器语言那样的低级语言，则这种翻译程序称作编译程 序。如果把编译程序看成一个“黑盒子”，它所执行的转换工作可以用图1.1来说明。 (蒙程序) (目标程序 图1.1绵详程序的功能 一个编轻程序的重要性体现在它使很多数计算机用户不必考虑与机器有关的繁琐细 节，使程序员和程序设计专家独立于机器，这对于当今机器的数量和种类持续不新地增长 的年代尤为重要。 使用过计算机的人都知道，除了编译程序外，还需要一些其它的程序才能生成一个可 在计算机上执行的目标程序。让我们分 析一下一个程序设计语言程序的典型 需预处理的辄程序 的处理过程（见图1.2），可以从中进- 预处理臀序 步了解编译程序的作用。 一个源程序有时可能分成几个模 程序 块存放在不同的文件里，将这些源程序 译程用 汇集在一起的任务，由一个叫做预处理 程序的程序来完成，有些预处理程序也 目标汇编程序 负责宏展开，像C语言的预处理程序要 工编程序 完成文件合并、宏展开等任务。图1.2 中的编译程序生成的目标程序是汇编 可再装配的机备代码 代码形式，需要经由汇编程序翻泽成可 装配/接一编辑程序 一可再装配目标文件 再装配的机器代码，再经由装配/连接 编辑程序与某些库程序连接成真正能 绝对机器代码 在机器上运行的代码。也就是说，一个 图1.2高级语言程序的处理过程 编译程序的输入可能要 一个或多个 1·