《ppt编译原理3章3.ppt》由会员分享，可在线阅读，更多相关《ppt编译原理3章3.ppt（60页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三章第三章词法分析词法分析3.1词法分析器的设计词法分析器的设计词法分析的主要工作词法分析的主要工作:从源程序的第一个字符开始，从左到右扫描源程序，一从源程序的第一个字符开始，从左到右扫描源程序，一次读一个字符，根据词法规则将有关字符组合成单词，并次读一个字符，根据词法规则将有关字符组合成单词，并识别各类单词，当确定单词类别后，将单词输出。识别各类单词，当确定单词类别后，将单词输出。在词法分析过程中还要完成其它任务，如：在词法分析过程中还要完成其它任务，如：过滤掉源程序中的注释和空白；过滤掉源程序中的注释和空白；记录读入字符的行号，以便发现错误后能报告出错位置；记录读入字符的行号，以便发现错
2、误后能报告出错位置；进行预编译工作进行预编译工作(对宏进行展开对宏进行展开等工作等工作)；符号表操作。符号表操作。错误处理等。错误处理等。词法分析与语法分析的接口方式：词法分析与语法分析的接口方式：(1)词法分析作为一遍：将词法分析器的输出结果放入一个中间文件上将词法分析器的输出结果放入一个中间文件上(外存外存)或直接存放在内存中，后面的语法分析程序将它作为或直接存放在内存中，后面的语法分析程序将它作为输入进行语法分析，这样通过一遍加工就可以将以字输入进行语法分析，这样通过一遍加工就可以将以字符串形式的源程序加工成单词串形式的源程序。符串形式的源程序加工成单词串形式的源程序。Lexical a
3、nalyzerCharacterstreamToken streamError messages(2)词法分析与语法分析安排在同一遍中：将词法分析编成一个子程序，该子程序由语法分析将词法分析编成一个子程序，该子程序由语法分析程序调用。当语法分析程序需要一个新单词时，调程序调用。当语法分析程序需要一个新单词时，调用该程序，每调用一次，则从源程序中读出一个单用该程序，每调用一次，则从源程序中读出一个单词，这样避免了中间文件的生成，可以提高编译效词，这样避免了中间文件的生成，可以提高编译效率。率。CharacterstreamLexical analyzersyntax analyzerAbstra
4、ctSyntax源程序的输入：源程序的输入：(1)一次性输入一次性输入：当内存较大时，把源程序：当内存较大时，把源程序一次性输入到内存的用户数据区，每个字一次性输入到内存的用户数据区，每个字符占一个字节，词法分析程序从数据区中符占一个字节，词法分析程序从数据区中依次读入字符。依次读入字符。数据区词法分析(2)分批次输入分批次输入：当内存不够大时，在内存：当内存不够大时，在内存开辟一个适当大小的输入缓冲区，输入时，开辟一个适当大小的输入缓冲区，输入时，把源程序分批输入到输入缓冲区，词法分把源程序分批输入到输入缓冲区，词法分析程序从缓冲区中读取字符，当缓冲区的析程序从缓冲区中读取字符，当缓冲区的字
5、符全部读完以后，再从外存上读入下一字符全部读完以后，再从外存上读入下一批，直到全部源程序字符读完为止。批，直到全部源程序字符读完为止。缓冲区词法分析(3)超前搜索超前搜索：词法分析程序在组合单词的时候，为了：词法分析程序在组合单词的时候，为了进一步判明情况和确定下一步要做什么以及为了处理上进一步判明情况和确定下一步要做什么以及为了处理上的方便等，常采取向前的方便等，常采取向前假读假读字符的办法字符的办法(超前搜索超前搜索)，即即先向前读取字符和判别字符是什么，不马上处理，当情先向前读取字符和判别字符是什么，不马上处理，当情况判明后，再回来处理已读过的字符。况判明后，再回来处理已读过的字符。例如
6、：有源程序，例如：有源程序，programexample(input,output);在判别保留字在判别保留字program过程中，当读到字符过程中，当读到字符m时，虽然前时，虽然前面字符为面字符为program，还要看是否结束，即后面字符是什么还要看是否结束，即后面字符是什么(字母、数字还是空格字母、数字还是空格)，所以不能马上处理，所以不能马上处理(断定是保留断定是保留字字)，而需要再向前假读一个字符，确定后再回来处理。而需要再向前假读一个字符，确定后再回来处理。在判别标识符在判别标识符example过程中，当读到字符过程中，当读到字符e时，虽然前时，虽然前面字符为面字符为example，
7、为了判别下一个字符是否是该标识符为了判别下一个字符是否是该标识符的一部分，也要判别下一个字符是否为字母或数字，所的一部分，也要判别下一个字符是否为字母或数字，所以不能马上处理以不能马上处理，需要再向前假读一个字符。需要再向前假读一个字符。Ex:p40有时，为了判别读进字符所组成的单词的类别，需向前假读若干字符！(4)输入缓冲区的处理：输入缓冲区的处理：显然，无论缓冲区设定为多大，显然，无论缓冲区设定为多大，都不能保证单词不会被它的边界打断，若有单词都不能保证单词不会被它的边界打断，若有单词TEST123，可能在缓冲区中成为：可能在缓冲区中成为：.TES在这种情况下，即使通过假读读到缓冲区的最后
8、一个字符，在这种情况下，即使通过假读读到缓冲区的最后一个字符，但仍不能找到该单词的右边界，这时，若从外存上再读一但仍不能找到该单词的右边界，这时，若从外存上再读一部分源程序进入缓冲区，则会将没有处理过的字符部分源程序进入缓冲区，则会将没有处理过的字符(TES)冲掉。为此，我们可将缓冲区分成相等的两个区域：冲掉。为此，我们可将缓冲区分成相等的两个区域：真读指针假读指针两个半区互补使用两个指针协同工作单词长度有无限制？单词的输出：单词的输出：(1)单词的种类：保留字(关键字）：如，program begin end var const for 标识符：如，程序名、变量名、常量名、类型名、过程名等常
9、数：如，125、0.745、15.2E+5算符：如，+、*、/、等界符：如，分号、逗号等(2)词法分析器的输出形式：为了便于编译程序进一步加工，单词的输出形式一般采用二元式：单词类别单词值用整数编码表示，如何分类以处理方便为原则，如：标识符归为一类；常数按类型分类；保留字一字一类，或将全体定位一类；界符可单独作为一类，或一符一类。采用什么样的输出形式也是取决于后续处理的方便，如：标识符用字符串编码或对应地址；常数用其自身值的二进制形式；保留字(分界符)若将全体定位一类则需输出其值，可用内部整数编码或串编码表示。例如：程序段例如：程序段ifi=5thenx：=y；在经过词法分析器在经过词法分析器
10、扫描后，输出的单词可表示如下：扫描后，输出的单词可表示如下：保留字保留字if(3，if)标识符标识符i(1，指向指向i的符号表入口的符号表入口)等号等号=(4，=)常数常数5(2，5的二进制表示的二进制表示)保留字保留字then(3，then)标识符标识符x(1，指向指向x的符号表入口的符号表入口)赋值号赋值号:=(4，：=)标识符标识符y(1，指向指向y的符号表入口的符号表入口)分号分号；(5，；)其中，类别码：其中，类别码：“1”表示标识符；表示标识符；“2”表示常数；表示常数；“3”表示保留字；表示保留字；“4”表示算符；表示算符；“5”表示界符。表示界符。词法分析的分离：词法分析的分离
11、：实际上，实际上，词法词法也是也是语法语法的一部分，词法描述完全可的一部分，词法描述完全可以归并到语法描述中去，只不过词法规则更简单些。进以归并到语法描述中去，只不过词法规则更简单些。进一步说，在编译程序中可以将词法分析包含在语法分析一步说，在编译程序中可以将词法分析包含在语法分析之中，那么为什么把编译过程的分析工作划分成词法分之中，那么为什么把编译过程的分析工作划分成词法分析和语法分析两个阶段？主要考虑的因素为：析和语法分析两个阶段？主要考虑的因素为：(1)使整个编译程序的结构更简洁、清晰和条理化；使整个编译程序的结构更简洁、清晰和条理化；(2)编译程序的效率会改进编译程序的效率会改进；(3
12、)增强编译程序的可移植性。增强编译程序的可移植性。3.2正规文法与状态转换图正规文法与状态转换图一、状态转换图一、状态转换图许多程序设计语言的单词，可以用正规文法来描述。许多程序设计语言的单词，可以用正规文法来描述。对于这样的语言，使用状态转换图可以设计词法分析程对于这样的语言，使用状态转换图可以设计词法分析程序（扫描器）。序（扫描器）。状态转换图状态转换图TG（简称状态图或转换图）简称状态图或转换图）是一张定义在字母表是一张定义在字母表上的有限方向图。上的有限方向图。在状态转换图中在状态转换图中:结点代表结点代表状态状态，用圆圈表示；，用圆圈表示；状态之间用状态之间用有向弧有向弧连结；连结；
13、有向有向弧上的标记弧上的标记（字符）表示在射出结（字符）表示在射出结点（有向弧的开始结点）所代表的状态点（有向弧的开始结点）所代表的状态下可能出现的输入符号或符号串。下可能出现的输入符号或符号串。字母表字母表=0,1上的一个上的一个转换图转换图用带有符号用带有符号“”的圆圈表示状态转换图的的圆圈表示状态转换图的初始状态初始状态用用表示表示终止状态终止状态。P41ex 一一个个状状态态转转换换图图可可用用于于接接受受（或或识识别别）一一定定的的符符号号串串。在在状状态态转转换换图图中中从从初初始始状状态态到到某某一一终终止止状状态态的的序序列列为为路路。对对于于某某一一符符号号串串，在在状状态态
14、转转换换图图中中，若若存存在在一一条条路路产产生生，则则称称状状态态转转换换图图接接受受（或或识识别别）该该符符号号串串，否否则则符符号号串串不不能能被被接接受受。能能被被状状态态转转换换图图TG接接受受的的符符号号串串的的集集合合记记为为L(TG)，称为称为状态转换图所能识别的语言状态转换图所能识别的语言。字母表=0,1上的一个转换图 由以上状态转换图可见，字母表上的符号串：10010100 0111 1011010011 011100 都能被上述转换图所接受。即有：L(TG)=01，10，0100，0111，1011，010011，011100，再如，设有字母表=a,b，则有字母表上的一个
15、状态转换图如下：由转换图可见，字母表=a,b上的符号串：a，b，ab，ba，aaa，bbb，aab，bba，均能被这个转换图所接受。从而有：L(TG)=a，b，ab，ba，aaa，bbb，aab，bba，例：识别一个简单语言的所有单词符号的状态图例：识别一个简单语言的所有单词符号的状态图 见P43 图3.3二、正规文法的状态转换图表示二、正规文法的状态转换图表示许多程序设计语言的单词可以用正规文法来表示，而许多程序设计语言的单词可以用正规文法来表示，而对于正规文法所描述的语言又可以用状态转换图来非形式对于正规文法所描述的语言又可以用状态转换图来非形式的表示。的表示。对于对于右线性文法右线性文法
16、GS，状态转换图的表示方法如下：状态转换图的表示方法如下：UxV|yxV|y V z V z(1)用用状态状态表示表示GS中的中的非终结符非终结符，GS的开始符号的开始符号S对对应状态转换图的应状态转换图的开始状态开始状态S；(2)增加一个新状态增加一个新状态Z，作为状态转换图的作为状态转换图的终止状态终止状态；(3)对于对于GS中形如中形如UxV的每条产生式，画一条从状态的每条产生式，画一条从状态U到状态到状态V的方向弧，弧上的的方向弧，弧上的标记为标记为x；(4)对于对于GS中形如中形如Uy的每条产生式，画一条从状态的每条产生式，画一条从状态U到终态到终态Z的方向弧，弧上的标记为的方向弧，
17、弧上的标记为y例如：给出与正规文法G(S)等价的状态转换图。GS：SaA SbBS AaB AbA BaS BbA B ASBZababab 正规文法与状态转换图等价，是指正规文法所确定的语言L(G)，与状态转换图所接受的语言L(TG)相同：L(G)=L(TG)对于对于左线性文法左线性文法GZ，状态转换图的表示方法如下：状态转换图的表示方法如下：UVx|yVx|y(1)用用状态状态表示表示GZ中的中的非终结符非终结符，GZ的的开始符号开始符号Z对对应状态转换图的应状态转换图的终止状态终止状态Z(2)增加一个增加一个新状态新状态S，作为状态转换图的作为状态转换图的初始状态初始状态；(3)对于对于
18、GZ中形如中形如UVx的每条产生式，画一条从状态的每条产生式，画一条从状态V到状态到状态U的方向弧，弧上的的方向弧，弧上的标记为标记为x；(4)对于对于GZ中形如中形如Uy的每条产生式，画一条从的每条产生式，画一条从初态初态S到状态到状态U的方向弧，弧上的的方向弧，弧上的标记为标记为y例如例如：给出与正规文法：给出与正规文法GZ等等价的状态转换图价的状态转换图GZ:ZU0|V1UZ1|1VZ0|0三、状态转换图的实现（三、状态转换图的实现（p42-46)例：识别一个简单语言的所有单词符号的状态图例：识别一个简单语言的所有单词符号的状态图 见图3.33.3正规表达式与有限自动机正规表达式与有限自
19、动机（转幻灯（转幻灯P38)3.3有限自动机有限自动机正正规规文文法法可可以以用用状状态态转转换换图图非非形形式式的的进进行行表表示示，这这就就表表明明正正规规文文法法所所对对应应的的语语言言(正正规规语语言言)可可以以用用状状态态转转换换图图来来接接受受(识识别别)。我我们们将将看看到到，有有限限自自动动机机正正是是对对状状态态转转换换图图进进一一步步形形式式化化的的结结果果，它它对对于于扫扫描描器器的的构构造造，特特别别是是扫扫描器自动生成将带来很大的方便。描器自动生成将带来很大的方便。确定的有限自动机确定的有限自动机(DeterministicFiniteAutomata)定义定义：一个
20、：一个确定有限自动机确定有限自动机（DFA）M是一个五元组：是一个五元组：M=(K，f，S，Z)，其中：其中：(1)K是一个非空有限集，它的每个元素称为一个状态，是一个非空有限集，它的每个元素称为一个状态，K即表示即表示DFA中包含的所有状态组成的集合；中包含的所有状态组成的集合；(2)是一个有限的输入字母表，它的每个元素称为一是一个有限的输入字母表，它的每个元素称为一个输入字符，所以个输入字符，所以也称为输入符号字母表；也称为输入符号字母表；(3)f是转换函数，它是从是转换函数，它是从K到到K的映象，即，如果的映象，即，如果f(ki,a)=kj(kiK,kjK，a)就意味着，当前状态为就意味
21、着，当前状态为ki，输入字符为输入字符为a时，将转换到下一个状态时，将转换到下一个状态kj，kj成为新的成为新的当前状态，我们把当前状态，我们把kj称为称为ki的一个后继状态；的一个后继状态；(4)SK是唯一的一个初始状态；是唯一的一个初始状态；(5)Z K，是是终终止状止状态态(终态终态)集合，集合，终终止状止状态态也称可接受也称可接受状状态态或或结结束状束状态态。例如例如：为为下下图图所示的状所示的状态图态图构造确定的有限自构造确定的有限自动动机机。DFAM=(S,U,V,Q,a,b,f,S,Q)其中：其中：S,U,V,Q为为DFAM的状态集的状态集K；a,b为输入符号字母表为输入符号字母
22、表；f定义为：定义为：f(S,a)=Uf(S,b)=Vf(V,a)=Uf(V,b)=Qf(U,a)=Qf(U,b)=Vf(Q,a)=Qf(Q,b)=QS为初始状态为初始状态;Q为终止状态集合，即只有为终止状态集合，即只有一个终态。一个终态。事实上，状态转换图是有限自动机的一种表示形式事实上，状态转换图是有限自动机的一种表示形式,假假定定DFAM含有含有m个状态，个状态，n个输入字符，那么这个状态转换个输入字符，那么这个状态转换图含有图含有m个状态个状态（结点），每个结点最多有（结点），每个结点最多有n个弧射出，整个弧射出，整个图含有唯一个图含有唯一一个初态结点一个初态结点(冠以冠以“”)和和若
23、干个终态结点若干个终态结点(用双圈表示用双圈表示)，若有，若有f(ki,a)=kj(kiK,kjK，a)，则则从从状状态结态结点点ki到状到状态结态结点点kj画画标记为标记为a的弧。的弧。一个一个DFA还还可以可以用一个用一个矩矩阵阵表示表示：矩矩阵阵的行表示状的行表示状态态，列表示列表示输输入字符，入字符，矩矩阵阵元素表示相元素表示相应应状状态态行和行和输输入字符列入字符列下的新状下的新状态态。例例如如：上例：上例的的DFA的的矩矩阵阵表示如表示如下：下：字符字符状态状态abSUVUQVVUQQQQ第一行表示初第一行表示初态态0001相相应终态应终态行在右端行在右端标标以以1，非非终态标终态
24、标以以0对于对于*中的任何字符串中的任何字符串,若若DFAM中存在一条从初态中存在一条从初态结点到某一终态结点的路结点到某一终态结点的路,且这条路上所有弧的标记连接且这条路上所有弧的标记连接成的字符串等于成的字符串等于，则则称称可以被可以被DFAM所接受所接受(识别识别)。若若M的初态结点同时又是终态结点，则的初态结点同时又是终态结点，则空串空串可被可被M所所接受接受（识别）。（识别）。DFAM所能识别的所有字符串的全体（字的全体）称为所能识别的所有字符串的全体（字的全体）称为DFAM所能接受的语言所能接受的语言，记为，记为L(M)若若*，f(S,)=P，其中其中S为为DFAM的初始状态，的初
25、始状态，PZ，Z为终态集。则称字符串为终态集。则称字符串可以被可以被DFAM所接受所接受(识别识别)为了加深对上述定义的理解，我们给出为了加深对上述定义的理解，我们给出扩充的转换函数扩充的转换函数的定义：的定义：f(q,)=q，其中其中qK，即即q为为任意状任意状态态；f(q,T)=f(f(q,T),),其中其中T,*。举例：举例：试证试证baab可被可被下面下面的的DFA所接受所接受。因因为为：f(S,baab)=f(f(S,b),aab)=f(V,aab)=f(f(V,a),ab)=f(U,ab)=f(f(U,a),b)=f(Q,b)=QQ属于属于终态终态，得，得证证可以看出：可以看出：这
26、这个定个定义义使得使得转换转换函数的定函数的定义义域从原来的域从原来的K扩扩充到充到K*上，即上，即f成为从成为从K*到到K的映象。的映象。DFA的的确确定定性性表表现现在在转转换换函函数数f:KK是是一一个个单单值值函函数数，也也就就是是说说对对任任何何状状态态kK,和和输输入入符符号号a，f(k,a)唯唯一一地地确确定定了了下下一一个个状状态态。从从状状态态转转换换图图来来看看，若若字字母母表表含含有有n个个输输入入字字符符，那那么么任任何何一一个个状状态态结结点点最最多多有有n条条弧弧射射出出，而且每条弧以一个不同的输入字符进行标记。而且每条弧以一个不同的输入字符进行标记。非确定的有限自
27、动机非确定的有限自动机(NondeterministicFiniteAutomata)一个一个非确定的有限自动机非确定的有限自动机(NFA)M是一个五元组：是一个五元组：M=(S，S0，F)，其中其中(1)S是一个非空有限集，它的每个元素称为一个状态；是一个非空有限集，它的每个元素称为一个状态；(2)是一个有限的是一个有限的输输入字母表，它的每个元素称入字母表，它的每个元素称为为一个一个输输入字符入字符;(3)是是转换转换函数，它是从函数，它是从S*到到2S的子集的映象的子集的映象(4)S0 S是一个非空的初始状是一个非空的初始状态态集；集；(5)F S，是是终终止状止状态态集合集合与与DFA
28、相同相同与与DFA相同相同对某个输入，可以对某个输入，可以到达多个状态到达多个状态初态可以是多个初态可以是多个与与DFA相同相同所以，一个含有所以，一个含有m个状态和个状态和n个输入字符的个输入字符的NFA可表示成可表示成如下的一张状态转换图：这张状态转换图含有如下的一张状态转换图：这张状态转换图含有m个状态结点，个状态结点，每个结点每个结点可射出若干条箭弧可射出若干条箭弧与别的结点相连接，每条弧用与别的结点相连接，每条弧用*中的一个串作标记中的一个串作标记(可相同可相同)，整个图，整个图至少含有一个初态至少含有一个初态结点结点以及以及若干个终态若干个终态结点。结点。例如例如：一个一个NFAM
29、=(0,1,2,3,4,a,b,f,0,2,4)f(0,a)=0,3f(0,b)=0,1f(1,b)=2f(2,a)=2f(2,b)=2f(3,a)=4f(4,a)=4f(4,b)=4其中：其中：那么，那么，它的它的状状态转换图态转换图表示表示为：为：它的它的矩阵矩阵表示表示为：为：跟跟DFA有相似的结论有相似的结论：对对于于*中的任何一个串中的任何一个串，若若NFAM中存在一条从某一初态结点到某一终态结点的路，且这中存在一条从某一初态结点到某一终态结点的路，且这条路上所有弧的标记依次连接成的串（不理睬那些标记为条路上所有弧的标记依次连接成的串（不理睬那些标记为的弧）等于的弧）等于，则称则称可
30、以被可以被NFAM所接受（识别）。若所接受（识别）。若M的某些结点既是初态结点又是终态结点，或者存在一条的某些结点既是初态结点又是终态结点，或者存在一条从某个初态结点到某个终态结点的从某个初态结点到某个终态结点的路，那么空串路，那么空串可被可被M所接受（识别）。所接受（识别）。可以看出，可以看出，DFA是是NFA的一个特例。并且可以证明，的一个特例。并且可以证明，对于每个对于每个NFAM存在一个存在一个DFAM使得使得L(M)=L(M)。对对于任何两个有限自于任何两个有限自动动机机M和和M，如果如果L(M)=L(M)，则则称称M与与M是是等价等价的。的。非确定的有限自动机的确定化非确定的有限自
31、动机的确定化将有限自动机用计算机程序表示出来，就能实现对词法将有限自动机用计算机程序表示出来，就能实现对词法的分析；的分析；在前例所示的在前例所示的NFA中，在状态中，在状态0下，面对输入下，面对输入a有两个转有两个转换，也就是可能进入状态换，也就是可能进入状态0或或3，而输入，而输入b也有两个转换。这也有两个转换。这些转换函数多值的情况，使得很难用计算机程序模拟些转换函数多值的情况，使得很难用计算机程序模拟NFA。前面说过前面说过：“对于每个对于每个NFAM存在一个存在一个DFAM使使得得L(M)=L(M)”就是说：设就是说：设L为一个由非确定有限自动机为一个由非确定有限自动机接受的集合（语
32、言），则存在一个接受接受的集合（语言），则存在一个接受L的确定的有限自动机的确定的有限自动机。下面给出从。下面给出从NFA构造识别同样语言的构造识别同样语言的DFA的算法。的算法。子集构造法子集构造法：将将NFA的一个状态子集在的一个状态子集在DFA中用一个中用一个状态表示出来。状态表示出来。从从NFA的距阵表示中可以看出，的距阵表示中可以看出，表项通常是一个状态的集合，表项通常是一个状态的集合，而在而在DFA的距阵表示中，表项的距阵表示中，表项是一个状态是一个状态。NFA到相应的到相应的DFA的构造的基的构造的基本想法是让本想法是让DFA的每个状态代的每个状态代表表NFA的一个状态集的一个状
33、态集合。合。即在转换后的即在转换后的DFA中，中，使用它的状态去记录在使用它的状态去记录在NFA中读入中读入一个输入符号后可能到达的所有状态一个输入符号后可能到达的所有状态。换句话说，在得到的换句话说，在得到的DFA中若输入符号串中若输入符号串a1a2an后，到后，到达某个状态，那么该状态表示对应的达某个状态，那么该状态表示对应的NFA的状态集的一个子的状态集的一个子集集，这个子集是这个子集是NFA在输入符号串在输入符号串a1a2an后可以到达的那后可以到达的那些状态组成的集合。些状态组成的集合。首先介绍两个重要运算：首先介绍两个重要运算：(1)状态集的状态集的-闭包闭包：状态集：状态集I中的
34、任何状态中的任何状态s经任意条经任意条弧弧而能到达的所有状态的集合，定义为状态集而能到达的所有状态的集合，定义为状态集I的的-闭包，闭包，表示为表示为-closure(I)。(2)状态集的状态集的a弧转换弧转换：状态集：状态集I中的任何状态中的任何状态s经过一条经过一条a弧而能到达的所有状态的集合，定义为状态集弧而能到达的所有状态的集合，定义为状态集I的的a弧转弧转换，表示为换，表示为move(I,a)。对于任意对于任意NFAM=(K，f，S，F)，I K，a不妨设不妨设I=s1,s2,sj，则则move(I,a)=f(s1,a)f(s2,a)f(sj,a)例如：有下图所示的例如：有下图所示的
35、NFA,我以它为例来说明以上两个运算我以它为例来说明以上两个运算。对于对于I=0，-closure(I)=-closure(0)=0,1,2,4,7；令令A=0,1,2,4,7同理若同理若I=2,3,-closure(I)=-closure(2,3)=1,2,3,4,6,7；则则move(A,a)=3,8move(A,b)=5同样可以求出其它状态集的同样可以求出其它状态集的-闭包和闭包和a弧转换弧转换P50ex3.3算法算法：有了以上所述两个运算，我们就可以构造：有了以上所述两个运算，我们就可以构造NFAN的状的状态集态集K的子集从而与的子集从而与DFAM的状态对应，即构造若干个状态的状态对应
36、，即构造若干个状态集集T1,T2,Ti，且且Ti K，这样就可以构成由若干个状态集这样就可以构成由若干个状态集组成的子集族组成的子集族C，C=(T1,T2,Ti)，具体如下：具体如下：(1)首先，令首先，令T=-closure(K0)作为作为C中的唯一成员中的唯一成员(开始以前开始以前C中为空中为空)，并且它是未标记的，其中，并且它是未标记的，其中K0为为NFAN的初态集的初态集(2)While（C中存在尚未标记的子集中存在尚未标记的子集T）dobegin标记标记T；for每个输入字母每个输入字母adobeginU:=-closure(move(T,a)；/显然显然U是一个状态集是一个状态集i
37、f（U不在不在C中）中）then将将U作为未标记的子集加入作为未标记的子集加入C中；中；end；end；例例:为下面的为下面的NFAN的状态集的状态集K构造状态子集族构造状态子集族C。在此在此NFAN中，状态集中，状态集K=0,1,2,3,4,5,6,7,8,9,10，初态集初态集K0=0，开始前开始前C不包含不包含任何状态集任何状态集(1)T0=-closure(K0)=-closure(0)=0,1,2,4,7，C=(T0)(2)C=(T0)T1=-closure(move(T0,a)=1,2,3,4,6,7,8C=(T0,T1)T2=-losure(move(T0,b)=1,2,4,5,
38、6,7C=(T0,T1,T2)(3)C=(T0,T1,T2)T3=-closure(move(T1,a)=1,2,3,4,6,7,8=T1舍弃舍弃T3=-closure(move(T1,b)=1,2,4,5,6,7,9C=(T0,T1,T2,T3)(4)C=(T0,T1,T2,T3)T4=-closure(move(T2,a)=1,2,3,4,6,7,8=T1舍弃舍弃T4=-closure(move(T2,b)=1,2,4,5,6,7=T2舍弃舍弃(5)C=(T0,T1,T2,T3)T4=-closure(move(T3,a)=1,2,3,4,6,7,8=T1舍弃舍弃T4=-closure(m
39、ove(T3,b)=1,2,4,5,6,7,10C=(T0,T1,T2,T3,T4)(6)C=(T0,T1,T2,T3,T4)T5=-closure(move(T4,a)=1,2,3,4,6,7,8=T1舍弃舍弃T5=-closure(move(T4,b)=1,2,4,5,6,7=T2舍弃舍弃C中所有状态子集都已经被标记，中所有状态子集都已经被标记，算法结束算法结束子集族子集族C由由5个子集组成个子集组成：T0=0,1,2,4,7T1=1,2,3,4,6,7,8T2=1,2,4,5,6,7T3=1,2,4,5,6,7,9T4=1,2,4,5,6,7,10由由NFA构造构造DFA的方法的方法:假
40、设假设NFAN=（S，S0，Kt），我们可以我们可以构造一个构造一个DFAM=K，f，S，Kt，使得使得L(M)=L(N)：(1)M的状态集的状态集K由由S的一些子集组成。我们用的一些子集组成。我们用K1,K2,Kj表示表示K的一个元素，的一个元素，其中其中K1,K2,Kj是是K中的状态，中的状态，NFA的若干个状态构成的若干个状态构成DFA的一个状态；的一个状态；(2)M和和N的输入字母表是相同的，即都是的输入字母表是相同的，即都是；(3)转换函数转换函数D是这样定义的：是这样定义的：D(K1,K2,Ki,a)=R1,R2,Ri其中其中:R1,R2,Ri=-closure(move(K1,K
41、2,Kj,a)(4)S0=-closure(K0)，即即M的开始状态等于的开始状态等于N的初态集的的初态集的-闭包；闭包；(5)Kt=Kj,Kk,Ke，其中其中Kj,Kk,KeS，且且Kj,Kk,KeKt例如：为下面的例如：为下面的NFAN构造构造DFAM并使并使L(M)=L(N)(1)由子集构造法得状态集由子集构造法得状态集S=T0，T1，T2，T3，T4(2)字母表字母表=a,b(4)初态初态S0=-closure(K0)=-closure(0)=0,1,2,4,7=T0(5)终态集终态集T4，因为只有因为只有T4包含包含NFAN的终态的终态10(T4=1,2,4,5,6,7,10)(3)
42、转换函数转换函数D其中其中转换转换函数函数D如下：如下：D(T0，a)=T1(-closure(move(T0,a)=1,2,3,4,6,7,8=T1)R1,R2,Ri=-closure(move(S1,S2,Sj,a)D(T0，b)=T2(-closure(move(T0,b)=1,2,4,5,6,7=T2)D(T1，a)=T1(-closure(move(T1,a)=1,2,3,4,6,7,8=T1)D(T1，b)=T3(-closure(move(T1,b)=1,2,4,5,6,7,9=T3)D(T2，a)=T1(-closure(move(T2,a)=1,2,3,4,6,7,8=T1)
43、D(T2，b)=T2(-closure(move(T2,b)=1,2,4,5,6,7=T2)D(T3，a)=T1(-closure(move(T3,a)=1,2,3,4,6,7,8=T1)D(T3，b)=T4(-closure(move(T3,b)=1,2,4,5,6,7,10=T4)D(T4，a)=T1(-closure(move(T4,a)=1,2,3,4,6,7,8=T1)D(T4，b)=T2(-closure(move(T4,b)=1,2,4,5,6,7=T2)将将T0，T1，T2，T3，T4用用A，B，C，D，E表示表示确定的有限自动机的最简化确定的有限自动机的最简化(最小化最小化)
44、对对任意一个任意一个DFAM构造另一个构造另一个DFAM，使使L(M)=L(M)，并且并且M的状态个数不多于的状态个数不多于M的状态个数。的状态个数。首先我们介绍几个有关的概念：首先我们介绍几个有关的概念：(1)多余状态多余状态:对于一个状态对于一个状态Si，若从开始状态出发，不可若从开始状态出发，不可能到达该状态能到达该状态Si，则则Si为多余为多余(无用无用)状态状态。S1，S5，S6为为多余状态多余状态(2)死状态死状态:对于一个状态对于一个状态Si，对任意输入符号对任意输入符号a，若转到它若转到它本身后，不可能从它到达终止状态，则称本身后，不可能从它到达终止状态，则称Si为死状态。为死
45、状态。(3)等价状态等价状态:若若Si为自动机的一个状态，我们把从为自动机的一个状态，我们把从Si出发能导出出发能导出的所有符号串集合记为的所有符号串集合记为L(Si)多余状态和死状态又称为无关状态。多余状态和死状态又称为无关状态。设有两个状态设有两个状态Si和和Sj,若有若有L(Si)=L(Sj),则称则称Si和和Sj是是等价状态等价状态。从从S1和和S2能导出相同的符号串集合：能导出相同的符号串集合：L(S1)=L(S2)=b，所以所以S1和和S2等价等价(4)可区别状态可区别状态:自动机中两个状态自动机中两个状态Si和和Sj，如果它们不如果它们不等价，则称它们是可区别的。等价，则称它们是
46、可区别的。(5)两个状态两个状态(Si和和Sj)等价的判断条件等价的判断条件(分类算法分类算法)状态状态Si和和Sj必须同时为终止状态或同时为非终止状态。即必须同时为终止状态或同时为非终止状态。即终止状态和非终止状态是可区别的（粗分）终止状态和非终止状态是可区别的（粗分）；如，如，S0，S1，S2肯定与肯定与S3不等价不等价状态状态Si和和Sj对于对于任意任意输输入符号入符号a，必必须转须转到等价的状到等价的状态态里里，否，否则则Si和和Sj是可区是可区别别的。（的。（a为为区分依据，可以推广）区分依据，可以推广）因因f(S0,b)=S2，f(S2,b)=S3，而而S2和和S3不等价，故不等价
47、，故S0和和S2也不等价也不等价DFA的化简算法的化简算法：对于：对于DFAM=(S,f,S0,Z)(1)首先将首先将DFA的状态集进行初始化，分成的状态集进行初始化，分成P=(Z,S-Z);(2)用下面的过程对用下面的过程对P构造新的划分构造新的划分Pnewfor(P中每个组中每个组G)do/每个组都是一个状态集每个组都是一个状态集begin把把G划分成小组，划分成小组，G中的任意两个状态中的任意两个状态Si和和Sj在同一组中，在同一组中，当且仅当对于当且仅当对于中任意中任意输输入符号入符号a，Si和和Sj的的a转换是到同转换是到同一组中，一组中，move(Si,a)Gi，move(Sj,a
48、)Gi。这样，只要这样，只要Si和和Sj的的a转换是到不同的组中，则说明转换是到不同的组中，则说明Si和和Sj是可区别的，是可区别的，可进行划分。可进行划分。在在Pnew中用刚完成的对中用刚完成的对G的划分代替原来的的划分代替原来的G。end;P:=Pnew；(3)重复执行重复执行(2)，直到，直到P中每个状态集不能再划分中每个状态集不能再划分(Pnew=P)为为止止;(4)合并等价状态合并等价状态,在每个在每个G中，取任意状态作为代表，删去其它状中，取任意状态作为代表，删去其它状态态;(5)删去无关状态，从其它状态到无关状态的转换都成为无定义。删去无关状态，从其它状态到无关状态的转换都成为无
49、定义。例题例题：将下图所示的将下图所示的DFAM最小化最小化(P58)首次划分首次划分:P0=(1,2,3,4,5,6,7)在在G=1,2,3,4中中:f(1,a)=6，f(2,a)=7(转转向向终态终态)；f(3,a)=1,f(4,a)=4(转转向非向非终态终态)，故故1,2和和3,4是可区是可区别别的，得的，得P1=(1,2，3,4，5,6,7)；在在G=1,2中中，f(1,a)=6,f(2,a)=7(转转向向终态终态子集子集),而而f(1,b)=f(2,b)=3,所以不可区所以不可区别别，不再，不再进进行划分；行划分；考察考察G=3,4，f(3,a)=1,f(4,a)=4,可可见见它它们
50、转们转向向P1的不同的不同组组，故，故得新的划分得新的划分P2=(1,2,3,45,6,7)；对对1,2重新重新进进行考察，行考察，发现发现它不能它不能进进行划分，而行划分，而3和和4已已经经最小也不能划分了；最小也不能划分了；考察考察G=5,6,7，因因f(5,b)转转向向3，而，而f(6,b)和和f(7,b)转转向向1,2，可得新划分，可得新划分P3=(1,2,3,4,5,6,7)；进进一步一步进进行考察，可以行考察，可以发现发现每个子每个子集都不能再划分了；集都不能再划分了；消去等价状消去等价状态态：1,2用用1表示，表示，6,7用用6表示，得到得新表示，得到得新DFAM如如右右图图所示