程序设计语言编 译原理主讲：赵会群

程序设计语言编译原理主讲 赵会群 课程安排简介 实验时间 实验一词法分析 3 27 4 17实验二语法分析 4 24 5 15实验地点 计算机系实验中心 或计算中心 考核办法 平时作业完成情况占10 实验作业完成情况占20 期末考试成绩占70 教材 陈火旺等 程序设计语言编译原理 国防工业出版社参考书 吕映芝 编译原理 清华大学出版社 杜淑敏 编译程序设计原理 北京大学出版社 联系方式 电话 88803818 E mail zhaohq 答疑时间和地点 每次课下课后 周四晚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的中间代码为 其中 T1和T2是中间结果变量 第四阶段 优化 优化的任务 对前段产生的中间代码进行加工变换 以期在最后阶段能产生出更为高效的目标代码 优化的主要方面有 公共子表达式的提取循环优化删除无用代码等等 例如 forK 1to100doBeginM I 10 K N J 10 KEnd 优化结果M 10 N 10 forK 1to100doBeginM 10 K N 10 KEnd 的中间代码为 优化后的代码为 第五阶段 目标代码生成 这一阶段的任务是 把中间代码变换成特定机器上的低级语言代码 这阶段实现最后的翻译 它的工作有赖于硬件系统结构和机器指令含义 目标代码的形式 绝对指令代码或可重定位的指令代码或汇编指令代码 如目标代码是绝对指令代码 则这种代码可立即执行 1 3编译程序的结构 1 3 1编译程序总框1 3 2表格与表格管理1 3 3出错处理1 3 4遍1 3 5编译前端和后端 1 3 1编译程序总框 1 3 2表格与表格管理 表格作用 编译程序在工作过程中需要保持一系列的表格 以登记源程序的各类信息和编译各阶段的进展状况 合理地设计和使用表格是编译程序构造的一个重要问题 表格管理的主要工作 编译各阶段都涉及到构造 查找或更新有关的表格 1 3 3出错处理 出错处理作用 一个好的编译程序应能最大限度地发现源程序中的各种错误 准确地指出错误的性质和发生错误的地点 并且能将错误所造成的影响限制在尽可能小的范围内 使得源程序在其余部分能继续被编译下去 以便进一步发现其它可能的错误 如果不仅能够发现错误 而且还能自动校正错误 那当然就更好了 但是 自动校正错误的代价是非常高的 1 3 3出错处理 错误特点 编译过程的每一阶段都可能错误 其中 绝大多数错误可以在编译的前三阶段检测出来 错误常分为语法错误和语义错误两大类语法错误是指源程序中不符合语法规则的错误 它们可在词法分析或语法分析时检测出来 语义错误是指源程序中不符合语义规则的错误 这些错误一般在语义分析时检测出来 有的语义错误要在运行时才能检测出来 语义错误通常包括 说明错误 作用域错误 类型不一致等等 1 3 4遍 所谓 遍 就是对源程序或源程序的中间结果从头到尾扫描一次 并作有关的加工处理 生成新的中间结果或目标程序 一个编译程序究竟应分成几遍 如何划分都与源语言 设计要求 硬件设备等诸因素有关 因此难于统一划定 1 3 5编译前端与编译后端 编译前端 与源语言有关但与目标机无关的那些部分 包括语法分析 语法分析 语义分析与中间代码产生 有时也把代码优化工作作为前端 编译后端 与目标机有关的部分 不依赖于源语言 而仅仅依赖于中间代码 如与目标机有关的代码优化和目标代码生成 目的 在中间语言的支持下 实现目标机改变 如Java的Bytecode可以实现跨平台运行 1 4编译程序与程序设计环境 程序设计环境 编辑程序 连接程序 调试工具 编译程序等等 例如 VisualC C Builder VisualJ 等 1 5编译程序的生成 用低级语言实现 用本机专用的机器语言和汇编语言实现 用高级语言实现 移植