编译原理课件(龙书为教材)

编译原理2020/4/18计算机学院辛明影2自我介绍姓名：辛明影电话：86413213教研室：计算机软件基础办公室：综合楼513[e-mail][e-mail]助课教师：洪晓鹏，综合楼614单丽丽，新技术楼6082020/4/18计算机学院辛明影3开课目的及应用前景：介绍设计与构造程序设计语言编译程序的原理与方法源程序编译程序目标程序连接可执行程序预备知识：形式语言与自动机、两门以上的高级程序设计语言汇编语言数据结构等How?2020/4/18计算机学院辛明影4内容简介：第一章：编译器的基本结构第二章：高级语言及其语法描述第三章：词法分析器第四章：语法分析技术第五章：语法制导翻译的主要概念及中间代码第六章：程序运行时的存贮分配问题第七章：代码优化第八章：目标代码生成2020/4/18计算机学院辛明影5教学设计：(1)自顶向下，逐步求精的方法(2)问题驱动(3)将课程设计成一个应用平台(4)用实验拓广课堂教学(5)精讲多练(6)承前启后教学目标：2020/4/18计算机学院辛明影6第一章绪论编译器就是一个程序，它读入用某种语言编写的源程序，并翻译成一个与之等价的另一种语言编写的源程序。编译器源程序目标程序错误信息Fortran、Pascal、Java、C…..另一种程序设计语言、汇编语言、机器语言1.1什么叫编译程序2020/4/18计算机学院辛明影71.2编译过程概述编译程序的工作，从输入源程序开始，到输出目标程序结束，与自然语言之间的翻译有很多相似之处。一段英文翻译成中文，需经下列步骤：识别出句子中的单词分析句子的语法结构根据句子的含义进行初步分析对译文进行修饰写出最后的译文编译程序词法分析代码优化语法分析语义分析及中间代码生成目标代码生成构成编译程序各个阶段Iamaexperiencedteacher.2020/4/18计算机学院辛明影8编译器的各个阶段：编译器是分阶段执行的。每个阶段将源程序从一种表示转换成另一种表示源程序词法分析器错误处理器符号管理表语法分析器语义分析器中间代码生成器代码优化器代码生成器编译的各个阶段2020/4/18计算机学院辛明影9各分析阶段随着编译器各个阶段的进展，源程序的内部表示不断地发生变化。以a=b+c*d为例1。词法分析读入源程序完成的任务：识别出单词：a、=、b、+、c、*、d并用记号方式表示识别出的单词关键字、标识符、常数、算符和界符例：25表示a、b、c、d；36：＝；３2：＋；31：*记号表示逻辑上相关的字符序列，常用整数来表示上述单词表示为：(25,a),(36,_),(25,b),(32,_),(25,c),(31,_),(25,d)2020/4/18计算机学院辛明影10语法分析在词法分析的基础上，根据语言的语法规则，把单词符号串组成各类语法单位.具体的说，语法分析是在单词流的基础上建立一个层次结构-----建立语法树赋值语句标识符=表达式a表达式标识符b+表达式表达式*标识符c表达式标识符d2020/4/18计算机学院辛明影11语义分析阶段语义分析利用语法分析阶段确定的层次结构来识别表达式和语句中的操作信息及类型信息=+ab*cdtemp1=c*dtemp2=b+temp1temp1temp2a=temp22020/4/18计算机学院辛明影12中间代码生成阶段本阶段将产生源程序的一个显式中间表示这种中间表示可以看成是某种抽象的程序，通常是与平台无关的其重要性质：1.易于产生2.易于翻译成目标程序下面是用三地址码和四元式表示的例子：temp1=c*dtemp2=b+temp1a=temp2（*,c,d,tempt1)(+,b,tempt1,tempt2)(=,tempt2,,a)2020/4/18计算机学院辛明影13代码优化阶段试图改进中间代码，以产生执行速度较快的机器代码对上面中间代码进行优化处理后，产生如下的代码：temp1=c*da=b+temp1temp1=c*dtemp2=b+temp1a=temp22020/4/18计算机学院辛明影14代码生成阶段生成可重定位的机器代码或汇编代码MovfR2，cMultR2,dMovfR1,bAddfR2,R1Movfa,R22020/4/18计算机学院辛明影151.3符号表管理inta,b;floate,fcharch1,ch2;为什么要先说明?定义了变量的类型，也就规定了变量在内存中的存放形式，在其上所能进行的运算解决符号地址到存贮地址上的映射2020/4/18计算机学院辛明影16编译器的一个基本功能是记录源程序中使用的标识符并将它们记载到符号表中。符号表是一个数据结构。每个标识符在符号表中都有一条记录名字记号类型种属……addrid1(25)id2(25)ba例：inta,b;int简变04并收集与每个标识符相关的各种属性信息，int简变2020/4/18计算机学院辛明影17符号表的接口：符号表的作用就是存放字符串或词素当一个字符串或词素被保存时，与之相对应的记号也被保存符号表上的操作：Insert(s,t):将符号串s和记号t插入符号表，返回相应表项的指针Lookup(s):在符号表中查找字符串s，查找成功返回相应指针，否则返回02020/4/18计算机学院辛明影18关键字的处理通常情况下，将关键字存在符号表中，作为符号表的初值。当词法分析程序识别出一个标识符s后，用lookup(s)查找符号表，如果是关键字，返回相应的记号；如果是变量名，返回记号id2020/4/18计算机学院辛明影19符号表的实现固定长标识符：采用前面的结构不定长标识符：使用单独的数组lexemesifeosinteospositioneosinitialeosIf(12)Int(13)Id1(25)Id2(25)存放标识符的字符串,符号表中存放标识符在lexemes的起始位置和相应记号2020/4/18计算机学院辛明影201.4编译各阶段的分组一、前端和后端前端包括词法分析、词法分析、语义分析，以及相关的错误处理和符号表的建立前端依赖于源程序并在很大程度上独立于目标机器。2020/4/18计算机学院辛明影21后端主要包括代码优化、代码生成和相关错误处理。后端依赖于目标机器。后端处理对象是由前端产生的结果，即中间代码前端生成与平台无关的字节码后端是由与平台有关的解释器对所生成的字节码文件进行解释执行Java语言的编译采用的是前端后端方式。2020/4/18计算机学院辛明影22二、编译的遍编译的若干阶段通常是以一遍来实现的，每遍读一次输入文件、产生一个输出文件。2020/4/18计算机学院辛明影23在编译的各个阶段都会发现源程序中的错误，1.5错误检测与报告为了使编译器能继续运行，以检测出源程序中更多的错误，在检测到错误后，必须以合适的方式进行错误处理。error第二章高级语言及其语法描述2020/4/18计算机学院辛明影25内容简介：本章概述程序设计语言的结构2.1程序语言的定义任何语言实现的基础是语言定义。语言的定义决定了该语言具有什么样的语言功能、什么样的数据结构、什么样的程序结构、以及具体的使用形式等细节问题。和主要的共同特征，并介绍程序设计语言主要语句的文法描述与形式定义。2020/4/18计算机学院辛明影26对于编译程序设计者来说：语言定义就是具体实现的理论依据。对于语言用户来说：语言定义就是一本用户手册。2.1.1语法语言的语法是指这样一组规则，用它可产生一个程序。规则：词法规则语法规则2020/4/18计算机学院辛明影27词法规则是指单词符号的形成规则字母表就是一个有穷字符集。C语言的字母表为：∑={a---z、A—Z、0—9、(、)、[、]、、.、!、~、+、-、*、/、&、%、、、=、^、|、?、,、;}C语言的标识符的构成规则：字母、下划线打头的字母、数字和下划线构成的符号串。如：a1、ave、_day一.词法规则2020/4/18计算机学院辛明影28上述的定义是用文字来描述的，当设计编译程序时，就要把它用形式的方式描述出来，就要用到形式语言。各类型的常数、标识符、基本字、算符和界符等正规式和有穷自动机是描述词法结构和进行词法分析的有效工具在现今多数程序设计语言中，单词符号一般包括：2020/4/18计算机学院辛明影29C语言的标识符的文法和自动机描述：例：C语言标识符的文法描述L（G）={w/w为字母或‘-’打头的字母数字串}解：P:I→aBI→-BI→aB→aBB→dBB→aB→d识别L（G）的自动机IBTa-a,d其它2020/4/18计算机学院辛明影30SACDFEB7dddddddee+–T*例：C语言实常数的文法描述文法：S→dAA→dAA→eDA→.BB→dCC→dCC→eDD→-ED→+ED→dFE→dFF→dFF→d其它其它其它10003.1410e+33.14e-512e50.1e242020/4/18计算机学院辛明影31二.语法规则语法规则规定了如何从单词符号形成更大的结构（即语法单位），换言之，语法规则是语法单位的形成规则一般的程序设计语言的语法单位有：表达式、语句、分程序、函数、过程和程序等下推自动机理论和上下文无关文法是我们讨论语法分析的理论基础2020/4/18计算机学院辛明影32表达式：E→E+TE→E-TE→TT→T*FT→T/FT→FF→(E)F→id主要语句的形式描述：2020/4/18计算机学院辛明影33布尔表达式：B→BorBB→BandBB→notBB→(E）B→idrelopidB→trueB→false2020/4/18计算机学院辛明影34赋值、分支、循环语句：S→id=ES→ifBthenSS→ifBthenSelseSS→whileBdoSS→{L}L→L;SL→S2020/4/18计算机学院辛明影35调用语句：S→callid(Elist)Elist→Elist,EElist→E|ε2020/4/18计算机学院辛明影36类型说明和过程说明语句：P→DD→D;DD→id:TD→id（Elist）D;ST→intT→float2020/4/18计算机学院辛明影37数组说明语句：L→id[Elist]Elist→Elist,EElist→E2020/4/18计算机学院辛明影382.1.2语义例：a=b+c*d例do999I=1,10对于一个语言来说，不仅要给出它的词法、语法规则，而且要定义它的单词符号和语法单位的意义，这就是语义问题对于编译程序来说，只有了解程序的语义，才知道应把它翻译成什么样的目标指令代码2020/4/18计算机学院辛明影392.2构造基础2.2.1程序结构简介一个高级语言程序通常由若干子程序段（过程、函数等）组成，许多语言还引入了类、程序包等更高级的结构2020/4/18计算机学院辛明影40一.FORTRAN一个FORTRAN程序由一个主程序和若干个辅助程序段组成PROGRAMMAIN.ENDSUBROUTINESUB1..ENDFUNCTIONFUN1.END它的定义是并列的2020/4/18计算机学院辛明影41FORTRAN的构成特点：同一名字在不同的程序段中一般都代表不同的对象，也就是说代表不同的存贮单元PROGRAMMAIN.integerxENDSUBROUTINESUB1Integerx.ENDIntegerxXX=9999100Integerx9999X=100XPROGRAMMAIN.ENDSUBROUTINESUB1.END一个名字对应多个对象2020/4/18计算机学院辛明影42但是不同程序段里的同名公用块却代表同一个存贮区域PROGRAMMAIN.Commona,bENDSUBROUTINESUB1commonx,y.ENDPROGRAMMAIN.ENDSUBROUTINESUB1.ENDCommona,babA=100B=5010050Commonx,yxyY=x+100200共享存贮单元多个名字对应一个对象2020/4/18计算机学院辛明影43二。PascalPascal允许子程序嵌套