《A2013-9-CH01--编译概述》由会员分享，可在线阅读，更多相关《A2013-9-CH01--编译概述（83页珍藏版）》请在金锄头文库上搜索。
1、第1章 编译概述,知识点：翻译、编译、解释的概念 编译的阶段、任务、及典型结构 编译程序的伙伴工具,2,编译概述,简介1.1 翻译和解释1.2 编译的阶段和任务1.3 编译有关的其他概念1.4 编译程序的伙伴工具1.5 编译原理的应用 小结,3,简介,什么是编译？把源程序转换成等价的目标程序的过程即是编译。编译程序的设计涉及到的知识：程序设计语言形式语言与自动机理论计算机体系结构数据结构算法分析与设计操作系统软件工程等,4,1.1 翻译和解释,一、程序设计语言二、翻译程序,5,一、程序设计语言,低级语言机器语言符号语言 汇编语言高级语言过程性语言面向用户的语言 如：C、Pascal专用语言面向
2、问题的语言 如：SQL面向对象的语言 如：Java、C+,6,7,8,9,高级语言的优点,高级语言独立于机器。所编程序移植性比较好。不必考虑存储单元的分配问题、数据的外部形式转换成机器的内部形式等细节。用变量描述存储单元具有丰富的数据结构和控制结构。数据结构：数组、记录等控制结构：循环、分支、过程调用等。更接近于自然语言。可读性好，便于维护。编程效率高。,10,11,把英文翻译为中文 识别出句子中的一个个单词；分析句子的语法结构；根据句子的含义进行初步翻译；对译文进行修饰；写出最后的译文。,二、翻译程序,12,翻译程序扫描所输入的源程序，并将其转换为目标程序，或将源程序直接翻译成结果。,编译器
3、(即编译程序)：把源程序翻译成目标程序的翻译器。笔译解释器(即解释程序)：直接执行源程序的翻译器。口译,13,编译程序,源程序是用高级语言或汇编语言编写的，目标程序是用目标语言表示的。,14,编译和执行阶段,编译时间：实现源程序到目标程序的转换所占用的时间。源程序和数据是在不同时间（即分别在编译阶段和运行阶段）进行处理的。,源程序,目标程序,编译时,数据,执行时,15,解释程序,解释程序解释执行源程序，不生成目标程序。同时处理源程序和数据。,源程序,数据,16,total:=total+rate*4 的解释过程,解释程序先将源程序转换成一棵树,遍历该树，执行结点上所规定的动作。,调用一个过程，
4、执行右边的表达式，计算结果送入total的存储单元,递归调用过程，对表达式进行计算,17,另一种有效的方法：先将源程序转换为某种中间形式，然后对中间形式的程序解释执行。例如: JAVA语言,操作系统平台,Java虚拟机(解释器),Java编译器,18,19,编译过程,把英文翻译为中文 识别出句子中的一个个单词；分析句子的语法结构；根据句子的含义进行初步翻译；对译文进行修饰；写出最后的译文。,词法分析,语法分析,语义分析和中间代码生成,优化,目标代码生成,20,1.2 编译的阶段和任务,一、分析阶段 根据源语言的定义，分析源程序的结构1.词法分析2.语法分析3.语义分析二、综合阶段 根据分析结果
5、构造出所要求的目标程序4.中间代码生成5.代码优化6.目标代码生成三、符号表的管理 四、错误诊断和处理,21,编译程序的典型结构,22,一、分析阶段,任务：根据源语言的定义，对源程序进行结构分析和语义分析，从而把源程序正文转换为某种内部表示。分析阶段是对源程序结构的静态分析。任务划分：1.词法分析2.语法分析3.语义分析,23,1. 词法分析,扫描，线性分析词法分析器:依次读入源程序中的每个字符，对构成源程序的字符串进行分解，识别出每个具有独立意义的字符串作为记号（token）并组织成记号流。把需要存放的单词放到符号表中，如变量名，标号，常量等。形成记号的字符串叫做该记号的单词(lexeme)
6、。工作依据:源语言的构词规则(即词法)，也称为模式(pattern)。标识符的模式是：以字母开头的字母数字序列。,24,词法分析器从左到右扫描组成源程序的字符串，并将其转换成单词(记号token)串；同时要：查词法错误，进行标识符登记符号表管理。输入：字符串输出：(种别码，属性值)序对 属性值token的机内表示,25,sum=(10+20)*(num+square);,结果： (标识符，sum) (赋值号，=) (左括号， ( ) (整常数，10) (加号，+ ) (整常数，20) (右括号， ) ) (乘号，* ) (左括号， ( ) (标识符，num) (加号，+ ) (标识符，squa
7、re) (右括号， ) ) (分号，; ),26,对 total:=total+rate*4 的词法分析,(1) 标识符 total （内部名字为id1）(2) 赋值号 :=(3) 标识符 total （内部名字为id1）(4) 加号 +(5) 标识符 rate （内部名字为id2）(6) 乘号 *(7) 整常数 4,27,空格、注释的处理及其他,分隔记号的空格：被删去源程序中的注释：被跳过识别出来的标识符要放入符号表。对某些记号还要增加一个“属性值”如发现标识符total时，词法分析器不仅产生一个记号如id，还把它的单词total填入符号表（如果total在表中不存在的话），记号id的属性值
8、就是指向符号表中R条目的指针。,28,2. 语法分析,层次结构的分析把记号流按语言的语法结构层次地分组，以形成语法短语或语法单位。源程序的语法短语常用分析树表示。工作依据：源语言的语法规则。输入：token序列输出：语法成分,29,功能：实现“组词成句”，将词组成各类语法成分：表达式、因子、项，语句，子程序构造分析树指出语法错误制导翻译,30,程序的层次结构通常由递归的规则表示，【例如】表达式的定义规则如下：(1) 任何一个标识符是一个表达式(2) 任何一个数是一个表达式如果expr1和expr2是表达式，expr1+expr2、expr1*expr2、(expr1)也都是表达式。【例如】使用
9、如下规则递归地定义语句：(1) 如果id是一个标识符，expr是一个表达式，则 id:= expr是一个语句。(2) 如果expr是一个表达式，stmt是语句，则 while(expr) do stmt和if(expr) then stmt都是语句。,31,根据语句和表达式的定义规则，构造total:=total+rate*4 的分析树,total是表达式；rate 是表达式；4是表达式rate*4是表达式；total+rate*4是表达式total:=total+rate*4是一个语句,32,total:=total+rate*4 的分析树,33,与该分析树对应的语法树如下：,语法树是分析树
10、的浓缩表示，其中，算符作为内部结点，运算对象作为子结点。,34,3. 语义分析,对语句的意义进行检查分析收集类型等必要信息用语法分析确定的层次结构表示各语法成份工作依据：源语言的语义规则(程序语义正确性的规定)一个重要任务：类型检查根据规则检查每个运算符及其运算对象是否符合要求；数组的下标是否合法；过程调用时，形参与实参个数、类型是否匹配等,float total, rate; total:=total+rate*4,35,赋值语句 total:=total+rate*4插入转换符的语法树,增加一个语义处理结点：将整型变为实型的一目运算符,36,total:=total+rate*4 的各分析
11、步骤及其中间结果,id1:=id1+id2*4,37,二、综合阶段,任务：根据所制定的源语言到目标语言的对应关系，对分析阶段所产生的中间形式进行综合加工，从而得到与源程序等价的目标程序。任务划分：(4) 中间代码生成(5) 代码优化(6) 目标代码生成,38,4. 中间代码生成,中间代码：一种抽象的机器程序（与机器无关）中间代码应具有两个重要的特点：易于产生易于翻译成目标代码中间代码有多种形式： 三地址代码具有的特点：每条指令除了赋值号之外，最多还有一个运算符。编译程序必须生成临时变量名，以便保留每条指令的计算结果。有些“三地址”指令少于三个操作数,39,total:=total+rate*4
12、 的三地址代码,temp1:=inttoreal(4)temp2:=id2*temp1temp3:=id1+temp2id1:=temp3,40,5. 代码优化,对代码进行改进(加工变换)，使之占用的空间少、运行速度快。,什么是代码优化？,代码优化首先是在中间代码上进行的。,temp1:=id2*4.0temp2:=id1+temp1id1:=temp2,temp1:=inttoreal(4)temp2:=id2*temp1temp3:=id1+temp2id1:=temp3,41,6. 目标代码生成,将中间代码变换成特定机器上的目标代码。依赖于硬件系统结构和机器指令的含义。生成的目标代码一般
13、是可以重定位的机器代码或汇编语言代码。涉及到的两个重要问题：对程序中使用的每个变量要指定存储单元（即，分配具体的存储地址）对变量进行寄存器分配（即，使用实际机器的寄存器）,42,total:=total+rate*4 的目标代码,MOVF id2, R2MULF #4.0, R2MOVF id1, R1ADDF R2, R1MOVF R1, id1,43,temp1:=inttoreal(4)temp2:=id2*temp1temp3:=id1+temp2id1:=temp3,temp1:=id2*4.0temp2:= id1+trmp1id1:= temp2,MOVF id2, R2MULF
14、 #4.0, R2MOVF id1, R1ADDF R2, R1MOVF R1, id1,44,total:=total+rate*4 的翻译过程,total:=total+rate*4,temp1:=inttoreal(4)temp2:=id2*temp1temp3:=id1+temp2id1:=temp3,temp1:=id2*4.0temp2:= id1+trmp1id1:= temp2,MOVF id2, R2MULF #4.0, R2MOVF id1, R1ADDF R2, R1MOVF R1, id1,id1:=id1+id2*4,45,三、符号表管理,编译程序的一项重要工作：记录
15、源程序中使用的标识符收集每个标识符的各种属性信息符号表是由若干记录组成的数据结构每个标识符在表中有一条记录记录的域是标识符的属性对符号表结构的要求：应允许快速地找到标识符的记录可在其中存取数据标识符的各种属性是在编译的各个不同阶段填入符号表的。,46,声明语句：float total, rate;,词法分析器：float是关键字total、rate是标识符在符号表中创建这两个标识符的记录语法分析器：total、rate都表示变量float表示这两个变量的类型可以把这两种属性及存储分配信息填入符号表。在语义分析和生成中间代码时，还要在符号表中填入对这个float型变量进行存储分配的信息。,47,
16、 ,管理各种符号表(常数、标号、变量、过程、结构。)，查、填（登记、查找）源程序中出现的符号和编译程序生成的符号，为编译的各个阶段提供信息。辅助语法检查、语义检查完成静态绑定、管理编译过程Hash表、链表等各种表的查、填技术。 “数据结构与算法”课程的应用。,48,四、错误处理,在编译的每个阶段都可能检测到源程序中存在的错误词法分析程序可以检测出非法字符错误。语法分析程序能够发现记号流不符合语法规则的错误。语义分析程序试图检测出具有正确的语法结构，但对所涉及的操作无意义的结构。代码生成程序可能发现目标程序区超出了允许范围的错误。由于计算机容量的限制，编译程序的处理能力受到限制而引起的错误。处理与恢复判断位置和性质适当的恢复,
