编译原理第1章引论.ppt

编译原理,主讲：曹阳,编译原理,第1章 引 言,1.1 什么叫编译程序 1.2 编译过程概述 1.3 编译程序的结构 1.4 编译程序的生成,第1章 引 言,教学目的,掌握编译程序的概念,了解编译的思想； 了解编译程序的分类; 理解编译程序的构成及各组成部分的作用； 了解编译程序的生成.,教学重点与难点,本章重点： 编译的概念； 编译程序的构成。 本章难点 ： 编译程序的构成及组成部分作用。,第1章 引言,1.1什么叫编译程序,问题：在计算机上执行一个高级语言程序一般要分几步？执行方式有几种？,1.1 什么叫编译程序,编译程序是现代计算机系统的基本组成部分. 从功能上看，一个编译程序就是一个语言翻译程序,它把一种语言(称作源语言)书写的程序翻译成另一种语言(称作目标语言)的等价的程序.,编译程序的分类（用途和侧重）,诊断编译程序； 优化编译程序； 交叉编译程序； 可变目标编译程序,专门用于程序的开发和调试,1.1 什么叫编译程序,编译程序的分类（用途和侧重）,诊断编译程序； 优化编译程序； 交叉编译程序； 可变目标编译程序,着重提高目标代码的效率,1.1 什么叫编译程序,编译程序的分类（用途和侧重）,诊断编译程序； 优化编译程序； 交叉编译程序； 可变目标编译程序,一个编译程序产生不同于其宿主机的机器代码 宿主机：运行编译程序的计算机,1.1 什么叫编译程序,编译程序的分类（用途和侧重）,诊断编译程序； 优化编译程序； 交叉编译程序； 可变目标编译程序,如果不需要重写编译程序中与机器无关的部分就能改变目标机； 目标机：运行编译程序所得的目标代码的计算机,1.1 什么叫编译程序,1. 2编译过程概述（编译器的组成）,任务：输入源程序，对构成源程序的字符串进行扫描和分析，识别出一个个的单词（符号）如关键字，标识符，常数，算符，界符。 例: for(i=1;i=5;i+) 词法分析结果如下： 关键字 for 界符 （ ,1. 2编译过程概述（编译器的组成）,又如一个C源程序片断： int a; a = a + 2; 词法分析后返回: 单词类型 单词值 保留字 int 标识符(变量名) a 界符 ; 标识符(变量名) a 算符(赋值) = 标识符(变量名) a 算符(加) + 整数 2 界符 ；,1. 2编译过程概述（编译器的组成）,任务：在词法分析的基础上，根据语言的语法规则，把单词符号分解成各类语法单位（如短语、句子等），并构造一棵能够正确反映该结构的语法树。 作用：通过语法分析确定整个输入是否构成语法上正确的“程序”。 注意：词法分析是种线性分析，而语法分析是一种层次分析。,1. 2编译过程概述（编译器的组成）,例：position := initial + rate * 60 ; 规则 :=“:=” :=“+” :=“*” :=“(”“)” := := :=,1. 2编译过程概述（编译器的组成）,赋值语句,标识符,表达式,表达式,+,表达式,表达式,标识符,整数,标识符,:=,表达式,*,position := initial + rate * 60 ;,1. 2编译过程概述（编译器的组成）,id1:=id2+id3*N,1. 2编译过程概述（编译器的组成）,任务：对语法分析所识别出的各类语法范畴，遵循语言的语义规则分析其含义是否正确。,1. 2编译过程概述（编译器的组成）,任务：语义分析的基础上按语言的语义规则进行初步的翻译（产生中间代码） 中间代码：是一种含义明确、便于处理的记号系统，它通常独立具体的硬件； 表示形式：四元式、三元式、间接三元式等,1. 2编译过程概述（编译器的组成）,例1：将id1:= id2 + id3 * 60表示成四元式 (1) (inttoreal, 60 - t1 ) (2) (* , id3 t1 t2 ) (3) (+ , id2 t2 t3 ) (4) (:= , t3 - id1 ),例2：把Z=（X+0.418）*Y/W翻译成四元式（教材）,1. 2编译过程概述（编译器的组成）,任务：对前阶段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效的目标代码。 根据范围不同分为：局部优化、循环优化、全局优化。 优化的主要方面有：公共子表达式的提取、循环优化、删除无用代码 优化的原则：等价变化 例见教材,1. 2编译过程概述（编译器的组成）,id1:= id2 + id3 * 60 (1) (inttoreal 60 - t1 ) (2) ( * id3 t1 t2 ) (3) ( + id2 t2 t3 ) (4) ( := t3 - id1 ) 变换 （1） ( * id3 60.0 t1 ) ( 2）（ + id2 t1 id1 ),1. 2编译过程概述（编译器的组成）,t1 = b* c t1 = b* c t2 = t1+ 0 t2 = t1 + t1 t3 = b* c a = t2 t4 = t2 + t3 a = t4,1. 2编译过程概述（编译器的组成）,任务：把中间代码变换成特定机器上的低级语言代码（目标代码） 目标代码形式：绝对指令代码、可重定位指令代码、汇编指令代码,1. 2编译过程概述（编译器的组成）,1.3 编译程序的结构,编译程序的总框 如图所示：,1.3 编译程序的结构,1.3.2 表格与表格管理,常用的表格：符号表、常数表、标号表、入口名表、过程引用表。 符号表：记录源程序中使用的名字收集每个名字的各种属性：信息类型、作用域、分配存储信息,Const1 常量 值：35 Var1 变量 类型：实 层次：2,例：position = initial + rate 60,1.3.2 表格与表格管理,1.3.3 出错处理,检查错误、报告出错信息、排错、恢复编译工作 源程序中的错误通常分为语法错误和语义错误， 在编译的前三个阶段就可以检测出来,1.3.3 出错处理,1.3.4 遍（编译程序的逻辑结构）,1) 定义：就是对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。 2) 分类：单遍扫描编译程序和多遍扫描编译程序,注意：既可以将几个不同的阶段合为一遍，也可以把一个阶段的工作分为若干遍，当一遍中包含若干阶段时，各阶段的工作是穿插进行的。,1.3.4 遍,一遍扫描即可完成整个编译工作的称为一遍扫描编译程序,其结构为：,1.3.5 编译的前端与后端,编译的前端（front end）：主要与源语言有关但与目标机无关的那些部分组成。 编译的后端（back end）：包括编译程序中与目标机有关的那些部分。 通常后端不依赖于源语言而仅仅依赖于中间语言。,1.3.5 编译的前端与后端,1.3.5 编译的前端与后端,1.4 编译程序的生成,1.4 编译程序的生成,实现方式 手工 机器语言 汇编 系统程序设计语言 自动构造工具lex yacc gcc,例：如果A机器上已有一个用A机器代码实现的某高级语言L1的编译程序，则我们可以用L1语言编写另一种高级L2的编译程序，把写好的L2编译程序经过L1编译程序编译后就可得到A机器代码实现的L2编译程序如图所：,1.4 编译程序的生成,第1章 小结,内容 1 什么是编译程序 2 编译过程和编译程序的结构 本章没有难以理解的内容,重点对编译程序的功能和结构做一综述,要