编译原理cmpl_01.ppt

1,第一章编译概述,主要介绍编译程序的基本概念、基本结构以及高级语言的程序设计环境。,1.1翻译程序与编译程序1.2编译过程和编译程序的基本结构1.2.1编译过程1.2.3编译程序的基本结构1.3编译程序的生成方法1.4编译程序在软件开发中的应用小节,2,1.1翻译程序和编译程序,翻译程序（translator）编译程序（compiler）源程序的加工过程与编译程序相关的程序,3,翻译程序,翻译程序是指这样一个程序，它把一种语言（源语言）所写的程序（源程序）翻译成与之等价的另一种语言（目标语言）的程序（目标程序）。,源语言：sourcelanguage源程序：sourceprogram目标语言：objectortargetlanguage目标程序：objectortargetprogram,4,编译程序（编译器）,如果源语言是高级语言，目标语言是低级语言，那么称这样的翻译程序为编译程序。,高级语言：C、PASCAL、C+、FORTRAN、JAVA低级语言：汇编语言、机器语言,高级语言所写程序,汇编语言或机器语言程序,5,源程序的加工过程,采用编译方式在计算机上执行高级语言编写的程序，一般分两大阶段，编译阶段和运行阶段。,6,源程序,机器语言目标程序,结果,初始数据,运行系统,如果编译阶段生成的目标程序不是机器程序，而是汇编程序，则程序的执行需分三个阶段，编译阶段、汇编阶段和运行阶段。,汇编语言目标程序,编译程序,汇编程序,7,一个语言的解释程序是这样的程序：它以该语言写的源程序作为输入，但不产生目标程序，而是边解释边执行源程序本身。,与编译程序相关的程序,解释程序（interpreter）汇编程序（assembler）连接程序（linker）装入程序（Loader）预处理程序（preprocessor）编辑器（editor）调试程序（debugger）描述器（profiler）项目管理程序（projectmanager）,汇编程序是用于特定计算机上的汇编语言的翻译程序。有时编译器把汇编语言作为目标语言，然后再由汇编程序将它翻译成目标代码。,连接程序将分别在不同的目标文件中编译或汇编的代码收集到一个可直接执行的文件中。在这种情况下，目标代码（即还未被连接的机器代码）与可执行代码的机器代码之间有了区别。连接程序还连接目标程序和用于标准库函数的代码，以及连接目标程序和计算机的操作系统提供的资源(存储分配程序及IO设备),编译器、汇编程序或连接程序生成的代码还不能运行，装入程序处理所有的与指定的基地址有关的可重定位地址，并将修改后的指令和数据放在内存中适当的位置。,预处理程序是在真正的编译开始之前由编译器调用的独立程序。预处理程序可以删除注释、包含其它文件以及执行宏替代。,编译器通常接受由任何生成标准文件（例如ASCII）的编辑器编写的源程序。最近，编译器已与一个编辑器和其它程序捆绑进一个交互的开发环境IDE中。,调试程序是可在被编译了的程序中判定执行错误的程序。运行一个带有调试程序的程序与直接执行不同，因为调试程序保存着大多数的源代码信息。,描述器是在执行中搜集目标程序行为统计的程序。程序员特别感兴趣的统计是每一个过程调用次数和每一个过程执行时间所占的百分比。这样的统计对于帮助程序员提高程序的执行速度极为有用。,将不同程序员编写的不同文件的各个独立版本整理在一起，能保存一组文件的历史，并能维护一个正在开发的程序的连贯版本。,9,1.2编译过程和编译程序的基本结构,编译过程是一种语言的翻译过程，它的工作过程类似于外文的翻译过程。,【例】英文句子翻译成中文句子的大致过程是：,词法分析：根据英语的词法规则，从由字母、空格字符和各种标点符号所组成的字符串中识别出一个一个的英文单词。语法分析：根据英语的语法规则，对词法分析后的单词串进行分析、识别，并做语法正确性检查，看其是否组成一个符合英语语法的句子。语义分析：对正确的英文句子分析其含义并用汉语表示出来.根据上下文的关系以及汉语语法的有关规则对词句坐必要的修饰工作。最后翻译成中文。,10,1.2.1编译过程概述,编译过程一般分为以下五个阶段（与自然语言翻译过程对比）：,词法分析语法分析语义分析与中间代码产生优化目标代码生成,11,对于PASCAL的循环语句ForI:=1to100do词法分析的结果是识别出如下的单词符号序列：基本字For、标识符I、赋值号:=、整常数1、基本字to、整常数100和基本字do，它们是组成上述PASCAL语句的基本单词符号。,1、词法分析（扫描器）,任务：源程序单词符号串（线性分析）依据：语言的词法规则描述词法规则的工具：正则式、正则文法、有限自动机举例：,12,2、语法分析,在PASCAL语言中，符号串Z:=X+0.618*Y代表一个赋值语句，是该符号串表示的最大的语法范畴。该符号串含有的语法范畴有：变量X、Y、Z；常量0.618；加法运算符+；乘法运算符*；乘法表达式0.618*Y；加法表达式X+0.618*Y；以及赋值语句Z:=X+0.618*Y。,任务：单词符号串各类语法范畴（层次结构分析）依据：语言的语法规则描述语法规则的工具：上下文无关文法、确定的下推自动机举例：,13,3、语义分析与中间代码产生,任务：语法范畴初步翻译、产生中间代码中间代码：独立于具体硬件的记号系统，四元式、三元式、逆波兰式等。依据：语言的语义规则描述语义规则的工具：属性文法举例：,在PASCAL语言中，符号串:Z:=X+0.618*Y经过语法分析进行初步翻译，可产生一种四元式形式的中间代码：,14,4、优化,forK:=1to100dobeginm:=I+10*K;n:=J+10*Kend,任务：中间代码高效的中间代码依据：等价变换规则变换方法：公共子表达式的提取、循环优化、删除无用代码、并行处理等举例：对以下Pascal程序片段的中间代码进行优化,15,源程序,优化后的中间代码,原中间代码：,16,源程序,原中间代码,优化后等价的中间代码：,17,5、目标代码生成,任务：中间代码依赖于机器的目标代码（汇编语言或机器语言）涉及的主要问题：指令的选择内存的分配寄存器的分配目标代码的形式：绝对指令代码汇编指令代码可重定位的指令代码,18,【例】c语言片段floatr,h,s;s=2*3.1416*r*(h+r);,经过词法分析识别出如下单词符号：基本字float标识符r,h,s常数2,3.1416运算符+,*,=界符(),;,19,(续)语法分析,根据语言的语法规则从单词符号串中识别出各种语法单位，并进行语法检查（检查各种语法单位在语法结构上的正确性）：变量s,h,r表达式2*3.1416*r*(h+r)赋值语句s=2*3.1416*r*(h+r),20,(续)语义分析,(*,2,3.1416,T1)(*,T1,r,T2)(+,r,h,T3)(*,T2,T3,T4)(=,T4,_,s),其中T1,T2,T3,T4是编译程序引进的临时变量,对语言的各种语法单位赋予具体的意义。语义分析的任务是首先对每种语法单位进行静态的语义检查，然后分析其含义，并用另外一种语言来描述这种语义。,上述语句的语义是：计算赋值号右边的表达式，并把它送到左边的变量所确定的内存单元中。语义分析时，先检查类型是否一致。,21,(续)优化,floatr,h,s;s=2*3.1416*r*(h+r);,(*,2,3.1416,T1)(*,T1,r,T2)(+,h,r,T3)(*,T2,T3,T4)(=,T4,_,s),(*,6.2832,r,T2)(+,h,r,T3)(*,T2,T3,T4)(=,T4,_,s),优化为,编译时都是已知的量，可以在编译时刻计算，不必等到运行时刻。,22,beginvarsum,first,count:real;sum:=first+count*10end.,保留字begin保留字var标识符sum逗号,标识符first逗号,标识符count冒号:保留字real分号;标识符sum赋值号:=标识符first加号+标识符count乘号*整数10保留字end界符.,*【例】Pascal程序片断,赋值语句,标识符,表达式,表达式,+,表达式,表达式,标识符,整数,标识符,:=,表达式,*,id1:=id2+id3*10的语法树,id1sum,id2first,id3count,10,24,id1:=id2+id3*10的语法树的另一种形式,:=,id1,+,id2,*,id3,10,25,语义分析，如：类型检查。,:=,id1,+,id2,*,id3,10,inttoreal,sum:=first+count*10,26,(inttoreal10-T1)(*id3T1T2)(+id2T2T3)(:=T3-id1),:=,id1,+,id2,*,id3,10,inttoreal,生成的四元式可以是,27,代码优化,(inttoreal10-T1)(*id3T1T2)(+id2T2T3)(:=T3-id1),(*id310.0T2)(+id2T2id1),(*id310.0T1)(+id2T1id1),28,(*id310.0t1)(+id2t1id1),sum:=first+count*10,MOVFid3,R2MULF#10.0,R2MOVFid2,R1ADDFR1,R2MOVR1,id1,*目标代码生成,29,1.2.2编译过程的结构,词法分析器,语法分析器,语义分析及中间代码生成器,优化器,目标代码生成器,出错处理程序,表格管理程序,源程序,单词符号,语法单位,中间代码,中间代码,目标代码,编译程序总框,30,表格与表格管理用途：登记源程序的各类信息和编译程序各阶段的进展情况，如符号表。管理：构造、查找、或更新。出错处理任务：发现并指出源程序中错误的性质和位置；自动校正错误。,31,遍（pass)：对源程序或源程序的中间结果从头至尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序的处理过程称为一遍。可以把一个阶段分为若干遍，也可以把多个阶段合为一遍，通常有一遍和多遍编译程序。,32,词法分析语法分析语义分析与中间代码生成优化目标代码生成,编译的前端与后端：前端（frontend）：由与源语言有关但与目标机无关的部分组成。后端（backend）：包括与目标机有关的部分。而一般不依赖于源语言，只与中间代码有关的编译阶段。,前端（中间代码）后端,33,1.3编译程序的生成,一.生成一个编译程序，要经历以下几个步骤：1、对源语言(语法、语义定义)和目标语言认真分析2、设计编译算法3、选择语言编制程序4、调试编译程序5、提交相关文档材料,34,二.生成编译程序的几种方法：机器/汇编语言直接编写在现有编译器基础上用高级语言编写先实现语言的内核编译再进行自编译扩展先实现某语言的编译再用该语言实现另一语言