编译概述(中国矿业大).ppt

编译技术,计算机学院计算机系 张辰,课程简介,学时:56学时 分为两部分:理论基础:70%,课堂教学实践部分:30%,实验(16学时)课程要求:掌握编译技术的基本理论、编译系统的构造（结构和机理）并进行编译程序相关部分的设计，加深对计算机高级语言的理解，在此基础上能够灵活运用所学技术解决实际问题。,程序如何被翻译为机器指令 1.变量的本质是什么？2.顺序、选择、循环语句对应哪些中间或目标代码？3.函数调用时局部变量在内存中如何分配？4.如何深入理解对象与变量的区别？5.对象如何存放？程序中同一类对象如何存放？看不见的this指针到底有什么用？6.函数重载编译器都做了什么？7.什么是多态？编译器做了哪些工作来支持虚函数？虚函数运行时是什么情况？8.任意给出一个面向过程或面向对象的程序，我如何深入分析执行过程？,为什么要学习编译原理,学习这门课程有利于加深对程序设计语言的理解，可以比较迅速掌握新的语言工具，也是读懂相关计算机著作的基础编译程序是计算机系统中的系统软件，包含许多软件技术，对于进行软件设计很有价值编译课程蕴含着计算机学科中解决问题的思路、抽象问题和解决问题的方法,（1）编译原理及实践 机械工业出版社，Kenneth C.Louden 冯博琴等翻译，英文 原版Complier Construction Principles and Practice。（2）程序设计语言编译原理，国防工业出版社，陈火旺等编著。（3）编译原理清华大学出版社，吕映芝等编著，1998。（4）编译原理和技术中国科技大学出版社，陈意云编著，1997。,参考书,国外参考书（编译圣经）,Compilers:Principles,Techniques and Tools(Dragon book),Modern Compiler Implementation in Java,C,ML(Tiger book),国外参考书（编译圣经）,国外参考书（编译圣经）,Advanced Compiler Design and Implementation(Whale book，鲸书),第一章 编译概述,1.1 什么是编译程序1.2 编译程序的逻辑结构1.3 编译阶段的组合1.4 编译程序实现的途径1.5 语言开发环境中的伙伴程序1.6 编译程序的构造工具,过程式语言 Fortran,Pascal,C函数式语言 Lisp逻辑式语言 Prolog对象式语言 C+汇编语言机器语言,程序设计语言：用来编写计算机程序的语言。,程序设计语言,高级语言低级语言：面向机器的语言,1.1 什么是编译程序,程序设计语言,机器语言：直接用计算机能够识别的二进制代码指令来编写程序的语言。由二进制的指令代码组成。1+3 表示为 10000001 00000001 00000011是最底层的计算机语言，不需要翻译就可以直接被计算机硬件识别。对应不同的计算机硬件有不同的机器语言。特点：执行速度快，但编写程序的难度大，修改、调试不方便，直观性差，不易移植。,程序设计语言,汇编语言：又称为符号语言。与机器语言一一对应，采用能帮助记忆的英文缩写符号（指令助记符）来代替机器语言指令中的操作码，用地址符号来代替地址码。用指令助记符及地址符号书写的指令称为汇编指令，用汇编指令编写的程序称为汇编语言源程序。将X、Y中的内容相加 表示为 ADD X Y机器不能直接识别汇编语言程序，必须把它翻译为机器语言程序才能执行。特点：比机器语言直观，容易理解和记忆，比高级语言的执行效率高，但通用性和移植性较差。,程序设计语言,高级语言：与具体的计算机硬件无关，是面向问题的程序设计语言，其表达方式接近于自然语言和数学语言，易于人们接受和掌握。采用类似于数学公式的书写方式：x=1+3特点：独立于具体的计算机硬件，程序的编制和调试方便，通用性和可移植性好。在计算机执行之前，需要通过编译程序翻译成目标语言程序，或需要通过解释程序边解释，边执行。时间与空间效率比较低。目前比较流行的高级语言有：Visual C,Visual Basic,Java，FoxPro，Pascal,Lisp,Cobol等。,翻译程序 把一种语言书写的程序（源程序）翻译成另一种语言的等价的程序（目标程序）。是汇编程序、编译程序以及各种变换程序的总称。,源程序、翻译程序、目标程序 三者关系：,源程序,翻译程序,目标程序,即源程序是翻译程序的输入，目标程序是翻译程序的输出,汇编程序 把汇编语言程序翻译成机器语言程序，这时的翻译程序称之为汇编程序，这种翻译过程称为“汇编”(Assemble）编译程序 把高级语言程序翻译成低级语言程序，这时的翻译程序称之为编译程序，这种翻译过程称“编译”（Compile),汇编程序与编译程序都是翻译程序，主要区别是加工对象的不同。由于汇编语言格式简单，常与机器语言之间有一一对应的关系。汇编程序所要做的翻译工作比编译程序简单的多。,编译程序是翻译程序的一种，它将一个用面向 人的源语言书写的程序（高级语言程序）翻译成 一个等价的面向硬件的目标程序（低级语言程序）,源程序,目标程序,编译程序,人可以理解的高级语言,机器可以“理解”的低级语言,解释程序 对源程序进行解释执行的程序 以源程序作为输入，但不产生目标程序，对源程序边解释边执行,比较编译程序与解释程序的区别编译程序：生成一个与源程序等价的目标程序，它可以完全取代源程序，目标程序可运行任意多次，不必依赖编译程序。解释程序:对源程序的每次执行都伴随着重新翻译的工作，而是不能摆脱翻译程序。有些编译程序既支持解释执行又支持编译执行，在程序的开发和调试阶段用解释执行，一旦程序调试完毕，便采用编译执行。,编译和解释程序：,解释程序和编译程序的区别,解释程序和编译程序的根本区别：是否生成目标代码,1.2 编译程序的逻辑结构,典型的编译过程具有5个基本阶段,源程序看作什么形式便于进行处理?,对于如下的字符串,词法分析程序将分析和识别出9个单词：X1=(2.0+0.8)*C1 1 2 3 4 5 6 7 8 9,源程序是由字符序列构成的，词法分析扫描源程序,根据语言的词法规则识别出一个个单词符号（语义上关联的符号串），并以某种编码形式输出。,任务：分析和识别单词。,1 词法分析,词法分析（自动分词+词性标注）,像翻译英文句子一样，先要分析单词，弄清各单词的意义和句中的作用，才能对句子进行翻译。主要任务：从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词。单词包括：保留字、标识符、运算符、分界符等。例：position:=initial+rate*60;,词法分析（自动分词+词性标注）position:=initial+rate*60;,单词类型单词值 标识符1(id1)position 算符(赋值):=标识符2(id2)initial 算符(加)+标识符3(id3)rate 算符(乘)*整数 60 界符；,又如一个C源程序片断：int a;a=a+2;词法分析后可能返回:单词类型单词值 保留字 int标识符(变量名)a界符;标识符(变量名)a算符(赋值)=标识符(变量名)a 算符(加)+整数 2界符；,有关术语,词法分析(lexical analysis or scanning)-The stream of characters making up a source program is read from left to right and grouped into tokens,which are sequences of characters that have a collective meaning.单词-token保留字-reserved word标识符-identifier(user-defined name),例如，对于前面提到的例子X1=(2.0+0.8)*C1 语法分析将、识别出来，进而将识别出来，在识别过程中进行语法检查，若有错误，则应输出出错信息。,任务：在词法分析的基础上，根据语法规则分析单词序列对应的语法成分，如表达式、各种说明、各种语句、函数等，并进行语法正确性检查。,2 语法分析,语法分析（自动句法分析）,语法分析程序与自然语言中句子的语法分析类似。语法分析定义了程序的结构元素及其关系。通常将语法分析的结果表示为分析树或语法树。主要任务：在词法分析的基础上，将单词分解成各类语法短语。一般语法短语可表示成语法树。功能:层次分析.依据源程序的语法规则把源程序的单词序列组成语法短语(表示成语法树).position:=initial+rate*60;,语法分析（自动句法分析）,规则:=“:=”:=“+”:=“*”:=“(”“)”:=:=:=,赋值语句,标识符,表达式,表达式,+,表达式,表达式,标识符,整数,标识符,:=,表达式,*,id1:=id2+id3*N,术语,语法分析(syntax analysis or parsing)The purpose of syntax analysis is to determine the source programs phrase structure.This process is also called parsing.The source program is parsed to check whether it conforms to the source languages syntax,and to construct a suitable representation of its phrase structure.语法树(推导树)(parse tree or derivation tree),3 语义分析和中间代码生成,语义分析：静态语义处理 审查源程序有无语义错误，为代码生成阶段收集类型信息。中间代码生成：动态语义处理,四元式（三地址指令）,四元式的语义为：2.0+0.8 T1 T1*C1 T2 T2 X1这样所生成的四元式与原来的赋值语句在语言的形式上不同，但语义上等价。,运算符 左运算对象 右运算对象 结果(+2.0 0.8 T1)(*T1 C1 T2)(=X1 T2)其中T1和T2为编译程序引入的临时变量,对于前面提到的例子 X1=(2.0+0.8)*C1,优化：上面的四元式中第一个四元式是计算常量表达式值，该值在编译时就可以算出并存放在临时变量中，不必生成目标指令来计算，这样四元式可优化为：编译时：2.0+0.8 T1,运算符 左运算对象 右运算对象 结果(*2.8 C1 T1)(=X1 T1),4 代码优化,5 目标代码生成,由中间代码很容易生成目标代码（地址指令序列）。这部分工作与机器关系密切，所以要根据机器进行，也可以进行优化处理。,注意：在翻译成目标程序的过程中，要切记保持语义的等价性。,在上列五个阶段中都要做两件事：（1）建表和查表；（2）出错处理；所以编译程序中都要包括表格管理和出错处理两部分,源程序示例,PROGRAM m;VAR a,b,c:real;BEGIN read(b,c);a:=b+c*60;write(a)END.,经词法分析源程序被加工成单词流,.,赋值语句,变 量,:=,表达式,表达式,+,项,项,因子,b,项,*,因子,因子,c,60,a,赋值语句经语法分析生成分析树,:=,a,+,b,*,c,inttoreal,60,赋值语句经语义分析生成语法树,生成中间代码,temp1:=inttoreal(60);temp2:=c*temp1;temp3:=b+temp2;a:=temp3;,优 化,Temp1:=c*60.0a:=b+temp1,生成目标代码,movf c,r2;mulf#60.0,r2;movf b,r1;addf r2,r1;movf r1,a;,符号表,1.3 编译阶段的组合,前端和后端 根据编译程序各部分功能，将编译过程分成前端和后端。,这一结构对于编译器的可移植性十分重要。某一编译程序的前端加上相应不同的后端则可以为不同的机器构成同一个源语言的编译程序。如果不同编译程序的前端生成同一种中间代码，再使用一个共同的后端，则可为同一机器生成几个语言的编译程序。,遍（PASS）遍：对源程序（或者源程序中间形式）从头到尾扫描一次，进行相应的加工处理，生成新的源程序中间形式或目标程序，通常称之为一遍。,JAVA源程序,词法、语法分析,*.class类文件格式,语义处理,内存代码缓冲区JAVA Byte code,Java 类文件格式输出处理,抽象语法树,Java 虚拟机,SUN GJC编译器举例,1.4 编译程序实现的途径,手工编写耗时，“效率”问题。自动生成 各个阶段基本上有相应的自动生成工具，如lex、yacc。自展（bootstrapping),编译程序的自动化技术,词法分析：Lex由Mike Lesk在1975年左右为UNIX开发的，现在流行的是Free Software Foundation创建的Gnu complier package包中的Flex语法分析：Yacc(yet another complier-complier)由Steve Johnson在1975年左右为UNIX开发的，现在流行的是bison+,词法分析器的自动生成程序,词法规则说明,词法分析程序,(C程序),输入：词法（正规表达式）识别动作（程序段）输出：yylex()函数,语法分析器的自动生成程序,语法规则说明,语法分析程序,(C程序),输入：语法规则（产生式）语义动作（程序段）输出：yyparse()函数,自展技术,先对语言的核心部分构造一个小小的编译程序（可用低级语言实现），再以它为工具构造一个能够编译更多语言成分的较大编译程序。如此扩展下去，就像滚雪球一样，越滚越大，最后形成人们所期望的整个编译程序。这种通过一系列的自展途径而形成编译程序的过程叫做自编译过程(编译程序的自展技术)。,L0,编译程序的移植技术,编译程序可以通过移植得到，即可以将一个机器（宿主机）上的一个具有自编译性的高级语言编译程序搬迁到另一个机器（目标机）上。而可移植性则是对这种搬迁过程中难易过程的一种度量。如果工作量不大，则称该程序是可以移植的；若移植一个程序的开销远远低于最初研制程序的开销，那么这种程序就是高度可移植的。,编译程序生成,编译程序的自展/自编译T型图,源语言S,目标语言T,编译程序的实现语言I,编译程序生成,编译程序的自展/自编译 我们的目标是在机器A（目标语言）上，用语言A（实现语言）构造高级语言L（源语言）的编译程序。,编译程序生成,编译程序的自展/自编译 Step1:我们可以考虑源语言L的子集语言S,S L。在机器A（目标语言）上，用语言A（实现语言）构造语言S的编译程序。,编译程序生成,编译程序的自展/自编译 Step2:在机器A（目标语言）上，用语言S（实现语言）构造语言L的编译程序。,编译程序生成,编译程序的自展/自编译 Step3:,编译程序生成,编译程序的移植/交叉编译考虑将A机器上语言L的编译实现移植到机器B上，即我们的目标是：,编译程序生成,编译程序的移植/交叉编译我们已有的编译程序是：,编译程序生成,编译程序的移植/交叉编译Step1:,用语言L编写的语言L到语言B的编译程序,借助已有的A机器上语言L的编译程序,得到机器A上（实现语言）语言L到语言B的编译程序,编译程序生成,编译程序的移植/交叉编译Step2:,用语言L编写的语言L到语言B的编译程序,新的A机器上语言L到语言B的编译程序,得到机器B上（实现语言）语言L到语言B的编译程序,编译程序相关的软件,预处理程序preprocessor宏替换macro包含文件展开include files汇编程序assembler两趟扫描解释程序interpreter连接程序linker装入程序loader重定位,1.6.2 编译程序的移植技术,编译程序可以通过移植得到，即可以将一个机器（宿主机）上的一个具有自编译性的高级语言编译程序搬迁到另一个机器（目标机）上。而可移植性则是对这种搬迁过程中难易过程的一种度量。如果工作量不大，则称该程序是可以移植的；若移植一个程序的开销远远低于最初研制程序的开销，那么这种程序就是高度可移植的。,编译程序相关的软件,调试程序debuggercc 编译器中 g 选项；与-O的关系描述程序profiler性能分析,1.5、语言开发环境中的伙伴程序,编辑器（editor）预处理器编译器连接程序装配程序调试程序,源程序：多文件、宏定义和宏调用，包含文件 目标程序：一般为汇编程序或可重定位的机器代码,框架源程序,预处理器,源程序,编译程序,目标程序（汇编）,汇编程序,可重定位机器码（Obj文件）,可重定位机器码（文件组）,连接编译,库目标、可重定位目标文件,可重定位机器码,加载器,可运行的机器代码,1.6 编译程序的构造工具,词法分析：Lex由Mike Lesk在1975年左右为UNIX开发的，现在流行的是Free Software Foundation创建的Gnu complier package包中的Flex语法分析：Yacc(yet another complier-complier)由Steve Johnson在1975年左右为UNIX开发的，现在流行的是bison+基于属性文法的系统：GAG(Generator based on Attributed Grammars),HLP(Helsinki Language Processor)基于语义文法的系统：CGSG(Compiler Generator for Semantics Grammars),编译原理的最新发展,开发复杂的算法程序，用于优化和简化程序IDE（Interactive development environment）并行编译技术：适合并行机和多处理机系统硬件描述语言及其编译技术,编技术面对的挑战新的问题New Computer Architectures:VLIW(Very Long Instruction Word),instead of CISC(Complex Instruction Set Computer)and RISC(ReducedInstruction Set Computer),Multi-core processor(superscalar execution,pipelining,and multithreading);Embedded environment Small ROM&RAM,特殊的指令集；Program Security.面对的挑战指令调度以支持指令的并行执行，降低CPU能耗（移动设备）；代码的空间和内存的优化，以支持微处理器对ROM和RAM的限制；程序的静态与动态分析以检测程序的安全漏洞；程序附注信息的认证以解决可执行文件在网络上传输的安全问题(Proof-Carrying Code)；认证编译器(Certied Compiler):保证相关性质经编译后还能保持。,c hfwang,-24/46-,什么是编译程序,同解释程序的区别编译程序的逻辑结构,分为那几个阶段编译阶段的组合,怎么组合？组合的依据编译程序实现的途径,如何实现,如何移植,小 结,