第三章词法分析及有穷自动机课件.ppt

第三章词法分析及有穷自动机第1页，此课件共127页哦第三章词法分析及有穷自动机 主主 要要 内内 容容 词法分析程序的设计过程。词法分析程序的设计过程。描述单词的文法：正规文法和描述单词的文法：正规文法和 正规式及它们之间的转正规式及它们之间的转换。换。单词识别机制（有穷自动机）。单词识别机制（有穷自动机）。正规式，正规文法和有穷自动机三者之间相互转换。正规式，正规文法和有穷自动机三者之间相互转换。第2页，此课件共127页哦1.词法分析程序的任务词法分析程序的任务一、词法分析程序的任务及处理方式一、词法分析程序的任务及处理方式 1.词法分析程序的任务词法分析程序的任务主要任务：从左至右逐个字符地对源程序进行扫描，产生一个个单词序列，用以语法分析。词法分析程序（扫描程序）：执行词法分析的程序。第3页，此课件共127页哦2.词法分析程序的处理方式词法分析程序的处理方式词法分析程序与语法分析程序接口方式有两种：v第一种方式：将词法分析作为单独一遍扫描，即在语法分析之前，实现源程序的词法分析工作。其输出（单词串）形成一个中间文件（内部形式的源程序表），然后移交给语法分析程序。第4页，此课件共127页哦v第二种方式：将词法分析程序编写成一个子程序，每当语法分析程序需要读一个新单词时，便去调用它。注：后一种方式比较好。因为不需要在内存中构造和保存中间文件。第5页，此课件共127页哦二、词法分析程序的二、词法分析程序的I/O 1.输入输入字符串表示的源程序 2.输出输出单词符号序列或单词符号。1)程序语言的单词符号程序语言的单词符号单词：指语言中具有独立意义的最小语法单位。语言中的单词符号：一般可归结为五种：v保留字（基本字）：如if,for,and等个数确定v标识符：表示常量、变量、类型、过程等名称个数不确定v常数：如34，-0.37等个数不确定v运算符：如+，-，*，/，等个数确定v界线符：如逗号，分号，括号等个数确定第6页，此课件共127页哦注：保留字，运算符，界线符可列表，供词法分析程序查询；保留字，运算符，界线符可列表，供词法分析程序查询；标识符和常数可用正规文法或正规式描述，供词法分析程序标识符和常数可用正规文法或正规式描述，供词法分析程序识别。识别。2)输出的单词形式输出的单词形式v二元组：（单词的种别码，单词自身值）1o 单词的种别码：表示单词的种类单词的种别码：表示单词的种类v分类的原则：处理简单v分类的方法：使每一个单词对应一个整数码v分类的目的：最大限度地区别各个单词单词地分类法有多种：v一种一类v一字一类或一符一类第7页，此课件共127页哦具体：具体：保留字：一字一种。如：if1then2。标识符：统归一种。常数：整数，实数，布尔v统为一种v或按类型分整数11实数12布尔13或全体一种第8页，此课件共127页哦+29:=17=21-14 18=22*15 23/16，1thenb:=10表示为一种一类的单词输出形式。第10页，此课件共127页哦if a1 then b:=10词法分析器=(1,if )(字符串表示的源程序)(2,a ),(4,)(3,1 的二进制数)(1,then )(2,b )(4,:=)(3,10 的二进制数)第11页，此课件共127页哦v例：采用一字一类或一符一类地分类技术，则保留字单词自身值可无，但事先构造一个保留字单词对照表，其值可在词表中查到。if a1 then b:=10词法分析器=(1,)字符串表示的源程序(10,a)(23,)(3,1的二进制数)(2,)(10,b)(17,)(11,10 的二进制数)上面符号表示要查保留词表第12页，此课件共127页哦表2.1保留字单词表单词类别码单词类别码.If1+29Then2-14else3*15./16.23for19:=17.第13页，此课件共127页哦2.词法分析程序的设计过程词法分析程序的设计过程一、词法分析程序的设计过程一、词法分析程序的设计过程v设计过程：v词法分析程序设计过程：词法分析程序设计过程：把有的单词（如：标识符和常数标识符和常数）用正规文法或正规式描述；将正规文法或正规式转换成等价的状态转换图（最小化的DFA图）；根据状态转换图设计词法分析程序（状态转换图可视为词法分析程序的框图）。转换规则转换规则分裂法分裂法子集法子集法状态转换图（DFA图）第14页，此课件共127页哦二、用状态转换图设计词法分析程序二、用状态转换图设计词法分析程序1.词法分析程序的预处理词法分析程序在识别单词前，需要对输入到缓冲区的源程序进行预处理。预处理：删去无用的空格，跳格，回车和换行等编辑性字符；删去注释部分每次对一串定长（如120个字符）的输入字符进行预处理，并装入一个指定的扫描缓冲区中。第15页，此课件共127页哦v扫描缓冲区是一个一分为二的区域，每一个区域可容纳120个字符，且相互交替使用。v搜索指针从单词起点开始搜索，如果遇到半区的边界但尚未达到单词的终点时，则可将后续的120个输入字符装进缓冲区的另一半中。第16页，此课件共127页哦2.状态转换图状态转换图v状态转换图是为了识别正规文法或正规式而专门设计的有向图。他是有穷自动机的非形式化表示。v状态转换图的组成状态转换图的组成：1o 有限个状态结点有限个状态结点状态结点代表正规文法的非终结符（用单圈表示）；开始状态结点：用双箭头指示；终止状态结点：用双圈表示。2o 弧线弧线弧上的标记弧上的标记x指明在射出弧的结点状态下可能出现指明在射出弧的结点状态下可能出现的输入字符或字符类的输入字符或字符类,即终结符。即终结符。(表示机器的识别方向表示机器的识别方向).大多数单词结构是用正规文法描述的大多数单词结构是用正规文法描述的x第17页，此课件共127页哦例：=|=|=+|-|*|/|.=；|，|(|)|.。3.由正规文法构造状态转换图由正规文法构造状态转换图1)左线性正规文法构造状态转换图左线性正规文法的一般形式：U=a|wa第18页，此课件共127页哦左线性正规文法构造状态转换图的步骤如下：增加一个开始状态结点s（假定文法的词汇表中不含s）；以每个非终结符为状态作结点；对于形如U=a的每一个规则，引一条从开始状态s到状态U的弧，弧上标记为a；对于形如U=wa的每一个规则，引一条从状态w到状态U的弧，弧上标记为a；以识别符号为终止状态。第19页，此课件共127页哦例：设有正规文法GZ：Z=U0|V1U=Z1|1V=Z0|0（描述的语言为L(G)=01,10）则状态转换图如下：以开始符号以开始符号Z 作终态作终态新增加开始新增加开始状态状态S第20页，此课件共127页哦例：标识符的转换图：从开始状态出发到某一终止状态结点为止，所经过的路径上的符号串，称能为该状态转换图所接收（识别）的符号串。如：标识符x26为上述转换图识别，识别路径为第21页，此课件共127页哦2)右线性正规文法构造状态转换图右线性正规文法U=a|aV构造状态转换图的步骤：增加一个终止状态结点z（假定文法的词汇表中不含z）；以每个非终结符为状态作结点；v对于形如U=a的每一个规则，引一条从开始状态U到终止状态z的弧，弧上标记为a；v对于形如U=aV的每一个规则，引一条从状态U到状态V的弧，弧上标记为a；以识别符号为开始状态。第22页，此课件共127页哦根据状态转换图设计词法分析程序根据状态转换图设计词法分析程序状态转换图实际上是编写词法分析程序的框图根据状态转换图写出相应的词法分析程序的方法：1o对于每个状态构造一小段程序。对于每个状态构造一小段程序。功能：从输入串中读一个字符；判明读入字符与由此状态出发的哪条弧上的标记匹配，便转至相匹配的那条弧所指的状态；均不匹配时便失败（不能达到正常出口）第23页，此课件共127页哦2o 再根据图形决定小段程序之间的调用。再根据图形决定小段程序之间的调用。注：词法分析程序除了识别单词外，还可为语法程序提供更多的信息。因此，可在这些小段程序中加上一些语义处理（如对数值进行10=2等）例：设有关于单词的文法G=(VN,VT,P,N1)其中，VN=N1,N2,N3,N4,N5,N6,N7VT=d,e,f,P：N1=dN2|N3|eN5N2=dN2|N3|eN5|N3=dN4这里d表示数字（09）；e10；f；表示空字符；N1表示无符号数，其一般形式为：ddddefddN4=dN4|eN5|N5=dN7|fN6N6=dN7N7=dN7|第24页，此课件共127页哦v试构造识别此单词的词法分析程序1 根据右线性正规文法，画出状态转换图根据右线性正规文法，画出状态转换图N1=3N2=34N2=34N3=345N4=3456N4=3456(达到出口),自上而下的推导过程。自上而下的推导过程。第25页，此课件共127页哦2根据状态转换图写词法分析程序为每一个状态结点写一个过程或函数：对N1结点：ProcedurePN1BeginCh:=getchar();Ifch=”e”thenPN5Elseifch=”d”thenPN2Elseifch=”thenPN3ElseerrorEnd;第26页，此课件共127页哦对N2结点：ProcedurePN2BeginCh:=getchar();Ifch=”e”thenPN5Elseifch=”d”thenPN2Elseifch=”thenPN3Elsereturn;End;对N3,N4,N5,N6,N7结点分别写出程序段：第27页，此课件共127页哦3 正规式与有穷自动机正规式与有穷自动机v为了进一步讨论词法分析程序的自动生成，需要将状态转换图的概念加以形式化；同时将由正规文法描述的单词由正规式描述，可利用有穷自动机生成词法分析程序。一、正规式与正规集一、正规式与正规集语言的单词结构不仅由正规文法描述，还可以由正规式描述。第28页，此课件共127页哦例：=|此正规文法描述了一个语言的集合。定义在字母，数字上的以字母开头的符号串的集合。这个集合还可以用正规式描述：字母(字母|数字)*。v正规式描述的字符串的集合称为正规集1正规式（也称正则式，正则表达式）和正规集的递正规式（也称正则式，正则表达式）和正规集的递归定义归定义设有字母表=a1,a2,an,那么(1),ai都是上的正规式，它们所描述的正规集分别为，ai；第29页，此课件共127页哦(2)若e1和e2都是上的正规式，它们所描述的正规集L(e1)、L(e2)，则：1o正规式的“或”（|）运算：e1|e2也是正规式，相应正规集为L(e1|e2)=L(e1)L(e2)；2o正规式的“连接”（.）运算：e1e2也是正规式，相应正规集为L(e1e2)=L(e1)L(e2)；3o正规式的“闭包”（*）运算:(e1)*也是正规式，相应正规集为L(e1)*)=(L(e1)*；(3)仅由有限次使用(1),(2)定义的表达式才是上的正规式，由这些正规式所表示的字符集才是上的正规集。第30页，此课件共127页哦例：设=a,b，则上的正规式和正规集有正规式正规集1o a和baL(a)=a和L(b)=bL(a)=L(a)L(a)L(a)=a=a,aa,.基本3 oa|bL(a|b)=L(a)L(b)=a,b4 oabL(ab)=L(a)L(b)=ab5 oa*L(a*)=(L(a)*=L(a)L(a)L(a).=a*=,a,aa,aaa,.复合6 oba*L(ba*)=L(b)L(a*)=b,ba,baa,baaa,7 oa|ba*L(a|ba*)=L(a)L(ba*)=a,b,ba,baa,8 o(a|b)*L(a|b)*)=(L(a|b)*=a,b*=,a,b,aa,ab,所有ab组成的串9 oa(a|b)*L(a(a|b)*)=L(a)(L(a)L(b)*=aa,b*10 o(a|b)*(aa|bb)(a|b)*L(a|b)*(aa|bb)(a|b)*)=a,b*aa,bba,b*012+123+2o第31页，此课件共127页哦 注：注：.正规式仅由字母正规式仅由字母中的终结符号，通过或，连接和闭包中的终结符号，通过或，连接和闭包三种运算组成的式子。三种运算组成的式子。例：有字母表例：有字母表=a，b，下面正规式，求正规集。，下面正规式，求正规集。ba*正规集：正规集：b开头后面跟开头后面跟0个或若干个个或若干个a。a(a|b)*正规集：正规集：a开头后面跟开头后面跟0个或个或a、b任意排列。任意排列。例：有字母表例：有字母表=a，b，下面用自然语言描述的正规集，求正，下面用自然语言描述的正规集，求正规式规式(可能不唯一可能不唯一)。以以ab结尾的所有字符串。结尾的所有字符串。(a|b)*ab 包含偶数个包含偶数个b的所有字符串。的所有字符串。(bb)*只包含一个只包含一个a的所有字符串。的所有字符串。b*ab*不包含不包含ab子串的所有字符串。子串的所有字符串。b*a*以以a开头开头b结尾的所有字符串。结尾的所有字符串。a(a|b)*b第32页，此课件共127页哦正规式的性质（1）正规式的等价性定义：若正规式e1与e2描述的正规集相同，即L(e1)=L(e2)，则e1与e2等价，记做e1=e2。（2）正规式的代数性质设r,s,t为正规式，正规式服从的代数规律有：1or|s=s|r“或”满足交换律2or|(s|t)=(r|s)|t“或”满足结合律3o(rs)t=r(st)“连接”满足结合律。“连接”不满足交换律4or(s|t)=rs|rt(s|t)r=sr|tr“连接”满足分配律5or=rr=r是“连接”的恒等元素第33页，此课件共127页哦(3)正规式的恒等式设A和B式正规式，有例：证明：A*=|AA*成立。证明:利用对应的正规集来证明：L(AA*|)=L(A)L(A*)UL()=L(A)L(A)*UL()=L(A)(L(A)UL(A)U(L(A).)UL()=L()U(L(A)U(L(A)U(L(A).)=(L(A)*)=L(A*)A*=AA*|例：设=d,e,+,-则上的正规式：d*(dd*|)(e(+|-|)dd*|)表示无符号数：2.12,3.6e-2等。表示无符号数的正规式，比表示无符号数的正规文法显得直观，简洁。表示无符号数的正规式，比表示无符号数的正规文法显得直观，简洁。1o（A*）*=A*2 oA|BA=(|B)A3 oA A*=A*A；A=AA*4 oA*=|A A*;A*=(A|)*012312+第34页，此课件共127页哦3正规文法与正规式的转换正规文法与正规式的转换关系：对任意一个正规文法存在定义同一语言的正规式反之：对于每一个正规式，存在一个生成同一语言的正规文法。两者之间具有等价的转换关系。有的语言容易用正规文法定义，有的语言则更容易用正规式定义转换：1o 正规式正规式-正规文法正规文法将上的一个正规式转换成正规文法G=(VN,VT,S,P)：v首先：令VT=第35页，此课件共127页哦v再确定产生式P和VN，其方法：对任何正规式r，选择非终结符S生成产生式S=r，并将S定义为G的识别符号。若r含有正规式x,y,对形如A=xy（连接的变换）产生式，用A=xB,B=y两个产生式替换。其中B是新选择的非终结符。对已经转换成文法中的形如：A=x*y（闭包和连接的变换）的产生式，则重写为：A=xA注：若y是则，AxAA=yA对形如：A=x|y（或的变换）的产生式，重写为A=x,A=y不断利用上述规则作变换，直到每个产生式右部最多含有一个终结符为止。第36页，此课件共127页哦例：将正规式R=a(a|d)*转换成相应的正规文法。解：令S是文法的识别符号，则首先形成：S=a(a|d)*然后形成：S=aA,A=(a|d)*(其中AVN)对于A=(a|d)*重写为：A=(a|d)AA=对于A=(a|d)A重写成：A=aA,A=dA最后转换的等价正规文法G=(VN,VT,S,P)VT=a,dVN=S,AP:S=aAA=aA|dA|第37页，此课件共127页哦2o正规文法正规文法正规式正规式基本是上述的逆过程。最后只剩下一个识别符号定义的产生式，且产生式的右部不含非终结符。其转换规则如下表：规则文法产生式正规式1A=xB,B=yA=xy2A=xA|yA=x*y3A=x,A=yA=x|y注：注：正规文法与正规式互相转换，关键式：正规文法与正规式互相转换，关键式：AxA|y A=x*y第38页，此课件共127页哦例：正规文法Gs：S=aAS=aA=aAA=dAA=aA=d求正规式解：先有：SaA|a规则3A=(aA|dA)|(a|d)规则3再将A的正则式变成：A=(a|d)A|(a|d)“或”分配律根据规则2变成：A=(a|d)*(a|d)再代入S的右部得：S=a(a|d)*(a|d)|a再利用正则式代数变换：S=a(a|d)*(a|d)|)S=a(a|d)*即：a(a|d)*为所求的正则式第39页，此课件共127页哦简便转换方法是:(1)将正规文法中的每一个非终结符表示成关于它的一个正规方程,获得一个联立方程组.(2)依据求解规则:v若x=x|,写成方程x=x+(“|”用“+”表示);则解为x=*.v若x=x|,写成方程x=x+(“|”用“+”表示);则解为x=*.以及正规式的分配律,交换律和结合律求关于文法识别符号的正规式方程组的解.此解就是关于文法识别符号S的一个正规式.例如,上例:先写出正规式方程组(方程组中用“+”代替“|”):S=aA|a写成:S=aA+a（1）A=aA|dA|a|d写成:A=aA+dA+a+d（2）将（2）式简化为：A=(a+d)A+(a+d)使用求解规则：A=(a|d)*(a|d)（3）将（3)的A代入（1)式：S=a(a|d)*(a|d)|a=a(a|d)*(a|d)|)a(a|d)*(a|d)|)=a(a|d)*即为所求的正规式。第40页，此课件共127页哦 例：设有正规文法例：设有正规文法G:Z=0AA=0A|0BB=1A|试给出该文法的正规式。试给出该文法的正规式。解：给出相应的正规式方程组：解：给出相应的正规式方程组：Z=0A（1）A=0A+0B（2）B=1A+（3）（3）代入（）代入（2）中的）中的B得：得：A=0A+01A+0=(0+01)A+0使用求解规则：使用求解规则：A=(0|01)*0（4）（4）代入（）代入（1）式中的）式中的A得：得：Z=0(0|01)*0所以，所以，0(0|01)*0 即为所求的正规式。即为所求的正规式。例：设有正规文法例：设有正规文法G:P:A:=aB|bB,B:=aC|a|b,C:=aB相应的正规式方程：相应的正规式方程：A=aB+bB （1）B=aC+a+b (2)C=aB .(3)(3)代入代入(2)中的中的C:B=aaB+a+b .(4)第41页，此课件共127页哦 对(4)式使用求解规则：B=(aa)*(a|b).(5)将（5）代入(1)式中的B：A=(a|b)(aa)*(a|b)(a|b)(aa)*(a|b)即为所求。二、有穷自动机二、有穷自动机(FA)自动机：是一种能进行运算，并能实现自我控制的装置。装有程序的计算机也具有运算和自我控制能力，因此计算机是一部自动机所谓有穷自动机：自动机受囿于它能存储的信息量，因此是有限的（有穷的）自动机是识别符号串处理的强有力的工具，因而它成为研究词法分析器的重要基础。有穷自动机分为：确定的有穷自动机（DFA）非确定的有穷自动机（NFA）第42页，此课件共127页哦确定的有穷自动机（确定的有穷自动机（DFA）(1)DFA的形式定义：的形式定义：一个DFAM是一个五元组：M=(S,f,S0,F)其中：S：非空有穷的状态集：每个元素是一个状态。：有穷输入字母表；每个元素是输入的一个字符。f：状态转换函数：是从SS的单值映射函数：f(S1,a)=S2S0S是唯一的开始状态FS是终止状态集，可空（识别不出的字符串）例：设有DFAM=(0,1,2,3,a,b,f,0,3)其中：f：f(0,a)=1f(0,b)=2DFA的函数式表示的函数式表示f(1,a)=3f(1,b)=2f(2,a)=1f(2,b)=3f(3,a)=3f(3,b)=3第43页，此课件共127页哦(2)DFA的状态图表示：开始状态为0，终止状态为3，状态集为0,1,2,3，字母表为：a,b一般：假定DFAM含有m个状态，n个输入字符，则状态图含有m个结点，每个结点最多有n条弧射出。第44页，此课件共127页哦(3)DFA的矩阵表示：矩阵的行表示状态，列表示输入字符，矩阵中的元素表示相应状态行和输入字符列下的新状态。即K行a列为f(K,a)的值。DFA的功能：的功能：对于*中的任何字符串,若存在一条从开始结点到某一终态结点的道路，其路上所有弧的标记符连成的字符串等于，则称能为DFA所识别（接受）。特别：若DFA的开始态结点同时又是终态结点，则空串可为DFA所识别。状态字符ab012132213333第45页，此课件共127页哦注：DFA有3种表示法：函数表示，状态图表示，状态矩阵表示。DFA的确定性表现在转换函数f:SS是一个单值函数。即：对于任何状态sS，和输入符号a,f(s,a)能唯一确定下一个状态。可以证明：若存在一个正规文法G，G产生的语言L（G）,当且仅当存在一个上的确定有穷自动机M，使得L（G）L（M）。即：正规文法G在上描述的语言，一定存在DFA能够识别这个语言。反之：若存在一个被DFA识别的语言，一定由存在的正规文法所描述。由于DFA能识别正规文法描述的单词，因此要想构造识别单词的词法分析程序，也就成为怎样构造DFA的问题了。第46页，此课件共127页哦2.非确定的有穷自动机（非确定的有穷自动机（NFA）(1)定义：一个NFA也是一个五元组：M（S，f，S0，F）其中：S，F同DFAS0S是一个非空开始状态集f：是一个多值的转换函数：SS的子集映射NFA与DFA的区别：NFA有一个开始状态集，而DFA只有一个开始状态；NFA转换函数是多值函数，DFA的转换函数是单值函数。第47页，此课件共127页哦例：设有NFAM（S,f,S0,F）其中，S=q0,q1,q2,q3,=x,y,S0=q0,F=q1f:f(q0,x)=q1,q2f(q0,y)=q0f(q1,x)=q0f(q1,y)=q1,q2f(q2,x)=q3f(q2,y)=q3f(q3,x)=q1,q3f(q3,y)=q3NFAM的状态图表示：第48页，此课件共127页哦状态字符xyq0 q1,q2 q0q1 q0 q1,q2q2 q3 q3q3 q1,q3 q3NFAM的矩阵表示：v注：DFA是NFA的特例；对于每个NFAM，存在一个DFAM,使得L(M)=L(M)对于任何两个有穷自动机M和M，若L(M)=L(M)，则称M与M等价。第49页，此课件共127页哦三、由正规式构造三、由正规式构造NFA或将或将NFA转换成正规式转换成正规式理论依据理论依据定理：正规式与有穷自动机是等价的。o上的NFAM，可以构造上的正规式R，使：L(M)=L(R)o 在上的每个正规式R，可以构造上的NFAM使：L(R)=L(M)注：由正规式（或正规文法）构造有穷自动机的意义在于：将单词的描述结构转换为对单词的识别结构。第50页，此课件共127页哦由正规式构造NFA方法：分裂法分裂法输入：输入：上的正规式R输出：输出：识别R的NFA步骤：1o 引进一个开始状态结点x和终止状态结点y：第51页，此课件共127页哦2o 若R为复合公式，分裂R直到每条边上只留下一个符号（可以为）为止；3o分裂的结果：保证一个唯一的开始状态结点和终止状态结点。第52页，此课件共127页哦例：设=x,y上的正规式e=xy*(xy|yx)x*,构造一个NFAM，使得L(M)=L(e)解:第53页，此课件共127页哦例：已知正则式e=0(1*)*|01，求：NFA(A*)*=A*(A|A*=A*)e=0(1*)*|01（利用恒式化简，然后构造NFA）=01*|01=0(1*|1)=01*构造NFA：第54页，此课件共127页哦将NFA转换成正规式方法：合并法合并法 （与分裂法相反）输入：NFAM输出：一个正规式e步骤：1o对于NFAM中的开始状态和终止状态分别新设置一个唯一的开始状态和终止状态，使所设的开始状态到原开始状态连接弧；原终止状态到所设的终止状态连接弧。s为新增的开始状态为新增的开始状态Z为新增的终止状为新增的终止状态态第55页，此课件共127页哦2o 利用下列规则进行合并，直到图中只剩下新设置的开始态和终止态为止。那么在开始态和终止态弧上的正规式便是所求的结果。第56页，此课件共127页哦例：已知NFA如下，求正规式e1o新设置一个唯一的开始状态和终止状态：第57页，此课件共127页哦2o按照合并规则进行合并e=(x|y)*(xy*y|yx*x)第58页，此课件共127页哦四、四、NFA到到DFA的转换（的转换（NFA的确定化）的确定化）1.理论依据和目的理论依据和目的定理：定理：若L为一个能被NFA接受的语言，则存在一个能接受L的DFA：即：L(NFAM)=L(DFAM)目的：目的：消除消除NFA中中弧弧。弧会使自动机做无用功。合并合并NFA中不确定的状态中不确定的状态。不确定状态不仅给自动机识别字符串带来困难，而且使得编制相应的词法分析程序变得更为复杂。NFA到DFA的转换的基本思想基本思想：DFA的每一个状态对应于的每一个状态对应于NFA的一组状态（状态集合）。的一组状态（状态集合）。方法方法：子集法子集法第59页，此课件共127页哦2.子集法子集法 分两种情况介绍分两种情况介绍NFA的确定化：不含弧的NFA的确定化。含弧的NFA的确定化由NFAA=（S,f,S0,F）构造DFAA=（S,f,q0,F）方法：1o DFAA的输入字母表与NFAA的完全相同2o把NFAA的每一个状态子集作为DFAA的一个状态，因此该构造方法称为子集法。第60页，此课件共127页哦3o设NFAA的任一状态子集r1，r2，,rn,riS(i=1,2,n),令r=r1，r2，,rn,rS。取a,DFAA的映射函数定义为：f(r,a)=qS其中，q=q1，q2，,qm,而q1，q2，,qm=f(r1,a)f(r2,a)f(rm,a)。4oDFAA的开始状态q0=S1，S2，,SK，其中，SiS0(i=1,2,K)5oDFAA的终止状态F=e|e=e1，e2，,ep,e1，e2，,epF第61页，此课件共127页哦具体操作方法：1o依据NFA,构造确定化矩阵：步骤：步骤：a.设状态S0是NFA的开始状态，以S0作为DFA的开始状态，S0S.b.再由f(S0,a)=S1,S2（a）若：f(S0,b)=S0（b）则：S0状态对于输入字符a,b的映射分别是状态S1,S2与S0。其中：S1,S2S是DFA的新状态。第62页，此课件共127页哦c.再求新状态S1,S2对于a,b的映射，设：f(S1,S2,a)=S0,S3Sf(S1,S2,b)=S1,S2,S3S，即：S0,S3和S1,S2,S3均为DFA的新状态。d.每得到一个新状态，就继续求新状态对a,b的映射，直到再没有新状态为止。2o 依据1o求出的确定化矩阵，代换出确定化的状态转换矩阵。3o依据确定化的状态转换矩阵画出状态转换图。（1）不含弧的NFA的确定化第63页，此课件共127页哦例:设有NFA的N=(q0,q1,q2,q3,x,y,f,q0,q1)的状态转换图如下：求等价的DFA（见前例）第64页，此课件共127页哦解：1o依据NFA，构造确定化矩阵：状态输入xyq0q1,q2q0q1,q2q0,q3q1,q2,q3q0,q3q1,q2,q3q0,q3q1,q2,q3q0,q1,q3q1,q2,q3q0,q1,q3q0,q1,q2,q3q0,q1,q2,q3q0,q1,q2,q3q0,q1,q2,q3q0,q1,q2,q3第65页，此课件共127页哦2o依据构造的确定化矩阵，代换成确定化的状态转换矩阵(用符号重写确定化矩阵)将确定化矩阵中的q0，q1,q2，q0,q3分别用符号标记：A1,A2,，A6即可。状态输入xyA1A2A1A2A3A4A3A4A3A4A5A4A5A6A6A6A6A6第66页，此课件共127页哦3o依据确定化的转换矩阵画出状态转换图确定开始状态为：A1(代替q0)终止状态为：A2，A4，A5，A6（A2，A4，A5，A6分别代替q1,q2，q1,q2,q3，q0,q1,q3，q0,q1,q2,q3,其中包含NFA中的终止态q1）第67页，此课件共127页哦（2）NFA的确定化的确定化（带有空移或空环路的NFA）设NFAM=(Q,f,Q0,F)，有：1o状态子集状态子集I的的闭包闭包（记为-closure(I)）vI蕴涵于Q,状态子集I的-closure(I)定义如下：若状态qI，则q-closure(I);若状态q-closure(I),q是由q出发经多条弧到达的状态，则q-closure(I)，显然，-closure(I)蕴涵于Q第68页，此课件共127页哦例：设有状态转换图如下：显然，状态集Q=1,2,3,4,5,6,7,8若子集I=1，则：-closure(I)=1,2(状态1I,1-closure(I)；又从状态1出发经弧可到达状态22-closure(I)若子集I=4，5，则：-closure(I)=2,4,5,6,7,8第69页，此课件共127页哦2o状态集合状态集合I的的a弧转换表示为弧转换表示为f(I,a)=q|f(q,a)=q,qI=J（其中J蕴涵Q）即：J是由子集I中的状态出发，经过一条a弧（跳过a弧前的任意条弧）可到达的状态的集合。令：Ia=-closure(J)表示：子集Ia是从子集I中任意状态出发，经a弧（前后可跳过弧）而到达的状态的集合。例：上例，若子集I=1,根据定义：子集J=f(1,a)=5,3,4于是：子集Ia=closure(J)=closure(5,3,4=5,3,4,6,2,8,7 1,2 的定义是为了消除空弧或空环。第70页，此课件共127页哦例：已知NFAM如下图。下面以此为例介绍NFA确定化过程。解：依据NFA的开始状态集S,求-closure(S)=S（汇集S射出弧的结点集合）作为DFA的开始状态。不断地按新的非空子集求对输入符号x,y的Ix和Iy，并将新的Ix或Iy作为DFA的状态。这一过程一直重复到不再出现新的Ix或Iy为止。第71页，此课件共127页哦如：Ix=-closure(1)=1,2,3 Iy=-closure()=Ix为非空新子集，作为DFA的状态，且继续以1,2,3求Ix和Iy。Ix=-closure(1,2,3)=4Iy=-closure(1,2,3)=2,3,5其中，4和2,3,5作为DFA的结点，且又是新的Ix,Iy,继续求Ix，ly，过程如下矩阵：IxIyS1,2,31,2,342,3,546,7,Z2,3,54,6,7,Z2,3,56,7,Z7,Z4,6,7,Z7,Z6,7,Z7,Z7,Z第72页，此课件共127页哦v分别：将七种状态集：S，1,2,3,4,2,3,5,6,7,Z,4,6,7,Z,7,Z用符号q0q6命名得DFA七种状态矩阵：DFA图如下：即为所求的DFA。IxIyq0q1q1q2q3q2q4q3q5q3q4q6q5q6q4q6q6第73页，此课件共127页哦例：已知NFA（如图），求与之等价的DFA。解：求DFA的开始状态（与上例不同）-closure(x)=x,0,1，作为DFA的开始态。构造确定化矩阵：IaIbx,0,10,2,10,10,2,10,2,10,1,30,10,2,10,10,1,30,2,10,y,10,y,10,2,10,1IaIbABCBBDCBCDBEEBC第74页，此课件共127页哦画DFA的图形表示第75页，此课件共127页哦五、五、DFA的化简（的化简（DFA的最小化）的最小化）1.化简化简DFA的目的的目的寻找一个状态数比M少的DFAM，使得L(M)=L(M)DFA的状态少，则依据它编写的词法分析程序就简单。2.化简化简化简问题：使化简后的DFA中，没有多余的状态没有多余的状态。使化简后的DFA中，没有两个是相互等价的没有两个是相互等价的状态状态。采用分割法。采用分割法。第76页，此课件共127页哦所谓多余状态：从自动机的开始状态出发，输入任何的字符串也不能到达的那个状态。从自动机的开始状态到某个结点有弧，但该结点无弧通向终止状态。不可到达的状态对于生成自动机的语言毫无意义。因此，应该从自动机中删去。第77页，此课件共127页哦v两个状态s和t等价的条件是：一致性条件：状态s和t必须同时为可接受状态（终止状态）或不可接受状态（非终止状态）。漫延条件：对于所有输入符号，状态s和t必须转换到等价的状态集里。如果两个状态不等价，则称这两个状态是可区别的。v自动机中的非终止状态与终止状态是可区别的（不满足一致性条件）第78页，此课件共127页哦v非终止状态0，2，1，3与终止状态4可区别。不满足一致性条件。v状态2与状态3可区别（状态2读入b后到达2;状态3读入b后到达4，而2和4不等价：即2，3不满足漫延条件）。注：分割法分割法就是使状态满足漫延条件和一致性条件。关键：满足漫延条件的分割方法。第79页，此课件共127页哦3.用分割法化简用分割法化简DFA 基本思想：基本思想：将DFA的状态集分成若干个互不相交的子集，使每个子集中的状态都是等价的，而不同状态子集中的状态则是不等价的。即是可区分的。1o首先，将DFA的状态分成两个子集：终止状态子集和非终止状态子集。（因为终止状态与非终止状态是可区别的）。（使状态满足一致性条件）2o 然后对每个子集进行再分解。分解后的两个状态属于同一个子集，当且仅当对于任何一个输入字符，它们的映射属于同一个子集，此过程一直执行到不能再分解为止。（使状态满足漫延条件）3o 将分解的每个子集作为化简后的DFA的每一个状态。且含有原来开始状态的子集和含有原来终止状态的子集分别作为开始状态和终止状态。第80页，此课件共127页哦具体DFA的化简过程。例：已知有DFA图如下，化简DFA：解：1o将所有终止状态归为一个子集S1=q1,q3,q4,q5;其余非终止状态归为另一个子集：S2=q0,q2第81页，此课件共127页哦2o 按可区别性分解子集S1和S2v分解S1：f(q1,x)=q2S2f(q3,x)=q4S1 f(q4,x)=q5S1f(q5,x)=q5S1(也可对y字符进行)将S1分解成两个子集S1=q1,S2=q3,q4,q5分解S2：f(q0,x)=q1S1f(q2,x)=q3S2将S2分解成两个子集q0,q2最后分解成4个子集：q1,q3,q4,q5,q0,q2分别用q1,q3,q0,q2来替换成4个子集的状态名。DFA的化简：的化简：第82页，此课件共127页哦用状态矩阵形式辅助完成化简用状态矩阵形式辅助完成化简xyq0q1q0q1q2q3q2q3q2q3q4q3q4q5q5q5q5q5分解：分解：S1=q0,q2,S2=q1,q3,q4,q5对对x，S2分解：分解：S21=q1,S22=q3,q4,q5 对对x，s1分解：分解：S12=q0,s12=q2,S22对对x或或y不能分解。不能分解。最后得到分解：最后得到分解：q0,q1,q2,q3,q4,q5第83页，此课件共127页哦例：将DFA（如下图）最小化。解：1o将终止态与非终止态的结点分为2个子集：=(A,B,C,D,E)(其中S0=A,B,C,D,S1=E)第84页，此课件共127页哦20 分解子集：S0A,B,C,D对a：对b：f(A,a)=B S0写成A,B,C,Da=BB包含在A,B,C,D中,A,B,C,D对a不被分裂f(B,a)=B S0f(C,a)=B S0f(D,a)=B S0f(A,b)=CS0写成A,B,C,Db=C,D,E C,D,E既不包含在A,B,C,D中，又不包含在E中，A,B,C,D对b要被分裂。f(B,b)=DS0f(C,b)=CS0f(D,b)=ES1第85页，此课件共127页哦=(A,B,C,D,E)(