编译原理(1).ppt

编译原理 1 山东师范大学信息科学与工程学院 课程的性质与任务 本课程地位属于计算机科学与技术专业的一门重要的专业必修课 本课程的学习有助于对语言的执行系统 程序语言的理解 通过本课程的学习 要掌握编译程序的一般构造原理 包括语言基础知识 词法分析程序设计原理和构造方法 各种语法分析技术和中间代码生成符号表的构造 代码优化 并行编译技术常识及运行时存储空间的组织等基本方法和主要实现技术 课程的地位 语言的发展 机器语言 汇编语言 高级语言 查询语言 标注语言 第1章编译程序概论 1 1什么是编译程序1 2编译过程概述1 3编译程序的结构1 4编译阶段的组合1 5编译技术和软件工具参考书 1 1什么是编译程序1 1 1语言处理程序 语言处理程序 把较高级语言编写的程序语义等价地变换成较低级语言程序的程序 汇编程序语言处理程序解释程序编译程序 源程序 目标程序 语言处理程序 0 语言的执行方式 解释方式 Basic 口译编译方式 C pascal 笔译 1 汇编程序 汇编程序 把用汇编语言编写的程序翻译成机器语言的程序 汇编语言是为特定的计算机或计算机系统设计的面向机器的语言 如 8086 8088PC Z 80 VAX汇编语言汇编的过程就是对汇编指令逐行进行处理 最终得到机器代码的过程 汇编语言程序 可重定位的机器语言程序 汇编程序 2 解释程序 解释程序 对用高级语言编写的程序进行逐句分析并立即得到结果 解释程序按源程序中语句的动态顺序逐句进行分析翻译 并立即予以执行 它不产生目标代码 BASICAPLLISPJava等语言就是采用解释方法实现的 计算结果 解释程序 源程序 初始数据 高级语言解释系统 interpreter 功能让计算机执行高级语言 basic lisp prolog 与编译程序的不同1 不生成目标代码2 能支持交互环境 同增量式编译系统 源程序初始数据 解释程序 计算结果 解释系统 直接对源程序中的语句进行分析 执行其隐含的操作 如 b 2 a b 2 编译程序writea 解释程序直接将4的值输出 显示 Int2StbLdbadd2Sta 生成代码 3 编译程序 编译程序 把用高级语言编写的源程序翻译成等价的低级语言 称作目标语言 程序 编译系统是编译程序和运行系统的合称 高级语言源程序 低级语言目标程序 编译程序 编译程序 续 一个编译程序把一个高级语言源程序翻译成目标程序的工作可分为前后衔接的六个阶段 词法分析 语法分析 语义分析 中间代码生成 代码优化及目标代码生成 大多数高级语言是采用编译的方法实现的 如PASCAL FORTRAN ADA C C PL 1 ALGOL60 ALGOL68 等等 1 1 2什么是编译程序 compiler 编译程序是现代计算机系统的基本组成部分 从功能上看 一个编译程序就是一个语言翻译程序 它把一种语言 称作源语言 书写的程序翻译成另一种语言 称作目标语言 的等价的程序 编译程序的功能 术语编译程序的源语言 源程序 编译程序的目标语言 目标程序 编译程序的实现语言 高级语言书写的程序 编译程序 低级语言程序 软件 计算机系统中的程序及其文档系统软件 居于计算机系统中最靠近硬件的一层 其他软件一般都通过系统软件发挥作用 他和具体的应用领域无关 如编译系统和操作系统等 语言处理系统 把软件语言书写的各种程序处理成可在计算机上执行的程序 软件语言 用于书写软件的语言 它主要包括需求定义语言 功能性语言 设计性语言 程序设计语言以及文档语言 预处理器 编译器 汇编器 装配连接编辑 骨架程序 源程序 目标汇编程序 可重定位机器代码 绝对机器码 可重定位目标文件库 高级语言程序的处理过程 语言转 变 换系统 C 编译器 C C Java Bytecode Java编译器 术语 编译程序 compiler 编译程序的源语言 源程序 sourcelanguage sourceprogram 编译程序的目标语言 目标程序 objectortargetlanguage objectortargetprogram 编译程序的实现语言 implementationlanguage 语言处理程序 languageprocessor 语言转 变 换 languagetransformation 1 2编译过程概述 编译逻辑过程词法分析语法分析语义分析中间代码生成代码优化目标代码生成 1 2 1词法分析 这个阶段的任务是从左至右 从上到下一个字符一个字符地读入源程序 对构成源程序的字符流进行扫描和分解 从而识别出一个个单词 varsum first count real sum first count 10 单词类型单词值标识符1 id1 sum算符 赋值 标识符2 id2 first算符 加 标识符3 id3 count算符 乘 整数10分号 又如一个C源程序片断 inta a a 2 词法分析后可能返回 单词类型单词值保留字int标识符 变量名 a界符 标识符 变量名 a算符 赋值 标识符 变量名 a算符 加 整数2界符 有关术语 词法分析 从左到右读字符流的源程序 识别 拼 单词 单词 具有独立意义的基本语法单位 保留字 具有特殊规定的意义 不允许用户将它们作为别用 是用户定义标识符的禁区 标识符 用来表示程序 过程 函数 类型 常量和变量等名称的符号 1 2 2语法分析 在词法分析的基础上 根据语言的语法规则 文法规则 把单词符号串分解成各类语法单位 如 短语 句子 程序段 和 程序 通过语法分解 确定整个输入串是否构成一个语法上正确的程序 例 符号串X 0 168 Y 经语法分析就可识别出这个字符串属于算术表达式 Y X 0 168 Y 语法分析所依循的是语言的语法规则 用产生式描述 sum first count 10规则 语法分析器读入单词 将它们组合成按产生式规定的各类语法单位 赋值语句 标识符 表达式 表达式 表达式 表达式 标识符 整数 标识符 表达式 id1 id2 id3 N 术语 语法 定义语言各语法成分的形式或结构 语法分析 依据源程序的语法规则把源程序的单词序列组成语法短语 表示成语法树 语法树 推导树 表示句型推导 或归约 的树型结构 语法树有助于理解一个句子语法结构的层次 1 2 3语义分析 语义审查 静态语义 上下文相关性类型匹配类型转换例 Programp Varrate real procedureinitial position initial rate 60 error error warning 语义分析的一个重要内容是类型检查 对表达式及语句中的各语法成分作类型检查和分析 如 Varcount real Varfirst real Varsum real sum first count 10 语义分析的一个重要内容是类型检查 上例中进行类型检查之后增加了内部节点inttoreal 术语 语法 用来定义语言中各语法成份的形式或结构 语义 用来规格各语法成份的含义和功能 即规定它们的属性或在执行时应进行的运算或操作 语义分析 检查源程序是否包含语义错误 并搜集类型 供后面的代码生成阶段使用 只有语法和语义正确的源程序才可被翻译成目标代码 语义分析程序需要进行频繁的造表和查表工作 语义分析之后生成一种介于源语言和目标语言之间的中间语言代码 中间代码有多种形式 三元式 四元式 逆波兰表示 树型结构例 a b c三元式 逆波兰表示式 abc 1 b c 树 2 a 1 a 四元式 bc b c a 1 2 4中间代码生成 id1 id2 id3 10因运算需要 需设置临时变量t1 t2 t3来存放中间运算结果 四元式 算符第一运算量第二运算量运算结果 1 inttoreal 10 t1 2 id3 t1 t2 3 id2 t2 t3 4 t3 id1 中间代码的几种形式 逆波兰表示 运算符在其运算量之后的表达式 三元式 OP ARG1 ARG2 四元式 OP ARG1 ARG2 RESULT 树 根结点OP 左子树ARG1 右子树ARG2 1 2 5代码优化 对前阶段产生的中间代码进行加工变换 以期在最后阶段能产生出更为高效 省时间和省空间 的目标代码 代码优化 id1 id2 id3 10 1 inttoreal10 t1 2 id3t1t2 3 id2t2t3 4 t3 id1 变换 1 id310 0t1 2 id2t1id1 代码优化 t1 b ct1 b ct2 t1 0t2 t1 t1t3 b ca t2t4 t2 t3a t4在本例中 b c的值没有改变 故t1 t3 由第二个表达式知道t2 t1 1 2 6目标代码生成 将前阶段产生的中间代码翻译为机器语言或汇编语言形式的目标程序 目标程序总是按某一具体计算机的机器语言或汇编语言来产生的 目标代码生成 id310 0t1 id2t1id1 movfid3 R2mulf 10 0 R2movfid2 R1addfR2 R1movfR1 id1 1 2 7符号表管理 记录源程序中使用的名字收集每个名字的各种属性信息类型 作用域 分配存储信息 Const1常量值 35Var1变量类型 实层次 2 在编译过程中 源程序中的标识符及其各种属性都要记录在符号表中 这些属性可以提供标识符的存储分配信息 类型信息 作用域信息等等 对于过程标识符 还要有参数信息 包括参数的个数和类型 实参和形参的结合方式等等 符号表是一种含记录的数据结构 通常一个标识符在符号表中占一个记录 记录中除了标识符的名字域之外 还有记录该标识符属性的域 符号表结构 名字 符号属性 1 2 8出错处理 编译的每一个阶段都会发现源程序的错误 在发现错误之后 一般要对其有一定的处理措施 因而编译还可继续执行 不会一有错误就停止编译工作 出错处理 errorhandling errorreportinganderrorrecovery 在词法分析中 能发现单词拼写错误 在语法分析中 检查单词串是否符合语法的结构规则 在语义分析中 编译程序进一步查出语法上虽正确但含有无意义的操作部分 如两个标识符相加 一个是数组名 一个是过程名 虽然语法上允许 但语义上不允许 各种错误 都应在相应的阶段进行处理 出错处理 errorhandling errorreportinganderrorrecovery 检查错误报告出错信息 错误种类及位置 校错及排错恢复编译工作 1 3编译程序的结构 components 词法分析程序语法分析程序语义分析程序中间代码生成程序代码优化程序目标代码生成程序符号表管理程序出错处理程序 出错处理 表格管理 1 4编译阶段的组合 分析 综合 synthesis 源程序的分析线性分析层次分析语义分析目标程序的综合编译的前端 frontend 这些阶段以来于源语言 与目标机无关 编译的后端 backend 依赖于目标机器的阶段 遍 趟 从头到尾扫描源程序 各种形式 一遍 pass 编译阶段和运行阶段存储结构 编译时运行时 名字表 目标代码缓冲区 编译用源程序中间表示各种表格 目标代码区 数据区 源程序缓冲区 1 5编译技术和软件工具 编译程序实现方式手工机器语言汇编系统程序设计语言自动构造工具lexyaccgcc 1 5 1编译程序的发展 计算模式 语言范式语言应用领域 编译程序 冯诺曼机体系结构并行体系结构嵌入系统 编译程序的发展 语言范型 paradigms 命令式 imperativelanguage 应用式 applicative 基于规则的 rule based 面向对象的 object oriented 编译程序执行环境批处理交互环境嵌入系统环境 1 语言范型 支持的计算模式 命令式 程序特点 语言执行的解释 编译技术发展快 语句1 改变机器状态系统语言语句2 内存自动化生成技术语句3 各种寄存器的内容 外存与万诺曼机的体系结构一般 应用式 函数式 程序特点 Functionn funetion2 funetion1 data 程序执行 执行一个个函数施用在数据上的变换最终得到的结果编译 语法分析容易 语义处理复杂 基于规则的语言 prolog yacc 程序特点 使能条件1 动作1使能条件2 动作2使能条件3 动作3面向对象语言 抽象数据类型 继承机制编译 动态绑定 2 执行环境 批处理环境 将源程序作为整体处理排除程序错误不能依靠用户的外部帮助交互环境 解释增量式编译嵌入式系统环境 交叉编译分布并行环境 并行编译程序创建和测试环境 独立编译编译和调试同时设计考虑 1 5 2编译技术和软件工具 结构化编辑器程序调试工具程序测试工具静态分析动态分析度量工具结构度量模块接口复杂度c分析工具 sourceinsight 高级语言转换工具广泛的语言领域数据库系统查询脚本语言置标语言 SGML HTML XML 1 5 3研究领域 并行编译技术交叉编译技术自展编译技术 1 并行化编译技术 目的 提高并行计算机体系结构的性能 超大规模计算的日益增长的需求高性能计算机并行软件 并行体系结构 单机速度 并行体系结构 途径1 途径2 并行体系结构编译技术支持串行程序并行化编译技术支持并行程序设计语言编译依赖于目标机的优化 低层 性能发挥 并行算法复杂 难掌握 难编程开发并行软件的困难