编译 第一章编译技术原理.ppt
编译技术原理,课 程 要 求,熟练掌握c、pascal语言的编程、语法结构；会一种程序设计语言的编程；会一种数据库开发语言，或熟悉文件的管理；按课程的进程，按时完成课程设计按时完成作业认真听讲，认真作笔记，上课不得迟到早退上课不得喧哗,第一章引 论,一、什么是编译程序 使用过现代计算机的人都知道，现代的编程软件，越来越趋向于智能化、自然语言化，越来越高级，但是，通过前期课程的学习，大家都知道，计算机是不能识别自然语言或高级语言，只能识别机器语言，那么我们的高级语言程序是如何在计算机上执行的呢？在计算机上执行一个高级语言程序一般要分两步：第一步：用一个翻译程序把高级语言翻译成机器语言程序；第二步：运行所得的机器语言程序求得计算结果。第二步我们暂时不考虑，那么第一步“翻译程序”是我们这门课讨论的重点，什么样的程序叫翻译程序？翻译程序是如何翻译的？世界上第一个编译程序FORTRAN编译程序是20世纪50年代中期研制成功的。,第一章引 论,一、什么是编译程序定义：假设，SL指源语言程序，TL指目标语言程序，则：翻译程序把SL变换为TL的程序，SL与TL逻辑上等价。编译程序SL为高级语言、TL为低级语言的翻译程序。汇编程序SL为汇编语言程序，TL为机器语言程序。解释程序逐条翻译，且立即执行，不生成目标程序。分类：根据侧重和用途，编译程序进一步划分：1.诊断编译程序:专门用于帮助程序的开发和调试的编译程序.2.优化编译程序:着重于提高目标代码效率的编译程序.3.交叉编译程序:运行编译程序的计算机称宿主机，运行编译程序所产生目标代码的计算机称目标机，如果一个编译程序产生不同于其宿主机的机器代码。4.可变目标编译程序：如果不需重写编译程序中与机器无关的部分就能改变目标机的编译程序。,第一章引 论,二、编译过程概述编译程序的过程，从输入源程序到输出目标程序为止的整个过程，非常复杂，但是从形式和操作步骤上来说，与自然语言的翻译很相近。例如：把引文翻译成中文的步骤：1.识别出句子中的一个个单词;2.分析句子的语法结构;3.根据句子的含义进行初步翻译;4.对译文进行修饰;5.写出最后的译文 按照编译程序的执行过程和它所完成的任务，可把编译过程分为五个阶段:词法分析、语法分析、语义分析与中间代码生成、优化、目标代码生成。又把五阶段分为两大部分：分析和综合。分析部分包括：词法分析、语法分析、语义分析。综合部分包括：中间代码生成、代码优化、目标代码生成。,词法分析任务：输入源程序，对构成源程序的字符串进行扫描和分解，过滤编辑符号，按词法规则分解为单词序列。单词分类：基本字（if、else、for、while等）、标识符、常数、算符、界符（标点和括号）。例如赋值语句：position:=initial+rate*60;词法分析的结果是识别出下列单词符号：标识符position 赋值号:标识符initial加号标识符rate 乘号*整常数60 分号；,词法分析在词法分析阶段的工作中，所依循的是语言的词法规则（或称构词规则）.描述词法规则的有效工具是：正规式和有限自动机。编译器的词法分析也叫线性分析或扫描练习题：pascal语言的循环语句：for I:=1 to 100 do 基本字 for 标识符 I 赋值号:=整常数 1 基本字 to 整常数 100 基本字 do,2、语法分析（简称为分析）,任务：在词法分析的基础上，根据语法规则，把单词序列分解为各种语法单位。语法单位：程序、程序段、语句、短语、表达式。词法分析把记号流按语言的语法结构层次地分组，例如：对赋值语句：position:=initial+rate*60;进行语法分析可得到如下所示的层次结构，称为语法分析树，简称语法树（或分析树）。,分析树的层次结构可以用递归规则表示。例如：下列规则定义包含、*运算的表达式：1.任意一个标识符是一个表达式；2.任意一个数是表达式；3.如果e1和e2都是表达式，则 e1+e2e1*e2(e1)都是表达式。例：对赋值语句：position:=initial+rate*60 由规则1得：initial 和rate 都是表达式 由规则2得：60是一个表达式 由规则3得：rate*60是一个表达式；initial+rate*60是一个表达式。类似的，可以用下列规则递归的定义语句：1、如果ID1是一个标识符，e2是一个表达式，则ID1:e2是一个语句。2、如果e1是一个表达式，st2是一个语句，则 While(e1)st2 和 if(e1)st2 都是语句。,3、语义分析,任务：对源程序进行语义检查和类型检查。语义分析使用语法分析确定的层次结构表示表达式和语句。类型检查是语义分析的一个重要部分，按照语言的类型规则检查和每个运算符相关的操作数。例：1、当数组下标为实数时，许多语言要求编译程序报告错误；2、一般允许二元运算符的操作数既可为整数，也可为实数，运算时要进行类型转换。,在以上分析的各阶段里，编译程序都把源程序变换成便于下一阶段处理的内部表示形式。对上述语句经每一阶段分析后产生的内部表示形式如下图所示，其中的id1、id2和id3分别表示词法分析器对标识符position、initial和rate产生的记号。,position:=initial+rate*60,4、中间代码的生成,任务：对源程序进行初步翻译的工作，生成中间代码。中间代码的特点：结构简单、语义明确、易于转换、易于优化。中间代码的形式：前缀式、三地址代码、四元式等。三地址代码由指令序列组成，每条指令最多有三个操作数。四元式的形式是：（算符，左操作数，右操作数，结果）例如：由语义分析得到的分析树可得到表达式position:=initial+rate*60的三地址代码表示形式为：temp1:=inttoreal(60)temp2:=id3*temp1temp3:=id2+temp2id1:=temp3 表达式position=initial+rate*60的四元式表示形式为：(inttoreal()，60，T1）(*，id3，T1，T2)(+，id2，T2，T3)(=，T3，id1)练习题：写出：Z:=(X+0.418)*Y/W的四元式和三地址代码,5、代码优化,任务：对中间代码进行加工变换，提高目标代码的效率（省时间、省空间）优化的主要方面有：循环优化、公因子提取、强度削弱等例如：对前面得到的三地址代码表示的中间代码，可优化为用下面两条指令表示：temp1:=id3*60.0id1:=id2+temp1又如，对c语言程序片段：K=1;While(k=100)M=I+10*K;N=J+10*k;k+;,优化后代码为：,需做300次加法200次乘法,只需做300次加法,6、目标代码生成,任务：把中间代码（或经优化后的代码）变换成特定机器上的绝对指令代码或可重新定位的指令代码或汇编指令代码。如果目标代码是绝对指令代码，则可立即执行。如果目标代码是汇编指令代码，则需经汇编器汇编之后才可运行。多数编译程序产生的目标代码都是可重新定位的指令代码，在运行之前必须借助连接装配程序把各个目标模块连接在一起，确定程序变量（或常数）在主存中的位置，使之成为可以独立运行的绝对指令代码程序。此阶段的一个关键问题是寄存器分配。例如：使用寄存器R1和R2，代码 temp1:=id3*60.0 id1:=id2+temp1可以翻译成如下的代码：MOVF ID3,R2 MULF#60.0,R2 MOVF ID2,R1 ADDF R2,R1 MOVF R1,ID1,一个语句的翻译过程示意图,Temp1:=id3*60.0id1:=id2+temp1,从源程序到中间代码生成产品,三、编译程序的结构,符号表管理,符号表 是为每个标识符保存一个记录的数据结构，记录着每 一个表示符的属性。符号表在各个阶段收集的信息一般不同。例如：在c，pascal语言中的变量定义语句 c 语言:real:position,initial,rate;pascal语言:var position,initial,rate:real;c语言中在读到变量名的时候，变量的属性已经知道，可以一起写入符号表，而pascaL语言中，词法分析器在程序扫描时，读到变量名的时候，并不知道表示符的属性，所以，符号表并不一定就记载有表示符的属性。,出错处理,一个好的编译程序不但能最大限度的发现错误，准确地指出错误的性质和发生错误的地点，而且能够把错误的范围缩小到尽可能小的范围，使程序的其他部分能继续编译下去；如果不仅能发现错误，而且能够知道校正错误就更好啦。源程序钟的错误分为语法错误和语义错误 语法错误：源程序中不符合语法或词法规则的错误，可在语法或词法分析中检测出来。（非法字符、括号不配、缺少等）语义错误：源程序中部符合语义规则的错误，一般在语义分析中检测出来，但有的要在运行时才能检测出来。（说明错误、作用域错误、类型不一致等）,遍,前面介绍的编译程序的五个阶段仅仅是逻辑功能上的一种划分。具体是现实时，受不同源语言、设计要求、使用对象和计算机条件的限制，往往将编译程序组织为若干遍定义：就是对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工，生成新的中间结果或目标程序。通常，一遍的工作，从外存上读取前一遍的中间结果开始，完成它的工作后，再将其产生的结果存到外存上去。当一遍中包括若干阶段时，各阶段的工作时穿插进行的。例如：我们可以把词法分析、语法分析及语义分析与中间代码生成合为一遍。这时，语法分析处于核心位置，当他在识别语法结构时需要下一个单词，他就调用词法分析器，一旦识别出一个语法单位时，他就调用中间代码生成器。遍的划分：多一点时编译程序的结构更清晰，但势必增加输入/输出消耗的时间。一般还是少一点好,编译前端与后端,编译前端主要由与源语言有关，但与目标机无关的部分组成。包括：词法分析、语法分析、语义分析与中间代码产生，有的代码优化工作也可以包括在前端。编译后端主要由与目标机有关的部分组成。包括：与目标机有关的代码优化、目标代码生成等。可以取编译程序的前端，改写其后端生成不同目标机上的相同语言的编译程序。也可以为几种语言写出生成相同中间代码的前端，再配上相同的后端，形成统一台机子上不同语言的编译程序,编译器的伙伴,预处理器,预处理器产生编译器的输入，负责收集源程序，他可以完成的任务：（1）宏处理#define（2）文件包括 例如：#include（3）语言扩充，用内部宏定义增强老语言的功能（数据库语言、没有的语句结构）。宏处理的几个名词：宏定义、宏引用、形式参数、实在参数举例说明：#define min(a,b)ab?b:a#include main()int m,n,i;m=10;n=15;I=10*min(m,n);printf(“%dn”,i);,汇编器,源程序：position:=initial+rate*60汇编语言程序：movf id3,r2 mulf#60.0,r2 movf id2,r1 Addf r2,r1 Movf r1,id1第一次扫描：mov a,r1 add#2,r1 mov r1,b 结果：标示符 地址 a 0 b 4第二次扫描：0001 01 00 00000000*0011 01 10 00000010 0010 01 00 00000100*,装配器和连接编辑器,装配器的两个功能连接编辑器的功能例,课后习题,1、请写出下列程序段的词法分析结果,并注明单词类型：(1)for(I=0,I100,I+)max=max+1;(2)I=0;do max=max+1;I+;while(I=100);2、请写出下列语句在编译各个阶段的结果(1)z=x+23*y/a;(2)tt=qq*55/nn+66*ff;,上课结束，谢谢大家,
