程序设计语言编 译 原 理主讲：赵会群课程安排简介章 节内 容总课时讲授课时实验课时第一章引 论22 第二章高级程序语言及其语法描述22 第三章词法分析18103.26-4.17第四章语法分析-自上而下分析88 第五章语法分析-自下而上分析1684.24-5.15第六章属性文法和语法制导翻译66 第七章语义分析及中间代码产生20125.21-6.1第八章符号表22 第十章优 化44 第十一章目标代码生成22 合 计805624(16) 实验时间： 实验一词法分析：3.27-4.17 实验二语法分析：4.24-5.15 实验地点： 计算机系实验中心（或计算中心） 考核办法: 平时作业完成情况占 10% 实验作业完成情况占 20% 期末考试成绩 占 70% 教材: 陈火旺等。程序设计语言编译原理， 国防工业出版社 参考书: 吕映芝。编译原理，清华大学出版社。 杜淑敏。编译程序设计原理，北京大学出版社。 联系方式: 电话：88803818; E-mail:zhaohqncut.edu.cn 答疑时间和地点: 每次课下课后、周四晚 8:00-9:00 五教8层软件体系结构研究室 五教11层教授办公室1106第一章 引论1.1 什么是编译程序 1.2 编译过程概述 1.3 编译程序结构 1.4 编译程序与程序设计环境 1.5 编译程序的生成1.1 什么是编译程序 编译程序起源： 计算机的机器语言：二进制形式的指令集合称为 该计算机的机器语言，它是计算机惟一能够直接 识别并接受的语言。 汇编语言：用助记符代替机器语言二进制编码的 一种语言，这就是汇编语言。但是计算机并不能 直接识别这种符号化语言，用汇编语言编写的程 序必须翻译成机器语言之后才能执行，这种“翻译” 是通过专门的软件汇编程序实现的。 高级语言：从具体机器中抽象出来，摆脱了依赖 具体机器的计算机程序设计语言。高级语言程序 需要翻译（编译）成最终能够直接执行的机器语 言程序才能执行。 编译程序： 能够把某一种语言程序（称为源语言程序 ）转换成另一种语言程序（称为目标程序 ），而后者与前者在逻辑上等价，这种程 序成为编译程序。 解释程序： 以该语言写的源程序作为输入，但不产生 目标程序，而是边解释边执行源程序本身 。高级语言程序 (源程序)解释程序计算机字节语言程序 或其他语言 编译程序分类： 诊断编译程序 帮助程序调试或测试 优化编译程序 提高代码效率 交叉编译程序 产生不同于其缩主机代码 可变目标编译程序 如果除与目标机相关的部分具有通用性1.2 编译过程概述 编译过程可大体上分为五个阶段： 词法分析 语法分析 语义分析与中间代码产生 优化 目标代码生成。第一阶段 词法分析 词法分析的任务： 输入源程序，对构成程序的字符串进行扫描和分 解，识别出一个个的单词符号。 单词符号： 构成语言的最小单元。如基本字 “if”，标识符， 常数123，算符 “+”和界符 “;”。 工具或方法 描述词法构词规则的有效工具是正规式和有限自 动机。 例如： 一个高级语言程序语句： for (I=1;I=100；I+) 词法分析从左侧开始扫描，逐一翻译该语句 后得到的单词符号为： for、(、I、=、；、1、I、=、100、；、I、+、)第二阶段：语法分析 语法分析的任务是： 在词法分析的基础上，根据语言的语法规 则，把单词符号串分解成各类语法单位。 工具或方法： 语法规则，通常用上下文无关文法描述。 例如： 对赋值语句Z=x+0.18*y的分析结果为： Z=为赋值语句，x+0.18*y为表达式。第三阶段：语义分析与中间代码产生 这一阶段通常包括两个方面的工作： 对每种语法范畴进行静态语义检查。如： 变量是否定义，类型是否正确等等。 根据语义规则进行中间代码的翻译。 中间代码: 是一种含义明确、便于处理的记号系统， 并独立于硬件系统。 工具或方法： 属性文法 例如：z=(x+0.418)*y/w的中间代码为：序号算符左操作数右操作数结果 (1) (2) (3)+ * /X T1 T20.418 Y WT1 T2 Z其中：T1和T2是中间结果变量第四阶段：优化 优化的任务： 对前段产生的中间代码进行加工变换，以 期在最后阶段能产生出更为高效的目标代 码。 优化的主要方面有： 公共子表达式的提取 循环优化 删除无用代码等等 例如： for K:=1 to 100 do Begin M:=I+10*K; N:=J+10*K End 优化结果 M=10； N=10; for K:=1 to 100 do BeginM:=10+K;N:=10+K End 的中间代码为：序号OPARG1ARG2RESULT注解（1）:=1K（2）j100K(9)（3）*10KT1（4）+IT1M（5）*10KT2（6）+JT2N（7）+K1K（8）j(2)（9） 优化后的代码为：序号OP ARG1 ARG2RESULT注解（1）:= IM（2）:= JN（3）:= 1K（4）j 100K(9)（5）+ M10M加法优于乘法（6）+ N10 N（7）+ K 1 K（8）j(4)（9）第五阶段：目标代码生成 这一阶段的任务是： 把中间代码变换成特定机器上的低级语言 代码。这阶段实现最后的翻译，它的工作 有赖于硬件系统结构和机器指令含义。 目标代码的形式： 绝对指令代码或可重定位的指令代码或汇 编指令代码。如目标代码是绝对指令代码 ，则这种代码可立即执行。1.3 编译程序的结构 1.3.1 编译程序总框 1.3.2 表格与表格管理 1.3.3 出错处理 1.3.4 遍 1.3.5 编译前端和后端1.3.1编译程序总框图1.1 编译程序总框源程序单词符号语法单位中间代码中间代码目标代码表 格管理出错处理语法分析器语法分析与中间代码产生器优化器目标代码生成器词法分析器1.3.2 表格与表格管理 表格作用： 编译程序在工作过程中需要保持一系列的 表格，以登记源程序的各类信息和编译各 阶段的进展状况。合理地设计和使用表格 是编译程序构造的一个重要问题。 表格管理的主要工作： 编译各阶段都涉及到构造、查找或更新有 关的表格。1.3.3 出错处理 出错处理作用： 一个好的编译程序应能最大限度地发现源 程序中的各种错误，准确地指出错误的性 质和发生错误的地点，并且能将错误所造 成的影响限制在尽可能小的范围内，使得 源程序在其余部分能继续被编译下去，以 便进一步发现其它可能的错误。如果不仅 能够发现错误，而且还能自动校正错误， 那当然就更好了。但是，自动校正错误的 代价是非常高的。 1.3.3 出错处理 错误特点： 编译过程的每一阶段都可能错误。其中，绝大多 数错误可以在编译的前三阶段检测出来。 错误常分为语法错误和语义错误两大类 语法错误是指源程序中不符合语法规则的错误， 它们可在词法分析或语法分析时检测出来。 语义错误是指源程序中不符合语义规则的错误， 这些错误一般在语义分析时检测出来，有的语义 错误要在运行时才能检测出来。语义错误通常包 括：说明错误、作用域错误、类型不一致等等。 1.3.4 遍 所谓“遍”就是对源程序或源程序的中间 结果从头到尾扫描一次，并作有关的加 工处理，生成新的中间结果或目标程序 。 一个编译程序究竟应分成几遍，如何划 分都与源语言、设计要求、硬件设备等 诸因素有关，因此难于统一划定。1.3.5 编译前端与编译后端 编译前端： 与源语言有关但与目标机无关的那些部分。包括 语法分析、语法分析、语义分析与中间代码产生 ，有时也把代码优化工作作为前端。 编译后端： 与目标机有关的部分，不依赖于源语言，而仅仅 依赖于中间代码，如与目标机有关的代码优化和 目标代码生成。 目的： 在中间语言的支持下，实现目标机改变。 如Java 的Bytecode可以实现跨平台运行。1.4 编译程序与程序设计环境 程序设计环境： 编辑程序、连接程序、调试工具、编译程 序等等。 例如： Visual C+、C+Builder、Visual J+等。1.5 编译程序的生成 用低级语言实现： 用本机专用的机器语言和汇编语言实现。 用高级语言实现：L1语言 代码L2语言语言程序L2语言目标语言程序转换支持 移植： 利用A机器上已有的高级语言L编写一个能够在B 机器上运行的高级语言L的编译程序。在A上实现L的B 上的编译A上实现L在B上 的编译程序在A上再一次编译 得到在B上的编译 程序 自编译方式： 先对语言的核心部分构造一个小小的编译 程序，再以它为工具构造一个能够编译更 多语言成分的较大编译程序。如此扩展下 去，就像滚雪球一样，越滚越大，最后形 成人们所期望的整个编译程序。小结 作业：