ch02--形式语言与自动机.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Wensheng Li BUPT 2008,第,2,章,形式语言与自动机基础,知识点：文法的形式定义,上下文无关文法、正规文法,推导、短语、分析树、二义性,有限自动机的形式定义,自动机、文法、表达式等价性,NFA,的确定化、,DFA,的最小化,形式语言与自动机基础,2.1,语言和文法,2.2,有限自动机,2.3,正规文法与有限自动机的等价性,2.4,正规表达式与有限自动机的等价性,2.5,正规表达式与正规文法的等价性,小 结,2,2.1,语言和文法,一、字母表和符号串,二、语言,三、文法及其形式定义,四、推导和短语,五、分析树及二义性,六、文法的变换,3,一、字母表和符号串,字母表,符号的非空有限集合,典型的符号是字母、数字、各种标点和运算符等。,符号串,定义在某一字母表上,由该字母表中的符号组成的有限符号序列,同义词：句子、字,符号串有关的几个概念,长度,符号串,的长度是指,中出现的符号的个数，记作,|,|,。,空串的长度为,0,，常用,表示。,4,前缀,符号串,的前缀是指从符号串,的末尾删除,0,个或多个符号后得到的符号串。如：,univ,是,university,的前缀,后缀,符号串,的后缀是指从符号串,的开头删除,0,个或多个符号后得到的符号串。如：,sity,是,university,的后缀,子串,符号串,的子串是指删除了,的前缀和,/,或后缀后得到的符号串。如：,ver,是,university,的子串,真前缀,、,真后缀,、,真子串,如果非空符号串,是,的前缀、后缀或子串，并且,，则称,是,的真前缀、真后缀、或真子串。,子序列,符号串,的子序列是指从,中删除,0,个或多个符号,(,这些符号可以是不连续的,),后得到的符号串。如：,nvst,5,连接,符号串,和符号串,的连接,是把符号串,加在符号串,之后得到的符号串,若,=,ab,，,=,cd,，,则,=,abcd,，,=,cdba,。,对任何符号串,来说，都有,=,=,幂,若,是符号串，,的,n,次幂,n,定义为：,n个,当,n=0,时，,0,是空串,。,假如,=,ab,，,则有：,0,=,1,=,ab,2,=,abab,n,=,abab,ab,n,个,ab,6,二、语言,语言：,在某一确定字母表上的符号串的集合,。,空集,，集合,也是符合此定义的语言。,这个定义并,没有把任何意义赋予语言中的符号串,。,语言的运算：,假设,L,和,M,表示两个语言,L,和,M,的,并,记作,LM,：,LM=s|s,L,或,s,M,L,和,M,的,连接,记作,LM,：,LM=,st|s,L,并且,t,M,L,的,闭包,记作,L,*,：即,L,的,0,次或若干次连接。,=L,0,L,1,L,2,L,3,L,的,正闭包,记作,L,+,：即,L,的,1,次或若干次连接。,=L,1,L,2,L,3,L,4,7,L=A,B,Z,a,b,z,，,D=0,1,9,可以把,L,和,D,看作是字母表,可以把,L,和,D,看作是语言,语言运算举例：,把,幂运算推广,到语言,L,0,=,，,L,n,=L,n-1,L,，,于是,L,n,是语言,L,与其自身的,n-1,次连接。,语言 描述,LD,全部字母和数字的集合,LD,由一个字母后跟一个数字组成的所有符号串的集合,L,4,由,4,个字母组成的所有符号串的集合,L,*,由字母组成的所有符号串（包括,）的集合,L(LD),*,以字母开头，后跟字母、数字组成的所有符号串的集合,D,+,由一个或若干个数字组成的所有符号串的集合,8,三、文法及其形式定义,文法,：所谓文法就是描述语言的语法结构的形式规则。,任何一个文法都可以表示为一个,四元组,G=(V,T,V,N,S,),V,T,是一个非空的有限集合，它的每个元素称为,终结符号,。,V,N,是一个非空的有限集合，它的每个元素称为,非终结符号,。,V,T,V,N,=,S,是一个特殊的非终结符号，称为文法的,开始符号,。,是一个非空的有限集合，它的每个元素称为,产生式,。,产生式的形式为：,“,”表示“,定义为,”（或“,由,组成,”）,、,(V,T,V,N,),*,，,左部相同的产生式,1,、,2,、,、,n,可以缩写,1,|,2n,“,|,”,表示“,或,”，每个,i,(i=1,2,n),称为,的一个,候选式,9,文法的分类,根据对产生式施加的限制不同，定义了四类文法和 相应的四种形式语言类。,文法类型 产生式形式的限制 文法产生的语言类,0,型文法 其中,(V,T,V,N,),*,0,型语言,|,|,0,1,型文法，即,1,型语言，即,上下文有关文法 其中,(V,T,V,N,),*,上下文有关语言,|,|,|,|,2,型文法，即,A,2,型语言，即,上下文无关文法 其中,A,V,N,，,(V,T,V,N,),*,上下文无关语言,3,型文法，即,A,a,或,A,aB,（,右线性），或,3,型语言，即,正规文法,A,a,或,A,Ba,（,左线性）正规语言,（线性文法）其中,A,B,V,N,，,a,V,T,10,上下文无关文法及相应的语言,所定义的语法单位,(,或称语法实体,),完全独立于这种语法单位可能出现的上下文环境,现有程序设计语言中，许多语法单位的结构可以用上下文无关文法来描述。,例：,描述算术表达式的文法,G,：,G=(i,+,-,*,/,(,),),其中,：,+|-|,*|/|,()|i,语言,L(G),是所有包括加、减、乘、除四则运算的算术表达式的集合。,11,如果,用“,:=”,代替“,”,，这组产生式可以写为：,:=+|-|,:=*|/|,:=()|i,元语言：,:=,表示 “定义为”或“由,组成”,表示非终结符号,|,表示“或”,BNF,（,Backus-Normal Form,）,表示法,12,文法书写约定,终结符号,次序靠前的小写字母，如：,a,、,b,、,c,运算符号，如：,+,、,-,、*、,/,各种标点符号，如：括号、逗号、冒号、等于号,数字,1,、,2,、,、,9,黑体字符串，如：,id,、,begin,、,if,、,then,非终结符号,次序靠前的大写字母，如：,A,、,B,、,C,大写字母,S,常用作文法的开始符号,小写的斜体符号串，如：,expr,、,term,、,factor,、,stmt,13,终结符号串,次序靠后的小写字母，如：,u,、,v,、,、z,文法符号串,小写的希腊字母，如：,、,、,、,可以直接用产生式的集合代替四元组来描述文法，第一个产生式的左部符号是文法的开始符号。,文法符号,次序靠后的大写字母，如：,X,、,Y,、,Z,14,四、推导和短语,例：,考虑简单算术表达式的文法,G,：,G=(+,，*，（，），,i,E,，,T,，,F,E,),：,E,E+T|T,T,T*F|F,F,（,E,）,|i,文法所产生的语言,从文法的开始符号出发，反复连续使用产生式对非终结符号进行替换和展开，就可以得到该文法定义的语言。,15,推导,假定,A,是一个产生式，,和,是任意的文法符号串，则有：,A,“,”,表示“一步,推导,”,即利用产生式对左边符号串中的一个非终结符号进行替换，得到右边的符号串。,称,A,直接推导出,也可以说,是,A,的,直接推导,或说,直接归约,到,A,16,从文法开始符号,E,推导出符号串,i+i,的详细过程,如果有直接推导序列：,1,2,n,则说,1,推导出,n,，,记作：,1,n,*,*,“,”,表示,0,步或多步推导,称这个序列是从,1,到,n,的,长度为,n,的推导,A,所用产生式 从,E,到,的推导长度,E E+T,E,E+T 1,E+T T+T,+T E,T 2,T+T F+T,+T T,F 3,F+T i+T,+T F,i 4,i+T i+F i+,T,F 5,i+F i+i i+,F,i 6,E,E+T T+T F+T i+T i+F i+i,17,最左推导,最右推导,如果,，并且在每“一步推导”中，都替换,中,最左边,的非终结符号，则称这样的推导为最左推导。记作：,*,*,lm,如果,，并且在每“一步推导”中，都替换,中,最右边,的非终结符号，则称这样的推导为最右推导。记作：,*,*,rm,最右推导也称为,规范推导,E,E+T T+T F+T i+T i+F i+i,E,E+T E+F E+i T+i F+i i+i,18,句型,句子,仅含有终结符号的句型是文法的一个,句子,。,语言,文法,G,产生的所有句子组成的集合是文法,G,所定义的,语言,，,记作,L(G),。,对于文法,G=(V,T,V,N,S,),，,如果,S,，,则称,是当前文法的一个句型。,*,若,S,，,则,是当前文法的一个,左句型,，,若,S,，,则,是当前文法的一个,右句型,。,*,lm,*,rm,L(G)=,|S,，,并且,V,T,*,+,19,对于文法,G=(V,T,V,N,S,),，,假定,是文法,G,的一个句型，如果存在：,短语,S,A,，并且,A,*,+,则称,是句型,关于非终结符号,A,的,短语,。,如果存在：,S,A,，,并且,A,*,则称,是句型,关于非终结符号,A,的,直接短语,。,一个句型的最左直接短语称为该句型的,句柄,。,例,:,E,T,T*F,T*(E),F*(E)i*(E),i*(E+T),i*(T+T),i*(F+T),i*(i+T),20,五、分析树及二义性,分析树,子树,子树与短语之间的关系,二义性,21,分析树,推导的图形表示，又称推导树。,一棵,有序有向树,，因此具有树的性质；,自己的特点：每一个结点都有标记。,根结点由文法的开始符号标记；,每个内部结点由非终结符号标记，它的子结点由这个非终结符号的这次推导所用产生式的右部各符号从左到右依次标记；,叶结点由非终结符号或终结符号标记，它们从左到右排列起来，构成句型。,E,T,T*F,T*(E),F*(E),i*(E),i*(E+T),i*(T+T),i*(F+T),i*(i+T),E,T,T F,F (E ),i E +T,T,F,i,E,T,T*F,F*F,i*F,i*(E),i*(E+T),i*(T+T),i*(F+T),i*(i+T),22,T,子树,E,子树,T,子树,E,T,T *F,F (E ),i E +T,T,F,i,子树,分析树中一个特有的,结点,、连同它的,全部后裔结点,、连接这些结点的,边,、以及这些结点的,标记,。,子树的根结点的标记可能不是文法的开始符号。,如果子树的根结点标记为非终结符号,A,，,则可称该子树为,A-,子树,。,23,直接短语,短语,句柄,E,T,T *F,F (E ),i E +T,T,F,i,子树与短语的关系,一棵,子树的所有叶结点自左至右排列起来，形成此句型相对于该子树根的,短语,；,分析树中,只有父子两代,的子树的所有叶结点自左至右排列起来，形成此句型相对于该子树根的,直接短语,；,分析树中,最左边,的那棵只有父子两代的子树的所有叶结点自左至右排列起来，就是该句型的,句柄,。,24,二义性,如果一个文法的某个句子有不止一棵分析树，则这个句子是,二,义性的,。,含有二义性句子的文法是,二,义性的文法,。,例：,考虑文法,G=(+,*,（,）,i,E,E,),：,E,E+E|E*E|(E)|,id,句子,id+id*id,存在两个不同的最左推导：,E,E+E,id+E,id+E*E,id+id*E,id+id*id,EE*E,E+E*E,id+E*E,id+id*E,id+id*id,有两棵不同的分析树,E,E +E,E *E,id,id,id,E,E *E,E +E,id,id,id,25,文法的二义性和语言的二义性,如果两个文法产生的语言相同，即,L(G)=L(G,),，,则称这两个,文法是等价,的。,有时，一个二义性的文法可以变换为一个等价的、无二义性的文法。,有些语言，根本就不存在无二义性的文法，这样的语言称为,二义性的语言,。,二义性问题是不可判定的,不存在一种算法，它能够在有限的步骤内确切地判定出一个文法是否是二义性的。,可以找出一些充分条件（未必是必要条件），当文法满足这些条件时，就可以确信该文法是无二义性的。,26,六、文法的变换,文法二义性的消除,左递归的消除,提取左因子,27,文法二义性的消除,映射程序设计语言中,IF,语句的文法：,stmt,if,expr,then,stmt,|,if,expr,then,stmt,else,stmt,|,other,句子,if,E,1,then,if,E,2,then,S,1,else,S,2,有两棵不同的分析树：,stmt,if,expr,then stmt,E,1,if,expr,then stmt else stmt,E,2,S,1,S,2,stmt,if,expr,then stmt else stmt,E,1,if,expr,then stmt S,2,E,2,S,1,28,最近最后匹配原则,else,必须匹配离它最近的那个未匹配的,then,出现在,then,和,else,之间的语句必须是“,匹配的,”。,所谓,匹配的语句,是不包含不匹配语句的,if-then-else,语句，或是其他任何非条件语句。,改写后的文法：,stmt,matched_stmt,|,unmatched_stmt,matched_stmt,if,expr,then,matched_stmt,else,matched_stmt,|other,unmatched_stmt,if,expr,then,stmt,|if,expr,then,matched_stmt,else,unmatched_stmt,29,句子,if E,1,then if E,2,then S,1,else S,2,的分析树,30,左递归的消除,一个文法是,左递归,的，如果它有非终结符号,A,，,对某个文法符号串,，存在推导：,消除左递归的方法：,简单情况,：如果文法,G,有产生式：,A,A,|,可以把,A,的这两个产生式改写为：,A,A,A,A,|,这两组产生式是等价的,由于从,A,推导出的符号串是相同的，即都是,A A,+,若存在某个,=,，则称该文法是,有环路的,。,31,例：,消除表达式文法中的左递归：,E,E+T|T T,T*F|F F,(E)|id,利用消除直接左递归的方法，可以改写为,:,E,TE,E,+TE,|,T,FT,T,*FT,|,F,(E)|,id,32,一般情况：,假定关于,A,的全部产生式是：,A,A,1,|A,2,|A,m,|,1,|,2,|,n,产生式可以改写为：,A,1,A,|,2,A,|,n,A,A,1,A,|,2,A,|,m,A,|,例如有间接左递归文法：,S,Aa|b,A,Ac|Sd,|,33,算法：,消除左递归,输入：无环路、无,-,产生式的文法,G,输出：不带有左递归的、与,G,等价的文法,G,方法：,(1),把文法,G,的所有非终结符号按某种顺序排列成,A,1,A,2,A,n,(2)for(i=1;i=n;i+),for(j=1;jn),个状态的,DFA,与之等价。,DFA D,的化简,，指寻找一个状态数比较少的,DFA D,，,使,L(D)=L(D,),。,可以证明，存在一个最少状态的,DFA D,，,使,L(D)=L(D,),，,并且这个,D,是唯一的,。,61,DFA D,的最小化过程,定义：,设,s,t,Q,，,若对任何,*,，,(s,),F,当且仅当,(t,),F,，,则称状态,s,和,t,是等价的。,否则称状态,s,和,t,是可区分的。,DFA D,的最小化过程：,把,D,的状态集合分割成一些互不相交的子集，使每个子集中的任何两个状态是等价的，而任何两个属于不同子集的状态是可区分的。在每个子集中任取一个状态作“代表”，删去该子集中其余的状态，并把射向其它结点的边改为射向,“,代表,”,结点。,如果得到的,DFA,中有死状态、或从初态无法到达的状态，则把它们删除。,62,把状态集合,Q,分割成满足要求的子集,把状态集合,Q,划分成两个子集：终态子集,F,和非终态子集,G,。,对每个子集进行划分：,取某个子集,A=s,1,s,2,s,k,取某个输入符号,a,，,检查,A,中的每个状态对该输入符号的转换。,如果,A,中的状态相对于,a,，,转换到不同子集中的状态，则要对,A,进行划分。使,A,中能够转换到同一子集的状态作为一个新的子集。,重复上述过程，直到每个子集都不能再划分为止,。,63,例：,对状态转换图所描述的,DFA D,最小化,第一步,：把,DFA D,的状态集合划分为子集，使每个子集中的状态相互等价，不同子集中的状态可区分。,A,开始,E,C,B,D,a,b,a,a,b,a,a,b,b,b,把,D,的状态集合划分为两个子集：,A,B,C,D,和,E,考察非终态子集,A,B,C,D,-,对于,a,，,状态,A,B,C,D,都转换到状态,B,，,所以对输入符号,a,而言，该子集不能再划分。,-,对于,b,，,状态,A,B,C,都转换到子集,A,B,C,D,中的状态，而状态,D,则转换到子集,E,中的状态。,-,应把子集,A,B,C,D,划分成两个新的子集,A,B,C,和,D,。,64,D,的状态集合被划分为：,A,B,C,、,D,和,E,考察子集,A,B,C,-,对于,a,，,状态,A,B,C,都转换到状态,B,，,所以对输入符号,a,而言，该子集不能再划分。,-,对于,b,，,状态,A,C,转换到,C,，,状态,B,转换到,D,。,状态,C,和,D,分属于不同的子集。,-,应把子集,A,B,C,划分成两个新的子集,A,C,和,B,。,D,的状态集合被划分为：,A,C,、,B,、,D,和,E,考察子集,A,C,-,对于,a,，,状态,A,C,都转换到状态,B,。,-,对于,b,，,状态,A,C,都转换到状态,C,。,-,该子集不可再划分。,D,的状态集合最终被划分为：,A,C,、,B,、,D,和,E,65,构造最小,DFA D,第二步：,为每个子集选择一个代表状态。,选择,A,为子集,A,C,的代表状态,D,的状态转换图,A,开始,E,D,B,a,b,a,b,b,a,a,b,D,的状态转换矩阵,状态 输入符号,a b,A B A,B B D,D B E,E B A,66,2.3,正规文法与有限自动机的等价性,如果对于某个正规文法,G,和某个有限自动机,M,，有,L(G)=L(M),，,则称,G,和,M,是等价的。,定理：,对每一个右线性文法,G,或左线性文法,G,，,都存在一个等价的有限自动机,M,。,证明：首先考虑右线性正规文法,设给定的一个右线性文法,G,为：,G=(V,T,，,V,N,，,S,，,),与,G,等价的有限自动机,M,为：,M=(,，,Q,，,q,0,，,F,，,),=V,T,，,q,0,=S,，,F=f,，,f,为新增加的一个终态符号，,f,V,N,，,Q=V,N,f,的定义为,：,若文法,G,有产生式,A,a,，,其中,A,V,N,，,a,V,T,，,则,(A,a)=f,。,若文法,G,有产生式,A,aA,1,|aA,2,|,aA,k,，,其中,A,A,i,V,N,(i=1,2,k),a,V,T,，,则,(A,a)=A,1,A,2,A,k,。,67,L(G),的充要条件是,L(M),，,所以,L(G)=L(M),在正规文法,G,中，开始符号,S,推导出,的充分必要条件为：在自动机,M,中，从初态,S,到终态,f,有一条路径，该路径上所有边的标记依次连接起来恰好是,。,现在考虑左线性正规文法,设给定的一个左线性文法,G,为：,G=(V,T,，,V,N,，,S,，,),与,G,等价的有限自动机,M,为：,M,=(,，,Q,，,q,0,，,F,，,),=V,T,，,F=S,，,新增加一个初态符号,q,0,，,q,0,V,N,，,Q=V,N,q,0,的定义为,：,若文法,G,有产生式,A,a,，,其中,A,V,N,，,a,V,T,，,则,(q,0,a)=A,。,若文法,G,有产生式,A,1,AaA,2,Aa,，,，,A,k,Aa,，,其中,A,A,i,V,N,(i=1,2,k),a,V,T,，,则,(A,a)=A,1,A,2,A,k,可以证明,L(G)=L(M,),，,即,有限自动机,M,与左线性文法,G,是等价的。,68,例：,设有右线性文法,G=(a,b,S,B,S,),，,其中,：,S,aB,B,aB|bS|a,试构造与,G,等价的有限自动机,M,。,设,FA M=(,Q,q,0,F,),=a,b q,0,=S F=f Q=S,B,f,转换函数,：,对于产生式,S,aB,，,有,(S,a)=B,对于产生式,B,aB,，,有,(B,a)=B,对于产生式,B,bS,，,有,(B,b)=S,对于产生式,B,a,，,有,(B,a)=f,FA M,的状态转换图：,S,B,f,开始,a,a,a,b,69,定理：,对每一个,DFA M,，,都存在一个等价的右线性文 法,G,和一个等价的左线性文法,G,。,设,DFA M,为：,M=(,，,Q,，,q,0,，,F,，,),构造右线性文法,G,：,G=(V,T,，,V,N,，,S,，,),V,T,=,、,V,N,=Q,、,S=q,0,的,构造：对任何,a,，及,A,、,B,Q,，,若存在,(A,a)=B,，,则：,如果,B,F,，,则有,A,aB,如果,B,F,，,则有,A,aB|a,证明,L(M),=,L(G),首先证明被,DFA M,接受的语言可以由右线性文法,G,产生,对任何,L(M),设,=a,1,a,2,a,n,，,a,i,，,存在,状态序列,：,q,0,q,1,q,n-1,q,q,F,，,有,转换函数,(q,0,a,1,)=q,1,，,(q,1,a,2,)=q,2,，,，,(q,n-1,a,n,)=q,因此在文法,G,中有,产生式,：,q,0,a,1,q,1,q,1,a,2,q,2,q,n-1,a,n,于是有,推导序列,：,q,0,a,1,q,1,a,1,a,2,q,2,a,1,a,2,a,n-1,q,n-1,a,1,a,2,a,n,因此，,a,1,a,2,a,n,是文法,G,生成的一个句子,，即,L(G),，,因此,L(M),L(G),70,再证明由文法,G,产生的语言，能够被,DFA M,所接受。,对任何,L(G),，,设,=a,1,a,2,a,n,，,其中,a,i,V,T,，,必存在,推导序列,：,q,0,a,1,q,1,a,1,a,2,q,2,a,1,a,2,a,n-1,q,n-1,a,1,a,2,a,n,DFA M,中有,转换函数,：,(q,0,a,1,)=q,1,(q,1,a,2,)=q,2,(q,n-1,a,n,)=q,并且,q,F,在,DFA M,中有一条,从,q,0,出发、依次经过状态,q,1,q,2,q,n-1,再到达终态,q,的道路,，路径上有向边的标记依次为,a,1,a2,a,n-1,a,n,，,这些标记依次连接起来恰好是,，所以,被,DFA M,所接受，即,L(M),，,因此,L(G),L(M),。,若,q,0,F,，,则,=,L(M),，,但,L(,G),，,即：,L(G)=L(M)-,进一步,改进文法,G,：,增加一个新的非终结符号,S,，及相应产生式：,S,S|,，,并用,S,代替,S,作为文法的开始符号。,改进后的文法,G,仍是右线性文法，并且满足：,L(M)=L(G),。,推论：,对任何一个有限自动机,M,，,都存在一个等价的,正规文法,G,，,反之亦然。,推论：,对任何一个右线性文法,G,，,都存在一个等价的,左线性文法,G,，反之亦然。,71,例：设有,DFA M=(a,b,q,0,q,1,q,2,q,3,q,0,q,3,),其中转换函数,如下：,(q,0,a)=q,1,(q,1,a)=q,3,(q,2,a)=q,2,(q,0,b)=q,2,(q,1,b)=q,1,(q,2,b)=q,3,试构造与之等价的右线性文法,G,。,DFA M,的状态转换图,q,0,q,1,q,2,q,3,a,a,a,b,b,b,开始,构造右线性文法,G=(V,T,V,N,S,),V,T,=a,b V,N,=q,0,q,1,q,2,q,3,S=q,0,产生式集合,(q,0,a)=q,1,，,q,0,aq,1,(q,0,b)=q,2,，,q,0,bq,2,q,1,a)=q,3,，,q,3,F,，,q,1,a|aq,3,(q,1,b)=q,1,，,q,1,bq,1,(q,2,a)=q,2,，,q,2,aq,2,(q,2,b)=q,3,，,q,3,F,，,q,2,b|bq,3,构造的文法,G,：,G=(a,b,q,0,q,1,q,2,q,0,),：,q,0,aq,0,|bq,2,q,1,a|bq,1,q,2,aq,2,|b,72,2.4,正规表达式与有限自动机的等价性,用正规表达式可以精确地定义集合，,定义,Pascal,语言标识符的正规表达式：,letter(letter|digit),*,定义：,字母表,上的正规表达式,(1),是正规表达式，它表示的语言是,(2),如果,a,，则,a,是正规表达式，它表示的语言是,a,(3),如果,r,和,s,都是正规表达式,分别表示语言,L(r),和,L(s),则：,1)(r)|(s),是正规表达式，表示的语言是,L(r)L(s),2)(r)(s),是正规表达式，表示的语言是,L(r)L(s),3)(r),*,是正规表达式，表示的语言是,(L(r),*,4)(r),是正规表达式，表示的语言是,L(r),正规表达式表示的语言叫做,正规集,。,73,正规表达式的书写约定,一元闭包*具有最高优先级，并且遵从左结合,连接运算的优先级次之，遵从左结合,并运算,|,的优先级最低，遵从左结合,例：,如果,=ab,，,则有：,正规表达式,a|b,表示集合,a,，,b,(a|b)(a|b),表示：,aa,，,ab,，,ba,，,bb,a,*,表示：由,0,个或多个,a,组成的所有符号串的集合,a|a,*,b,表示：,a,和,0,个或多个,a,后跟一个,b,的所有符号串的集合,(a|b),*,表示：由,a,和,b,构成的所有符号串的集合,(a,*,|b,*,),*,如果两个正规表达式,r,和,s,表示同样的语言，即,L(r)=L(s),则称,r,和,s,等价,，写作,r=s,。,如：,(a|b)=(b|a),74,正规表达式遵从的代数定律,定律 说明,r|s=s|r “,并”运算是可交换的,r|(s|t)=(r|s)|t “,并”运算是可结合的,(,rs)t,=,r(st,),连接运算是可结合的,r(s|t)=,rs|rt,(s|t)r=,sr|tr,连接运算对并运算的分配,r=r,，,r,=r,对连接运算而言，,是单位元素,r,*,=(r|,),*,和,之间的关系,r,*,=r,*,是等幂的,r,*,=r,+,|,，,r,+,=,rr,*,+,和*之间的关系,75,定理：,对任何一个正规表达式,r,，,都存在一个,FA M,，,使,L(r)=L(M),，,反之亦然,。,证,1,：设,r,是,上的一个正规表达式，则存在一个具有,-,转移的,NFA M,接受,L(r),。,首先，为正规表达式,r,构造如下图所示的拓广转换图。,i,f,r,然后，按照下面的转换规则，对正规表达式,r,进行分裂、加入新的结点，直到每条边的标记都为基本符号为止。,x,y,r,1,r,2,x,z,r,1,y,r,2,代之以,：,若,r=r,1,r,2,则将：,x,y,r,1,|r,2,x,y,r,2,r,1,代之以,：,若,r=r,1,|r,2,则将：,x,y,r,1,*,x,z,y,r,1,代之以,：,若,r=r,1,*,则将：,76,证,2,：设有,FA M,，,则存在一个正规表达式,r,，,它表示的语言即该,FA M,所识别的语言。,首先，在,FA M,的转换图中增加两个结点,i,和,f,，,并且增加,边，将,i,连接到,M,的所有初态结点，并将,M,的所有终态结点连接到,f,。,形成一个新的与,M,等价的,NFA N,。,然后，反复利用下面的替换规则，逐步消去,N,中的中间结点，直到只剩下结点,i,和,f,为止。,x,y,r,1,r,2,x,z,r,1,y,r,2,代之以,：,x,y,r,1,|r,2,x,y,r,2,r,1,代之以,：,x,y,r,1,*,x,z,y,r,1,代之以,：,77,例：,为正规表达式,(a|b),*,abb,，,构造等价的,NFA,。,构造过程：,0,f,(a|b),*,abb,(a),0,f,(a|b),*,3,1,2,a,b,b,(b),0,f,ab,3,1,2,a,b,b,4,(c),0,f,a,3,1,2,a,b,b,4,b,(d),78,例：,构造与如下的,NFA M,等价的正规表达式,r,。,0,1,3,4,2,5,6,7,a,b,a,a,b,b,a,b,0,1,2,5,6,7,a|b,a|b,aa,bb,0,2,5,7,(a|b),*,(a|b),*,aa|bb,0,7,(a|b),*,(,aa|bb,)(a|b),*,79,2.5,正规表达式与正规文法的等价性,正规表达式与正规文法具有,同样的表达能力,对任何一个正规表达式都可以找到一个正规文法，使这个正规文法所产生的语言（即正规语言）恰好是该正规表达式所表示的语言（即正规集），反之亦然。,正规表达式和正规文法都可以用来描述程序设计语言中单词符号的结构,用正规表达式描述，清晰而简洁；,用正规文法描述，易于识别。,80,正规定义式,定义：令,是字母表，正规定义式是如下形式的定义序列：,d,1,r,1,d,2,r,2,d,n,r,n,其中,d,i,是不同的名字，,r,i,是,d,1,d,2,d,i-1,上的正规表达式。,例：,Pascal,语言的无符号数可用如下的正规表达式来描述：,digit,+,(.digit,+,|,)(E(+|-|,)digit,+,|,),正规定义式：,digit,0|1|9,digits,digit digit,*,optional_fraction,.digits|,optional_exponent,(E(+|-|,)digits)|,num,digits optional_fraction optional_exponent,81,表示的缩写,引入正闭包运算符,+,r,*,=r,+,|,、,r,+,=,rr,*,digits,digit,+,引入可选运算符？,r?=r|,optional_fraction,(.digits)?,optional_exponent,(E(+|-)?digits)?,引入表示,字符组,abc,，,表示正规表达式,a|b|c,digit,0-9,标识符的正规表达式：,A-Za-zA-Za-z09,*,82,正规表达式转换为等价的正规文法,例：,Pascal,语言标识符的正规表达式：,letter(letter|digit),*,引入名字,letter,、,digit,、和,id,正规定义式：,letter,A|B|Z|a|b|z,digit,0|1|9,id,letter,(,letter,|,digit,),*,关键：,如何把正规定义式转换为相应的正规文法,分析：,为子表达式,(letter|digit),*,取一个名字,rid,展开第三个正规定义,83,正规文法,(letter|digit),*,=,|(letter|digit),+,=,|(letter|digit),(letter|digit),*,=,|letter(letter|digit),*,|digit(letter|digit),*,=,|(A|B|Z|a|b|z)(letter|digit),*,|(0|1|9)(letter|digit),*,=,|A(letter|digit),*,|B(letter|digit),*,|Z(letter|digit),*,|a(letter|digit),*,|b(letter|digit),*,|z(letter|digit),*,|0(letter|digit),*,|1(letter|digit),*,|9(letter|digit),*,id,和,rid,看成是文法的非终结符号，产生式：,id,A rid|B rid|Z rid|a rid|b rid|z rid,rid,|A rid|B rid|Z rid|a rid|b rid|z rid|0 rid|1 rid|9 rid,把,letter,和,digit,看作是终结符号，产生式：,id,letter,rid,rid,|,letter,rid,|,digit,rid,84,正规文法的产生式和正规定义式中的正规定义,两个不同的概念，具有不同的含义。,产生式：,左部是一个非终结符号，右部是一个符合特定形式的文法符号串,，,中的非终结符号可以与该产生式左部的非终结符号相同，即允许非终结符号的递归出现。,正规定义：,左部是一个名字，右部是一个正规表达式，表达式中出现的名字是有限制的，即只能是此定义之前已经定义过的名字。,85,小 结,字母表和符号串,前缀、后缀、子串、子序列、真前缀、真后缀、真子串,连接、幂,语言,语言的运算：并、连接、闭包、正闭包,文法,形式定义,G=(V,T,V,N,S,),文法的分类,上下文无关文法（,A,）,正规文法,右线性文法（,A,aB,Aa,）,左线性文法（,A,Ba,Aa,）,86,推导,一步推导、直接推导、推导的长度,最左推导、最右推导、规范推导,句型、左句型、右句型、规范句型,句子,短语,短语、直接短语、句柄,S,A,，,并且,A,*,+,S,A,，,并且,A,*,分析树及二义性,分析树、子树,子树与短语之间的关系,子树,短语,只有父子两代的子树,直接短语,最左边的只有父子两代的子树,句柄,句子二义性、文法的二义性、语言的二义性,87,文法的变换,文法的改写,左递归的消除,简单的直接左递归的消除,间接左递归的消除算法,改写文法为无,-,产生式的文法,提取左公因子,有限自动机,形式定义,M=(,Q,q,0,F,),DFA,：,：,QQ,NFA,：,：,Q2,Q,具有,-,转移的,NFA,：,Q(,)2,Q,自动机之间的等价性,NFA,确定化,具有,-,转移的,NFA,的确定化,88,DFA,的最小化,状态等价、状态可区分,将,DFA,的状态集合划分为等价状态子集,正规文法与有限自动机之间的等价性,为右线性文法构造,DFA,为,DFA,构造右线性文法,正规表达式与有限自动机之间的等价性,为,NFA,构造正规表达式,为正规表达式构造,NFA,正规表达式与正规文法之间的等价性,同等表达能力,利用正规定义式，将正规表达式转换为正规文法,89,