《北大编译原理》PPT课件.ppt

3,4,编译程序,目标程序,源程序,把高级语言程序翻译成等价的低级语言程序。,编译系统：编译程序和运行程序,编译程序的功能,5,词法分析,语法分析,语义分析,中间代码生成,优化,目标代码生成,目标代码,源程序,符号表管理,错误诊查处理,3,编译程序的逻辑结构,6,源程序,PROGRAMm;VARa,b,c:real;BEGINread(b,c);a:=b+c*60;write(a)END.,7,经词法分析源程序被加工成单词流,.,8,赋值语句,变量,:=,表达式,表达式,+,项,项,因子,b,项,*,因子,因子,c,60,a,赋值语句经语法分析生成分析树,9,:=,a,+,b,*,c,inttoreal,60,赋值语句经语义分析生成语法树,10,生成中间代码,temp1:=inttoreal(60);temp2:=c*temp1;temp3:=b+temp2;a:=temp3;,11,优化,Temp1:=c*60.0a:=b+temp1,生成目标代码,movfc,r2;mulf#60.0,r2;movfb,r1;addfr2,r1;movfr1,a;,12,符号表,13,错误的诊查处理,编译程序在各个阶段应诊断和报告源程序中的错误，包括词法错误，语法错误，语义错误。编译程序应报告出错地点，并给出简明准确的提示信息。,14,编译程序（器）的组织,前端和后端源程序中间代码目标代码仅依赖源程序仅依赖目标计算机遍（PASS)：对输入文件（源程序或其等价的中间形式）从头到尾扫视，完成预定的处理。,遍,输入文件,输出文件,前端,后端,15,词法分析,语法分析,语义分析和中间代码生成,源程序,中间代码,符号表管理,错误的诊查处理,把前端组织成一遍扫描,16,设计编译程序应首先研究的问题,首先研究源程序的语法和语义及运行模型，源是设计编译程序的出发点。研究目标计算机，设计目标代码的指令系统，它是由目标计算机扩充而成，扩充后的计算机称作抽象计算机。目前的通用计算机往往和源语言执行模型不一致。,编译程序,源程序,目标程序,抽象,目标,17,教和学的几个问题,重要性：处理字符串的一般方法；构造大程序的方法；实用；研究课题：新的语言及实现技术；并行编译技术。学习方法：（1）源程序是源泉；（2）把每个阶段放到整个编译程序背景中学习；（3）认真做作业。每周有一次答疑。参与网上教材的修改与创新。,18,教材和参考书,教材：（1）编译程序设计原理北京大学出版社，杜淑敏等编著。（2）网络版（软件工程中心资助）。,19,（1）编译原理，清华大学出版社，吕映芝等编著，1998。（2）程序设计语言编译原理，国防工业出版社，陈火旺等编著，1984。（3）AlfredV.Aho,RaviSethiJeffreyD.Ullman,Compilers:Principles,Techniques,andTools,Addison-Wesly,1986。（4）ModernCompilerImplementationinC,AndrewW.AppelandMaiaGinsburg,1998,19,参考书,20,21,学习本章的目的,构造编译程序的算法是从研究源程序及目标程序产生的，首先找到源语言的形式描述，根据这种描述，构造出相应的分析加工程序。语言分语法，语义和语用。程序语言语法的形式描述是很好用的，语义的形式描述不那磨好用，但它推动语言理论的发展。,22,2.1.1字母表2.1.2符号串一.符号串的定义二.术语三.符号串的运算四.符号串集合的运算,2.1符号串,23,字母表是符号的非空有穷集合。任何程序语言都有自己的字母表，例如:1.计算机语言：由符号“0”和“1”组成的字母表,=0，12.ASCII字符集；3.Pascal字母表为：=AZ,az,09,+,-,*,/,:,;，.，,(,),2.1.1字母表,24,一.符号串的定义(1)是上的一个符号串。(2)若x是上的符号串，而a是的元素,则xa是上的符号串。(3)y是上的符号串,当且仅当它由(1)和(2)导出。由字母表中的符号所组成的的任何有穷序列被称之为该字母表上的符号串,也称作字。,2.1.2符号串,25,设s是符号串前缀：移走s的尾部的零个或多于零个符号后缀：删去s的头部的零个或多于零个符号子串:从s中删去一个前缀和一个后缀子序列:从s中删去零个或多于零个符号(这些符号不要求是连续的）逆转（用SR表示）：将S中的符号按相反次序写出而得到的符号串。长度：是该符号串中的符号的数目。例如|aab|=3,|=0。,二术语,26,：符号串s=banana前缀：,b,ba,ban,bana,banan,banana后缀：banana,anana,nana,ana,na,a,子串:banana,anana,banan,anan,真前缀，真后缀，真子串:xsx子序列:baa(这些符号不要求是连续的）逆转（用SR表示）：ananab长度：banana=6,例,27,1.连接：设x和y是符号串，它们的连接xy是把y的符号写在x的符号之后得到的符号串。例如，x=ba,y=nana,xy=banana.2.方幂：x0=;x1=x;x2=xx;xn=xn-1x;例如,x=ba,x1=ba,x2=baba,x3=bababa,.,三.符号串的运算,28,设L和M是两个符号串集合，则1.合并：LMs|sLorsM2.连接：LMst|sLandtM3.方幂：L0=，L1L，L2LL,.,LnLn-1L4.语言L的Kleene闭包，记作L*，L*Li(i=0)=L0L1L2L35语言L的正闭包，记作L+（L+LL*）L+Li(i=1)=L1L2L3L4,四.符号串集合(语言）的运算,29,如：L=AZ,azD=091LD=AZ,az,092LD是由所有用一个字母后跟一个数字组成的符号串所构成的集合。3L4是由所有的四个字母的符号串构的集合。4L（LD)*是由所有的字母打头的字母和数字组成的符号串所构成的集合.5D+是由所有的长度大于等于1的数字串所构成的集合.,例,30,2.2文法和语言的定义,2.2.1引子2.2.2文法和语言的定义一.文法和语言的定义二.推导三.语言四.最左推导和最右推导五。短语，直接短语，句柄,31,引子,分析：Thegreywolfwilleatthegoat,谓语,主语,冠词,形容词,名词,动词,直接宾语,助动词,句子,动原,冠词,名词,Thegreywolfwilleatthegoat,32,为了进行机械分析，：“句子由主语后跟随谓语组成”表示为：,句子主语谓语（1）主语冠词形容词名词（2）冠词the形容词grey谓语动词直接宾语（5）动词助动词动词原形（6）助动词will动词原形eat直接宾语冠词名词（9）名词wolf名词goat,语法规则,33,：终结符号集，非终结符号集，语法规则，开始符号。,终结符号集VT=the，grey,wolf,will,eat,goat非终结符号集VN=句子，主语，谓语，冠词，形容词，名词，动词，直接宾语，助动词，动词原形语法规则集P=句子主语谓语，开始符号S=句子,句子的语法有四部分,34,句子主语谓语冠词形容词名词谓语the形容词名词谓语thegrey名词谓语thegreywolf谓语thegreywolf动词直接宾语.thegreywolfwilleatthegoat,句子根据规则推导出来,35,句子thegreywolfwilleatthegoatthegreywolfwilleatthewolfthegreygoatwilleatthewolfthegreygoatwilleatthegrey合符语法且合符语义的句子仅是：thegreywolfwilleatthegoat,+,句子既要合符语法又要合符语义,36,分析：Thegreywolfwilleatthegoat,句子,主语,谓语,冠词,形容词,名词,动词,直接宾语,助动词,动原,冠词,名词,goat,the,eat,will,The,grey,wolf,句型分析一,37,分析：Thegreywolfwilleatthegoat,句子,主语,谓语,冠词,形容词,名词,动词,直接宾语,助动词,动原,冠词,名词,goat,the,eat,will,The,grey,wolf,句型分析二,38,一个上下文无关文法G=（VT，VNS,P），其中：VT是一个非空有穷终结符号集合；VN是一个非空有穷的非终结符号集合，且VTVN；SVN，称为开始符号。P是一个产生式的非空有穷集合，每个产生式的形式是A(或A:)，其中AVN，（VTVN）*。开始符号S至必须在某个产生式的左部出现一次。缩写形式：A1|2,一文法的定义,39,G=(a,+,*,(,),，P)P：*（)aEE+TTTT*FFF(E)a(2.1),例2.2算术表达式的文法G:,40,令G=(VT,VN,S,P),若AP,且,(VTVN)*,则称A直接推出,表示成AA直接推出直接归约到A如果存在一个直接推导序列：012n（n0）表示成0n0n或者0=n或者0n,+,+,*,二.定义2.3直接推导和推导的定义,41,例：EE+TT+TF+Ta+Ta+Fa+a,42,设文法G（VT，VN，S,P）。如果S,则称是一个句型。仅含终结符号的句型是一个句子。语言L(G）是由文法G产生的所有句子所组成的集合：L(G)|S且VT*例2.3考虑一个文法G(a,b,S,S，P）其中P：SaSbabSaSbaaSbba3Sb3an-1Sbn-1anbn,*,+,三.定义2.4：语言的定义,43,设G=(VT=a,b,VN=S,A,B,S,PP由下列产生式组成:SaB|bAAa|aS|bAABb|bS|aBBL(G)=w|wa,b+,且w中有相同个数的a和b。用归纳法证明下面结论（对w的长度）：(1)Sw,当且仅当w中含有相同个数的a和b。(2)Aw,当且仅当w中a的个数比b的个数多一个。(3)Bw,当且仅当w中b的个数比a的个数多一个。归纳基础当|w|=1，Aa,Bb,不能从S导出长度为1的终极行,则上述结论显然成立。,*,*,*,例2.4,44,设(1),(2)和(3)对于长度不超过k-1的所有w都成立。那么，证明对|w|=k也成立。对于（1），推导的第一步必是SaB或SbA,对于第一种情形，必有w=aw1且Bw1，|w1|=k-1，它含的b个数比a多一个，因此，w中a,b的个数相等。推导的第一步是SbA,证明完全类似。反之，|w|=k,w中a,b的个数相等,要证Sw。考虑的S推导，推导出的开始符号，或为a或为b。若SaB,Bw1,|w1|=k-1,w1中b的个数比a多一个,w=aw1。若SbA，证明和类SaB类似。（2）和（3）的证明留给同学们。,*,*,*,归纳步骤：,45,:对于w和G,wL(G)是否存在Sw，如何构造例如，GE（例2.2）和w=a+aaEE+TT+TF+Ta+Ta+TFa+FFa+aFa+aa（最左）特点：A(A)，VT*EE+TE+TFE+TaE+FaE+aaT+aaF+aaa+aa特点：A(A)，VT*（最右）,+,四.最左推导和最右推导,46,令GS是一个文法，如果有SA且A则称是一个关于非终结符号A的，句型的短语。其次如果有SA且A则称是直接短语。一个句型的最左直接短语称为该句型的句柄。文法（21）的一个句型a1*a2+a3，尽管有Ea2a3，但是a2a3并不是该句型的一个短语,因为不存在Ea1*E。短语：a1,a2,a3，a1*a2,a1*a2+a3直接短语:a1，a2,a3句柄:a1,+,*,*,+,+,定义2.5,47,2.3分析树和二义性,一.分析树的定义二.如何画出分析树三.子树四.二义性文法的定义五.在构造编译程序中如何处理二义性文法,48,设G=（VT，VN，S，P）,G的一棵分析树满足如下条件：1.每一个结点有一个标记，此标记是VTVN中的符号。2根的标记是S。3如果一个结点是内部结点，且有标记A,那么A必在VN中。4如果编号为n的结点有标记A,结点n1,n2,nk是点n的从左到右的儿子，并分别有标记X1,X2,Xk，则AX1X2Xk必须是P中的产生式5.如果结点n有标记，那么结点n是叶子，且是它父亲唯一的儿子。,一.分析树的定义,49,例2.5G=(VT,VN,S,P),其中P:SaASaASbASSba,3,1,2,4,6,5,7,8,9,10,11,S,a,A,S,S,b,A,a,a,b,a,50,根据推导序列，对每步推导画相应分枝,A,S,a,S,b,S,A,a,a,b,a,aSbAS,aabAS,aabbaS,aabbaa,aAS,S,二.如何画出分析树(1.自顶向下）,51,根据归约序列，对每步归约画相应分枝,A,S,a,S,b,S,A,a,a,b,a,aAa,aSbAa,aSbbaa,aabbaa,aAS,S,二.如何画出分析树(2.自底向上）,52,1.一个句型推导或分析用一棵树结构图示出来，它反应了一个句子语法结构的层次。2.对于一个句子的多种推导（若文法是无二义性的），采用各种推导过程，画出的分析树是一样的。分析树并未描述推导过程。3.在书中，用画分析树的过程解释语法分析过程，用分析树图解语法结构。分析树是推导的图形表示。,关于分析树的几点说明,53,一棵分析树中一个特有的结点连同它的全部后裔，连接这些后裔的边以及这些结点的标记。例如：,S,A,b,S,a,S,b,a,A,a,a,三.子树,54,短语：一棵子树的所有叶子自左至右排列起来形成一个相对于子树根的短语。直接短语：仅有父子两代的一棵子树，它的所有叶子自左至右排列起来所形成的符号串。句柄：一个句型的分析树中最左那棵只有父子两代的子树的所有叶子的自左至右排列。例如，对表达式文法GE和句子a1+a2*a3，挑选出推导过程中产生的句型中的短语，直接短语，句柄。,用子树解释短语，直接短语，句柄:,55,E,E+T,T+T,F+T,a1+T,a1+T*F,a1+F*F,a1+a2*F,E+T,T,T+T,F,F+T,a1,a1+T,a1,T*F,a1+T*F,a1,F,F*F,a1+F*F,a1,a2,a1+a2*F,a2*F,a1,a2,a3,a2*a3a1+a2*a3,E,E,+,T,T,F,a1,T,*,F,F,a2,a3,a1+a2*a3,短语,例(a),56,E,E+T,E+T*F,E+T*a3,E+F*a3,E+a2*a3,T+a2*a3,F+a2*a3,E,E,+,T,T,F,a1,T,*,F,F,a2,a3,a1+a2*a3,例(b),57,描述一个句子的文法不是唯一的；2.对于一个句子的分析应是唯一的。考虑表达式下面的文法GE,其产生式如下：EE+EE*E(E)a对于句子a+a*a,有如下两个最左推导：EE+Ea+Ea+E*Ea+a*Ea+a*aEE*EE+E*Ea+E*Ea+a*Ea+a*a,四.文法的二义性的定义,58,EE+Ea+Ea+E*Ea+a*Ea+a*a,EE*EE+E*Ea+E*Ea+a*Ea+a*a,E,E,+,E,E,*,E,a,a,a,E,E,*,E,+,E,E,a,a,a,最左推导,例(1),59,EE+EE+E*EE+E*aE+a*aa+a*a,EE*EE*aE+E*aE+a*aa+a*a,E,E,+,E,E,*,E,a,a,a,E,E,*,E,+,E,E,a,a,a,最右推导,例(2),60,如果一个文法的句子存在两棵分析树,那磨,该句子是二义性的。如果一个文法包含二义性的句子,则称这个文法是二义性的;否则，该文法是无二义性的。几点说明：1.一般来说，程序语言存在无二义性文法，对于表达式来说，文法（2.1）是无二义性的。对于条件语句，经常使用二义性文法描述它：SifexprthenSifexprthenSelseSother二义性的句子:ife1thenife2thens1elses2,四.二义性（歧义性，ambiquity)的定义:,61,下面是Smathed_sunmathed_smathed_sifexprthenmathed_selsemathed_sotherunmathed_sifexprthenSifexprthenmathed_selseunmathed_s它显然比较复杂，因此：2.在能驾驭的情况下，使用二义性文法。,描述if语句的无二义性文法的产生式:,62,3.对于任意一个上下文无关文法，不存在一个算法，判定它是无二义性的；但能给出一组充分条件，满足这组充分条件的文法是无二义性的。4.存在先天二义性语言。例如，aibicji,j1aibjcji,j1存在一个二义性的句子akbkck。压缩过的文法（化简了的文法）：1形式的产生式：AAP；2.每个非终结符号A必须都有用处。即，SA且A，VT*,*,+,63,2.4形式语言概观,2.4.1文法分类2.4.2非上下文无关文法的语言结构2.4.3上下文无关语言和正规语言的区别,64,逐渐对产生式施加限制四种类型：0型，1型，2型，3型0型：G=(VT,VN,S,P)规则形式：,(VTVN)*,推导：1型（上下文有关）：规则形式：AAVN,.(VTVN)*,2型（上下文无关）：规则形式：AAVN，(VTVN)*3型（右线性）：AaBAa（左线性）ABaAaaVT,2.4.1文法分类,65,在我们使用的程序语言中,有些语言结构并不是总能用上下文无关文法描述的。例2.9L1=wcw|wa,b+。例如,aabcaab就是L1的一个句子。这个语言是检查程序中标识符的声明应先于引用的抽象。例2.10L2=anbmcndm|n,m0，它是检查过程声明的形参个数和过程引用的参数个数一致问题的抽象。,2.4.2非上下文无关的语言结构,66,语言中过程定义和引用的语法并不涉及到参数个数，例如，Pascal的过程语句可描述为s-callid(r-list)r-listr-list,r|r实参和形参个数的一致性检查也是放在语义分析阶段完成的。定义2.7如果一个上下文无关文法G中存在具有下列特征的非终结符A:AA其中,VTVN+,则称A为自嵌套的,+,2.4.3上下文无关语言和正则语言的区别,67,包含自嵌套非终结符号的文法是语言anbn|n0是上下文无关语言，原因是找不到一个非自嵌套的上下文无关文法描述它；语言anbm|n，m0是正则语言,原因是存在一个正规文法描述它。在程序语言中，与词法有关的规则属于正规文法；与局部语法有关的规则属于上下文无关文法；而与全局语法和语义有关的部分往往要用上下文有关文法来描述。,上下文无关文法。,68,用上下文有关文法描述程序语言不仅相当困难，将使语法定义变得烦杂，难懂，而且一般不能构造有效的分析程序，因此，通常用上下文无关文法描述，而把与上下文有关的限制包含在非形式描述的全局语法与语义中。把描述词法的正规文法从描述语法的上下文无关文法中分离出来。在分离出正则文法后的上下文无关文法中，这些单词符号是属于终结符号VT中的符号。文法(2.1)中的表达式文法，a是终结符号。,为什么不用上下文有关文法描述程序语言？,69,：1.1GS:(b),(c),(d),(e)1.2GS:(a),(b),(c),(d)1.3Gbexpr:(b)1.写出下面语言的三型文法：（a)ann0(b)anbmn,m1(c)anbmckn,m1(d)Pascal的标识符(e)Pascal的整数2.已知文法GS，其产生式如下：S(S)(a)L(GS)是什磨？(b)对于(a)的结果，试给出证明。,作业,70,3.1词法分析程序的设计：词法分析器的功能，输出，把它组织成单独程序3.2词法分析器的手工构造：用DFA能识别单词，构造DFA并用程序实现它3.3有限自动机：有限自动机的等价性，一个FAm,min(DFAm)L(m)=L(m)3.4正规表达式：单词能用正规表达式描述，能用DFA识别3.5正规文法与有限自动机的等价性3.6词法分析程序自动构造工具LEX简介,71,=,8,0,;,e,n,i,L,L,i,n,e,=,8,0,;,=,=,;,;,输入,0,3,1,字母,字母,数字,数字,数字,=,；,4,5,6,2,0,0,0,0,0,0,0,输出,id,Line,=,num,80,;,有限控制器,分析结束,72,3.1词法分析程序的设计,3.1.1词法分析程序的功能源程序单词序列3.1.2单词的词类和属性（词类符号，单词的属性值）3.1.3词法分析程序作为一个独立子程序（1）语法分析程序的子程序；（2）组织成一遍扫描。,词法分析器,73,Whileijdoifijtheni:i-jelsej:=jIwhile，i，j，do，if，i，j,then,i,:=,i,-,j,else,j,:=,j,-,i,词法分析器,74,词类和属性computatorn.Calcculatingmachine.程序语言单词的分类：1关键字(保留字或基本字)：begin,end2标识符：用来表示各种名字3字面常数：256，3.14，true,abc4运算符：如，、*、/等等5分界符：如逗号，分号，冒号等,75,词法分析器的输出：（词类编码，单词自身的属性值）词类编码提供给语法分析程序使用；单词自身的属性值提供给语义分析程序使用。具体的分类设计以方便语法分析程序使用为原则。关键字可分成一类，也可以一个关键字分成一类。常数可统归一类，也可按类型（整型、实型、布尔型等），每个类型的常数划分成一类。单词自身的属性值提供的内容，是由词法分析和语义分析的任务划分决定的。,76,例如：图31的源程序经词法分析器while，id，指向j的符号表人口的指针relationalop，NEid，指向j的符号表人口的指针do，if，id，指向i的符号表入口的指针id，指向j的符号表入口的指针,77,3.1.3把词法分析设计成一个独立程序（1）组织成一遍扫描；（2）作为语法分析和语义分析的子程序,词法分析,语法分析,语义分析和中间代码生成,源程序,中间代码,符号表管理,错误的诊查处理,78,32词法分析器的手工构造,为了构造词法分析器，要研究构词法，每种词类的结构模式以及识别它的数学模型有限自动机。它的模拟程序可以作为词法分析器的控制程序。321确定的有限自动机（DFA）322构造识别单词的DFA323编写词法分析程序,79,3.2.1确定的有限自动机DFA(DeterministicFiniteAutomata)一.设计一个奇偶校验器二.DFA的定义三.DFA的三种表示四.DFA接受的语言五.DFA判定w是否属于L(m)的模拟算法结论：如果我们能构造一个DFAM，使得L(M)是编译器处理的程序语言中的单词，那么模拟DFAM的程序将可以用作词法分析器的控制程序。,80,一设计一个奇偶校验器DFA是由集合，序列和函数定义的数学模型，它对于上的w，判定是可接受的还是不可接受的。例如，设计一个DFAm，奇偶校验器，首先，w是由0，1组成的字符串，因此，1.=0,1且w在一条输入带上。,01011$,读头,81,2.状态集：它记忆已读入w子串的状态,m是奇偶校验器，它应该记住，初始序列是奇数个1还是偶数个1。因此，m有even和odd两个状态.3.even为开始状态。4.转换函数，（qold,a)=qnewm有:(even,0)=even（even,1)=odd(odd,0)=odd（odd,1)=even5.接受状态（或终止状态）集odd若w使m从初始状态出发，最后到达一个接受状态，则w被m接受；否则w被m拒绝。,82,二定义31一个确定的有限自动机M（记作DFAM）是一个五无组（，0，），其中（）是一个有限状态集合。（）是一个字母表，它的每个元素称为一个输入符号。（）0，0称为初始状态。（），称为终结状态集合。（）是一个从到的单值映射(，)（,，）表示当前状态为q,输入符号为a时，自动机将转换到下一个状态，称为的一个后继。,83,例33设（，）其中（，），（，）3（，），（，）（，），（，）（，），（，）三一个有三种表示：（1）象上面，用转换函数；（2）转移矩阵；（3）状态转换图。,84,转移矩阵,0,1,3,2,a,a,a,a,b,b,b,b,3,状态转换图,易存储,85,四DFAM接受的语言如果对所有*，以下述方式递归地扩张的定义（，），(，）(，w），），对任何,，则有（）*，若存在，使（，）对于例3.3的DFAM和w=baa，(0，ba）=(2,a）=(1,）=3,86,从状态转换图看，从初态出发，沿任一条路径到达接受状态，这条路径上的弧上的标记符号连接起来构成的符号串被接受。,0,1,2,3,a,a,a,a,b,b,b,b,87,五.DFAM判定?(）的算法：输入：$q:=q0;a:=nextchar;WHILEa$DOBEGINq:=move(q,a);a:=nextchar;END;IFqINFTHENreturn(”yes)ELSEreturn(”no);,88,3.2.2手工构造识别单词的DFAm根椐DFA识别单词的定义，在研究给定程序语言单词结构的基础上，能直接构造出识别它的DFAm。例如：对于Pascal,标识符：字母开始的字母数字串。整数：非空数字串。无符号实数（用表示数字）：（a)dd.ddE(+-)dd(b)ddE(+-)dd(c)dd.dd,89,1,3,4,2,字母,字母,数字,数字,数字,Pascal标识符,Pascal整数和实数,0,1,3,4,6,5,2,7,0,0,d,d,d,d,d,d,d,E,E,+,7,*,*,*,90,3.2.3编写词法分析程序根据画出的状态转换图（识别单词的）构造词法分析程序，每个状态对应一段程序，完成到达此状态的工作；词法分析程序的控制程序模拟状态转换图的状态转换。在识别标识符的过程中，要拼写出来，并和保留字区别开来；在识别常数的过程中，要把它转换成机器表示以作为属性值。,91,使用下面的全局变量和过程：1.Character2.Token3.Getchar4.getbc5.Concatenation6.letter,digit7.Reserve8.Retract9.buildlist10.return,92,作业：3.23.3解释下面每个有限自动机识别的语言是什磨？,(a),1,2,3,4,5,6,7,8,9,0,0,0,0,0,0,0,1,1,1,1,1,1,1,(b),1,2,3,4,5,a,a,a,a,a,93,(c),0,1,2,0,0,0,1,1,1,3.4给出接受下列在字母表0，1上的语言的DFA:(a)所有以00结束的串的集合；（b)所有具有三个0的串的集合。,0,94,3.3有限自动机FAm3.3.1非确定的有限自动机NFAm一.NFAm二.FA的等价定理三.例3.3，用DFA模拟NFA的动作四.从一个NFA构造DFA的算法3.3.2确定的有限自动机的化简一.何谓确定的有限自动机的化简二.等价状态的定义三.确定的有限自动机的化简方法,95,一.非确定的有限自动机NFAm定义32非确定有限自动机是一个五元组（，q，）其中，q，的意义和的定义一样，而是一个从到的子集的映射，即：类似FA，NFAm可用状态转换图表示，可定义NFAm接受的语言。,96,二.FA的等价性定理3.1对任何一个NFAm，都存在一个DFAm，使L(m)=L(m)证明思想：用m的一个状态对应m的一个状态集合，用这种方法，能从一个NFAm构造一个DFAm，称作子集构造法。例3.2NFAm=(0,1,q0,q1,q0,),其中(q0,0)=q0,q1,(q0,1)=q1(q1,0)=(q1,0)=q0,q1,97,q0,q0,q1,0,0,1,1,1,q0,q0,q0,q1,q0,q1,0,1,1,0,1,L(m)=L(m)=0,1+100,1*,98,0,1,4,2,3,6,5,7,8,9,10,a,a,b,b,b,0,1,2,4,7,0,1,2，4,7,a,3,a,8,6,1,2,4,7,3,8,6,1,2,4,7,b,5,b,9,6,1,2,4,7,a,5,9,6,1,2,4,7,b,b,5,6,1,2,4,b,10,5,10,6,1,2,4,7,7,b,例3.3从具体例子的讨论,提炼出从NFA构造DFA的算法。,99,四.从NFA构造DFA的算法1.closure(S)的定义和算法从S中任一状态出发，仅沿弧到达的状态集合，T=S(edge(t,),其中，edge(t,a)是NFA中从状态t出发，仅沿a弧到达的状态集合。如下计算T：T:=S;REPEATT:=T;T:=T(edge(t,)(tT)UNTILT=T,tT,100,2.DFA的转移函数DFAedge(d,a)=closure(edge(t,a)其中，d是NFA的状态集，a。从NFA构造DFA，是对于NFA的所有输入,，用DFA模拟NFA的动作，令t1是NFA的初态，DFA的初态d1=closure(t1)，若，dj=DFAedge(di,a),那磨，从di到dj存在一条用a标识的弧。算法3,2从一个NFA构造一个DFA,td,101,States1:=-closure(t1);p:=1;j:=1;WHILEj=pDOforeachae:=DFAedge(statesj,a);IFe=statesiforsomei=pTHENtransj,a=iELSEp:=p+1;statesp:=e;transj,a:=p;j:=j+1;,102,0,1,4,3,6,5,7,8,9,10,a,b,b,b,2,a,3,8,6,1,2,4,7,0,1,2,4,7,2,5,6,1,2,4,7,3,2,5,9,6,1,2,4,7,4,2,3,2,5,10,6,1,2,4,7,5,2,3,103,3.3.2确定的有限自动机的化简一.何谓确定的有限自动机的化简所谓一个DFAm=(,Q,q0,F,)的化简是指寻找一个状态数比较少的DFAm,使L(m)=L(m)。而且可以证明，存在一个最少状态的DFAm,使L(m)=L(m)。二.等价状态的定义设p,qQ，若对任何w*,(p,w)F当且仅当(q,w)F，则称p和q是等价状态。否则，称p和q是可区别的。,104,q1,q2,q3,q4,q1,q2,q3,q6,q4,q5,q7,b,a,a,a,a,a,a,a,a,a,a,a,b,b,b,b,b,b,b,b,b,b,105,1.等价状态定义了状态集合上的等价关系。因此，状态集合能被划分成等价类；2.两个状态p和q等价应满足如下条件：（a）一致性条件，p和q必须同时或为接受状态或为非接受状态；（b）蔓延性条件，对于a，（p,a)=r,（q,a)=s,r和s必须等价;相反,r和s不等价,p和q不等价。判定两个状态p和q不等价，只要o找到一个w*，使（p,w)F且（q,w)F，或者相反。W称为判别序列。,106,三.方法：构造一张表，对每一个状态对（qi,qj）（ij）有一表项，每当发现一对状态不等价时，就放一个x到相应表项中。1.根据一致性条件，在每一个对应于终结状态和非终结状态的表项中放上一个x。2.根据蔓延性性条件，对每一个状态对（p,q），若a，（p,a）=r，（q,a）=s，r和s不等价，则（p,q）不等价。重复2，直到没有新的不等价状态对出现。,107,q8,q7,q6,q5,q1,q2,q3,1,1,1,1,0,1,1,1,0,0,0,0,0,0,q2q3q5q6q7q8,q1q2q3q5q6q7,x,x,x,x,x,x,x,x,x,x,x,x,x,108,3.4正规表达式用正规表达式描述单词，把它转换成识别装置-有限自动机。3.4.1正规表达式与单词一.正规表达式的定义二.正规表达式的代数性质三.正规定义式四.例示，用正规定义式描述单词3.4.2正规表达式与有限自动机的等价性L(r)=L(m),109,一.正规表达式的定义是字母表正规表达式正规表达式表达的语言1.，2.a,aa3.若r,sL(r),L(s)则(a)(r)(s)L(r)L(s)(b)(r)(s)L(r)L(s)(c)(r)*(L(r)*(d)(r)L(r),110,注：（1）正规表达式描述的集合称作正规集（正规表达式的计算描述如何构造正规集）。（2）“*”，连接，“”运算左结合，优先级由高到低。例：=A,B,Z,a,b,z,0,1,9AB.Zab.zL(A)L(B)L(Z)L(a)L(b).L(z)=A,B,Z,a,b,z01.9L(0)L(1).L(9)=0,1,9,111,(AB.Zab.z)(AB.Zab.z)(01.9)*A,B,Z,a,b,z(A,B,Z,a,b,z0,1,9)*标识符例3.3=a,b(a)aba,b(b)(ab)(ab)aa,ab,ba,bb(c)a*,a,aa,aaa,aaaa,(d)(ab)*(,a,b,aa,ab,ba,bb,aaa,.(e)aab*,112,二.正规表达式的代数性质,113,正闭包r+,表达的语言(L(r)+(L(r)+=(L(r)1(L(r)2(L(r)3r*=r+r+=rr*三.正规定义式给正规表达式命名，引用。，序列：d1r1d2r2.dnrn其中di表示不同的名子，每一个ri是d1,d2,di-1上的正规表达式。正规定义式和产生式的区别。,114,四.例示，用正规定义式描述单词例3.4Pascal标识符和无符号实数letter(letterdigit)*letterAB.Zab.zdigit01.9idletter(letterdigit)*(digit)+(.(digit)+)(E(+-)(digit)+)digitsdigit(digit)*fractiondigitsexponent(E(+-)digits)numdigitsfractionexponent,115,3.4.2正规表达式与有限自动机的等价性单词结构用正规表达式描述，用机械的方法（程序），把正规表达式变换成等价的有限自动机。定理3.2设r是上一个正规表达式，则存在一个FAm接受L(r)。反之亦然。证对正规表达式r的运算数目作归纳。设r具有零个运算，则或r=或r=或r=a,q0,q0,q1,q0,q1,a,r=,r=,r=a,116,设结论对少于i(i1)个运算的正规表达式r成立。当r有i个运算时，有三种情况：情况1r=r1r2情况2r=r1r2情况3r=r1*有m1=(1,Q1,q1,F!,1),m2=(2,Q2,q2,F2,2)且L(m1)=L(r1),L(m2)=L(r2)，由m1和m2构造m,使得L(m)=L(r).构造方法图示如下：,q0,q1,f1,f2,q2,f0,m2,m1,r=r1r2,117,q0,q1,f1,q2,f0,m2,m1,f2,q1,f1,r=r1r2,r=r1*,上述证明方法，是对于一个正规表达式r,构造一个FAm,且L(m)=L(r)的算法,但假定知道r的计算顺序。正规表达式r的语法是上下文无关文法。,118,例3.5构造与下列正规式(c)r=01*1等价的有限自动机。语法树如左下图。,*,0,1,1,q0,q1,0,q2,q3,1,q2,q3,q5,q4,1,119,0,1,q0,q1,q6,q7,1,q2,q5,q4,q0,q1,q4,q2,q3,q3,q6,q7,1,1,0,q8,q5,q9,120,对于上任一NFAm，能构造上一个正规表达式r，使得L(r)=L(m)。把转换图的概念拓广，每条弧上可以用一个正规式标记。首先，在m的转换图上加进x,y两个结。从x用弧连接到m的所有初态结点，从m的所有接受态结点用弧连接到y，从而构成一个新的NFAm，L(m)=L(m)。下面，逐步消去NFAm中的状态结点，直至剩下x,y为止。在消结的过程中，逐步用正规式标记弧。消结的过程是直观的，只需反复使用下面的替换规则。,121,a,b,c,a,c,a,c,a,c,a,b,c,a,c,r1,r2,r2,r2,r1,r1,r3,r1r2,r1r2,r1r2*r3,替换规则,代之以,代之以,代之以,122,3.5正规文法与有限自动机(FA)的等价性L(G)=L(m)定理3.3对于每一个右线性正规文法或左线性正规文法G，都存在一个FAm，使L(m)=L(G)证给定右线性正规文法G=(VT,VN,S,P),设fVN，令m=(VT,Q,S,F,),其中，F=fQ=VNf,转移函数定义如下：(a)Aa,(A,a)=f(b)AaA1aA2.aAn(A,a)=A1,A2,.,An,123,给定左线性正规文法G=(VT,VN,S,P),设q0VN，令m=(VT,Q,q0,S,),其中，Q=VNq0,转移函数定义如下：(a)Aa,(q0,a)=A(b)A1A,a,A2Aa,AnAa(A,a)=A1,A2,.,An定理3.4对于每一个DFAm，都存在一个右线性正规文法G和一个左线性正规文法G，使L(m)=L(G)=L(G)。证设m=(,VN,S,F,),右线性正规文法G的构造方法如下：,124,若sF,G=(,VN,S,P),P的定义如下：对任何a及A,BVN,若有(A,a)=B,则(a)BF,AaB(b)BFAaaB若sF,S0VN,S0S构造左线性正规文法，P的定义如下：对任何a及A1,A2VN,有(A1,a)=A2,则(a)A1是初态，A2a(b)A1不是初态,A2A1a,125,例3.6DFAm右线性正规文法GNFAm左线性正规文法G,A,D,C,B,0,1,1,1,1,0,0,0,A00B1DB0D1CC00B1DD0D1D,126,A,D,C,B,0,1,1,1,1,0,0,0,S0C0B0C0CB1D1B0C1D0D1,f,0,0,NFAm,左线性正规文法,127,3.6词法分析程序的自动构造工具LEX简介一.原理单词的结构用正规式描述正规式NFADFAminDFA二.用LEX建立词法分析程序的过程,LEX编译器,LEX源程序lex.1,Lex.yy.c,128,C编译器,Lex.yy.c,a.out,a.out,输入流,单词序列,三.lex源程序lex源程序由三部分组成,129,声