编译原理-西安交通大学2-词法分析-3..ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,编译原理-西安交通大学2_词法分析_3.0,编译原理-西安交通大学2_词法分析_3.0编译原理-西安交通大学2_词法分析_3.0源程序扫描器,scanner1、关键字2、标识符5、界符4、运算符3、常数由程序语言定义的具有固定意义的标识符。也可称为保留字或基本字。例如：Pascal中的begin，end，if等。界符：如逗号、分号、括号、/*，*/等。它是确定的。运算符：如+、-、*、/等。它是确定的。常数的类型一般有整型、实型、布尔型、文字型等。它是不限的。用来表示各种名字，如变量名、数组名、过程名等。它是不限的。,源程序,扫描器,scanner,1,、关键字,词法分析器的,功能,如下图所示：,2,、标识符,5,、界符,4,、运算符,3,、常数,由程序语言定义的具有固定意义的标识符。也可称为保留字或基本字。例如：,Pascal,中的,begin,，,end,，,if,等。,界符：如逗号、分号、括号、,/*,，,*/,等。它是确定的。,运算符：如,+,、,-,、,*,、,/,等。它是确定的。,常数的类型一般有整型、实型、布尔型、文字型等。它是不限的。,用来表示各种名字，如变量名、数组名、过程名等。它是不限的。,2.1对词法分析器的要求,2.1.1词法分析器的功能和输出形式,词法分析器的,功能,：输入源程序，输出单词符号。,单词符号,：一个程序语言的基本语法符号。分为以下,5,种。,1,、,关键字,：由程序语言定义的具有固定意义的标识符。也可称为保留字或基本字。例如：,Pascal,中的,begin,，,end,，,if,等。它是,确定,的。,2,、,标识符,：用来表示各种名字，如变量名、数组名、过程名等。它是,不限,的。,3,、,常数,：常数的类型一般有整型、实型、布尔型、文字型等。它是,不限,的。,4,、,运算符,：如,+,、,-,、,*,、,/,等。它是,确定,的。,5,、,界符,：如逗号、分号、括号、,/*,，,*/,等。它是,确定,的。,确定,不限,单词符号的表示形式,：词法分析器所输出的单词符号常常表示成,二元式（单词种别，单词自身的值）,。,单词种别,可以用以下形式表示：,1,、一类单词统一用一个整数值代表其属性。例如：,1,代表关键字，,2,代表标识符等。,2,、每一个单词一个类别。例如：,1,代表,BEGIN,，,2,代表,END,等。,单词自身的值,可以表示成：常量的二进制表示；常量、变量等在符号表种的地址码，等等。,注意：,一个语言的单词符号如何分种，分几种，怎样编码，是一个技术问题。标识符一般同归为一种。常数则宜按类型（整、实、布尔）分。关键字可以将其全体视为一种，也可,一字一种,。,运算符可采用一符一种，但也可把具有一定共性的视为一种。界符则一般采用,一符一种,。如何进行分种主要取决于处理上的方便。,若是一符一种分种，单词自身值就不需要了。否则，要查符号表。,例,2-1,：,151,FORTRAN,编译程序的词法分析器在扫描输入串,IF(5EQ,M)GOTO 100,后，它输出的,单词符号串,是：,逻辑,IF,（,34,，,_,）,左括号 （,2,，,_,）,整常数 （,20,，,5,的二进制表示）,等号 （,6,，,_,）,标识符 （,26,，,M,）,右括号 （,16,，,_,）,GOTO,（,30,，,_,）,标号 （,19,，,100,的二进制表示）,IF,为关键字，种别编码,34,，采用一符一种的编码方式。,常数类型，种别编码,20,，单词自身的值为,5,的二进制表示。,(,为界符，种别编码,2,，采用一符一种的编码方式。,等号为运算符，种别编码,6,，采用一符一种的编码方式。,M,为标识符，种别编码,26,，单词自身值为,M,。,),为界符，种别编码,16,，采用一符一种的编码方式。,GOTO,为关键字，种别编码,30,，采用一符一种的编码方式。,100,为标号，种别编码,19,，单词内部的值用,100,的二进制表示。,例,2-2,：下述,C+,代码段：,while(i=j)i-,；,经词法分析器处理以后，它将被转换为如下的,单词符号串,(while,，,_),(,，,_),(id,，指向,i,的符号表指针,),(=,，,_),(id,，指向,j,的符号表指针,),(),，,_),(id,，指向,i,的符号表指针,),(-,，,_,),(,；，,_),2.1.2词法分析与语法分析的关系,1,、把词法分析从语法分析中脱离出来的,优点,：,使编译程序的,结构,更加简洁、清晰和条理化。,词法分析和语法分析,方法,不同，词法分析可以使用正则文法自动构造,scanner,简单。,有利于提高语法分析的,效率,。,可以改善词法分析的细节，甚至于一个语法分析配几个,scanner,，把不同的输入变成一种内部表示。,2,、把词法分析作为独立的一,遍,scanner,当作一遍。,把,scanner,当作子程序。,外存,scanner,语法分析,源程序,单词符号,scanner,作为一遍,语法,分析,scanner,源程序,scanner,作为子程序,2.2词法分析器的设计,设计前提,：,把,scanner,作为一个独立的子程序；,词法分析器的任务为输出单词符号。,2.2.1预处理,必要性,：,编辑性字符如空白符、回车符等，除了出现在文字和,常数中以外，在别处出现都没有意义。,功 能,：剔除无用字符。,实 现,：预处理子程序。,输入,列表,预处理,子程序,扫描器,扫描缓冲区,输入缓冲区,单词符号,图,2.1,词法分析器,语法分析器,预处理部分,扫描器,若,识别,输入语句,IF(5.EQ.M)GOTO 100,，若缓冲区情况如下所示：,IF(5.EQ.M)GO,起点指示器,搜索指示器,输入缓冲区,TO 100,IF(5.EQ.M)GO,起点指示器,搜索指示器,输入缓冲区,TO 100,IF(5.EQ.M)GO,起点指示器,搜索指示器,两 个 互 补 输 入 缓 冲 区,120,个字符,扫描缓冲区的,结构,：,缓冲区大小,：,120,个字符。,采用两个,指示器,：起点指示器、搜索指示器。,两个互补区,。,2.2.2单词符号的识别超前搜索,单词符号识别的简单方法：,超前搜索,。,关键字识别,：,例如：在标准,FORTRAN,中,1,、,DO99K,=1,10,2,、,IF,(5.EQ.M)I=10,3,、,DO99K,=1.10,4,、,IF,(5)=55,其中的,DO,、,IF,为关键字,其中的,DO,、,IF,为标识符的一部分,标识符的识别,多数语言的标识符是字母开头的“字母,/,数字”串，而且在程序中标识符的出现后都跟着算符或界符。因此，不难识别。,常数的识别,对于某些语言的常数的识别也需要使用超前搜索。,算符和界符的识别,对于诸如,C+,语言中的“,+”,、“,-”,，这种复合成的算符，需要超前搜索。,2.2.3状态转换图,转换图,：是一张有限方向图。在状态转换图中，,结点,代表,状态,，用圆圈表示。状态之间用,箭弧,连接。箭弧上的,标记（字符）,代表在射出结状态下可能出现的输入字符或字符类。,状态转换图的功能,:,用于识别一定的字符串。,初态,：一张转换图的启动条件，至少有一个,用圆圈表示。,终态,：一张转换图的结束条件，至少有一个，用双圈表示。,*,：表示多读进了一个字符。,X,Y,(a),转换图示例,2,字母,其他,字母或数字,*,（,b,）识别标识符的转换图,其他,2,数字,数字,*,（,c,）识别整数的转换图,例,2-3,：简单的状态转换图示例：,初态,终态,从,0,状态到,1,状态可能出现字母,图,2.2,状态转换图,7,*,数字,数字,数字,数字,E,或,D,+,或,数字,其他,E,或,D,数字,其他,数字,例,2-4,：识别,FORTRAN,实型常数,的转换图：,例如下列实型常数可以被以下转换图识别：,1.23E+4,.56E-7,例,2-5,：综合实例,做出识别下表所示的小语言的,单词符号,的状态转换图,*,2,字母,非字母与数字,字母或数字,*,空白,5,4,数字,数字,非数字,*,6,10,11,13,12,*,8,9,*,非,*,，,（,）,其他,。,右图即为对上页所示的简单语言进行,词法分析,的状态转换图。,2.2.4状态转换图的实现,1,、,CHAR,字符变量，存放最新读进的源程序字符。,2,、,TOKEN,字符数组，存放构成单词的字符串。,3,、,GETCHAR,过程，将下一输入字符读入,CHAR,，搜索指示器前移一个字符。,4,、,GETBC,过程，检查,CHAR,中的字符是否为空白。若是，则调用,GETCHAR,直至,CHAR,中进入一个非空白字符。,5,、,CONCAT,过程，把,CHAR,中的字符连接到,TOKEN,之后。,6,、,LETTER,布尔函数过程，它们分别判断,CHAR,中的字符是数字或是字母，,DIGIT,从而给出真假值,TRUE,、,FALSE,。,7,、,RESERVE,整型函数过程，用,TOKEN,中的字符串查保留字表，若是一个保留,字则给予编码，否则回送,0,值（假定,0,不是保留字的编码）。,8,、,RETRACT,过程，把搜索指示器回调一个字节，把,CHAR,中的字符置为空白。,以上函数和子程序过程都不难编制，使用它们能够方便的构造状态转换图的对应程序。一般，我们可以让每,一个状态结,对应,一个程序段,。,例如：我们可以让不含回路的分叉结，对应一个,CASE,语句，或者是一组,IFTHENELSE,语句。具体见后面实例。,终态结,一般对应一个,RETURN(C,VAL),语句。其中,C,为单词种别编码；,VAL,是字符数组的,TOKEN,，或者是一个整数值，或者无定义。具体见后面实例。,为了把,状态转换图,转化成,程序,，每个,状态,要建立一段,程序,，它要做的工作如下：,第一步,：从输入缓冲区中取一个字符。为此，我们使用函数,GETCHAR,，每次调用它，推进先行指针，送回一个字符。,第二步,：确定在本状态下，哪一条箭弧是用刚刚来的输入字符标识的。如果找到，控制就转到该弧所指向的状态；若找不到，那么寻找该单词的企图就失败了。,失 败,：先行指针必须,重新回到,开始指针处，并用另一状态图来搜索,另一,单词。如果所有的状态转换图都试过之后，还没有匹配的，就表明这是一个词法错误，此时，调用错误校正程序。,GETCHAR,是过程，将下一输入字符读入,CHAR,，搜索指示器前移一个字符。,例,2,6,：以下,CASE,语句段对应的状态图,:,state i,：,GETCHAR,；,CASE,CHAR,OF,A.Z,：,state j,；,0.9,：,state k,；,/,：,state l,；,END,；,FAIL,数字,字母,/,字符变量，存放最新读进的源程序字符。,过程，将下一输入字符读入,CHAR,，搜索指示器前移一个字符。,对于如上的状态转换图，,状态,0,的代码如下所示：,state 0,：,C:=,GETCHAR,;,if,LETTER(C),then goto state 1,else,FAIL(),2,字母,其他,字母或数字,LETTER(),是布尔函数过程，当且仅当,C,中的字符是字母，它返回真假值,TRUE,。,FAIL(),是例子程序，它移回,先行指针,（,lookahead pointer,）,开始下一状态转换图，或调用出错程序。,例,2-7,：示例,如何把,状态结,对应于一段,程序,：,*,对于如上的状态转换图，,状态,1,的代码如下所示：,state 1,：,C:=,GETCHAR,;,if,LETTER(C),or,DIGIT(C),then goto state,1,else if,DELIMITER(C),then goto state 2,else,FAIL(),2,字母,其他,字母或数字,DIGIT(),是布尔函数过程，当且仅当,C,中的字符是数字，它返回真假值,TRUE,。,DELIMITER(C),是过程，只要碰到标识符后的分界符，它返回,TRUE,。,分界符,一般为：空格、算术、逻辑符号，括号、；、,.,、，。,*,对于如上的状态转换图，终态,状态,2,的代码如下所示：,state 2,：,RETRACT(),;,RETURN($id,，,INSTALL(),2,字母,其他,字母或数字,RETRACT(),是过程，由于分界符不属于标识符，所以我们要把先行指针,回调,一个字符。,INSTALL(),是过程，如我们识别出的标识符不在符号表中，我们把它装入,符号表,。我们还要给语法分析程序返回一个,二元式,。,*,如果同时识别,标识符,和,定义符,，,则需要,修改,为,State2,：,修改之后，,状态,2,的代码如下所示：,state 2,：,RETRACT(),;,c:=,RESERVE();,if c=0,then,RETURN($id,，,INSTALL),else,RETURN(C,_),RESERVE(),整型函数过程,针对,TOKEN,中的字符串进行查找，看其是否是,保留字,，是保留字给出它的编码，否则回送,0,（假定,0,不是保留字编码）。,例,2,8,：以下程序段对应的状态图,state i,：,GETCHAR,；,WHILE,LETTER,OR,DIGIT,DO,GETCHAR,；,state j,：,布尔函数过程，它们分别判断,CHAR,中的字符是数字或是字母，从而给出真假值,TRUE,、,FALSE,。,其它,字母或数字,例,2,9,：以下程序段对应的状态图,0 9,：,BEGIN,WHILE,DIGIT,DO,BEGIN,CONCAT,；,GETCHAR,END,；,RETRACT,；,RETURN($INT,DTB),；,END,；,非数字,数字,数字,4,*,RETURN,语句，对应终态结，其中,$INT,为种别编码，,DTB,为一个把十进制转换到二进制的转换函数。它把,TOKEN,中的数字译成,标准二进制码,，并以此为函数值返回。,正规式与正规集的递归定义：,1,、,和,都是,字母表,上的正规式，它们所表示的正规集分别为,和,；,2,、任何,a,，,a,是,上的一个,正规式,，它所表示的,正规集,为,a,；,3,、,正规式 正规集 正规式 正规集,U L(U),（,U,|,V,）,L(U),L(V),V L(V),（,U,V,）,L(U)L(V),(U),*,L(U),*,（闭包）,仅由有限次使用上述三步骤而得到的表达式才是,上的,正规式,。仅由这 些正规式所表示的子集才是,上的,正规集,。,2.3正规表达式与有限自动机,2.3.1正规式与正规集,运算符的优先顺序：先,“,*”,，次,“,”,，最后,“,|”,“,|,”,读做“或”,“,”,读做“连接”,“,*,”,读做“闭包”,*,的子集,U,V,：,积,UV=,|,U,&,V,n,次积,V,n,=VVV V,V,0,=,V,的闭包,V*=V,0,U,V,1,U V,2,U,V,的正则闭包,V,+,=V V*,例,2-11,：令,a,，,b,，下面是,上的,正规式,和相应的,正规集,：,正规式 正规集,ba,*,上所有的以,b,为首，并且后跟任,意多个,a,的字，,b,ba,baa,baaa,a(a|b),*,上所有的以,a,为首的字,(a|b)*(aa|bb)(a|b)*,上所有含有两个连续的,a,或者,b,的字,例,2-10,：令,A,，,B,，,0,，,1,，则：,正规式 正规集,(A|B)(A|B|0|1),*,上“标识符”的全体,(0|1)(0|1),*,上“数”的全体,若两个正规式表示相同的正规集，则认为二者,等价,，记为,U=V,。例如：,b(ab),*,=(ba),*,b,(a|b),*,=(a,*,b,*,),*,令,U,、,V,和,W,均为,正规式,，显而易见，下列,关系,普遍成立：,1,、,U|V=V|U,（交换律）；,2,、,U|(V|W)=(U|V)|W,（结合律）；,3,、,U(VW)=(UV)W,（结合律）；,4,、,U(V|W)=UV|UW,（分配律）,(V|W)U=VU|WU,；,5,、,U=U,=U,。,2.3.2确定有限自动机（DFA）,一个,确定有限自动机（,DFA,）,M,是一个五元式：,M,(S,s,0,F),，其中,1,、,S,是一个有限集，它的每个元素称为一个,状态,2,、,是一个有穷,字母表,，它的每个元素称为一个,输入字符,3,、,是一个从,S,至,S,的单值部分映射。,(s,a)=s,意味着：当现行状态为,S,、输入字符为,a,时，将转换到下一状态,s,。我们称,s,为,s,的一个后继状态。,4,、,s,0,S,是唯一的,初态,5,、,F S,是一个,终态集,（可空）。,显然，一个,DFA,可用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示,(s,a),的值。这个矩阵称为,状态转换矩阵,。,例,2-12,：有,DFA,M=(0,1,2,3,a,b,0,3),其中,为,:,(0,a)=1,(0,b)=2,(1,a)=3,(1,b)=2,(2,a)=1,(2,b)=3,(3,a)=3,(3,b)=3,相应的状态转换矩阵如下表：,一个,DFA,也可用一张（确定的）,状态转换图,来表示。假定,DFA M,含有,m,个状态和,n,个,输入字符,，那么，这个状态转换图含有,m,个,状态结点,，每个结点顶多有,n,条箭弧射出和别的结点相连接，整张图含有一个,初态结点,和若干个（可以为,0,）,终态结点,。,3,图,2.5,状态转换图,a,a,a,a,b,b,b,如下表所示的状态转换矩阵对应的状态转换图如右图：,3,a,a,a,b,b,b,上图所示的状态转换图的,S,、,及,*,如下：,S=0,1,2,3,=a,b,*,=|,为,，或者,为,a,、,b,的任意组合,从初态,0,到终态,3,有如图所示的通路，箭弧上到标记符连接起来的字,aa,属于,*,，所以右图所示的,DFA,可以识别字,aa,。,同理：从初态,0,到终态,3,还有如图所示的通路，箭弧上到标记符连接起来的字,bba,属于,*,，所以右图所示的,DFA,可以识别字,bba,。,a,例,2-13,：科学表示法中数字常量的,正则表达式,对应的,DFA,：,digit,digit,nat,对应的,DFA,如下图,digit=0-9,nat=digit,+,signedNat=(+|-)?nat,number=signedNat(“”nat),？,signedNat,对应的,DFA,如下图,加上可选的小数部分，,数字常量的,正则表达式,number=signedNat(“”nat),？,对应的,DFA,如下图：,+,digit,digit,digit,-,+,digit,digit,digit,-,digit,digit,a,b,b,b,接受与,正则式,ab+|ab*|b*,相同的语言的,DFA,如下所示：,例,2-14,：串中,只有一个,b,被如下所示的,DFA,接受,：,b,not b,not b,例,2-15,：包含,最多一个,b,的串被如下所示的,DFA,接受：,b,not b,not b,注意二者之,间的区别,定理,：如果一个,DFA M,的,输入字母表,为,，则我们也称,M,是,上的一个,DFA,。可以证明,:,上的一个字集,V,*,是正规的，当且仅当存在,上的,DFA M,，使得,V=L(M),。,DFA,的,确定性,表现在映射,：,SS,是一个,单值函数,。即：对于任何状态,sS,和输入符号,a,，,(s,a),唯一确定了一个状态。,从转换图角度，我们也可以得到答案。,如果允许是一个,多值函数,，我们就得到下一节要讲到的,非确定自动机,的概念。,2.3.3非确定有限自动机（NFA）,一个,非确定有限自动机（,NFA,）,M,是一个五元式：,M,(S,S,0,F),，其中,1,、,S,是一个有限集，它的每个元素称为一个,状态,2,、,是一个,有穷,字母表,，它的每个元素称为一个,输入字符,3,、,是一个从,S,*,至,S,的子集的映射，即,：,S,*,2,s,4,、,S,0,S,是唯一的,初态,5,、,F,S,是一个,终态集,（可空）。,一个含有,m,个状态和,n,个输入字符的,NFA,可用一张如下的状态转换图来表示：该图含有,m,个状态结点，每个结点可以射出若干条弧与别的结点相连接，,每条弧用,*,中的一个字（可以是不同的字，也可以是空字）做标记,，整张图至少含有一个初态结点和若干个（可以为,0,）终态结点。某些结点既可以是初态结点也可以是终态结点。,1,aa,a,b,2,bb,ab,a,b,0,ab,ba,aa,bb,ab,ba,aa,bb,y,a,a,a,a,b,b,b,b,下图所示的状态转换图的,S,、,及,*,如下：,S=0,1,2,3,=a,b,*,=|,为,，或者,为,a,、,b,的任意组合,对于,*,中的任何一个字,，若存在一条从某一初态结点到某一终态结点的通路，且这条通路上所有弧上的标记字依序连接成的字（忽略,）等于,，则称,可以为,NFA M,识别,。,从初态,x,到终态,y,的连接通路弧上，有如下标记字：,a a ,，去除,，为,aa,，所以字,aa,可为,NFA,接受。,4,a,a,b,例,2-16,：上图所示的,NFA,的以下两个转换序列都可以接受串,abb,：,允许接受,ab,允许接受与,ab*,匹配的字符串,允许接受与,b*,匹配的字符串,允许接受与,ab,+,匹配的字符串,由此，我们可以看出这个,NFA,接受与正则式,ab,+,|ab,*,|b,*,相同的语言！,接受,ab,接受,ab,接受,ab,接受,ab,接受,ab,接受,ab,*,接受,ab,接受,ab,接受,ab,*,接受,b,*,练习：考虑以下,NFA,通过怎样的转换,接受串,acab,：,10,a,b,c,DFA,是,NFA,的特例,，可以采用,子集法,将,NFA,确定化。,假定,I,是,NFA M,的状态集,(S),的一个,子集,，我们定义,_CLOSURE(I),为：,1,、若,s,I,，,则,s,_CLOSURE,(I),；,2,、若,sI,，那么从,s,出发经过,任意,条,弧,而能到达的,任何状态,s,都属于,_CLOSURE(I),。,状态集,_CLOSURE(I),称为,I,的,_,闭包,。,_CLOSURE(I)的定义,假定,I,是,NFA M,的状态集的,子集,，,a(a,是输入字符,),定义,Ia,=,_CLOSURE(J),其中，,J,是那些可从,I,中的某一状态结点出发,经过一条,a,弧,而,到达的状态结点的全体。,Ia定义,=a1,a2,.ak,。先,构造一张表,，该表每一行含有,k+1,列。置该表的,首行首列为,_CLOSURE(X),。,重复上述过程，直至所有,第二列,和,第三列,的,子集,均已在,第一列,上出现了为止。,如果某一行的第一列的状态子集已经确定，例如记为,I,那么，求出这一行的第二个和第三个子集,I,a,和,I,b,看它们是否已 在表的第一列出现，将未出现的,填入,到后面空行的第一列。,1,表的,初始化,构造,2,处理表的,一行,3,重复处理,子集算法,例,2-17,：考虑下图所示,NFA,的,确定化,：,y,a,a,a,a,b,b,b,b,I=,_CLOSUREX,为,X,5,1,。,从状态,I,出发经过一条,a,弧而能到达的状态全体,J,为,5,3,而,_CLOSURE(J)=5,3,1,。从而,Ia=5,3,1,。,初态,_,闭包,X,5,1,Ja,为,5,3,_CLOSURE(J),为,5,3,，,1,（根据,_,闭包的定义）,根据此方法依次求出左边表中的状态转换矩阵即可。,对右下图表中的所有,子集,重新命名，得到左图中的状态转换矩阵形成如下状态转换矩阵，从而得到相应的,DFA,。如图所示：,3,a,a,a,a,b,b,b,5,4,6,a,b,b,a,b,重命名为状态,0,重命名为状态,1,根据重命名的状态填写表格,a,b,例,2-18,：考虑下图所示,NFA,的确定化：,1,在,letter,上有到,2,的转换,：,2=2,，,3,，,4,，,5,，,7,，,10,2,3,4,5,7,10,letter,在,letter,上有到,6,的转换,：,6=4,，,5,，,6,，,7,，,9,，,10,4,5,6,，,7,9,，,10,letter,在,digit,上有到,8,的转换,：,8=4,，,5,，,7,，,8,，,9,，,10,4,5,7,，,8,9,，,10,digit,letter,digit,digit,letter,注意：所有这些状态都有在,letter,和,digit,上的转换。,上图所示,NFA,的确定化后的,DFA,如下：,子集构造过程如下：,初始状态,：,1=1,10,letter,letter,digit,2.3.4正规文法与有限自动机的等价性,对于,正规文法,G,和,有限自动机,M,，如果,L(G)=L(M),则称,G,和,M,是,等价,的。,关于正规文法和有限自动机的,等价性,，有以下结论：,1,、对于每一个,正规文法,G,，都存 在一个有限自动机,M,，使得,L(M)=L(G),。,2,、对于每一个,有限自动机,M,，都存在一个正规文法,G,使得,L(G)=L(M),。,2.3.5正规式与有限自动机的等价性,关于,正规式,和,有限自动机,的,等价性,，有以下结论：,1,、对于任何有限自动机,M,，都存在一个正规式,r,，使得,L(r),（正规式所表示的集合）,=L(M),。,2,、对于任何,正规式,r,都存在一个有限自动机,M,使得,L(M)=L(r),。,替换规则,：用于证明结论：对于任何有限自动机,M,，都存在一个正规式,r,，使得,L(r)=L(M,）。,V,1,V,2,V,1,V,2,代之以,V,1,V,2,V,1,|,V,2,（自动机）代之以（,正规式是或,）,V,1,V,3,V,2,V,1,V,2,*,V,3,代之以,2.3.6确定有限自动机的化简,一个,确定有限自动机,M,的化简是指：,寻找一个,状态数,比,M,少的,DFA M,，使得,L(M)=L(M),。,一个,DFA M,的,状态最少化,过程旨在将,M,的状态集分割成一些,不相交的子集,，使得任何不同的两个子集中的状态都是可区别的，而同一子集中的任何两个状态都是等价的。最后，在每个子集中选出一个代表，同时,消去,其它等价状态。,3,a,a,a,a,b,b,b,5,4,6,a,b,b,a,b,a,b,例,2-19,：考虑下图所示,DFA,的化简：,首先：把,M,的状态分为,2,组：,终态组,3,4,5,6,非终态组,0,，,1,，,2,其次：考察,3,4,5,6,由于,3,4,5,6a,和,3,4,5,6b,都包含于,3,4,5,6,所以它不能在划分。,再考察,0,，,1,，,2,由于,0,，,1,，,2a,1,，,3,，它既不包含于,3,4,5,6,也不包含在,0,，,1,，,2,中，因此，它要划分，由于状态,1,经,a,弧到达状态,3,，而状态,0,、,2,经,a,弧到达状态,1,，因此，应该把,1,分出来，形成,1,、,0,2,。,再考察,0,，,2,由于,0,，,2b,2,，,5,，它没有包括在上述三组中，因此，它要划分，形成,0,、,2,。,划分的组为：3,4,5,6,0，1，2,划分的组为：,3,4,5,6,1,0,2,划分的组为：,3,4,5,6,1,0,2,至此，整个划分有,4,组：,3,4,5,6,1,0,2,。每个组都不可再划分。最后令状态,3,代表,3,，,4,，,5,，,6,，把原来到达,4,、,5,、,6,状态得弧都导入,3,，并删除,4,、,5,、,6,，这样就得到了下图,化简以后的,DFA,：,3,a,a,a,b,b,b,a,谢谢！,