编译概述中国矿业大课件

E-mail:Compiler 学时学时:5656学时学时 分为两部分分为两部分:理论基础理论基础:70%,:70%,课堂教学课堂教学实践部分实践部分:30%,:30%,实验实验(16(16学时学时)课程要求课程要求:掌握编译技术的基本理论、编译系统的构造（结构和机掌握编译技术的基本理论、编译系统的构造（结构和机理）并进行编译程序相关部分的设计，加深对计算机高级理）并进行编译程序相关部分的设计，加深对计算机高级语言的理解，在此基础上能够灵活运用所学技术解决实际语言的理解，在此基础上能够灵活运用所学技术解决实际问题问题。程序如何被翻译为机器指令程序如何被翻译为机器指令 1.变量的本质是什么？2.顺序、选择、循环语句对应哪些中间或目标代码？3.函数调用时局部变量在内存中如何分配？4.如何深入理解对象与变量的区别？5.对象如何存放？程序中同一类对象如何存放？看不见的this指针到底有什么用？6.函数重载编译器都做了什么？7.什么是多态？编译器做了哪些工作来支持虚函数？虚函数运行时是什么情况？8.任意给出一个面向过程或面向对象的程序，我如何深入分析执行过程？为什么要学习编译原理为什么要学习编译原理b学习这门课程有利于加深对程序设计语言的学习这门课程有利于加深对程序设计语言的理解，可以比较迅速掌握新的语言工具，也理解，可以比较迅速掌握新的语言工具，也是读懂相关计算机著作的基础是读懂相关计算机著作的基础b编译程序是计算机系统中的系统软件，包含编译程序是计算机系统中的系统软件，包含许多软件技术，对于进行软件设计很有价值许多软件技术，对于进行软件设计很有价值b编译课程蕴含着计算机学科中解决问题的思编译课程蕴含着计算机学科中解决问题的思路、抽象问题和解决问题的方法路、抽象问题和解决问题的方法 （1 1）编译原理及实践编译原理及实践 机械工业出版社，机械工业出版社，Kenneth C.Louden Kenneth C.Louden 冯博琴等翻译，英文冯博琴等翻译，英文 原版原版Complier Construction Principles and Complier Construction Principles and PracticePractice 。（2 2）程序设计语言编译原理程序设计语言编译原理，国防工业出版，国防工业出版社，社，陈火旺陈火旺等编著。等编著。（3 3）编译原理编译原理清华大学出版社，吕映芝等编清华大学出版社，吕映芝等编著，著，19981998。（4 4）编译原理和技术编译原理和技术中国科技大学出版社，中国科技大学出版社，陈意云编著，陈意云编著，19971997。参考书参考书国外参考书（编译圣经）国外参考书（编译圣经）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 编译程序的构造工具程序设计语言：程序设计语言：用来编写计算机程序的语言。1.1 什么是编译程序什么是编译程序程序设计语言 机器语言：直接用计算机能够识别的二进制代码指令来编写程序的语言。由二进制的指令代码组成。1+3 表示为表示为 10 是最底层的计算机语言，不需要翻译就可以直接被计算机硬件识别。对应不同的计算机硬件有不同的机器语言。特点：执行速度快，但编写程序的难度大，修改、调试不方便，直观性差，不易移植。程序设计语言 汇编语言：又称为符号语言。与机器语言一一对应，采用能帮助记忆的英文缩写符号（指令助记符）来代替机器语言指令中的操作码，用地址符号来代替地址码。用指令助记符及地址符号书写的指令称为汇编指令，用汇编指令编写的程序称为汇编语言源程序。将将X、Y中的内容相加中的内容相加 表示为表示为 ADD X Y 机器不能直接识别汇编语言程序，必须把它翻译为机器语言程序才能执行。特点：比机器语言直观，容易理解和记忆，比高级语言的执行效率高，但通用性和移植性较差。程序设计语言 高级语言：与具体的计算机硬件无关，是面向问题的程序设计语言，其表达方式接近于自然语言和数学语言，易于人们接受和掌握。采用类似于数学公式的书写方式：x=1+3 特点：独立于具体的计算机硬件，程序的编制和调试方便，通用性和可移植性好。在计算机执行之前，需要通过编译程序翻译成目标语言程序，或需要通过解释程序边解释，边执行。时间与空间效率比较低。目前比较流行的高级语言有：Visual C,Visual Basic,Java，FoxPro，Pascal,Lisp,Cobol等。比较 机器语言汇编语言高级语言硬件识别是唯一可以识别的语言不可识别不可识别是否可直接执行 可直接执行不可，需汇编、连接不可，需编译/解释、连接 特点面向机器占用内存少执行速度快使用不方便面向机器占用内存少执行速度快较为直观与机器语言一一对应v面向问题/对象v占用内存大v执行速度相对慢v标准化程度高v便于程序交换，使用方便 定位低级语言，极少使用低级语言，很少使用高级语言，种类多，常用翻译程序翻译程序 把一种语言书写的程序（源程序）翻译成另一种语言的等价等价的程序（目标程序）。是汇编程序、编译程序以及各种变换程序的总称。源程序、翻译程序、目标程序 三者关系：源程序翻译程序目标程序即源程序是翻译程序的输入，目标程序是翻译程序的输出汇编程序汇编程序 把汇编语言程序翻译成机器语言程序，这时的翻译程序称之为汇编程序，这种翻译过程称为“汇编”(Assemble）编译程序编译程序 把高级语言程序翻译成低级语言程序，这时的翻译程序称之为编译程序，这种翻译过程称“编译”（Compile)汇编程序与编译程序都是翻译程序，主要区别是加工对象的不同。由于汇编语言格式简单，常与机器语言之间有一一对应的关系。汇编程序所要做的翻译工作比编译程序简单的多。编译程序编译程序是翻译程序的一种，它将一个用面向是翻译程序的一种，它将一个用面向 人的源语言书写的程序（高级语言程序）翻译成人的源语言书写的程序（高级语言程序）翻译成 一个一个等价等价的面向硬件的目标程序（低级语言程序）的面向硬件的目标程序（低级语言程序）源程序源程序目标程序目标程序编译程序编译程序人可以理解的高级语言机器可以“理解”的低级语言 解释程序解释程序 对源程序进行解释执行的程序对源程序进行解释执行的程序 以源程序作为输入，但不产生目标程序，对源程序以源程序作为输入，但不产生目标程序，对源程序边解释边执行边解释边执行 比较编译程序与解释程序的区别比较编译程序与解释程序的区别编译程序：编译程序：生成一个与源程序等价的目标程序，它可生成一个与源程序等价的目标程序，它可以完全取代源程序，目标程序可运行任意多次，不以完全取代源程序，目标程序可运行任意多次，不必依赖编译程序。必依赖编译程序。解释程序解释程序:对源程序的每次执行都伴随着重新翻译的对源程序的每次执行都伴随着重新翻译的工作，而是不能摆脱翻译程序。工作，而是不能摆脱翻译程序。有些有些编译程序既支持解释执行又支持编译执行，在程编译程序既支持解释执行又支持编译执行，在程序的开发和调试阶段用解释执行，一旦程序调试完序的开发和调试阶段用解释执行，一旦程序调试完毕，便采用编译执行。毕，便采用编译执行。编译和解释程序：功能功能工作结果工作结果实现技术上实现技术上编译编译程序程序源程序的一个转换转换系统源程序的目标代码目标代码把中间代码转换成目标程序解释解释程序程序源程序的一个执行执行系统源程序的执行结果执行结果执行中间代码解释程序和编译程序的区别解释程序和编译程序的：是否生成目标代码1.2 编译程序的逻辑结构编译程序的逻辑结构典型的编译过程具有典型的编译过程具有5个基本阶段个基本阶段S.PO.P语义分析与中间代码生成目标代码生成程序代码优化语法分析程序词法分析程序出错处理信息表管理源程序看作什么形式便于进行处理?对于如下的字符串,词法分析程序将分析和识别出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:=+N 60*id1 Positionid2 initialid3 rate术语 语法分析(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*cinttoreal 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 ;符号表名 字种 类 类 型 层 次 偏移量m过 程0a变 量 real1db变 量 real1d+4c变 量 real1d+81.3 编译阶段的组合前端和后端前端和后端 根据编译程序各部分功能，将编译过程分成前端和后端。前端前端：通常将与源程序有关的编译部分称为前端。词法分析、语法分析、语义分析、中间代码生成（优化）-分析部分 特点：与源语言本身有关 后端后端：与目标机有关的部分称为后端。目标代码生成、目标代码的优化-综合部分 特点：与目标机有关后端前端源程序目标程序中间代码 这一结构对于编译器的可移植性可移植性十分重要。某一编译程序的前端加上相应不同的后端则可以为不同的机器构成同一个源语言的编译程序。如果不同编译程序的前端生成同一种中间代码，再使用一个共同的后端，则可为同一机器生成几个语言的编译程序。后端前端源程序目标程序中间代码 遍遍（PASS）遍：对源程序（或者源程序中间形式）从头到尾扫描一次，进行相应的加工处理 ，生成新的源程序中间形式或目标程序，通常称之为一遍。第一遍 第二遍 S.P中间形式1S.P中间形式2C2C1S.PO.P 上一遍的结果是下一遍的输入，最后一遍生成目标程序。五个基本阶段：是将源程序翻译为目标程序在逻辑上逻辑上要完成的 工作。遍：是指完成上述5个基本阶段的工作，要经过多次扫描处理。每一遍扫描可以完成一个或多个阶段的工作。要注意遍与基本阶段的区别要注意遍与基本阶段的区别JAVA源程序源程序词法、语法分析词法、语法分析*.class类文件格式类文件格式语义处理语义处理内存代码缓冲区内存代码缓冲区JAVA Byte codeJava 类文件格式输出处理类文件格式输出处理抽象语法树抽象语法树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()函数函数自展技术Ln=LLn=LL1L1 先对语言的核心部分构造一个小小的编译程序（可用低级语言实现），再以它为工具构造一个能够编译更多语言成分的较大编译程序。如此扩展下去，就像滚雪球一样，越滚越大，最后形成人们所期望的整个编译程序。这种通过一系列的自展途径而形成编译程序的过程叫做自编译过程(编译程序的自展技术)。L0L0编译程序的移植技术 编译程序可以通过移植得到，即可以将一个机器（宿主机）上的一个具有自编译性的高级语言编译程序搬迁到另一个机器（目标机）上。而可移植性则是对这种搬迁过程中难易过程的一种度量。如果工作量不大，则称该程序是可以移植的；若移植一个程序的开销远远低于最初研制程序的开销，那么这种程序就是高度可移植的。编译程序生成 编译程序的自展/自编译T型图S T I源语言S目标语言T编译程序的实现语言I编译程序生成 编译程序的自展/自编译 我们的目标是在机器A（目标语言）上，用语言A（实现语言）构造高级语言L（源语言）的编译程序。L A A编译程序生成 编译程序的自展/自编译 Step1:我们可以考虑源语言L的子集语言S,S L。在机器A（目标语言）上，用语言A（实现语言）构造语言S的编译程序。S A A编译程序生成 编译程序的自展/自编译 Step2:在机器A（目标语言）上，用语言S（实现语言）构造语言L的编译程序。L A S编译程序生成 编译程序的自展/自编译 Step3:L A SS A AL A A编译程序生成 编译程序的移植/交叉编译考虑将A机器上语言L的编译实现移植到机器B上，即我们的目标是：L B B编译程序生成 编译程序的移植/交叉编译我们已有的编译程序是：L A A编译程序生成 编译程序的移植/交叉编译Step1:L B LL A AL B A用语言L编写的语言L到语言B的编译程序借助已有的A机器上语言L的编译程序得到机器A上（实现语言）语言L到语言B的编译程序编译程序生成 编译程序的移植/交叉编译Step2:L B LL B AL B B用语言L编写的语言L到语言B的编译程序新的A机器上语言L到语言B的编译程序得到机器B上（实现语言）语言L到语言B的编译程序编译程序相关的软件 预处理程序preprocessor宏替换macro包含文件展开include files 汇编程序assembler两趟扫描 解释程序interpreter 连接程序linker 装入程序loader重定位1.6.2 编译程序的移植技术 编译程序可以通过移植得到，即可以将一个机器（宿主机）上的一个具有自编译性的高级语言编译程序搬迁到另一个机器（目标机）上。而可移植性则是对这种搬迁过程中难易过程的一种度量。如果工作量不大，则称该程序是可以移植的；若移植一个程序的开销远远低于最初研制程序的开销，那么这种程序就是高度可移植的。编译程序相关的软件 调试程序debugger cc 编译器中 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)编译原理的最新发展编译原理的最新发展b开发复杂的算法程序，用于优化和简化程序bIDE（Interactive development environment）b并行编译技术：适合并行机和多处理机系统b硬件描述语言及其编译技术 编技术面对的挑战新的问题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)；认证编译器(Certified Compiler):保证相关性质经编译后还能保持。c hfwang-24/46-什么是编译程序,同解释程序的区别 编译程序的逻辑结构,分为那几个阶段 编译阶段的组合,怎么组合？组合的依据 编译程序实现的途径,如何实现,如何移植 小小 结结