概论--电子工业出版社.ppt

编译原理 武汉理工大学 计算机科学与技术学院 编译原理 计算机科学与技术学院 何九周 教材： 编译原理(第二版)胡伦骏等编 电子工业出 版社 参考书： 编译原理吕映芝等编 清华大学出版社 编译原理学习与解题指南伍春香编著 华中科技大学出版社 Compiler Construction Principles and Practice ， Kenneth C. Louden 教材与参考书 学时 总学时56理论学时48实验学时8 在这一学期里，希望我们能共同努力 ，学好这门功课！ 教学目的 编译系统是现代计算机系统的基本组成之 一，编译程序构造的基本原理和技术不仅 应用于编译程序的设计，也广泛应用于一 般软件的设计和实现。本课程是计算机专 业、软件工程专业的一门十分重要的核心 专业课。 通过本课程的学习，旨在使学生掌握编 译的基本理论、原理和技术，并对编译程 序有较为具体的认识。使学生能运用所学 过的基本知识、着手开发系统程序，为今 后的工作（技术和理论研究）打下基础。 教学计划 1 编译原理概述 2学时 2 文法和语言 8学时 3 词法分析 8学时 4 自顶向下语法分析方法 6学时 5 自底向上语法分析法 6学时 6 语法制导翻译和中间代码生成 8学时 7 符号表 2学时 8 目标程序运行时的存储组织 2学时 9 代码优化 4学时 10 代码生成 2学时 学习要求 编译程序是一个系统性很强的软件。在 课程中我们按阶段进行讨论，但在学习时心 中一定要有系统的概念，把每个阶段放到整 个编译程序背景中学习，才不致将所学的内 容孤立化。通过课程的学习应掌握各个阶段 的功能和设计原则，以及在编译中的逻辑关 系。理解他们怎样作为一个整体完成编译任 务的，并且或多或少做些实践工作更能加深 理解。 第1章 编译概述 本章主要介绍在后面的章节中将要学 到什么内容。 第1章教学内容 了解：什么是翻译程序、编译程序、解释 程序； 明确编译程序的功能及其在计算机系统中 的作用； 了解源语言程序被编译为目标程序的整个 过程，这个过程一般划分为哪些阶段； 知道编译技术可用于哪类软件的设计和开 发。 一、什么是编译程序 【翻译程序】将源语言程序转换为目标语 言程序的等价的程序称为翻译程序。 某一种语言程序另一种语言程序 转换 源语言程序 目标语言程序 编译程序 【编译程序】将高级语言源程序翻译为低级 语言目标程序的程序称为编译程序。 高级语言程序低级语言程序编译程序 机器或汇编程序 编译程序的意义：使得多数计算机用户不必 考虑与机器有关的繁琐细节，使程序员和程 序专家独立于机器。 汇编程序 【汇编程序】将汇编语言源程序翻译为机器 语言目标程序的程序称为汇编程序。 汇编语言程序机器语言程序汇编程序 【反汇编程序】将机器语言源程序翻译为汇编 语言目标程序的程序称为反汇编程序。 高级语言有两种翻译途径： 编译方式与解释方式。 它们的主要区别在于是否产生目标程序 。 解释程序不产生目标程序，而是边 解释边执行源程序本身，是一种“会 话型”语言。 编译程序与解释程序的异同 二、高级语言程序的处理过程 需预处理的源程序 预处理的程序 源程序 目标汇编程序 可再装配的机器代码 编译程序 汇编程序 连接装配程序 可再装配的 目标代码 绝对机器代码 三、编译程序的工作过程 编译程序的工作，从输入源程序开始 到输出目标程序为止的整个过程，是非 常复杂的。但就其过程而言，它与人们 进行自然语言之间的翻译有许多相近之 处。 英汉翻译与编译的比较 【例如】英语句子 This is a book. 的翻译过程： 1、识别单词 2、“组词成句” 3、分析句子的含义 ，并进行初步翻译 4、修饰译文 5、写出最后译文 编译程序的翻译过程 类似： 1、词法分析 2、语法分析 3、语义分析与中间 代码生成 4、代码优化 5、目标代码生成 编译程序的5个阶段 编译程序的工作过程一般划分为五 个阶段： 词法分析 语法分析 语义分析与中间代码生成 优化 目标代码生成 1.词法分析 任务：从左至右读字符流的源程序，识别(拼 )单词。 【单词】单词是具有独立意义的最小语法单 位。 识别原则：词法规则 描述工具：正规式 正规文法 有穷自动机FA 自动生成工具：LEX 【例如】某赋值语句如下： yx1x2 * 60； 词法分析阶段识别出的单词序列为： 单词类型单词值 标识符(变量名) y 算符(赋值) = 标识符(变量名) x1 算符(加法) + 标识符(变量名) x2 算符(乘法) * 整数 60 界符 ； 2.语法分析 任务：依据源程序的语法规则把源程序的单 词序列组成更大的语法成分“组词成句 ” (表示成语法树) 。 识别原则：语法规则 描述工具：上下文无关文法 下推自动机PDA 自动生成工具：YACC 赋值语句的语法规则 := = := + := * :=( ) := := := 赋值语句 标识符表达式 表达式+ 表达式表达式 标识符整数 标识符 = 表达式 * 语 法 树 3.语义分析与中间代码生成 任务：对语法分析所识别出的各类语法范畴，分析 其含义，并进行初步翻译（产生中间代码）。 语义审查(静态语义) 上下文相关性 类型匹配 类型转换 识别原则：语义规则 描述工具：属性文法 实现方法：语法制导翻译 中间代码 所谓“中间代码”是一种含义明确、便于处理的 记号系统，它通常独立于具体的硬件。这种记 号系统或者与现代计算机的指令形式有某种程 度的接近，或者能够比较容易地把它变换成现 代计算机的机器指令。 许多编译程序采用了一种与“三地址指令”非常 近似的“四元式”作为中间代码，其形式是： (算符 , 运算对象1 , 运算对象2 , 结果) 常用的中间代码有：四元式，三元式，间接三元 式，逆波兰记号和树形表示等等。 中间代码生成示例 赋值语句 y= x1 + x2* 60 对应的四元式是： (1) (*,x2,60,t1) (2) (+,x1,t1,t2) (3) (=,t2,-,y) 4.优化 任务：对前段产生的中间代码进行加工变换 ，以期在最后阶段能产生出更为高效（省 时间和空间）的目标代码。 主要包括：公共子表达式的提取 循环优化 删除无用代码等等 优化所依循的原则：程序的等价变换规则。 优化示例 【例如】程序片断： for K：1 to 100 do begin M：I10 * K； N：J 10*K end 中间代码为： ( ：, 1, , K ) ( j , 100, K, （9）) ( * , 10, K, T1 ) ( , I, T1 , M ) ( * , 10, K, T2 ) ( , J, T2 , N ) ( , K, 1 , K ) ( j , , ,（2）) 循环中需做 300次加法 和200次乘 法 优化后的中间代码为： ( ：, I, , M ) ( ：, J, , N ) ( ：, 1, , K ) ( j , 100, K, （9）) ( , M, 10 , M ) ( , N, 10 , N ) ( , K, 1 , K ) ( j , , ,（4）) 循环中只 需做300次 加法 5.目标代码生成 任务：把中间代码（或经优化处理之后）变 换成特定机器上的低级语言代码。 生成原则：硬件系统结构和机器指令含义。 目标代码的形式： 绝对指令代码 可重定位的指令代码 汇编指令代码 目标代码生成示例 (*,x1 ,60.0,t1) (+,x2 ,t1 ,x1) movfx1,R2 mulf#60.0,R2 movfx2,R1 addfR2,R1 movfR1,x1 注意 上述编译过程的阶段划分只是一种典型的分 法，事实上并不是所有的编译程序都分成这 样几个阶段的。 有些编译程序对优化没有什么要求，优化阶 段就可省去。在某些情况下，为了加快编译 速度，中间代码产生阶段也可以去掉。有些 最简单的编译程序是在语法分析的同时产生 目标代码。但是，多数实用编译程序的工作 过程大致都像上面所说的那五个阶段。 其它 编译程序的另外两个重要的工作是表格管理 和出错处理。 编译过程中源程序的各种信息被保留在种种 不同的表格里，编译各阶段的工作都涉及到 构造、查找或更新有关的表格，因此需要有 表格管理的工作；如果编译过程中发现源程 序有错误，编译程序应报告错误的性质和错 误发生的地点，并且将错误所造成的影响限 制在尽可能小的范围内，使得源程序的其余 部分能继续被编译下去，有些编译程序还能 自动校正错误，这些工作称之为出错处理。 表格与表格管理 编译程序在工作过程中需要保持一系列 的表格，以登记源程序的各类信息和编 译各阶段的进展状况。合理地设计和使 用表格是编译程序构造的一个重要问题 。 在编译程序中最重要的一种表格是符号 表。 记录源程序中使用的名字 收集每个名字的各种属性信息 类型、作用域、分配存储信息 出错处理 一个编译程序不仅应能对书写正确的程序 进行翻译，而且应能对出现在源程序中的 错误进行处理。如果源程序有错误，编译 程序应设法发现错误，把有关错误信息报 告给用户。这部分工作是由专门的一组程 序（叫做出错处理程序）完成的。 出错处理程序的任务包括检查错误、报告 出错信息、排错、恢复编译工作。 四、编译程序的组成 编译过程的五个阶段的任务，再加上表 格管理和出错处理的工作可分别由几个 模块或程序完成，它们分别称作词法分 析程序、语法分析程序、语义分析程序 、中间代码生成程序、代码优化程序、 目标代码生成程序、表格管理程序和出 错处理程序。从而可给出一个典型的编 译程序结构框图，如图所示。 编译程序的组成 源程序 词法分析器 单词符号 语法分析器 语法单位 语义分析与中间代码生成器 中间代码 优化器 中间代码 目标代码生成器 目标代码 表 格 管 理 程 序 出 错 处 理 程 序 五、编译的前端与后端 o 常把编译的过程分为前端和后端。 o 前端：主要依赖于源语言而与目标机无关 。通常包括词法分析、语法分析、语义分析和 中间代码生成这些阶段，某些优化（中间代码 优化），也包括相应的出错处理和符号表管理 等工作。 o 后端：依赖于目标机而一般不依赖源语言 。后端包括目标代码生成和目标代码优化，以 及相关出错处理和符号表操作。 六、遍（pass） 所谓“遍”就是对源程序或源程序的中间结果从 头到尾扫描一次，并作有关的加工处理，生成 新的中间结果或目标程序。 Turbo C是一遍完成编译，以及预处理和后续处 理。 两遍编译： 1.进行词法分析、语法分析、语义分析，生成中间代 码作为文件保留，以及符号表文件。 2.优化后生成目标代码作为文件保留。 三遍编译： 3.对目标代码的优化。 七、编译程序涉及的三种语言 源语言：要深刻理解源语言(如 FORTRAN 、Pascal或 C)结构(语法)和含义(语义)； 目标语言：最终的目标语言还是机器语言 ，则必须搞清楚硬件的系统结构和操作系 统的功能； 宿主语言：编写编译程序的语言。 自编译程序：宿主语言是源语言。例如 PASCAL。 八、编译程序的生成 q手工 q机器语言 q汇编 q系统程序设计语言，自编译，移植，交叉 编译等方式 q自动构造工具lex yacc 九、编译程序与程序设计环境 编译程序无疑是实现高级语言的一个最重 要的工具。但支持程序设计人员进行程序设 计开发通常还需要其它一些工具：如编辑程 序、连接程序、调试程序等。编译程序与这 些程序设计工具一起构成所谓的程序设计环 境。 在一个程序设计环境中，编译程序起着中 心的作用。连接程序、调试程序、程序分析 等工具直接依赖于编译程序所产生的结果， 而其它工具的构造也常常要用到编译的原理 、方法和技术。 十、编译技术在软件工具中的应用 大部分系统软件与应用软件的开发通 常要用