编译 第一章 编译技术原理.ppt

编译技术原理编译技术原理 2 课课 程程 要要 求求 n n 熟练掌握熟练掌握c c、pascalpascal语言的编程、语法结构语言的编程、语法结构 ； n n 会一种程序设计语言的编程；会一种程序设计语言的编程； n n 会一种数据库开发语言，或熟悉文件的管理会一种数据库开发语言，或熟悉文件的管理 ； n n 按课程的进程，按时完成课程设计按课程的进程，按时完成课程设计 n n 按时完成作业按时完成作业 n n 认真听讲，认真作笔记，上课不得迟到早退认真听讲，认真作笔记，上课不得迟到早退 n n 上课不得喧哗上课不得喧哗 3 第一章 引第一章 引 论论 一、什么是编译程序一、什么是编译程序 使用过现代计算机的人都知道，现代的编程软件，越来越趋使用过现代计算机的人都知道，现代的编程软件，越来越趋 向于智能化、自然语言化，越来越高级，但是，通过前期课程向于智能化、自然语言化，越来越高级，但是，通过前期课程 的学习，大家都知道，计算机是不能识别自然语言或高级语言的学习，大家都知道，计算机是不能识别自然语言或高级语言 ，只能识别机器语言，那么我们的，只能识别机器语言，那么我们的高级语言程序是如何在计算高级语言程序是如何在计算 机上执行的呢？机上执行的呢？ 在计算机上执行一个高级语言程序一般要分两步：在计算机上执行一个高级语言程序一般要分两步： 第一步：用一个翻译程序把高级语言翻译成机器语言程序；第一步：用一个翻译程序把高级语言翻译成机器语言程序； 第二步：运行所得的机器语言程序求得计算结果。第二步：运行所得的机器语言程序求得计算结果。 第二步我们暂时不考虑，那么第一步“翻译程序”是我们这门 课讨论的重点，什么样的程序叫翻译程序？翻译程序是如何翻 译的？ 世界上第一个编译程序fortran编译程序是20世纪50年代 中期研制成功的。 4 第一章 引第一章 引 论论 一、什么是编译程序一、什么是编译程序 定义定义：假设，：假设，slsl指源语言程序，指源语言程序，tltl指目标语言程序，则：指目标语言程序，则： 1.1.翻译程序把翻译程序把slsl变换为变换为tltl的程序，的程序，slsl与与tltl逻辑上等价。逻辑上等价。 2.2.编译程序编译程序slsl为高级语言、为高级语言、tltl为低级语言的翻译程序。为低级语言的翻译程序。 3.3.汇编程序汇编程序slsl为汇编语言程序，为汇编语言程序，tltl为机器语言程序。为机器语言程序。 4.4.解释程序逐条翻译，且立即执行，不生成目标程序。解释程序逐条翻译，且立即执行，不生成目标程序。 分类分类：根据侧重和用途，编译程序进一步划分：根据侧重和用途，编译程序进一步划分： 1. 1.诊断编译程序诊断编译程序: :专门用于帮助程序的开发和调试的编译程序专门用于帮助程序的开发和调试的编译程序. . 2. 2.优化编译程序优化编译程序: :着重于提高目标代码效率的编译程序着重于提高目标代码效率的编译程序. . 3. 3.交叉编译程序交叉编译程序: :运行编译程序的计算机称运行编译程序的计算机称宿主机宿主机，运行编译，运行编译 程序所产生目标代码的计算机称程序所产生目标代码的计算机称目标机目标机，如果一个编译程序产，如果一个编译程序产 生不同于其宿主机的机器代码。生不同于其宿主机的机器代码。 4. 4.可变目标编译程序：如果不需重写编译程序中与机器无关的可变目标编译程序：如果不需重写编译程序中与机器无关的 部分就能改变目标机的编译程序。部分就能改变目标机的编译程序。 5 第一章 引第一章 引 论论 二、编译过程概述二、编译过程概述 编译程序的过程，从输入源程序到输出目标程序为止的整 编译程序的过程，从输入源程序到输出目标程序为止的整 个过程，非常复杂，但是从形式和操作步骤上来说，与自然语个过程，非常复杂，但是从形式和操作步骤上来说，与自然语 言的翻译很相近。言的翻译很相近。 例如：把引文翻译成中文的步骤：例如：把引文翻译成中文的步骤： 1. 1.识别出句子中的一个个单词识别出句子中的一个个单词; ; 2. 2.分析句子的语法结构分析句子的语法结构; ; 3. 3.根据句子的含义进行初步翻译根据句子的含义进行初步翻译; ; 4. 4.对译文进行修饰对译文进行修饰; ; 5. 5.写出最后的译文写出最后的译文 按照编译程序的执行过程和它所完成的任务，可把编译过按照编译程序的执行过程和它所完成的任务，可把编译过 程分为五个阶段程分为五个阶段: :词法分析词法分析、语法分析语法分析、语义分析与中间代码生语义分析与中间代码生 成成、优化优化、目标代码生成目标代码生成。 又把五阶段分为两大部分：又把五阶段分为两大部分：分析分析 和 和 综合。综合。 分析部分包括：词法分析、语法分析、语义分析。 分析部分包括：词法分析、语法分析、语义分析。 综合部分包括：中间代码生成、代码优化、目标代码生成 综合部分包括：中间代码生成、代码优化、目标代码生成 。 6 1.1.词法分析词法分析 n n 任务任务：输入源程序，对构成源程序的字符串进行扫描和分：输入源程序，对构成源程序的字符串进行扫描和分 解，过滤编辑符号，按词法规则分解为单词序列。解，过滤编辑符号，按词法规则分解为单词序列。 单词分类单词分类：基本字（：基本字（ifif、elseelse、forfor、whilewhile等）、标等）、标 识符、识符、 常数、算符、界符（标点和括号）。常数、算符、界符（标点和括号）。 n n 例如例如赋值语句：赋值语句： position:=initial+rate*60;position:=initial+rate*60; 词法分析的结果是识别出下列单词符号： 词法分析的结果是识别出下列单词符号： 标识符 标识符 positionposition 赋值号 赋值号 : : 标识符 标识符 initialinitial 加号 加号 标识符 标识符 raterate 乘号 乘号 * * 整常数 整常数 6060 分号 ；分号 ； 7 1.1.词法分析词法分析 n n 在词法分析阶段的工作中，所依循的是语言的词法规则（在词法分析阶段的工作中，所依循的是语言的词法规则（ 或称构词规则）或称构词规则）. . n n 描述词法规则的有效工具是：正规式和有限自动描述词法规则的有效工具是：正规式和有限自动 机。机。 n n 编译器的词法分析也叫编译器的词法分析也叫线性分析线性分析或或扫描扫描 n n 练习题：练习题： pascalpascal语言的循环语句：语言的循环语句： for i:=1 to 100 do for i:=1 to 100 do 基本字基本字 forfor 标识符标识符 i i 赋值号赋值号 := := 整常数整常数 1 1 基本字基本字 toto 整常数整常数 100 100 基本字基本字 dodo 82 2、语法分析、语法分析（简称为分析 ） n n 任务任务：在词法分析的基础上，根据语法规则，把单根据语法规则，把单 词序列分解为各种语法单位。词序列分解为各种语法单位。 n n 语法单位：程序、程序段、语句、短语、表达式。语法单位：程序、程序段、语句、短语、表达式。 n n 词法分析把记号流按语言的语法结构层次地分组，词法分析把记号流按语言的语法结构层次地分组， 例如：对赋值语句： 例如：对赋值语句：position:=initial+rate*60;position:=initial+rate*60; 进行语法分析可得到如下所示的层次结构，称为语进行语法分析可得到如下所示的层次结构，称为语 法分析树，简称法分析树，简称语法树语法树（或（或分析树分析树）。）。 赋值语句 表达式 表达式 标识符 position + 表达式 标识符表达式 标识符 表达式 数initial rate60 * = ： 9 分析树的层次结构可以用递归规则表示。例如：下列规分析树的层次结构可以用递归规则表示。例如：下列规 则定义包含、则定义包含、* *运算的运算的表达式表达式： 1. 1.任意一个标识符是一个表达式；任意一个标识符是一个表达式； 2. 2.任意一个数是表达式；任意一个数是表达式； 3. 3.如果如果e1e1和和e2e2都是表达式，则都是表达式，则 e1+e2e1+e2 e1*e2e1*e2 (e1)(e1) 都是表达式。都是表达式。 例：对赋值语句：例：对赋值语句：position:=initial+rate*60position:=initial+rate*60 由规则由规则1 1得：得：initial initial 和和rate rate 都是表达式都是表达式 由规则由规则2 2得：得：6060是一个表达式是一个表达式 由规则由规则3 3得：得：rate*60rate*60是一个表达式；是一个表达式； initial+rate*60initial+rate*60是一个表达式。是一个表达式。 类似的，可以用下列规则递归的定义类似的，可以用下列规则递归的定义语句语句： 1 1、如果、如果id1id1是一个标识符，是一个标识符，e2e2是一个表达式，则是一个表达式，则 id1:id1:e2e2 是一个语句。 是一个语句。 2 2、如果、如果e1e1是一个表达式，是一个表达式，st2st2是一个语句，则是一个语句，则 while(e1) st2while(e1) st2 和和 if(e1) st2if(e1) st2 都是语句。都是语句。 10 3、语义分析 n n 任务：对源程序进行任务：对源程序进行语义检查语义检查和和类型检查类型检查。 n n 语义分析使用语法分析确定的层次结构表示表达式和语句。语义分析使用语法分析确定的层次结构表示表达式和语句。 n n 类型检查是语义分析的一个重要部分，按照语言的类型规则类型检查是语义分析的一个重要部分，按照语言的类型规则 检查和每个运算符相关的操作数。检查和每个运算符相关的操作数。 例：例： 1 1、当数组下标为实数时，许多语言要求编译程序报告错误；、当数组下标为实数时，许多语言要求编译程序报告错误； 2 2、一般允许二元运算符的操作数既可为整数，也可为实数，运、一般允许二元运算符的操作数既可为整数，也可为实数，运 算时要进行类型转换。算时要进行类型转换。 :=:= positionposition+ initialinitial * * raterate 6060 (a)(a)紧缩形式表示的分析树紧缩形式表示的分析树 :=:= positionposition+ initialinitial * * raterate 6060 inttorealinttoreal (b)(b)语义分析插入整型到实型的转换语义分析插入整型到实型的转换 11 在以上 在以上分析分析的各阶段里，编译程序都把源程序变换成便的各阶段里，编译程序都把源程序变换成便 于下一阶段处理的内部表示形式。于下一阶段处理的内部表示形式。 对上述语句经每一阶段分析后产生的内部表示形式如下对上述语句经每一阶段分析后产生的内部表示形式如下 图所示，其中的图所示，其中的id1id1、id2id2和和id3id3分别表示词法分析器对标识分别表示词法分析器对标识 符符positionposition、initialinitial和和raterate产生的记号。产生的记号。 position:position:=initialinitial+raterate*60*60 词法分析词法分析 id1:id1:=id2id2+id3id3*60*60 :=:= id1 id1+ id2 id2 * * id3 id3 6060 语法分析语法分析 :=:= id1 id1+ id2 id2 * * id3 id3 6060 inttorealinttoreal 语义分析语义分析 12 4 4、中间代码的生成、中间代码的生成 n n 任务：对源程序进行初步翻译的工作，生成中间代码。任务：对源程序进行初步翻译的工作，生成中间代码。 n n 中间代码的特点：中间代码的特点： 结构简单、语义明确、易于转换、易于优化。 结构简单、语义明确、易于转换、易于优化。 n n 中间代码的形式：中间代码的形式： 前缀式、三地址代码、四元式等。 前缀式、三地址代码、四元式等。 n n 三地址代码由指令序列组成，每条指令最多有三个操作数。三地址代码由指令序列组成，每条指令最多有三个操作数。 n n 四元式的形式是：（算符，左操作数，右操作数，结果）四元式的形式是：（算符，左操作数，右操作数，结果） 例如：由语义分析得到的分析树可得到 例如：由语义分析得到的分析树可得到表达式表达式 position:=initial+rate*60position:=initial+rate*60的三地址代码表示形式为：的三地址代码表示形式为： temp1:=inttoreal(60)temp1:=inttoreal(60) temp2:=id3*temp1temp2:=id3*temp1 temp3:=id2+temp2temp3:=id2+temp2 id1:=temp3id1:=temp3 表达式表达式position=initial+rate*60position=initial+rate*60的四元式表示形式为：的四元式表示形式为： (inttoreal()(inttoreal()，6060，t1t1） (* (* ，id3id3，t1t1，t2)t2) (+(+，id2id2，t2t2，t3)t3) (=(=，t3 t3 ， ，id1)id1) n n 练习题：练习题： 写出：写出：z:=(x+0.418)*y/wz:=(x+0.418)*y/w的四元式和三地址代码的四元式和三地址代码 13 5 5、代码优化、代码优化 n n 任务：对中间代码进行加工变换，提高目标代码的效率（任务：对中间代码进行加工变换，提高目标代码的效率（ 省时间、省空间）省时间、省空间） n n 优化的主要方面有：循环优化、公因子提取、强度削弱等优化的主要方面有：循环优化、公因子提取、强度削弱等 n n 例如：对前面得到的三地址代码表示的中间代码，可优化例如：对前面得到的三地址代码表示的中间代码，可优化 为用下面两条指令表示：为用下面两条指令表示： temp1:=id3*60.0temp1:=id3*60.0 id1:=id2+temp1id1:=id2+temp1 又如，对 又如，对c c语言程序片段：语言程序片段： k=1;k=1; while(k100k100 n y 中间代码为：优化后代码为： k=1k=1 m=im=i n=jn=j m=m+10m=m+10 n=n+10n=n+10 k=k+1k=k+1 k100k100 n y 需做300次加法 200次乘法 只需做只需做300300次加法次加法 15 6 6、目标代码生成、目标代码生成 n n 任务：把中间代码（或经优化后的代码）变换成特定机器上的任务：把中间代码（或经优化后的代码）变换成特定机器上的绝对指令代绝对指令代 码码或或可重新定位的指令代码可重新定位的指令代码或或汇编指令代码汇编指令代码。 如果目标代码是如果目标代码是绝对指令代码绝对指令代码，则可立即执行。，则可立即执行。 如果目标代码是如果目标代码是汇编指令代码汇编指令代码，则需经汇编器汇编之后才可运行。，则需经汇编器汇编之后才可运行。 多数编译程序产生的目标代码都是多数编译程序产生的目标代码都是可重新定位的指令代码可重新定位的指令代码，在运行之前必，在运行之前必 须借助连接装配程序把各个目标模块连接在一起，确定程序变量（或常数须借助连接装配程序把各个目标模块连接在一起，确定程序变量（或常数 ）在主存中的位置，使之成为可以独立运行的绝对指令代码程序。）在主存中的位置，使之成为可以独立运行的绝对指令代码程序。 n n 此阶段的一个关键问题是寄存器分配。此阶段的一个关键问题是寄存器分配。 n n 例如：使用寄存器例如：使用寄存器r1r1和和r2r2，代码代码 temp1:=id3*60.0 temp1:=id3*60.0 id1:=id2+temp1 id1:=id2+temp1可以翻译成如下的代码：可以翻译成如下的代码： movf id3,r2movf id3,r2 mulf #60.0,r2 mulf #60.0,r2 movf id2,r1 movf id2,r1 addf r2,r1 addf r2,r1 movf r1,id1 movf r1,id1 16 一个语句的翻译过程示意图一个语句的翻译过程示意图 temp1:=id3*60.0 id1:=id2+temp1 中间代码生成器 temp1:=inttoreal(60) temp2:=id3*temp1 temp3:=id2+temp2 id1:=temp3 代码优化器 代码生成器 movf id3,r2 movf id3,r2 mulf #60.0,r2 mulf #60.0,r2 movf id2,r1 movf id2,r1 addf r2,r1 addf r2,r1 movf r1,id1movf r1,id1 从源程序到中间 代码生成产品 17 三、编译程序的结构三、编译程序的结构 源程序源程序 词法分析器 语法分析器 语义分析器 中间代码生成器 代码优化器 目标代码生成器 目标程序目标程序 符号表管理器符号表管理器 错误处理器错误处理器 分析 部分 综合 部分 18 符号表管理 符号表符号表 是为每个标识符保存一个记录的数据结构，记录是为每个标识符保存一个记录的数据结构，记录 着每着每 一个表示符的属性。一个表示符的属性。 符号表在各个阶段收集的信息一般不同。符号表在各个阶段收集的信息一般不同。 例如：在例如：在c c，pascalpascal语言中的变量定义语句语言中的变量定义语句 c c 语言语言: : real :position,initial,rate;real :position,initial,rate; pascal pascal语言语言: : var position,initial,rate:real;var position,initial,rate:real; c c语言中在读到变量名的时候，变量的属性已经知道，语言中在读到变量名的时候，变量的属性已经知道， 可以一起写入符号表，而可以一起写入符号表，而pascalpascal语言中，词法分析器在语言中，词法分析器在 程序扫描时，读到变量名的时候，并不知道表示符的属性程序扫描时，读到变量名的时候，并不知道表示符的属性 ，所以，符号表并不一定就记载有表示符的属性。，所以，符号表并不一定就记载有表示符的属性。 19 出错处理出错处理 n n 一个好的编译程序不但能一个好的编译程序不但能最大限度最大限度的发现错误，的发现错误， 准确地指出错误的性质和发生错误的地点，而且准确地指出错误的性质和发生错误的地点，而且 能够把错误的能够把错误的范围缩小范围缩小到尽可能小的范围，使程到尽可能小的范围，使程 序的其他部分能继续编译下去；如果不仅能发现序的其他部分能继续编译下去；如果不仅能发现 错误，而且能够知道错误，而且能够知道校正校正错误就更好啦。错误就更好啦。 n n 源程序钟的错误分为语法错误和语义错误源程序钟的错误分为语法错误和语义错误 语法错误：源程序中不符合语法或词法规则的语法错误：源程序中不符合语法或词法规则的 错误，可在语法或词法分析中检测出来。（非法错误，可在语法或词法分析中检测出来。（非法 字符、括号不配、缺少等）字符、括号不配、缺少等） 语义错误：源程序中部符合语义规则的错误，语义错误：源程序中部符合语义规则的错误， 一般在语义分析中检测出来，但有的要在运行时一般在语义分析中检测出来，但有的要在运行时 才能检测出来。（说明错误、作用域错误、类型才能检测出来。（说明错误、作用域错误、类型 不一致等）不一致等） 20 遍遍 前面介绍的编译程序的五个阶段仅仅是逻辑功能上的前面介绍的编译程序的五个阶段仅仅是逻辑功能上的 一种划分。具体是现实时，受不同源语言、设计要求、使一种划分。具体是现实时，受不同源语言、设计要求、使 用对象和计算机条件的限制，往往将编译程序组织为若干用对象和计算机条件的限制，往往将编译程序组织为若干 遍遍 n n 定义：就是对源程序或源程序的中间结果从头到尾扫描一定义：就是对源程序或源程序的中间结果从头到尾扫描一 次，并作有关的加工，生成新的中间结果或目标程序。次，并作有关的加工，生成新的中间结果或目标程序。 n n 通常，一遍的工作，从外存上读取前一遍的中间结果开始通常，一遍的工作，从外存上读取前一遍的中间结果开始 ，完成它的工作后，再将其产生的结果存到外存上去。，完成它的工作后，再将其产生的结果存到外存上去。 n n 当一遍中包括若干阶段时，各阶段的工作时穿插进行的。当一遍中包括若干阶段时，各阶段的工作时穿插进行的。 例如：我们可以把词法分析、语法分析及语义分析与中间例如：我们可以把词法分析、语法分析及语义分析与中间 代码生成合为一遍。这时，语法分析处于核心位置，当他代码生成合为一遍。这时，语法分析处于核心位置，当他 在识别语法结构时需要下一个单词，他就调用词法分析器在识别语法结构时需要下一个单词，他就调用词法分析器 ，一旦识别出一个语法单位时，他就调用中间代码生成器，一旦识别出一个语法单位时，他就调用中间代码生成器 。 n n 遍的划分：多一点时编译程序的结构更清晰，但势必增加遍的划分：多一点时编译程序的结构更清晰，但势必增加 输入输入/ /输出消耗的时间。一般还是少一点好输出消耗的时间。一般还是少一点好 21 编译前端与后端编译前端与后端 n n 编译前端主要由与源语言有关，但与目标机无关编译前端主要由与源语言有关，但与目标机无关 的部分组成。包括：词法分析、语法分析、语义的部分组成。包括：词法分析、语法分析、语义 分析与中间代码产生，有的代码优化工作也可以分析与中间代码产生，有的代码优化工作也可以 包括在前端。包括在前端。 n n 编译后端主要由与目标机有关的部分组成。包括编译后端主要由与目标机有关的部分组成。包括 ：与目标机有关的代码优化、目标代码生成等。：与目标机有关的代码优化、目标代码生成等。 n n 可以取编译程序的前端，改写其后端生成不同目可以取编译程序的前端，改写其后端生成不同目 标机上的相同语言的编译程序。标机上的相同语言的编译程序。 n n 也可以为几种语言写出生成相同中间代码的前端也可以为几种语言写出生成相同中间代码的前端 ，再配上相同的后端，形成统一台机子上不同语，再配上相同的后端，形成统一台机子上不同语 言的编译程序言的编译程序 22 编译器的伙伴编译器的伙伴 语言扩充程序 预处理器 汇编器 编译器 装配器/连接编辑器 源程序 目标汇编程序 绝对机器代码 重定位机器代码 库、重定位目标文件 图1-5 一个语言处理系统 23 预处理器预处理器 n n 预处理器产生编译器的输入，负责收集源程序，他可以完成的任务：预处理器产生编译器的输入，负责收集源程序，他可以完成的任务： （1 1）宏处理）宏处理# #definedefine （2 2）文件包括）文件包括 例如：例如：# #includeinclude （3 3）语言扩充，用内部宏定义增强老语言的功能（数据库语言、没有语言扩充，用内部宏定义增强老语言的功能（数据库语言、没有 的语句结构）。的语句结构）。 n n 宏处理的几个名词：宏处理的几个名词： 宏定义、宏引用、形式参数、实在参数宏定义、宏引用、形式参数、实在参数