目 录 前言. 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·
预处理程序来产生，另外，为得到能运行的机器代码，编译程序的输出可能仍需要进一步 地处理。 前面介绍过，编译程序的基本任务是将源语言程序翻译成等价的日标语言程序我们 知道，源语言的种类成千上万，从常用的诸如FORTRAN,PASCAL和C语言，到各种各 样的计算机应用领域的专用语言，而目标语言也是成千上万的，加上编译程序根据它们的 构造不同，所执行的具体功能的差异又分成了各种类型，比如：一趟编译、多趟编译的、具 有调试或优化功能的等等，尽管存在这些明显的复杂因素，但是任何编译程序所必须执行 的主要任务基本是一样的，通过理解这些任务，使用同样的基本技术，我们可以为各种各 样的源语言和目标语言设计和构造编译程序。 据说第一个编译程序的出现是在20世纪50年代早期，很难讲出确切的时间，国为当 初大量的实验和实现工作是由不同的小组独立完成的，多数早期的编译工作是将算术公 式翻译成机器代码。用现在的标准来衡量，当时的编译程序能完成的工作十分初步，如只 允许简单的单目运算，数据元素的命名方式有很多限制，然而它们莫定了对高级语言编译 系统的研究和开发的基础，20世纪50年代中期出现了FORTRAN等一批高级语言，相 应的一批编译系统开发成功。随着编译技术的发展和社会对编译程序需求的不断增长，20 世纪50年代末有人开始研究编译程序的自动生成工具，提出并研制编译程序的编译程 序。它的功能是以任一语言的词法规则、语法规则和语义解释出发，自动产生该语言的编 译程序。目前很多自动生成工具已广泛使用，如词法分析程序的生成系统LEX,语法分析 程序的生成系统YACC等，20世纪60年代起，不断有人使用自展技术来构造编译程序 自展的主要特征是用被编译的语言来书写该语言自身的编译程序。1971年，PASCAL的 编译程序用自展技术生成后，其影响就越来越大。 随着并行技术和并行语言的发展，处理并行语言的并行编译技术正在深入研究之中 将串行程序转换成并行程序的自动并行编译技术也正在深入研究之中， 1.2编译过程概述 编译程序完成从源程序到目标程序的翻译工作，是一个复杂的整体的过程。从概念上 来讲，一个编译程序的整个工作过程是划分成阶段进行的，每个阶段将源程序的一种表示 形式转换成另一种表示形式，各个阶段进行的操作在逻辑上是紧密连接在一起的，图1.3 给出了一个编译过程的各个阶段，这是一种典型的划分方法。事实上，某些阶段可能组合 在一起，这些阶段间的源程序的中间表示形式就没必要构造出来了，图1.3中将编译过程 划分成了词法分析，语法分析、语义分析、中间代码生成，代码优化和目标代码生成六个阶 段，我们将分别介绍各阶段的任务。另外两个重要的工作：表格管理和出错处理与上述六 个阶段都有联系，编译过程中源程序的各种信息被保留在种种不同的表格里，编译各阶段 的工作都涉及到构造、查找或更新有关的表格，因此需要有表格管理的工作：如果编译过 程中发现源程序有错误，编译程序应报告错误的性质和错误发生的地点，并且将错误所造 成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被编译下去，有些编译 程序还能自动校正错误，这些工作称之为出错处理。 ·2
我们从源程序在不同阶段所被转换成的表 示形式的不同来介绍各个阶段的任务。 源程序 词法分析阶段是编译过程的第一个阶 词法分析 段。这个阶段的任务是从左到右一个字符一个 字符地读入源程序，对构成源程序的字符流进 语法分析 行扫描和分解，从而识别出一个个单词（也称单 语义分析 司符号或符号)。这里所谓的单词是指逻辑上紧 密相连的一组字符，这些字符具有集体含义。比 中间代码生皮 如标识符是由字母字符开头，后限字母、数字字 代码优化 符的字符序列组成的一种单词。保留字（关键字 或基本字)是一种单词，此外还有算符，界符等 目标代码生成 等。例如某源程序片断如下 目标程序 begin var sum.first,count:real;sum : first+-count*l0end.词法分析阶段将构成这 图1.3编译的各个阶段 段程序的字符组成了如下单词序列： 1.保留字 begin 2.保留字 var 3.标识符 sum 4,逗号 5.标识符 first 6.逗号 7.标识符 count 8.目 号 9.保留字 real 10.分号 11.标识符 sum 12.赋值号 13.标识符 first 14.加号 15.标识符 count 16.乘号 17.整数 10 18.保留字end 19.界符 可以看出，五个字符即b,e,g,i和n构成了一个分类为保留字的单词begin,两个字 符即：和=构成了表示赋值运算的符号：=，这些单词间的空格在词法分析阶段都被滤 掉了。 我们使用idl,id2和id3分别表示sum,first和count三个标识符的内部形式，那么 经过词法分析后上述程序片断中的赋值语句sum:=-first-十count*l0则表示为id1= id2+id3*10 语法分析是编译过程的第二个阶段。语法分析的任务是在词法分析的基础上将单 词序列分解成各类语法短语，如“程序”，“语句”，“表达式”等等。一般这种语法短语，也称 语法单位，可表示成语法树，比如上述程序段中的单词序列： id1=id2+id3*10经语法分析得知其是PASCAI.语言的“赋值语句”，表示成如 图1.4所示的语法树或是图1.5所示的那种形式. 语法分析所依据的是语言的语法规则，即描述程序结构的规则，通过语法分析确定整 个输入串是否构成一个语法上正确的程序。 3▣
标识符 id3(count) 图1.4语句id1:=id2+id3*10的语法树 id2 id3 图1.5语句id1=id2+id3*10的语法树的另一种形式 程序的结构通常是由递归规则表示的，例如，我们可以用下面的规则来定义表达式： (1)任何标识符是表达式」 (2)任何常数（整常数、实常数）是表达式。 (3)若表达式1和表达式2都是表达式，那么：表达式1+表达式2 表达式1￥表达式2 (表达式1) 都是表达式 类似地，语句也可以递归地定义，如 (1)标识符=表达式是语句。 (2)while(表达式) do语句和 (表达式) then语句clse语句 都是语句。 上述赋值语句id1:=id2+id3*10之所以能表示成图1.4的语法树，依据的是赋值 语句和表达式的定义规则 词法分析和语法分析本质上都是对源程序的结构进行分析。但词法分析的任务仅对 源程序进行线性扫描即可完成，比如识别标识符，因为标识符的结构是字母打头的字母和 数字串，这只要顺序扫描输入流，遇到既不是字母又不是数字字符时，将前面所发现的所 有字母和数字组合在一起而构成单词标识符。但这种线性扫描则不能用于识别递归定义 的语法成分，比如就不能用此办法去匹配表达式中的括号， 语义分析阶段是审查源程序有无语义错误，为代码生成阶段收集类型信息，比如语 义分析的一个工作是进行类型审查，审查每个算符是否具有语言规范允许的运算对象，当 不符合语言规范时，编译程序应报告错误，如有的编译程序要对实数用作数组下标的情况 4
报告错误。又比如某些语言规定运算对象可被强制，那么当二目运算施于一整型和-一实型 时，编译程序应将整型转换成实型而不能认为是源程序的错误，假如在语句sum:=frs 十count*10中，*的两个运算对象：count是实型，10是整型，则语义分析阶段进行类型 审查之后，在语法分析所得到的分析树上增加一语义处理结点，表示整型变成实型的一目 算符inttoreal,则图l.5的树变成图1.6所示的那样， id? 图1,6桶入语义处理结点的树 中间代码生成在进行了上述的语法分析和语义分析阶段的工作之后，有的编译程 序将源程序变成一种内部表示形式，这种内部表示形式叫做中间语言或中间代码。所调 “中间代码”是一种结构简单，含义明确的记号系统，这种记号系统可以设计为多种多样的 形式，重要的设计原则为两点：一是容易生成：二是容易将它翻译成目标代码。很多编译程 序采用了一种近似“三地址指令”的“四元式”中间代码，这种四元式的形式为：（运算符，运 算对象1，运算对象2，结果)。 比如源程序sum=first-十count￥10可生成四元式序列，如图1.7所示，其中ti =1,2,3)是编译程序生成的临时名字，用于存放运算结果的。 (1) (inttoreal 10 t) (2) (￥ id3 t1t） (3) id2tata） (4) (= t id1) 图1.7中间代码 代码优化在此阶段的任务是对前阶段产生的中间代码进行变换或进行改造，目的 是使生成的目标代码更为高效，即省时间和省空间.比如图1.7的代码可变换为图1.8的 代码，仅剩了两个四元式而执行同样的计算。也就是编译程序的这个阶段已经把将10转 换成实型数的代码化简掉了，同时因为t,仅仅用来将其值传递给d1,也可以被化简掉， 这只是优化工作的两个方面，此外诸如公共子表达式的删除，强度削弱、循环优化等优化 工作将在第11章详细介绍。 (￥id310.0t) (id2 t id1) 图1.8优化后的中间代码 目标代码生成这一阶段的任务是把中间代码变换成特定机器上的绝对指令代码或 可重定位的指令代码或汇编指令代码。这是编译的最后阶段，它的工作与硬件系统结构和 指令含义有关，这个阶段的工作很复杂，涉及到硬件系统功能部件的运用、机器指令的选 5
择、各种数据类型变量的存储空间分配以及寄存器和后缓寄存器的调度等】 例如，使用两个寄存器(R,和R),可能生成如图1.9的某汇编代码。 (D)MOVF id3. (2)MULF #10.0, R (3)MOVE id2, R. (40 . (5)MOV id 图1.9目标代码 第一条指令将id3的内容送至寄存器R2,第二条指令将其与实常数10.0相乘，这里 用#表明10.0处理为常数，第三条指令将i2移至寄存器R,第四条指令加上前面计算 出的R:中的值，第五条指令将寄存器R,的值移到id1的地址中，这些代码实现了本节开 头给的源程序片断的赋值。 前面提到过上述编译过程的阶段划分是一典型处理模式，事实上并非所有的编译程 序都分成这样几个阶段，有些编译程序并不要生成中间代码，有些编译程序不进行优化， 优化阶段即可省去，有些最简单的编译程序在语法分析的同时产生目标指令代码，如第2 章介绍的P1,/0语言编译程序。不过多数实用的编译程序都采用上述几个阶段的工作过 程。 1.3编译程序的结构 上述编译过程的六个阶段的任务，再加上表格管理和出错处理的工作可分别由几个 模块或程序完成，它们分别称作词法分析程序、语法分析程序，语义分析程序、中间代码生 成程序、代码优化程序、目标代码生成程序、表格管理程序和出错处理程序，从而可给出一 个典型的编译程序结构框图，如图1.10所示。 源程字 词法分桥程序 表 语法分析程序 格 语义分析程序 中间代码生成程序 序 代码优化程序 目标代码生成程序 目标程序 困1.10编译程序结构框图 ·6