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

程序设计语言 编 译 原 理 主讲：赵会群,课程安排简介,实验时间： 实验一词法分析：3.27-4.17 实验二语法分析：4.24-5.15 实验地点： 计算机系实验中心（或计算中心）,考核办法: 平时作业完成情况占 10% 实验作业完成情况占 20% 期末考试成绩 占 70% 教材: 陈火旺等。程序设计语言编译原理， 国防工业出版社 参考书: 吕映芝。编译原理，清华大学出版社。 杜淑敏。编译程序设计原理，北京大学出版社。,联系方式: 电话：88803818; E-mail: 答疑时间和地点: 每次课下课后、周四晚 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是中间结果变量,第四阶段：优化,优化的任务： 对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效的目标代码。 优化的主要方面有： 公共子表达式的提取 循环优化 删除无用代码等等,例如： 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 Begin M:=10+K; N:=10+K End,的中间代码为：,优化后的代码为：,第五阶段：目标代码生成,这一阶段的任务是： 把中间代码变换成特定机器上的低级语言代码。这阶段实现最后的翻译，它的工作有赖于硬件系统结构和机器指令含义。 目标代码的形式： 绝对指令代码或可重定位的指令代码或汇编指令代码。如目标代码是绝对指令代码，则这种代码可立即执行。,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 编译程序与程序设计环境,程序设计环境： 编辑程序、连接程序、调试工具、编译程序等等。 例如： Visual C+、C+Builder、Visual J+等。,1.5 编译程序的生成,用低级语言实现： 用本机专用的机器语言和汇编语言实现。 用高级语言实