编译方法第1章课件.ppt

1,编译方法,教材Compilers:Principle,Technique,and Tools机械工业出版社,2,第1章 引 论,语言处理器编译过程编译器的结构编译器的构造编译技术的应用 程序设计语言基础,3,一、语言处理器,语言分三个层次：机器语言、汇编语言和高级语言。,低级语言,高级语言,程序设计语言,机器语言,汇编语言,过程式语言,函数式语言,逻辑式语言,对象式语言,C7 06 0000 0002,MOV X,2,X=2,翻译,4,编译程序,翻译一种语言（源语言）的程序成为等价的另一种语言（目标语言）的程序，并能报告源语言程序中错误的一种程序。,Source program 源程序,Target Program目标程序,Compiler,Error messages出错信息,5,编译过程,解释过程,6,语言处理系统,源程序,预处理器,编译器,汇编器,链接器/加载器,经过预处理的源程序,目标汇编语言程序,可重定位机器代码,目标机器代码,库文件可重定位对象文件,编译器的输入可能由预处理产生，而编译器的输出也可能需要进一步的处理才能成为可执行的机器代码。,7,Compiler Cousins-Preprocessors Provide Input to Compilers1.Macro Processing宏处理,#define in C:does text substitution before compiling,#define Y A*B+C#define Z getchar(),8,2.File Inclusion,#include in C-bring in another file before compiling,9,Compiler Cousins-Assemblers,汇编代码是机器码容易记忆的形式，使用标识符名称而不是2进制代码表示操作和存储地址。两遍扫描汇编:First Pass:一个标识符的存储单元在第一次被遇到时分配的，假定每个标识符占4字节存储空间。(0-offset)e.g.substitute 0 for a,and 4 for bSecond Pass:将每个操作符翻译成机器语言中代表相应操作的二进制码；将代表存储单元的每个标识符翻译成符号表中该标识符的地址。,MOV a,R1ADD#2,R1MOV R1,b,0001 01 00 00000000*0011 01 10 000000100010 01 00 00000100*,b=a+2,10,Compiler Cousins-Loaders and Link-Editors,连接编辑程序Link-editor：将多个可重定位的机器代码程序的文件组装成一个程序，其中，一个或多个可能是库程序文件。装入程序Loader：使可重定位的（relocatable）机器代码改变其地址并把改变的指令放入内存。,0001 01 00 00001111*0011 01 10 000000100010 01 00 00010011*,起始地址L=00001111，则a=00001111，b=00010011,0001 01 00 00000000*0011 01 10 000000100010 01 00 00000100*,11,二、编译过程概述,源程序,目标程序,编译程序,词法分析,语法分析,语义分析,中间代码生成,中间代码优化,目标代码生成,编译的各个阶段,目标代码优化,12,Phase 1.Lexical Analysis 词法分析（线性分析过程）,词法分析的任务是：对输入的源程序字符流进行从左到右的扫描，识别出一个个词法单元(称单词或记号token)，并输出记号的内部表示形式。记号一般分为5类：保留字（begin、end、if、for、while等）、标识符、常数、运算符和分界符（标点符号、括号、注释符号等）完成词法分析任务的程序称为词法分析器（scanner）。,13,For Example:position=initial+rate*60;,All are tokens,2.其次将源程序转换为内部形式输出：,1.首先识别出程序中出现的记号及其类型,3.在词法分析过程中，还要对源程序做一些简单处理，如滤掉空格、去掉注释、报告错误等。,14,Phase 2.Parsing or Syntax Analysis（语法分析）,任务：在词法分析基础上，将单词串（记号串）组成各类语法单位（如表达式、语句、程序等），通过分析确定整个输入串是否构成语法上正确的程序，如果不能，给出语法错误。这种语法单位（语法范畴）可以表示成语法树。完成语法分析任务的程序称为语法分析程序（parser）。功能：依据源语言的语法规则把源程序的单词序列组成语法短语(表示成分析树/语法树)。,15,What is a Grammar?,语法分析所依据的是语言的语法规则，文法是规则的集合，它们支配了tokens 中的相互依赖和结构。语言的语法规则通常是由递归规则来定义，如上述例子中表达式和语句可由下述递归规则来定义：,statement,是,expression,or while statement,or if statement,or.,expression,is an,identifier=expression,or(expression),or expression+expression,or expression*expression,or number,or identifier,or.,16,分析树（Parse Tree）程序字符流:position=initial+rate*60tokens序列:,identifier,identifier,expression,identifier,expression,number,expression,expression,expression,expression,(position),=,+,*,(60),(initial),(rate),树的结点是利用该语言的文法来建造的,expression is an identifier=expression,expression is an expression+expression,expression is an identifier,expression is an expression*expression,expression is an number,expression is an identifier,statement,statement is an expression,17,语法树是分析树的一种压缩表示,=,position,initial,rate,60,+,*,树的内结点表示操作符，相应的操作数是该节点的子节点。,18,Phase 3.Semantic Analysis（语义分析）,找复杂的语义错误语义审查，同时收集类型信息，把信息存放在语法树或符号表中。支持代码生成分析树根据语义动作进行扩展,语义审查-上下文相关性、类型匹配、类型转换例:void p();float:rate;void initial();position=initial+rate*60；/*error*/*error*/*warning*/;,19,=,position,initial,rate,60,+,*,=,position,initial,rate,inttofloat,+,*,Conversion Action,60,Compressed Tree,20,Most Important Activity in This Phase:Type Checking 类型检查-Legality of OperandsMany Different Situations:,float=int+char;Aint=Areal+int;while char int do.Etc.,21,Phase 4.Intermediate Code Generation（中间代码生成）,所谓中间代码，是一种含义明确、便于处理的记号系统，通常独立于具体硬件，与现有计算机的指令系统非常相似，比较容易转换成特定计算机的机器指令。常用的中间代码有：三元式、四元式、逆波兰式等。不管用哪种表示形式，其设计原则是容易生成，也容易转换成计算机的机器指令。很多编译程序采用三地址码形式的中间代码，其形式为：x=y op z，x、y、z是名字、常量或变量，op代表操作符。三地址赋值指令右部最多只有一个运算符，有些运算分量少于三个。,22,赋值语句 position=initial+rate*60的三地址码,t1=inttofloat(60)t2=id3*t1t3=id2+t2id1=t3,=,id1,id2,id3,inttofloat,+,*,60,23,Phase 5.Code Optimizer（代码优化）,代码优化的任务是：对产生的中间代码进行等价变换，使生成的目标代码更为高效（时间和空间）。优化的目的主要是提高运行效率，节省存储空间。优化主要有两类，一是与机器有关的优化，主要设计如何分配寄存器，如何选择指令，这类优化是在生成目标代码时进行的；另一类优化与机器无关，主要是对中间代码的优化。主要有局部优化、循环优化等。,24,代码优化 id1=id2+id3*60,t1=inttofloat(60)t2=id3*t1t3=id2+t2id1=t3,t1=id3*60.0id1=id2+t1,变换,优化方法包括：公共子表达式的提取、循环优化、删除无用代码等。,25,Phase 6.Code Generator（目标代码生成）,目标代码生成的任务是：把中间代码（或经优化的中间代码）变换成特定机器上的低级语言代码（可重定位的指令代码或汇编指令代码）。这一阶段的工作依赖于机器的硬件系统结构和机器指令的含义。工作较复杂，涉及到硬件系统功能部件的运用、机器指令的选择、各种数据类型变量的存储空间分配以及寄存器的分配和调度。,26,目标代码生成,t1=id3*60.0id1=id2+t1,LDF R2,id3MULF R2,R2,#60.0LDF R1,id2ADDF R1,R1,R2 STF id1,R1,27,三、编译器结构,编译程序的七个阶段的功能可分别用七个模块来完成，分别称为词法分析器、语法分析器、语义分析器、中间代码生成器、中间代码优化器、目标代码生成器和目标代码优化器。此外，一个完整的编译程序还必须包括“表格管理”和“出错处理”两部分。整个编译过程从逻辑上来说可以划分为各自独立的若干阶段，一个阶段的输出成为下一个阶段的输入。,28,The Many Phases of a Compiler,源程序（字符流）,1.词法分析器,2.语法分析,3.语义分析,4.中间代码生成器,5.(机器无关)代码优化,6.代码生成器,记号流,语法单位（语法树）,语法树,中间代码,中间代码,Target Program,Symbol-table Manager,Error Handler,1,2,3,4,5:Analysis-Our Focus6,7:Synthesis,7.(机器相关)代码优化,目标机器语言,但在实现时，为了提高编译效率通常采用语法制导的方法。整个编译过程以语法分析为中心，整合词法分析、语义分析和中间代码生成成为一个高效、有机连接的整体。,29,对于多遍扫描的编译程序，第一遍的输入是什么？最后一遍的输出是什么？阶段如何组合？分成几“遍”？主要依据源语言和目标机器的特征。,编译阶段的组合,将编译程序阶段划分为编译前端（front end）和后端（back end），编译前端由词法分析、语法分析、语义分析和中间代码生成，以及中间代码优化工作，它主要与源语言有关，与目标机器无关，是对源程序进行分析的过程；编译后端包括目标代码生成和目标代码优化，依赖于中间语言而与源语言无关，是对分析过程的综合，将中间代码生成目标代码。遍（趟）从头到尾扫描源程序/中间表示（各种形式）一遍(pass)并完成规定任务的过程。,为n种语言m种机器构造编译器,跟目标机无关,跟源语言无关,30,支持分析过程的两个阶段,符号表建立/维护标识符的属性信息表明该标识符的存储位置、类型、作用域等信息。当标识符是一个过程名时，他的属性信息还包括：参数的个数与类型、每个参数的传递方法以及返回值的类型等信息。符号表是一个数据结构，每个标识符在符号表中都有一个记录，记录的每个域对应于记号的一个属性。在词法、语法及语义分析阶段建立并初始化，在分析与综合阶段被利用并更新。出错处理：检查错误、报告出错信息、排错、恢复编译工作编译程序在各个阶段应诊断和报告源程序中的错误，包括词法错误，语法错误，语义错误。编译程序应报告出错地点，并给出简明准确的提示信息。,31,Reviewing the Entire Process,32,Reviewing the Entire Process,Errors,t1=inttoreal(60)t2=id3*t1t3=id2+t2id1=t3,t1=id3*60.0id1=id2+t1,LDF R2,id3MULF R2,R2,#60.0LDF R1,id2ADDF R1,R1,R2 STF id1,R1,position.initial.rate.,Symbol Table,3 address code,33,四、编译器的构造,要在一台机器上为某种语言构造一个编译程序，必须从下述三方面入手：(1)源语言：是编译程序处理的对象。对被编译的源语言要深刻理解其结构和含义，即该语言的词法、语法和语义规则，以及有关的约束和特点；(2)目标语言与目标机：是编译程序处理的结果和运行环境。目标语言是汇编语言或机器语言，必须对硬件系统结构，操作系统的功能，指令系统等很清楚；(3)编译方法与工具：是生成编译程序的关键。必须准确掌握把一种语言的程序翻译为另一种语言的程序的方法。同时应考虑所使用的方法与既定的源语言、目标语言是否相符合，构造是否方便，从时间、空间上考虑是否高效，实现的可能性和代价等诸多因素，并尽可能考虑使用先进、方便的生成工具。,34,编译器构造工具,语法分析器的生成器:根据程序设计语言的语法描述自动生成语法分析程序。扫描器的生成器:根据语言的单词正则表达式生成词法分析程序语法指导的翻译引擎:生成一组用于遍历分析树并生成中间代码的例程。自动代码生成程序:依据一组将中间代码翻译成机器语言的规则，生成一个代码生成程序。数据流引擎:帮助收集数据流信息，支持优化。编译器构造工具集：提供用于构造编译器不同阶段的例程的工具集合。,35,编译程序的实现方式,生成编译程序的方法有：1直接用机器语言或汇编语言编写（编译程序核心部分常用汇编语言编写）；2用高级语言编写编译程序（这是普遍采用的方法）；3自编译（用某种高级语言书写自己的编译程序）；4用编译工具自动生成部分程序：LEX（词法分析）与YACC（用LALR分析方法自动生成语法分析器）；5.移植（同种语言的编译程序在不同类型的机器之间移植）。,36,五、编译技术的应用,编译并不限于程序设计语言的应用 Text Formatters正文格式化程序输入是一个字符流，输出的是排版好的字符串。Silicon Compilers硅片编译程序输入是一个源程序，输出是一个电路设计。Database Query Processors数据库查询处理程序Database Query Languages Are Also a Programming Language 查询解释器把含有关系和布尔运算的谓词翻译成数据库命令，在数据库中查询满足该谓词的记录,37,六、程序设计语言基础,静态与动态区别环境与状态静态作用域动态作用域参数传递别名,38,静态与动态区别,静态策略：编译时刻可以决定问题的策略动态策略：在运行时刻才能决定问题的策略静态作用域：通过阅读程序可以确定声明的作用域动态作用域：运行时，同一个对x的使用会指向x几个声明中的某一个例子：Java类中成员变量x声明的作用域 public int x;-动态策略，每个对象都有自己用于存放 x 的位置，因此编译是无法预先确定这些位置。public static int x;-x为类变量，静态策略，在编译时可以确定存放 x 的内存位置。,39,环境与状态,环境：从名字到内存的映射。声明决定其环境，名字变量映射。状态：内存位置到其值的映射。x=y+1：该语句改变了 x 的状态。,int i;/*全局i*/void f()int i;/*局部i*/i=3;/*对局部 i 的使用*/x=i+5;/*对全局 i 的使用*/,环境与状态大部分是动态绑定的。静态绑定：环境-static声明状态宏定义#define AYSIZE 1000,标识符：字母开头的、由字母和数字组成的字符串名字：可以是标识符，也可以是表达式。如：x.y受限名字变量：分配存储位置的名字。对于同一个标识符可多次声明，声明一次引入一个新变量声明：说明事物的类型定义：确定事物的值,40,静态作用域与块结构,大多数语言一般情况下：使用静态作用域，动态绑定环境与状态。块是一个复合语句。C使用“”和“”界定块。特点：一个声明序列，跟着一个语句序列；块可以嵌套。,main()B1:int a=1;int b=1;B2:int b=2;B3:int a=3;cout a b;B4:int b=4;cout a b;cout ab;cout ab;,41,动态作用域,作用域策略依赖于只有程序在执行时刻才能知道的一个或多个因素。C预处理器中的宏扩展多态过程：同一个过程名根据参数类型具有多个定义的过程。#define a x+1int x=2;void c()printf(“%dn”,a);void b()int x=1;c();void main()b();c();,解析x：选择最近调用且对x有声明的函数,42,参数传递机制,值调用：实在参数的值传递给形参，被调用过程执行中，实参不受影响。例外：传递的是指针，如数组名。引用调用：传递的是实参地址。被调用过程执行结果将改变实参值。别名：引用调用时，两个以上的形参指向同一实参所在位置。不同形参变量明互称对方变量的别名。例子：a 是一个数组名，若用调用语句q(a,a)调用过程q(x,y)，则 x、y 变成对方的别名，如果 q 中语句：x10=2，那么 y10=?别名在优化是必须考虑：若 x=2 是 x 唯一赋值的语句，在正常情况下a=1+x优化为a=3，但若 x 存在别名y，则不能轻易替换，如存在：y=4，将改变x的值。,43,作业：,P22：练习1.611.64,