编译原理恐龙书.ppt
《编译原理恐龙书.ppt》由会员分享,可在线阅读,更多相关《编译原理恐龙书.ppt(696页珍藏版)》请在三一办公上搜索。
1、编译原理,2023/10/17,辛明影,2,自我介绍,姓名:辛明影电话:86413213 教研室:计算机软件基础 办公室:综合楼513,助课教师:洪晓鹏,综合楼614 单丽丽,新技术楼608,2023/10/17,辛明影,3,开课目的及应用前景:,介绍设计与构造程序设计语言编译程序的原理与方法,源程序,编译程序,目标程序,连接,可执行程序,预备知识:,形式语言与自动机、,两门以上的高级程序设计语言,汇编语言,数据结构等,How?,2023/10/17,辛明影,4,内容简介:,第一章:编译器的基本结构,第二章:高级语言及其语法描述,第三章:词法分析器,第四章:语法分析技术,第五章:语法制导翻译的
2、主要概念及中间代码,第六章:程序运行时的存贮分配问题,第七章:代码优化,第八章:目标代码生成,2023/10/17,辛明影,5,教学设计:,(1)自顶向下,逐步求精的方法(2)问题驱动(3)将课程设计成一个应用平台(4)用实验拓广课堂教学(5)精讲多练(6)承前启后,教学目标:,2023/10/17,辛明影,6,第一章绪论,编译器就是一个程序,它读入用某种语言编写的源程序,并翻译成一个与之等价的另一种语言编写的源程序。,编译器,源程序,目标程序,错误信息,Fortran、Pascal、Java、C.,另一种程序设计语言、,汇编语言、机器语言,1.1什么叫编译程序,2023/10/17,辛明影,
3、7,1.2编译过程概述,编译程序的工作,从输入源程序开始,到输出目标程序结束,与自然语言之间的翻译有很多相似之处。,一段英文翻译成中文,需经下列步骤:,识别出句子中的单词,分析句子的语法结构,根据句子的含义进行初步分析,对译文进行修饰,写出最后的译文,编译程序,词法分析,代码优化,语法分析,语义分析及中间代码生成,目标代码生成,构成编译程序各个阶段,I am a experienced teacher.,2023/10/17,辛明影,8,编译器的各个阶段:,编译器是分阶段执行的。,每个阶段将源程序从一种表示转换成另一种表示,源程序,词法分析器,错误处理器,符号管理表,语法分析器,语义分析器,中
4、间代码生成器,代码优化器,代码生成器,编译的各个阶段,2023/10/17,辛明影,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),2023/10/17,辛明影,10,语法分析,在词法分析的
5、基础上,根据语言的语法规则,把单词符号串组成各类语法单位.,具体的说,语法分析是在单词流的基础上建立一个层次结构-建立语法树,赋值语句,标识符,=,表达式,a,表达式,标识符,b,+,表达式,表达式,*,标识符,c,表达式,标识符,d,2023/10/17,辛明影,11,语义分析阶段,语义分析利用语法分析阶段确定的层次结构来识别表达式和语句中的操作信息及类型信息,=,+,a,b,*,c,d,temp1=c*d,temp2=b+temp1,temp1,temp2,a=temp2,2023/10/17,辛明影,12,中间代码生成阶段,本阶段将产生源程序的一个显式中间表示,这种中间表示可以看成是某种
6、抽象的程序,通常是与平台无关的,其重要性质:1.易于产生2.易于翻译成目标程序,下面是用三地址码和四元式表示的例子:,temp1=c*dtemp2=b+temp1a=temp2,(*,c,d,tempt1)(+,b,tempt1,tempt2)(=,tempt2,a),2023/10/17,辛明影,13,代码优化阶段,试图改进中间代码,以产生执行速度较快的机器代码,对上面中间代码进行优化处理后,产生如下的代码:,temp1=c*da=b+temp1,temp1=c*dtemp2=b+temp1a=temp2,2023/10/17,辛明影,14,代码生成阶段,生成可重定位的机器代码或汇编代码,M
7、ovf R2,cMult R2,dMovf R1,bAddf R2,R1Movf a,R2,2023/10/17,辛明影,15,1.3符号表管理,int a,b;float e,fchar ch1,ch2;,为什么要先说明?,定义了变量的类型,也就规定了变量在内存中的存放形式,在其上所能进行的运算,解决符号地址到存贮地址上的映射,2023/10/17,辛明影,16,编译器的一个基本功能是记录源程序中使用的标识符,并将它们记载到符号表中。,符号表是一个数据结构。,每个标识符在符号表中都有一条记录,名字,记号,类型,种属,addr,id1(25),id2(25),b,a,例:int a,b;,in
8、t,简变,0,4,并收集与每个标识符相关的各种属性信息,,int,简变,2023/10/17,辛明影,17,符号表的接口:,符号表的作用就是存放字符串或词素,当一个字符串或词素被保存时,与之相对应的记号也被保存,符号表上的操作:,Insert(s,t):将符号串s和记号t插入符号 表,返回相应表项的指针,Lookup(s):在符号表中查找字符串s,查找成功返回相应指针,否则返回0,2023/10/17,辛明影,18,关键字的处理,通常情况下,将关键字存在符号表中,作为符号表的初值。,当词法分析程序识别出一个标识符s后,用lookup(s)查找符号表,如果是关键字,返回相应的记号;如果是变量名,
9、返回记号id,2023/10/17,辛明影,19,符号表的实现,固定长标识符:采用前面的结构,不定长标识符:使用单独的数组lexemes,i f eos i n t eos p o s i t i o n eos i n i t i a l eos,If(12),Int(13),Id1(25),Id2(25),存放标识符的字符串,符号表中存放标识符在lexemes的起始位置和相应记号,2023/10/17,辛明影,20,1.4编译各阶段的分组,一、前端和后端,前端包括词法分析、词法分析、语义分析,以及相关的错误处理和符号表的建立,前端依赖于源程序并在很大程度上独立于目标机器。,2023/10/
10、17,辛明影,21,后端主要包括代码优化、代码生成和相关错误处理。,后端依赖于目标机器。,后端处理对象是由前端产生的结果,即中间代码,前端生成与平台无关的字节码,后端是由与平台有关的解释器对所生成的字节码文件进行解释执行,Java语言的编译采用的是前端后端方式。,2023/10/17,辛明影,22,二、编译的遍,编译的若干阶段通常是以一遍来实现的,每遍读一次输入文件、产生一个输出文件。,2023/10/17,辛明影,23,在编译的各个阶段都会发现源程序中的错误,,1.5错误检测与报告,为了使编译器能继续运行,以检测出源程序中更多的错误,在检测到错误后,必须以合适的方式进行错误处理。,error
11、,第二章 高级语言 及其语法描述,2023/10/17,辛明影,25,内容简介:,本章概述程序设计语言的结构,2.1 程序语言的定义,任何语言实现的基础是语言定义。,语言的定义决定了该语言,具有什么样的语言功能、,什么样的数据结构、,什么样的程序结构、,以及具体的使用形式等细节问题。,和主要的共同特征,,并介绍程序设计语言主要语句的文法描述与形式定义。,2023/10/17,辛明影,26,对于编译程序设计者来说:语言定义就是具体实现的理论依据。,对于语言用户来说:语言定义就是一本用户手册。,语法,语言的语法是指这样一组规则,用它可产生一个程序。,规则:词法规则 语法规则,2023/10/17,
12、辛明影,27,词法规则是指单词符号的形成规则,字母表就是一个有穷字符集。,C语言的字母表为:=a-z、AZ、09、(、)、.、!、+、-、*、/、,C语言的标识符的构成规则:,字母、下划线打头的字母、数字和下划线构成的符号串。如:a1、ave、_day,一.词法规则,2023/10/17,辛明影,28,上述的定义是用文字来描述的,当设计编译程序时,就要把它用形式的方式描述出来,就要用到形式语言。,各类型的常数、,标识符、,基本字、,算符和界符等,正规式和有穷自动机是描述词法结构和进行词法分析的有效工具,在现今多数程序设计语言中,单词符号一般包括:,2023/10/17,辛明影,29,C语言的标
13、识符的文法和自动机描述:,例:C语言标识符的文法描述L(G)=w/w为字母或-打头的字母数字串,解:P:I aB I-B I a B aB B dB Ba B d,识别L(G)的自动机,I,B,T,a,-,a,d,其它,2023/10/17,辛明影,30,S,A,C,D,F,E,B,7,d,d,d,d,d,d,d,e,e,+,T,*,例:C语言实常数的文法描述,文法:S dA A dA A eD A.B B dC C dC C eD D-E D+E D dF E dF F dF F d,其它,其它,其它,1000,3.14,10e+33.14e-5,12e50.1e24,2023/10/17,
14、辛明影,31,二.语法规则,语法规则规定了如何从单词符号形成更大的结构(即语法单位),换言之,语法规则是语法单位的形成规则,一般的程序设计语言的语法单位有:,表达式、,语句、,分程序、,函数、,过程和程序等,下推自动机理论和上下文无关文法是我们讨论语法分析的理论基础,2023/10/17,辛明影,32,表达式:EE+T EE-T ET TT*F TT/F TF F(E)F id,主要语句的形式描述:,2023/10/17,辛明影,33,布尔表达式:B B or B B B and B B not B B(E)B id relop id B true B false,2023/10/17,辛明影
15、,34,赋值、分支、循环语句:S id=E S if B then S S if B then S else S S while B do S S L L L;SL S,2023/10/17,辛明影,35,调用语句:Scall id(Elist)Elist Elist,E Elist E|,2023/10/17,辛明影,36,类型说明和过程说明语句:P D D D;D D id:T Did(Elist)D;ST int T float,2023/10/17,辛明影,37,数组说明语句:L idElist Elist Elist,E Elist E,2023/10/17,辛明影,38,语义,例:
16、a=b+c*d,例do 999 I=1,10,对于一个语言来说,不仅要给出它的词法、语法规则,而且要定义它的单词符号和语法单位的意义,这就是语义问题,对于编译程序来说,只有了解程序的语义,才知道应把它翻译成什么样的目标指令代码,2023/10/17,辛明影,39,2.2 构造基础,2.2.1 程序结构简介,一个高级语言程序通常由若干子程序段(过程、函数等)组成,,许多语言还引入了类、程序包等更高级的结构,2023/10/17,辛明影,40,FORTRAN,一个FORTRAN 程序由一个主程序和若干个辅助程序段组成,PROGRAM MAIN.ENDSUBROUTINE SUB1.ENDFUNCT
17、ION FUN1.END,它的定义是并列的,2023/10/17,辛明影,41,FORTRAN 的构成特点:,同一名字在不同的程序段中一般都代表不同的对象,也就是说代表不同的存贮单元,PROGRAM MAIN.integer xENDSUBROUTINE SUB1Integer x.END,Integer x,X,X=9999,100,Integer x,9999,X=100,X,PROGRAM MAIN.ENDSUBROUTINE SUB1.END,一个名字对应多个对象,2023/10/17,辛明影,42,但是不同程序段里的同名公用块却代表同一个存贮区域,PROGRAM MAIN.Commo
18、n a,bENDSUBROUTINE SUB1 common x,y.END,PROGRAM MAIN.ENDSUBROUTINE SUB1.END,Common a,b,a,b,A=100B=50,100,50,Common x,y,x,y,Y=x+100,200,共享存贮单元,多个名字对应一个对象,2023/10/17,辛明影,43,二。Pascal,Pascal 允许子程序嵌套定义,Program main 说明部分Begin 可执行部分end,Pascal的程序结构,Program main Beginend,Procedure P1Beginend,Procedure P11Begi
19、nend,Procedure P2Beginend,也允许并列定义,2023/10/17,辛明影,44,关于名字的作用域的规定:,标识符X的任意一次出现(除去说明语句中)都意味着对某个说明语句中说明的这个变量X的引用,此时,说明语句同标识符X应共处一个最小程序中,即:,P1中说明的X只在P1中有效,P11是P1的内层子程序,P11中没有再对X作新的说明,则在P11中对X的引用,实际上引用的就是P1中说明的X,,即内部过程可以引用外部过程中定义的量,2023/10/17,辛明影,45,三.java,Java语言是一种面向对象的高级语言,它很重要的方面是类和继承的概念,同时支持多态性和动态绑定等特
20、性,Class carInt color_num;Int door_num;Int speed;.Void push_break()Void add_oil(),Class benz extends car Double price;Void ABS(),2023/10/17,辛明影,46,一个类把有关的数据及其操作封装在一起构成一个抽象数据类型,一个子类继承其父类的所有数据和方法,并且可以加入自己新的定义,在java中,变量和方法的定义之前可以加上public、private、pretected等修饰词,,以限制其它类的对象对于这些变量和方法的使用,2023/10/17,辛明影,47,2.2
21、.2 构造基础,程序设计语言的数据对象:,数据、,函数、,过程,常用能反映其本质的、有助于记忆的名字来表示,一.名字,特性:,一个名字对应一个对象,,普通变量,多个名字对应一个对象,一个名字对应多个对象,,common,数组、重载、局部变量、重写、,2023/10/17,辛明影,48,每个对象可以看做是一个存贮单元,,可能是一个字,也可能是多个字,名字具有属性,,通常由说明语句给出,一个名字的属性,包括:类型和作用域,类型决定了它有什么样的值,,作用域规定了值的存在范围,值在计算机内的表示,,以及对它能施加什么样的运算,2023/10/17,辛明影,49,二.数据类型,1.初等数据类型,数值数
22、据:整形、实型、双精度等,可施行算术运算,逻辑数据:可施行逻辑运算,字符数据:,指针类型:,2023/10/17,辛明影,50,三。数据结构,1。数组,从逻辑上讲,一个数组是由同类型数据所组成的n 维矩形结构,一个数组所需的存贮空间大小在编译时就已知道的,则称此数组是一个确定的数组;否则称为可变数组,设int Al1u1,l2u2 lnun 为n维数组各维的长度:di=ui-li+1(1in),2023/10/17,辛明影,51,任一数组元素Ai1,i2,in的地址为:D=a+(i1-l1)d2d3 dn+(i2-l2)d2 d2 dn+(in-1-ln-1)dn+(in-ln),整理后C=(
23、l1 d2+l2)d3+l3)d4+ln-1)dn+ln,C是数组计算中不变的部分,2023/10/17,辛明影,52,变量部分:v=(i1 d2+i2)d3+i3)d4+in-1)dn+in,任一数组元素Ai1,i2,in的地址:addr=a-c+v,2023/10/17,辛明影,53,在编译时,当遇到说明时,必须把数组的有关信息记录在一个“内情向量”之中,用于数组元素的地址计算。,数组的内情向量包括:,维数,各维的上、下限,首地址及数组的类型,ln,un,dn,l2,l1,un,un,d1,d2,N维数,C常数,T类型,A首地址,2023/10/17,辛明影,54,对于确定数组来说,内情向
24、量可登记在符号表中;,对于可变数组,内情向量的信息在编译时无法全部知道,只有到运行阶段才能全部确定下来,存贮分配也要等到运行时方能进行,2023/10/17,辛明影,55,2.记录(结构),从逻辑上讲,记录是由已知的数据组合起来的一种结构,Struct student char name20;boolean partmember;int age;stu;,2023/10/17,辛明影,56,记录结构最简单的存贮方式是连续存放,上述的变量stu共占7个字,共28个字节,Stu.nameStu.partmember Stu.age,3.字符串、表格和队列,kK+1.K+20.K+24.,.,202
25、3/10/17,辛明影,57,四.抽象数据类型,一个抽象数据类型包括:,这种类型对象的封装,作用于这些数据对象的抽象运算的集合,数据对象的一个集合,C+、Java语言通过类对抽象类型提供支持,2023/10/17,辛明影,58,五.语句与控制结构,1.表达式,要解决的问题:,优先级,结合率,2.语句,语句可分为:,说明语句:,可执行语句:,定义各种不同数据类型的变量和运算,描述语句的动作,执行语句分为:赋值、控制和I/O语句,2023/10/17,辛明影,59,赋值句,A=B,左值,右值,名字的左值指它所代表的存贮单元地址,名字的右值指该 单元的内容,2023/10/17,辛明影,60,控制语
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 恐龙
链接地址:https://www.31ppt.com/p-6333816.html