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

编译原理,15.06.2020,.,2,自我介绍,姓名：辛明影电话：86413213教研室：计算机软件基础办公室：综合楼513xmy63xmy63,助课教师：洪晓鹏，综合楼614单丽丽，新技术楼608,15.06.2020,.,3,开课目的及应用前景：,介绍设计与构造程序设计语言编译程序的原理与方法,源程序,编译程序,目标程序,连接,可执行程序,预备知识：,形式语言与自动机、,两门以上的高级程序设计语言,汇编语言,数据结构等,How?,15.06.2020,.,4,内容简介：,第一章：编译器的基本结构,第二章：高级语言及其语法描述,第三章：词法分析器,第四章：语法分析技术,第五章：语法制导翻译的主要概念及中间代码,第六章：程序运行时的存贮分配问题,第七章：代码优化,第八章：目标代码生成,15.06.2020,.,5,教学设计：,(1)自顶向下，逐步求精的方法(2)问题驱动(3)将课程设计成一个应用平台(4)用实验拓广课堂教学(5)精讲多练(6)承前启后,教学目标：,15.06.2020,.,6,第一章绪论,编译器就是一个程序，它读入用某种语言编写的源程序，并翻译成一个与之等价的另一种语言编写的源程序。,编译器,源程序,目标程序,错误信息,Fortran、Pascal、Java、C.,另一种程序设计语言、,汇编语言、机器语言,1.1什么叫编译程序,15.06.2020,.,7,1.2编译过程概述,编译程序的工作，从输入源程序开始，到输出目标程序结束，与自然语言之间的翻译有很多相似之处。,一段英文翻译成中文，需经下列步骤：,识别出句子中的单词,分析句子的语法结构,根据句子的含义进行初步分析,对译文进行修饰,写出最后的译文,编译程序,词法分析,代码优化,语法分析,语义分析及中间代码生成,目标代码生成,构成编译程序各个阶段,Iamaexperiencedteacher.,15.06.2020,.,8,编译器的各个阶段：,编译器是分阶段执行的。,每个阶段将源程序从一种表示转换成另一种表示,源程序,词法分析器,错误处理器,符号管理表,语法分析器,语义分析器,中间代码生成器,代码优化器,代码生成器,编译的各个阶段,15.06.2020,.,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),15.06.2020,.,10,语法分析,在词法分析的基础上，根据语言的语法规则，把单词符号串组成各类语法单位.,具体的说，语法分析是在单词流的基础上建立一个层次结构-建立语法树,赋值语句,标识符,=,表达式,a,表达式,标识符,b,+,表达式,表达式,*,标识符,c,表达式,标识符,d,15.06.2020,.,11,语义分析阶段,语义分析利用语法分析阶段确定的层次结构来识别表达式和语句中的操作信息及类型信息,=,+,a,b,*,c,d,temp1=c*d,temp2=b+temp1,temp1,temp2,a=temp2,15.06.2020,.,12,中间代码生成阶段,本阶段将产生源程序的一个显式中间表示,这种中间表示可以看成是某种抽象的程序，通常是与平台无关的,其重要性质：1.易于产生2.易于翻译成目标程序,下面是用三地址码和四元式表示的例子：,temp1=c*dtemp2=b+temp1a=temp2,（*,c,d,tempt1)(+,b,tempt1,tempt2)(=,tempt2,a),15.06.2020,.,13,代码优化阶段,试图改进中间代码，以产生执行速度较快的机器代码,对上面中间代码进行优化处理后，产生如下的代码：,temp1=c*da=b+temp1,temp1=c*dtemp2=b+temp1a=temp2,15.06.2020,.,14,代码生成阶段,生成可重定位的机器代码或汇编代码,MovfR2，cMultR2,dMovfR1,bAddfR2,R1Movfa,R2,15.06.2020,.,15,1.3符号表管理,inta,b;floate,fcharch1,ch2;,为什么要先说明?,定义了变量的类型，也就规定了变量在内存中的存放形式，在其上所能进行的运算,解决符号地址到存贮地址上的映射,15.06.2020,.,16,编译器的一个基本功能是记录源程序中使用的标识符,并将它们记载到符号表中。,符号表是一个数据结构。,每个标识符在符号表中都有一条记录,名字,记号,类型,种属,addr,id1(25),id2(25),b,a,例：inta,b;,int,简变,0,4,并收集与每个标识符相关的各种属性信息，,int,简变,15.06.2020,.,17,符号表的接口：,符号表的作用就是存放字符串或词素,当一个字符串或词素被保存时，与之相对应的记号也被保存,符号表上的操作：,Insert(s,t):将符号串s和记号t插入符号表，返回相应表项的指针,Lookup(s):在符号表中查找字符串s，查找成功返回相应指针，否则返回0,15.06.2020,.,18,关键字的处理,通常情况下，将关键字存在符号表中，作为符号表的初值。,当词法分析程序识别出一个标识符s后，用lookup(s)查找符号表，如果是关键字，返回相应的记号；如果是变量名，返回记号id,15.06.2020,.,19,符号表的实现,固定长标识符：采用前面的结构,不定长标识符：使用单独的数组lexemes,ifeosinteospositioneosinitialeos,If(12),Int(13),Id1(25),Id2(25),存放标识符的字符串,符号表中存放标识符在lexemes的起始位置和相应记号,15.06.2020,.,20,1.4编译各阶段的分组,一、前端和后端,前端包括词法分析、词法分析、语义分析，以及相关的错误处理和符号表的建立,前端依赖于源程序并在很大程度上独立于目标机器。,15.06.2020,.,21,后端主要包括代码优化、代码生成和相关错误处理。,后端依赖于目标机器。,后端处理对象是由前端产生的结果，即中间代码,前端生成与平台无关的字节码,后端是由与平台有关的解释器对所生成的字节码文件进行解释执行,Java语言的编译采用的是前端后端方式。,15.06.2020,.,22,二、编译的遍,编译的若干阶段通常是以一遍来实现的，每遍读一次输入文件、产生一个输出文件。,15.06.2020,.,23,在编译的各个阶段都会发现源程序中的错误，,1.5错误检测与报告,为了使编译器能继续运行，以检测出源程序中更多的错误，在检测到错误后，必须以合适的方式进行错误处理。,error,第二章高级语言及其语法描述,15.06.2020,.,25,内容简介：,本章概述程序设计语言的结构,2.1程序语言的定义,任何语言实现的基础是语言定义。,语言的定义决定了该语言,具有什么样的语言功能、,什么样的数据结构、,什么样的程序结构、,以及具体的使用形式等细节问题。,和主要的共同特征，,并介绍程序设计语言主要语句的文法描述与形式定义。,15.06.2020,.,26,对于编译程序设计者来说：语言定义就是具体实现的理论依据。,对于语言用户来说：语言定义就是一本用户手册。,2.1.1语法,语言的语法是指这样一组规则，用它可产生一个程序。,规则：词法规则语法规则,15.06.2020,.,27,词法规则是指单词符号的形成规则,字母表就是一个有穷字符集。,C语言的字母表为：=a-z、AZ、09、(、)、.、!、+、-、*、/、,C语言的标识符的构成规则：,字母、下划线打头的字母、数字和下划线构成的符号串。如：a1、ave、_day,一.词法规则,15.06.2020,.,28,上述的定义是用文字来描述的，当设计编译程序时，就要把它用形式的方式描述出来，就要用到形式语言。,各类型的常数、,标识符、,基本字、,算符和界符等,正规式和有穷自动机是描述词法结构和进行词法分析的有效工具,在现今多数程序设计语言中，单词符号一般包括：,15.06.2020,.,29,C语言的标识符的文法和自动机描述：,例：C语言标识符的文法描述L（G）=w/w为字母或-打头的字母数字串,解：P:IaBI-BIaBaBBdBBaBd,识别L（G）的自动机,I,B,T,a,-,a,d,其它,15.06.2020,.,30,S,A,C,D,F,E,B,7,d,d,d,d,d,d,d,e,e,+,T,*,例：C语言实常数的文法描述,文法：SdAAdAAeDA.BBdCCdCCeDD-ED+EDdFEdFFdFFd,其它,其它,其它,1000,3.14,10e+33.14e-5,12e50.1e24,15.06.2020,.,31,二.语法规则,语法规则规定了如何从单词符号形成更大的结构（即语法单位），换言之，语法规则是语法单位的形成规则,一般的程序设计语言的语法单位有：,表达式、,语句、,分程序、,函数、,过程和程序等,下推自动机理论和上下文无关文法是我们讨论语法分析的理论基础,15.06.2020,.,32,表达式：EE+TEE-TETTT*FTT/FTFF(E)Fid,主要语句的形式描述：,15.06.2020,.,33,布尔表达式：BBorBBBandBBnotBB(E）BidrelopidBtrueBfalse,15.06.2020,.,34,赋值、分支、循环语句：Sid=ESifBthenSSifBthenSelseSSwhileBdoSSLLL;SLS,15.06.2020,.,35,调用语句：Scallid(Elist)ElistElist,EElistE|,15.06.2020,.,36,类型说明和过程说明语句：PDDD;DDid:TDid（Elist）D;STintTfloat,15.06.2020,.,37,数组说明语句：LidElistElistElist,EElistE,15.06.2020,.,38,2.1.2语义,例：a=b+c*d,例do999I=1,10,对于一个语言来说，不仅要给出它的词法、语法规则，而且要定义它的单词符号和语法单位的意义，这就是语义问题,对于编译程序来说，只有了解程序的语义，才知道应把它翻译成什么样的目标指令代码,15.06.2020,.,39,2.2构造基础,2.2.1程序结构简介,一个高级语言程序通常由若干子程序段（过程、函数等）组成，,许多语言还引入了类、程序包等更高级的结构,15.06.2020,.,40,FORTRAN,一个FORTRAN程序由一个主程序和若干个辅助程序段组成,PROGRAMMAIN.ENDSUBROUTINESUB1.ENDFUNCTIONFUN1.END,它的定义是并列的,15.06.2020,.,41,FORTRAN的构成特点：,同一名字在不同的程序段中一般都代表不同的对象，也就是说代表不同的存贮单元,PROGRAMMAIN.integerxENDSUBROUTINESUB1Integerx.END,Integerx,X,X=9999,100,Integerx,9999,X=100,X,PROGRAMMAIN.ENDSUBROUTINESUB1.END,一个名字对应多个对象,15.06.2020,.,42,但是不同程序段里的同名公用块却代表同一个存贮区域,PROGRAMMAIN.Commona,bENDSUBROUTINESUB1commonx,y.END,PROGRAMMAIN.ENDSUBROUTINESUB1.END,Commona,b,a,b,A=100B=50,100,50,Commonx,y,x,y,Y=x+100,200,共享存贮单元,多个名字对应一个对象,15.06.2020,.,43,二。Pascal,Pascal允许子程序嵌套定义,Programmain说明部分Begin可执行部分end,Pascal的程序结构,ProgrammainBeginend,ProcedureP1Beginend,ProcedureP11Beginend,ProcedureP2Beginend,也允许并列定义,15.06.2020,.,44,关于名字的作用域的规定：,标识符X的任意一次出现（除去说明语句中）都意味着对某个说明语句中说明的这个变量X的引用,此时，说明语句同标识符X应共处一个最小程序中，即：,P1中说明的X只在P1中有效,P11是P1的内层子程序，P11中没有再对X作新的说明，则在P11中对X的引用，实际上引用的就是P1中说明的X，,即内部过程可以引用外部过程中定义的量,15.06.2020,.,45,三.java,Java语言是一种面向对象的高级语言，它很重要的方面是类和继承的概念，同时支持多态性和动态绑定等特性,ClasscarIntcolor_num;Intdoor_num;Intspeed;.Voidpush_break()Voidadd_oil(),ClassbenzextendscarDoubleprice;VoidABS(),15.06.2020,.,46,一个类把有关的数据及其操作封装在一起构成一个抽象数据类型,一个子类继承其父类的所有数据和方法，并且可以加入自己新的定义,在java中，变量和方法的定义之前可以加上public、private、pretected等修饰词，,以限制其它类的对象对于这些变量和方法的使用,15.06.2020,.,47,2.2.2构造基础,程序设计语言的数据对象：,数据、,函数、,过程,常用能反映其本质的、有助于记忆的名字来表示,一.名字,特性：,一个名字对应一个对象,，普通变量,多个名字对应一个对象,一个名字对应多个对象,，common,数组、重载、局部变量、重写、,15.06.2020,.,48,每个对象可以看做是一个存贮单元，,可能是一个字，也可能是多个字,名字具有属性，,通常由说明语句给出,一个名字的属性，包括：类型和作用域,类型决定了它有什么样的值，,作用域规定了值的存在范围,值在计算机内的表示，,以及对它能施加什么样的运算,15.06.2020,.,49,二.数据类型,1.初等数据类型,数值数据：整形、实型、双精度等，可施行算术运算,逻辑数据：可施行逻辑运算,字符数据：,指针类型：,15.06.2020,.,50,三。数据结构,1。数组,从逻辑上讲，一个数组是由同类型数据所组成的n维矩形结构,一个数组所需的存贮空间大小在编译时就已知道的，则称此数组是一个确定的数组；否则称为可变数组,设intAl1u1,l2u2lnun为n维数组各维的长度：di=ui-li+1(1in),15.06.2020,.,51,任一数组元素Ai1,i2,in的地址为：D=a+(i1-l1)d2d3dn+(i2-l2)d2d2dn+(in-1-ln-1)dn+(in-ln),整理后C=(l1d2+l2)d3+l3)d4+ln-1)dn+ln,C是数组计算中不变的部分,15.06.2020,.,52,变量部分：v=(i1d2+i2)d3+i3)d4+in-1)dn+in,任一数组元素Ai1,i2,in的地址:addr=a-c+v,15.06.2020,.,53,在编译时，当遇到说明时，必须把数组的有关信息记录在一个“内情向量”之中，用于数组元素的地址计算。,数组的内情向量包括：,维数，各维的上、下限，首地址及数组的类型,ln,un,dn,l2,l1,un,un,d1,d2,N维数,C常数,T类型,A首地址,15.06.2020,.,54,对于确定数组来说，内情向量可登记在符号表中；,对于可变数组，内情向量的信息在编译时无法全部知道，只有到运行阶段才能全部确定下来，存贮分配也要等到运行时方能进行,15.06.2020,.,55,2.记录（结构）,从逻辑上讲，记录是由已知的数据组合起来的一种结构,Structstudentcharname20;booleanpartmember;intage;stu;,15.06.2020,.,56,记录结构最简单的存贮方式是连续存放,上述的变量stu共占7个字，共28个字节,SStu.partmemberStu.age,3.字符串、表格和队列,kK+1.K+20.K+24.,.,15.06.2020,.,57,四.抽象数据类型,一个抽象数据类型包括：,这种类型对象的封装,作用于这些数据对象的抽象运算的集合,数据对象的一个集合,C+、Java语言通过类对抽象类型提供支持,15.06.2020,.,58,五.语句与控制结构,1.表达式,要解决的问题：,优先级,结合率,2.语句,语句可分为：,说明语句：,可执行语句：,定义各种不同数据类型的变量和运算,描述语句的动作,执行语句分为：赋值、控制和I/O语句,15.06.2020,.,59,赋值句,A=B,左值,右值,名字的左值指它所代表的存贮单元地址,名字的右值指该单元的内容,15.06.2020,.,60,控制语句,无条件转移语句：Gotolable,条件语句：IfBthenSIfBthenSelseS,循环语句：WhileBdoSRepeatSuntilBForI=e1toe2stepe3,过程调用语句：CallP(x1,x2,.xn),返回语句：Return(E),15.06.2020,.,61,说明语句,说明语句用于定义名字的性质。,编译程序把这些性质登记在符号表中，并检查程序中名字的引用和说明是否一致。,许多说明语句不产生目标代码,但有的说明语句，如过程说明和可变数组说明，则要产生相应的目标代码,15.06.2020,.,62,简单句和复合句,简单句是指不包含其它语句成分的基本句。赋值、goto语句等,复合句则指那些句中有句的语句,If(x=0)thenx=1x=1;y=2;gotol1;,15.06.2020,.,63,programreference（input，output）；vara，b：integer；procedureswap（x，y：integer）；vartemp：integer；begintemp:x；x：y；y：tempend;begina：1;b：2;swap(a，b);writeln(a=，a，b=,b）end.,2.2.3参数传递,结果是什么？,15.06.2020,.,64,1传值调用,实在参数和形式参数结合的方法：传值调用（call-by-value）引用调用（call-by-reference）复制恢复（copy-restore）传名调用（call-by-name）,15.06.2020,.,65,子程序为每一个形参开辟一个存贮单元，用于存放相应实参的值。,子程序执行时，每当访问形参时，就直接访问形参单元。,实参：,形参：,传值调用可以实现如下：,主调过程计算实在参数，并把它们的右-值放入到形式参数的存储空间中。,15.06.2020,.,66,使用传值的方法，调用swap（a,b）等价于下面几步：x：=ay：=btemp：=xx：=yy：=temp,15.06.2020,.,67,2引用调用（传地址）把实在参数的地址传递给相应的形式参数,在目标代码中，在被调用过程中对形式参数的一次引用就成为对传递给被调用过程的指针的一个间接引用。,Reference,abxy,12,swap,ab,temp,15.06.2020,.,68,子程序为每个形参开辟一个单元，用于存放相应实参的地址，,执行时，子程序间址方式访问这些形参单元,当实参为表达式或常数时，则存放它们值的临时单元。,实参：,地址,形参：,Temp:=x;x:=y;y:=temp;,temp:=a;a:=b;b:=temp;,15.06.2020,.,69,3复制恢复（传值结果）实现：1.当控制流入到被调用过程之前，把实在参数的右-值和左-值传递到被调用过程中；2.当控制返回时，把形式参数的现行右-值复制回到相应的实在参数的左-值中。,15.06.2020,.,70,子程序为每个形参分配两个存贮单元B1和B2，B1用于存放实参地址，B2用于存放实参值。,执行时，对B2单元使用直接访问形式；返回前，按B1中的地址把B2中的内容存入主调程序的实参单元中。,实参：,地址,形参：,B1,B2,B1,15.06.2020,.,71,在主调程序中设置计算实参地址和右值的形实替换子程序THUNK,子程序中为相应实参开辟一个形式单元，用于存放该实参的THUNK子程序的入口地址。,执行时，每当要对形参进行访问时，就调用THUNK子程序，以获得相应实参地址或值,4传名调用,对形参的访问是发生在实参单元上的,15.06.2020,.,72,例：有程序段：procedurep(x,y,z)beginy=y+1;z=z+x;end,Begina=2;b=3;c=4;P(a,b,c);printa,b,c;end,15.06.2020,.,73,传值：,a,b,c,实参,形参,x,y,z,2,3,4,P(a,b,c);,2,3,4,y=y+1;,输出：234,4,6,Z=z+x;,A=2B=3C=4,15.06.2020,.,74,传地址：,a,b,c,实参,形参,x,y,z,2,3,4,P(a,b,c);,y=y+1,输出：246,4,6,Z=z+x;z=z+x,15.06.2020,.,75,传值结果：,a,b,c,实参,形参,XB1B2,YB1B2,ZB1B2,2,3,4,输出：246,Z=z+x;,JSRThunkYb,输出：246,4,6,Z=z+x;jsrThunkZc,xa,15.06.2020,.,77,例：有程序段：procedurep(x,y,z)beginy=y+1;z=z+x;end,Begina=2;b=3;P(a+b,a,a);printaend,15.06.2020,.,78,传值：,a,b,a+b,实参,形参,x,y,z,2,3,P(a+b,a,a);,5,2,2,y=y+1;,输出：2,3,7,Z=z+x;,A=2B=3,5,15.06.2020,.,79,传地址：,a,b,a+b,实参,形参,x,y,z,2,3,5,P(a+b,a,a);,y=y+1,输出：8,3,Z=z+x;z=z+x,8,15.06.2020,.,80,传名：,a,b,实参,形参,x,y,z,2,3,P(a+b,a,a);,JSRThunkYa,输出：9,3,9,Z=z+x;jsrThunkZa,xa+b,第三章词法分析,15.06.2020,.,82,编译器的各个阶段：,编译器是分阶段执行的。,每个阶段将源程序从一种表示转换成另一种表示,源程序,词法分析器,错误处理器,符号管理表,语法分析器,语义分析器,中间代码生成器,代码优化器,代码生成器,编译的各个阶段,15.06.2020,.,83,3.2词法分析器的手工构造：用DFA能识别,3.3词法分析程序自动构造工具LEX简介,3.1词法分析程序的设计：,15.06.2020,.,84,=,8,0,;,0,1,3,4,2,5,6,e,n,i,L,字母,字母,字母,字母,数字,数字,数字,=,=,；,；,0,1,2,4,5,6,3,L,i,n,e,=,8,0,;,id(25),Line,=(36),num(27),80,;(45),数字,字母,字母,1,1,=,=,0,0,0,3,;,;,1,输入,输出,有穷控制器,单词的词类和属性（词类符号，单词的属性）,15.06.2020,.,85,3.1词法分析程序的设计,二、扫描器的任务,一、词法分析程序的功能源程序单词序列,词法分析器,1、组织源程序的输入,2、识别单词，转换成机内表示形式,3、删除注释行、空格及无用符号,4、查填符号表,5、检查词法错误,15.06.2020,.,86,ifijtheni:0elsej:=1,词法分析,ifIJThenI0elsej=1,15.06.2020,.,87,三、词类和属性,2标识符：用来表示各种名字,3字面常数：256，3.14，true,abc,4运算符：如，、*、/等等,5分界符：如逗号，分号，冒号等,程序语言单词的分类：1关键字(保留字或基本字)：while,if,15.06.2020,.,88,界符和运算符:,词法分析器的输出：（词类编码，单词自身的属性值）,关键字可分成一类，也可以一个关键字分成一类。,常数可统归一类，也可按类型（整型、实型、布尔型等），每个类型的常数划分成一类。,所有的标识符分为一类。,词类编码原则:,一字一码。,一类型一码。,一类一码。,一符一码。,15.06.2020,.,89,表3.1单词词类编码,15.06.2020,.,90,对于关键字、界符、运算符来说，它们的词类编码就可以表示其完整的信息，,而对于标识符，词类编码所反映的信息不够充分，标识符的具体特性还要通过单词自身的属性进行互相区分。,标识符的单词自身的属性常用其在符号表中的入口指针来表示,故对于这类单词，其单词自身的属性值通常为空,15.06.2020,.,91,对于常数，其单词自身的属性常用其在常数表中的入口指针来表示,15.06.2020,.,92,以语句子a=b+c*d为例，假设按表3.1为单词编码，词法分析后的结果为：,Token字,符号表,a=b+c*d,a25,b25,c25,d25,15.06.2020,.,93,四、词法分析的设计形式（1）设计成一个独立程序，完成词法分析的任务，结果以文件的形式组织，做为语法分析的输入,源程序,词法分析,符号表,TOKEN字,错误信息,15.06.2020,.,94,词法分析,语法分析,语义分析和中间代码生成,源程序,中间代码,符号表管理,错误的诊查处理,（2）作为语法分析和语义分析的子程序,15.06.2020,.,95,五、词法分析程序的设计框图,SCANNER,OUTPUT,sort,字母,RECOGID,数字,RECOGDIG,/,HANDLCOM,RECOGDEC,界符,RECOGSTR,LOOKUP,15.06.2020,.,96,32词法分析器的手工构造,为了构造词法分析器，要研究构词法，每种词类的结构模式以及识别它的数学模型有穷自动机。321确定的有限自动机（DFA）322构造识别单词的DFA323编写词法分析程序,15.06.2020,.,97,SCANNER,OUTPUT,sort,字母,RECOGID,数字,RECOGDIG,/,HANDLCOM,RECOGDEC,界符,RECOGSTR,LOOKUP,15.06.2020,.,98,一、手工构造识别单词的DFAm根椐DFA识别单词的定义，在研究给定程序语言单词结构的基础上，能直接构造出识别它的DFAm。例如：对于C语言,整数：非空数字串。,无符号实数（用d表示数字）:,(a)dd.ddE(+-)dd,ddE(+-)dd,(c)dd.dd,0.1e+14,12e-4,3.141592,(d)dddd,1000,15.06.2020,.,99,I,B,T,T,a,-,a,d,其它,例：C语言的标识符,标识符：字母开始的字母数字串。,15.06.2020,.,100,例：C语言实常数的文法描述,0,1,2,3,4,5,6,7,d,d,d,E,d,E,d,-,+,d,d,1000,3.1415,12e-4,0.1e+14,.,15.06.2020,.,101,在识别标识符的过程中，首先要拼写出来，并和保留字区别开来；识别出的标识符要填入符号表中,二、编写词法分析程序,根据画出的状态转换图（识别单词的）构造词法分析程序，每个状态对应一段程序，完成到达此状态的工作；,在识别常数的过程中，要把它转换成机器表示以作为属性值，记录到常数表中。,词法分析程序的控制程序模拟状态转换图的状态转换。,15.06.2020,.,102,programSCANNER;Begininitiate符号表,字符串表,行,列计数器;Open源文件,TOKEN文件,打印机文件;RepeatFIRSTCH(CH);ifCH!=EOLthencallSORT(CH)elseRDLINE;untilCH=EOF;把符号表,字符串表做成文件;close源文件,TOKEN文件;callOUTPUTR;,模块0：扫描器主控,15.06.2020,.,103,单词分类模块(SORT)输入：CH内含单词首符；procedureSORT(CH);caseCHof字母:字母:callRECOGID(CH,TOKEN);/:callHANDLECOM(CH,TOKEN);数字:callRECOGDIG(CH,TOKEN);callRECOGSTR(CH,TOKEN);otherwisecallRECOGDEL(CH,TOKEN);endcase;writeTOKENintoTOKEN文件;Return,15.06.2020,.,104,procedureRECOGID(CH,TOKEN);WORD:=;WORD:=WORD|CH;RepeatcallGETCH(CH);ifCH是字母或数字thenWORD:=WORD|CH;untilCH!=字母或数字;ifCH是非法字符thencallPRINTERR(非法字符)else列计数-1;ifWORD是关键字thenTOKEN:=(关键字种别码,_)elsecallLOOPUP(WORD,标识符,ENTRY)TOKEN:=(标识符种别码,ENTRY);Return;,识别标识符；输入：CH中含标识符的首字母；输出：TOKEN(二元式形式);,15.06.2020,.,105,procedureHANDLECOM(TOKEN);callGETCH(CH);ifCH!=*then列计数-1;TOKEN=(/的识别码,_);return;TOKEN=-1;GETCH(CH);while列计数E+T*id,=E+F*id,=E+id*id,E=-EE推导出-E,=一步或多步推导,=零步或多步推导,*,+,=T+id*id,=F+id*id,=id+id*id,15.06.2020,.,122,最左推导：每一步都坚持替换当前句型中最左非终结符的推导,最右推导：每一步都坚持替换当前句型中最右非终结符的推导，也称为规范推导,+句子：S=w称终结符串w是文法G句子,+句型：S=称是文法G的句型,+语言：L（G）=w/S=w,15.06.2020,.,123,二、语法树,语法描绘了如何从文法的开始符号推导出一个句子的过程,语法树可以看成是推导的图形表示，但它不能显示出替代的顺序,前面句子id+id*id推导过程所对应的分析树如下：,15.06.2020,.,124,EE+TTT*FFFididid,15.06.2020,.,125,4.如杲A是某个内结点的非终结符标记，A1，A2，An是该结点从左到右排列的所有子结点的标记，则AA1A2An是一个产生式,3.每个内结点由一个非终结符标记,1.树根标记为开始符号,2.每个叶结点由终结符或者标记,语法具有如下特性的树：,15.06.2020,.,126,语法树的叶结点从左到右的排列，刚好是这个文法所产生的语言的一个句子,一个文法生成的语言就是它的某个分析树所生成的句子的集合,为给定的终结符串（句子）构造一棵分析树的过程称为这个串（句子）的语法分析（parsing),15.06.2020,.,127,三、二义性,句子id+id*id有两棵分析树与之对应,EE+EidE*Eidid,EE*EE+Eididid,15.06.2020,.,128,给定一个文法G，如果L（G）中存在一个具有两棵或两棵以上分析树的句子，,很显然，描述算术表达式的文法GEE+E|E*E|（E）|-E|id是一个二义性文法,造成二义性的原因是：文法中没有体现出结合率和优先级,我们就称该文法为二义性的，G也叫二义性文法。,15.06.2020,.,129,大多数的语法分析器都要求文法是无二义性的,消除二义性：,可以通过改写文法来消除二义性,例：stmtifexprthenstmt|ifexprthenstmtelsestmt|other,15.06.2020,.,130,通过例子ifE1thenifE2thenS2elseS3很容易证明这是一个二义性文法,s,if,E,then,S,else,S,if,E,then,S,15.06.2020,.,131,S,if,E,then,S,if,E,then,S,else,S,15.06.2020,.,132,在程序设计语言中，我们常常采用“最近匹配”原则来解决这种二义性,文法改写出为：,stmtmatched_stmt|unmatched_stmtmatched_stmtifexprthenmatched_stmtelsematched_stmt|otherunmatched_stmtifexprthenmatched_stmtelseunmatched_stmt|ifexprthen_stmt,15.06.2020,.,133,四、左递归,如果文法G具有一个非终结符A使得对某个字符串存在推导A=A,例：下面是描述算术表达式的算法SEEE+T|TTT*F|FF(E)|id,为句子id*id+id构造分析树SE+TE+TE+T：,则称文法G是左递归的；,如果AA，则称文法G是直接左递归的,+,15.06.2020,.,134,左递归会使分析进入到无限循环之中,消除简单左递归的方法：对于含有左递归的产生式AA|,可用下面的非左递归的产生式代替：AAAA|,15.06.2020,.,135,例：下面是描述算术表达式的算法EE+T|TTT*F|FF(E)|id,消除E和T的直接左递归，得到：,ETE,E+TE|,TFT,F(E)|id,T*FT|,15.06.2020,.,136,对于一般情况而言，若某一文法G的产生式具有如下形式：,则可用如下方法消除左递归:,AA1|A2|Am|1|2|n,A1A|2A|nA,A1A|2A|mA|,很容易证明改造前后的文法是等价的,15.06.2020,.,137,例：文法G（P）：P（Q）|aP|aQQ,P|P试消除左递归,15.06.2020,.,138,消除左递归后，方法改为：,P（Q）|aPaQPQ，,15.06.2020,.,139,SQc|cQRb|bRSa|a,S,这样的递归无法用前面的方法消除,对于含有间接左递归的文法：,=Qc,=Rbc,=Sabc,出现了左递归,15.06.2020,.,140,消除左递归的一般算法：,输入：无循环推导和产生式的方法G,输出：与G等价的无左递归文法,算法：,15.06.2020,.,141,1.以某种顺序排列非终结符A1A2An2.fori=1tondobeginforj=1toi-1dobegin改写AiAj规则，方法如下：如果Aj1|2|k则Ai1|2|n；end消除Ai中的所有直接左递归End3.化简由2所得文法,15.06.2020,.,142,SQc|cQRb|bRSa|a,对如下文法消除左递归：,1.将非终结符排序为R、Q、S,2.R不存在左递归，将R代入Q：QSab|ab|b,3.Q不存在左递归，将Q代入SSSabc|abc|bc|c,4.消除直接左递归后，得文法：,15.06.2020,.,143,SabcS|bcS|cSSabcS|QRb|bRSa|a,5.化简文法,SabcS|bcS|cSSabcS|,15.06.2020,.,144,Z-AA-aB|aC|Ad|AeB-bBC|fC-c,15.06.2020,.,145,五、提取左因子,为句子ifE1thenS1elseS2构造一棵语法树,文法：stmtifexprthenstmt|S|ifexprthenstmtelsestmt,stmtifexprthenstmtE1ifthenstmt,回溯,15.06.2020,.,146,造成这种情况的原因是产生式具有相同的首符号，从而导致不清楚该用哪个来替换非终结符,可通过改写产生式来推迟这种决定，直到看见足够多的输入符号，可以作出正确选择为止,上例可改为：stmtifexprthenstmtS|SSelsestmt|,15.06.2020,.,147,stmtifexprthenstmtSE1elsestmt,提取左因子算法：,输入：文法G,输出：一个等价的提取了左因子的文法,方法：对于A1|2|n|,可改写为：AA|,A1|2|n,15.06.2020,.,148,例：文法G（P）：P（Q）|aP|aQQ,P|P试消除回朔,15.06.2020,.,149,六、FIRST与FOLLOW集,1.FIRST集,回朔和左递归搞的人真烦哪！,怎样才能做到每次选的产生都正确呢？,郁闷哪！,FIRST（）=a|=a,aVT如果=则FIRST（）。,例：stmtifexprthenstmtSSelsestmtS,定义：FIRST（）是由推导出的所有的第一个终结符号组成的集合，即：,15.06.2020,.,150,算法：求FIRST（X）的算法描述如下：,例：First(ifexprthenstmtS)=ifFirst(elsestmt)=elseFirst()=,15.06.2020,.,151,如果X是非终结符，且XY1Y2Yk,则a)Y1=FIRST(Y1)中的所有符号都在FIRST（X）中,b)Y1Y2Yi-1=,FIRST（Yi）,中的所有符号都在FIRST（X）中,如果X是一个产生式，则FIRST（X）,如果X是终结符，则FIRST（X）是X,c)Y1Y2Yk=,则FIRST（X）,15.06.2020,.,152,例1：有文法G（S）SBAABSAdBaABbSBc试写出其FIRST集,First(B)=a,First(B)=b,First(B)=c,First(S)=First(BA)=a,b,c,First(A)=First(BS)=a,b,c,First(A)=d,15.06.2020,.,153,2.FOLLOW集,定义：FOLLOW（A）是由所有句型中紧跟在A后面的终结符a组成的集合*FOLLOW（A）=a|S=Aa,aVt,算法：FOLLOW（S）,对于AB的产生式，则FIRST（）-放入FOLLOW（B）,对于AB或AB，其中=则将FOLLOW（A）放入FOLLOW（B）中,15.06.2020,.,154,例1：对于文法GETEE+TE|TFTT*FT|F(E)|id求其FIRST和FOLLOW集,解：FIRST(F)=(,idFIRST(T)=*,FIRST(T)=FIRST(F)=(,idFIRST(E)=+,FIRST(E)=FIRST(T)=(,id,15.06.2020,.,155,FOLLOW(F)=FIRST（T)FOLLOW(T)=+,),*,$,FOLLOW(E)=),FOLLOW(E)=FOLLOW(E)=),FOLLOW(T)=FOLLOW(T)=FIRST(E)FOLLW(E)=+,),15.06.2020,.,156,例：AaAAbAAcABABdC,对句子abc