第3章 词法分析精选PPT.ppt

第3章 词法分析第1页，本讲稿共73页n任务任务n扫描或词法分析阶段将源程序读作字符文件并将其分为若扫描或词法分析阶段将源程序读作字符文件并将其分为若干个单词。干个单词。n词法分析的处理结构词法分析的处理结构n(1)把词法分析程序作为主程序。把词法分析程序作为主程序。n(2)把词法分析程序作为语法分析程序调用的子程序。把词法分析程序作为语法分析程序调用的子程序。n由由于于把把词词法法分分析析器器安安排排成成一一个个子子程程序序比比较较自自然然，因因此此，词词法分析程序通常采用第二种处理结构。法分析程序通常采用第二种处理结构。第2页，本讲稿共73页词法分析的两种处理结构词法分析的两种处理结构(a)词法分析程序作为主程序词法分析程序作为主程序(b)词法分析程序作为子程序词法分析程序作为子程序第3页，本讲稿共73页3.1 扫描处理扫描处理n单词的分类单词的分类n关键字关键字(keyword)/保留字保留字(reserved word)：如：如C语言语言中的中的if、else、while和和do等，这些字保留了语言所规定等，这些字保留了语言所规定的含义，是编译程序识别各类语法成分的依据。几乎的含义，是编译程序识别各类语法成分的依据。几乎所有程序语言都限制用户使用保留字来作为标识符。所有程序语言都限制用户使用保留字来作为标识符。n标识符标识符(identifier)：用来标记常量、数组、类型、：用来标记常量、数组、类型、变量、过程或函数名等，通常由用户自己定义。变量、过程或函数名等，通常由用户自己定义。第4页，本讲稿共73页n常常数数：包包括括各各种种类类型型的的常常数数，如如整整型型常常数数386、实实型型常常数数0.618、布布尔尔型型常常数数TRUE、字字符符串串常常数数“Hello world!”等。等。n运运 算算 符符：如如“+”、“-”、“*”、“/”、“”、“0)inr=inr+368;else inr=inr*inr;经过词法分析器输出：经过词法分析器输出：(if,_)(,_)(id,“count”)(,_)(num,0)(),_)(id,“inr”)(=,_)(id,“inr”)(+,_)(num,368)(;,_)(else,_)(id,“inr”)(=,_)(id,“inr”)(*,_)(id,“inr”)(;,_)第8页，本讲稿共73页n剔除空白符和注释剔除空白符和注释空白符包括空格、制表符、换行符等。空白符包括空格、制表符、换行符等。n常数常数把数字组合成常数，用一个单词类别（例如把数字组合成常数，用一个单词类别（例如num）来表示所有的常数，而常数的值作为单词（这里是来表示所有的常数，而常数的值作为单词（这里是num）的值。单词和单词的值一起传递给语法分析）的值。单词和单词的值一起传递给语法分析器。例如，输入器。例如，输入31+28+59经过词法分析输出经过词法分析输出(num,31)(+,_)(num,28)(+,_)(num,59)。第9页，本讲稿共73页n识别标识符和关键字识别标识符和关键字用一个单词类别（例如用一个单词类别（例如id）来表示所有的标识符。当）来表示所有的标识符。当输入流中出现形成标识符的字符串时，字符串存储在输入流中出现形成标识符的字符串时，字符串存储在符号表的一个表项中，而指向该表项的指针则成为单符号表的一个表项中，而指向该表项的指针则成为单词（这里是词（这里是id）的值。）的值。由于关键字通常也满足标识符的形成规则，所以要由于关键字通常也满足标识符的形成规则，所以要区别关键字和标识符，一个简单的办法是把所有关区别关键字和标识符，一个简单的办法是把所有关键字保存在一张表中，通过查表，不是关键字的就键字保存在一张表中，通过查表，不是关键字的就是标识符。是标识符。第10页，本讲稿共73页n词法词法 分析器的接口分析器的接口词法分析器介于语法分析器和源程序字符输入词法分析器介于语法分析器和源程序字符输入流之间，并与这两者交互。词法分析阶段从输流之间，并与这两者交互。词法分析阶段从输入字符流读字符并形成单词，然后将生成的单入字符流读字符并形成单词，然后将生成的单词极其值传递给编译器的下一个阶段。词极其值传递给编译器的下一个阶段。输入输入词法分析器词法分析器语法分析器语法分析器读字符读字符回退字符回退字符传递单词传递单词及其值及其值第11页，本讲稿共73页在某些情况下，词法分析器在把单词传给语法分在某些情况下，词法分析器在把单词传给语法分析器之前，需要从输入串超前地读入一些字符，析器之前，需要从输入串超前地读入一些字符，以确定需要传递给语法分析器的正确单词。例如，以确定需要传递给语法分析器的正确单词。例如，词法分析器在读到词法分析器在读到字符时需要读入下一个字符。字符时需要读入下一个字符。如果下一个字符是如果下一个字符是=，则词法分析器把，则词法分析器把=组合在组合在一起作为形成一起作为形成“大于等于大于等于”操作符单词的字符串；操作符单词的字符串；否则把否则把作为形成作为形成“大于大于”操作符单词的字符串，操作符单词的字符串，这时词法分析器已经多读了一个字符。多读入的这时词法分析器已经多读了一个字符。多读入的字符必须退回给输入流，因为它可能是下一个单字符必须退回给输入流，因为它可能是下一个单词的开始符号。词的开始符号。第12页，本讲稿共73页3.2 单词的描述单词的描述正规表达式正规表达式n正规表达式正规表达式(Regular Expression)n正规表达式正规表达式用来表示字符串的结构。用来表示字符串的结构。n一个正规表达式一个正规表达式r完全由它所匹配的串集来完全由它所匹配的串集来定义。反过来，这个集合称为由该正规表定义。反过来，这个集合称为由该正规表达式表示的达式表示的正规集正规集或生成的语言，写作或生成的语言，写作L(r)。n正规表达式简称正规表达式简称正规式正规式。第13页，本讲稿共73页程序设计语言的单词就是具有特定格式的字符串，所以我们程序设计语言的单词就是具有特定格式的字符串，所以我们可以用正规表达式来定义单词。例如，可以用正规表达式来定义单词。例如，如果字母用如果字母用letter表示，表示，数字用数字用digit表示，则标识符集可以用正规表达式定义为表示，则标识符集可以用正规表达式定义为letter(letter|digit)*其中，其中，letter与与(letter|digit)*的并置表示两者的连接；的并置表示两者的连接；“|”表示两个表达式二者选一，表示两个表达式二者选一，letter|digit 表示在表示在letter和和digit中两者选一；中两者选一；“*”表示零次或多次引用表示零次或多次引用“*”标记的表达标记的表达式，式，(letter|digit)*是是letter|digit的零次或多次并置，即表示长的零次或多次并置，即表示长度为度为0,1,2,的字母数字串。的字母数字串。letter(letter|digit)*表示字母开头表示字母开头的字母数字串，也即标识符集。的字母数字串，也即标识符集。letter(letter|digit)*就是表示标识符的正规表达式，而标识就是表示标识符的正规表达式，而标识符集就是这个正规表达式所表示的正规集。符集就是这个正规表达式所表示的正规集。第14页，本讲稿共73页n对于给定的字母表对于给定的字母表，正规式和正规集的递归定义：，正规式和正规集的递归定义：(1)和和 都是都是 上的正规式，表示的正规集分别为上的正规式，表示的正规集分别为 和和。(2)对任何对任何a，a是是 上的正规式，表示的正规集为上的正规式，表示的正规集为a。(3)如如果果R和和S是是 上上的的正正规规式式，它它们们所所表表示示的的正正规规集集分分别别为为L(R)和和L(S)，则：，则：R|S是是 上的正规式，表示的正规集为上的正规式，表示的正规集为L(R)L(S)；R S是是 上的正规式，表示的正规集为上的正规式，表示的正规集为L(R)L(S)；(R)*是是 上的正规式，它所表示的正规集为上的正规式，它所表示的正规集为(L(R)*；(R)也是也是 上的正规式，它所表示的正规集为上的正规式，它所表示的正规集为L(R)。(4)仅仅由由有有限限次次使使用用规规则则(1)(3)得得到到的的表表达达式式是是 上上的的正正规规式式，它它所表示的集合是所表示的集合是 上的正规集。上的正规集。第15页，本讲稿共73页n正正规规式式间间的的运运算算符符“|”表表示示或或，“”表表示示连连接接（通通常常可可省省略略），“*”表表示示闭闭包包，使使用用括括号号可可以以改改变变运运算算的的次次序序。如如果果规规定定“*”优优先先于于“”，“”优优先先于于“|”，则则在在不不出出现现混混淆淆的的情情况况下下括括号号也可以省去。也可以省去。n注注意意正正规规表表达达式式a、字字符符串串a和和符符号号a这这三三者者的的含含义义是是不不同同的的，我我们们可可以以从从上上下下文文中中清清楚楚地地区区分分出所谈到的出所谈到的a的具体含义。的具体含义。n对对于于 上上的的正正规规式式R和和S，如如果果它它所所表表示示的的正正规规集集L(R)=L(S)，则称，则称R和和S等价，并记为等价，并记为R=S。第16页，本讲稿共73页n正规表达式的性质正规表达式的性质(1)交换律：交换律：R|S=S|R。(2)结合律：结合律：R|(S|T)=(R|S)|T；R(ST)=(RS)T。(3)分配律：分配律：R(S|T)=RS|RT；(R|S)T=RT|ST。(4)同一律：同一律：R=R =R。(5)幂等律：幂等律：R*=R*第17页，本讲稿共73页n例例3-2 令令=a,bnL(a|b)=a,b。nL(a|b)(a|b)=aa,ab,ba,bb，表示同样集合的另一正，表示同样集合的另一正规表达式可以是规表达式可以是aa|ab|ba|bb。nL(a*)=,a,aa,aaa,。nL(a|b)*)=,a,b,aa,ab,ba,bb,aaa,aab,aba,abb,baa,bab,aba,bbb,，表示由零个或多个，表示由零个或多个a或或b构构成的字符串集合，即由成的字符串集合，即由a和和b构成的所有字符串的集构成的所有字符串的集合。也可用正规表达式合。也可用正规表达式(a*b*)*来表示。来表示。nL(a|a*b)=a,b,ab,aab,aaab,，表示包含串，表示包含串a和零个或多和零个或多个个a后跟随一个后跟随一个b构成的字符串集合。构成的字符串集合。第18页，本讲稿共73页n例例3-3 证明：设证明：设L(a+)=a*-，则有，则有a+=aa*。证明证明 L(a+)=a*-=,a,a2,a3,-=a,a2,a3,=a,a,a2,=aa*=L(a)L(a*)=L(aa*)故故 a+=aa*第19页，本讲稿共73页3.3 单词的识别单词的识别n状态转换图状态转换图(state transition diagram)n在词法分析中，可以用状态转换图识别单词。在词法分析中，可以用状态转换图识别单词。n状态转换图是有向图，结点代表状态，用圆圈表示；状态转换图是有向图，结点代表状态，用圆圈表示；结点之间可由有向边连接，有向边上可标记字符。结点之间可由有向边连接，有向边上可标记字符。从结点从结点i指向结点指向结点j标记字符标记字符x的有向边表示在状态的有向边表示在状态i下，下，若输入字符为若输入字符为x，则读入，则读入x并转换到状态并转换到状态j。ijx第20页，本讲稿共73页n状态（即结点）数是有限的，其中必有一初始状态（简称状态（即结点）数是有限的，其中必有一初始状态（简称初态，一般用初态，一般用start标记）以及若干终止状态（简称终标记）以及若干终止状态（简称终态），终止状态的结点用双圈表示以区别于其它状态。态），终止状态的结点用双圈表示以区别于其它状态。n从初态出发，状态转换图有向边上的字符逐个与输入字从初态出发，状态转换图有向边上的字符逐个与输入字符匹配，若达到终态，则输入字符构成该状态转换图识符匹配，若达到终态，则输入字符构成该状态转换图识别出的一个单词。别出的一个单词。第21页，本讲稿共73页标识符及无符号数的状态转换图标识符及无符号数的状态转换图(a)标标识识符符；(b)无无符符号号整整数数；(c)无无符符号号数数例如，用于识别标识符、无符号整数、无符号数的状态转换例如，用于识别标识符、无符号整数、无符号数的状态转换图，其初始状态均用图，其初始状态均用0状态表示。状态表示。第22页，本讲稿共73页n某些终止状态是在读入了一个其它不属于该单词的符号某些终止状态是在读入了一个其它不属于该单词的符号后才得到相应的单词编码的，这表明在识别单词的过程后才得到相应的单词编码的，这表明在识别单词的过程中多读入了一个符号，所以识别出单词后应将最后多读中多读入了一个符号，所以识别出单词后应将最后多读入的这个符号予以回退；我们对此类情况的处理是在终入的这个符号予以回退；我们对此类情况的处理是在终态上以态上以“*”作为标识。作为标识。n以模式以模式“=”和和“”的状态转换图为例。的状态转换图为例。0678start=*other第23页，本讲稿共73页n状态转换图的实现状态转换图的实现n状态转换图非常容易用程序实现，最简单的办法是让每状态转换图非常容易用程序实现，最简单的办法是让每个状态对应一小段程序。个状态对应一小段程序。n对于不含回路的分支状态来说，可以让它对应一个对于不含回路的分支状态来说，可以让它对应一个switch()语句或一组语句或一组if-else语句。语句。n对于含回路的状态来说，可以让它对应一个对于含回路的状态来说，可以让它对应一个while语语句。句。n终态一般对应一个终态一般对应一个return()语句；语句；return意味着从词法分意味着从词法分析器返回到调用段，一般指返回到语法分析器。析器返回到调用段，一般指返回到语法分析器。n程序的大小与图中状态数和边数成正比。程序的大小与图中状态数和边数成正比。第24页，本讲稿共73页C语言子集的单词符号及内码值语言子集的单词符号及内码值单词单词种别编码种别编码助记符助记符内码值内码值while1whileif2ifelse3elseswitch4switchcase5case标识符标识符6idid在符号表中的位置在符号表中的位置常数常数7numnum在常数表中的位置在常数表中的位置+8+9*10*=11relopLE11relopLT=11relopEQ=12=；13；综合例子：一个综合例子：一个C语言子集的简单词法分析器语言子集的简单词法分析器第25页，本讲稿共73页简单词法分析的状态转换图简单词法分析的状态转换图 第26页，本讲稿共73页(1)character：字字符符变变量量，存存放放最最新新读读入入的的源源程程序序字字符。符。(2)token：字符数组，用来存放构成单词的字符串。：字符数组，用来存放构成单词的字符串。(3)getbe()：过滤空白字符。：过滤空白字符。(4)concatenation()：将：将token中的字符串与中的字符串与character中的字符连接作为中的字符连接作为token中新的字符串。中新的字符串。(5)letter()和和digit()：判判断断character中中的的字字符符是是否否为为字字母母和和数数字字的的布布尔尔函函数数，是是则则返返回回true，否否则返回则返回false。第27页，本讲稿共73页(6)reserve()：按按token数数组组中中的的字字符符串串查查表表判判别别其其是是否否为为保保留留字字，若若是是保保留留字字则则返返回回它它的的编编码码，否否则则返回返回0值。值。(7)retract()：扫描指针回退一个字符，同时将：扫描指针回退一个字符，同时将character置为空白。置为空白。(8)buildlist()：将将标标识识符符登登录录到到符符号号表表或或将将常常数数登登录录到常数表。到常数表。(9)error()：出现非法字符，显示出错信息。：出现非法字符，显示出错信息。第28页，本讲稿共73页token0=0;/*对对token数组初始化数组初始化*/s=getchar();getbe();/*滤除空格滤除空格*/switch(s)case a:case b:case Z:第29页，本讲稿共73页 while(letter()digit()concatenation();/*将当前读入的字符送入将当前读入的字符送入token数组数组*/getchar();retract();/*扫描指针回退一个字符扫描指针回退一个字符*/c=reserve();if(c=0)buildlist();/*将标识符登录到符号表中将标识符登录到符号表中*/return(id，指向指向id的符号表入口指针的符号表入口指针);第30页，本讲稿共73页else return(保留字码保留字码，null);case 0:case 1:case 9:while(digit()concatenation();getchar();第31页，本讲稿共73页retract();buildlist();/*将常数登录到常数表中将常数登录到常数表中*/return(num，num的常数表入口指针的常数表入口指针);case+:return(+，null);case-:return(-，null);case*:return(*，null);第32页，本讲稿共73页case:getchar();if(character=)return(relop,LE);else retract();return(relop，LT);case=:getchar();第33页，本讲稿共73页if(character=)return(relop,EQ);else retract();return(=,_);case;:return(;,_);default:error();第34页，本讲稿共73页3.4 有穷自动机有穷自动机有穷自动机（有穷自动机（FA,finite automata）是更一般化的状态）是更一般化的状态转换图，它分为确定有穷自动机转换图，它分为确定有穷自动机DFA和非确定有穷自和非确定有穷自动机动机NFA两种。两种。可以通过构造有穷自动机从正规表达式导出识别正可以通过构造有穷自动机从正规表达式导出识别正规集的识别器。确定和不确定的有穷自动机都能而规集的识别器。确定和不确定的有穷自动机都能而且仅能识别正规集，即它们能够识别正规表达式所且仅能识别正规集，即它们能够识别正规表达式所表示的语言。表示的语言。确定的有穷自动机导出的识别器比不确定的有穷自动确定的有穷自动机导出的识别器比不确定的有穷自动机导出的识别器快得多，但确定的有穷自动机可能比机导出的识别器快得多，但确定的有穷自动机可能比与之等价的不确定的有穷自动机大得多。与之等价的不确定的有穷自动机大得多。第35页，本讲稿共73页3.4.1 确确定定有有穷穷自自动动机机(DFA,deterministic finite automata)n定定义义：一一个个确确定定的的有有穷穷自自动动机机Md（记记为为DFA Md）是一个五元组是一个五元组Md=(S,f,s0,Z)，其中：，其中：(1)S是一个有穷状态集；是一个有穷状态集；(2)是一个有穷输入字母表；是一个有穷输入字母表；(3)f是是一一个个从从S到到S的的单单值值映映射射，叫叫做做转转换换函函数数，即即f(si,a)=sj且有且有si、sj S和和a；(4)s0 S，是惟一的一个初态；，是惟一的一个初态；(5)Z S，是一个终态集。，是一个终态集。第36页，本讲稿共73页n例例3-4 DFA M=(S,U,V,Q,a,b,f,S,Q)，其中，其中f(S,a)=Uf(V,a)=Uf(S,b)=Vf(V,b)=Qf(U,a)=Qf(Q,a)=Qf(U,b)=Vf(Q,b)=QSUVQababbaa,b第37页，本讲稿共73页有穷自动机也可以用状态转换矩阵表示。状态转有穷自动机也可以用状态转换矩阵表示。状态转换矩阵的行表示状态，列表示输入符号，矩阵元换矩阵的行表示状态，列表示输入符号，矩阵元素表示素表示f(si,a)的值。用的值。用“”标明初态；否则第标明初态；否则第一行即是初态，相应终态行在表的右端标以一行即是初态，相应终态行在表的右端标以1，非，非终态端标以终态端标以0。字符字符状态状态abSUV0UQV0VUQ0QQQ1第38页，本讲稿共73页对于对于*中的任何字符串中的任何字符串t，若存在一条从初态结，若存在一条从初态结点到某一终态结点的路径，且这条路径上所有点到某一终态结点的路径，且这条路径上所有边的标记字符连接成的字符串等于边的标记字符连接成的字符串等于t，则称，则称t可为可为DFA M所接受（识别）。所接受（识别）。DFA M所能接受的字符串的全体称作所能接受的字符串的全体称作M接受的语言，接受的语言，记为记为L(M)。上的一个字符串集合上的一个字符串集合V*是正规的，当且仅当是正规的，当且仅当存在一个存在一个 上的确定有穷自动机上的确定有穷自动机M，使得，使得V=L(M)。第39页，本讲稿共73页例例3-5 接受正规表达式接受正规表达式(a|b)*abb表示的正规集的表示的正规集的DFA。第40页，本讲稿共73页3.4.2 非非确确定定有有穷穷自自动动机机(NFA,nondeterministic finite automata)一一个个非非确确定定有有穷穷自自动动机机Mn（记记为为NFA Mn）是是一一个五元组个五元组Mn=(S,f,Q,Z)，其中：，其中：(1)S、Z的意义与的意义与DFA相同；相同；(2)f是一个从是一个从S*到到2S的映射，其中的映射，其中2S表示表示S的幂集；的幂集；(3)Q S，是一个非空初态集。，是一个非空初态集。第41页，本讲稿共73页nNFA和和DFA的区别的区别nNFA可以有若干个初始状态，而可以有若干个初始状态，而DFA仅有一个初始状态；仅有一个初始状态；nNFA的的f不不是是一一个个函函数数，而而是是一一个个多多值值映映射射，即即f(si,a)=某某些些状状态态的的集集合合（si S），它它表表示示不不能能由由当当前前状状态态和和当当前前输输入入字字符符惟惟一一地地确确定定下下一一个个要要转转换换的的状状态态，也也即即允允许许同同一一个个状状态态对对同同一一个个输输入入字字符符可可以以有有不不同同的的输输出出边。边。第42页，本讲稿共73页例例3-6一个一个NFAM=(0,1,2,3,4,a,b,f,0,2,4)，其中，其中f(0,a)=0,3f(2,b)=2f(0,b)=0,1f(3,a)=4f(1,b)=2f(4,a)=4f(2,a)=2f(4,b)=4识别那些含有相继两个识别那些含有相继两个a或相继两个或相继两个b的串。的串。01234a,ba,ba,bbbaa第43页，本讲稿共73页例例3-7 接受正规表达式接受正规表达式(a|b)*abb表示的正规集的表示的正规集的NFA。第44页，本讲稿共73页n自动机的等价自动机的等价n定义：对于任何两个有穷自动机定义：对于任何两个有穷自动机M和和M，如果如果L(M)=L(M)，则称，则称M与与M等价等价。n结论：结论：nDFA是是NFA的特例。的特例。n对于每个对于每个NFA M都存在一个都存在一个DFA M，使得，使得L(M)=L(M)。n所以所以DFA与与NFA的描述能力相同。的描述能力相同。第45页，本讲稿共73页3.4.3 从从NFA到到DFA的变换的变换对给定的对给定的NFA相应地构造出一个与之等价的相应地构造出一个与之等价的DFA，使，使它们能够识别相同的语言。采用子集法来对它们能够识别相同的语言。采用子集法来对NFA M确确定化。定化。n定义定义n-closure(I)：状态集：状态集I的的-闭包。状态集闭包。状态集I中的任何状中的任何状态态s经任意条连续的经任意条连续的 边能到达的状态的集合。边能到达的状态的集合。nmove(I,a)：状态集：状态集I中的任何状态中的任何状态s经过一条经过一条a边能到达的边能到达的状态的集合。状态的集合。nIa=-closure(move(I,a)：第46页，本讲稿共73页n例例3-8 已知一状态转换图如图所示，且假定已知一状态转换图如图所示，且假定I=-closure(1)=1,2，试求从状态，试求从状态I出发经过一条出发经过一条有向边有向边a而能到达的状态集而能到达的状态集J和和-closure(J)。解解答答从从状状态态I中中的的状状态态1或或状状态态2出出发发经经过过一一条条a弧而能到达的状态集弧而能到达的状态集J为为J=move(I,a)=4,5,3若若si J，则由，则由si出发经过任意条出发经过任意条 有向边而能到达的有向边而能到达的任何状态任何状态sj-closure(J)，因此，因此-closure(J)=4,7,5,6,2,3,8第47页，本讲稿共73页n子集法对子集法对NFA确定化确定化n(1)构构造造一一张张转转换换表表，其其第第一一列列为为状状态态子子集集I，对不同的，对不同的a(a)在表中单设一列在表中单设一列Ia。n(2)表表的的第第一一行行第第一一列列其其状状态态子子集集I为为-closure(Q)；其中，；其中，Q为初始状态集合。为初始状态集合。n(3)根根据据第第一一列列中中的的I为为每每一一个个a求求其其Ia并并记记入入对对应应的的Ia列列中中，如如果果此此Ia不不同同于于第第一一列列已已存存在在的的所所有有状状态态子子集集I，则则将将其其顺顺序序列列入入空空行中的第一列。行中的第一列。第48页，本讲稿共73页n(4)重重复复步步骤骤(3)直直至至对对每每个个I及及a均均已已求求得得Ia，并并且且无无新新的的状状态态子子集集Ia加加入入第第一一列列时时为为止；此过程可在有穷步后终止。止；此过程可在有穷步后终止。n(5)重新命名第一列的每一状态子集，则重新命名第一列的每一状态子集，则转换表便成为新的状态转换矩阵，其状态转换表便成为新的状态转换矩阵，其状态转换函数转换函数f是是S到到S的单值映射，即为与的单值映射，即为与NFA M等价的等价的DFA M。n(6)第一列的第一个状态子集作为第一列的第一个状态子集作为DFA M的初态，包含的初态，包含NFA M终态的状态子集作为终态的状态子集作为DFA M的终态。的终态。第49页，本讲稿共73页n例例3-9 正规表达式正规表达式(a b)*(aa bb)(a b)*的的NFA M如图如图所示，试将其确定化为所示，试将其确定化为DFA M。第50页，本讲稿共73页IIaIbX,1,21,2,31,2,41,2,31,2,3,5,6,Y1,2,41,2,41,2,31,2,4,5,6,Y1,2,3,5,6,Y1,2,3,5,6,Y1,2,4,6,Y1,2,4,5,6,Y1,2,3,6,Y1,2,4,5,6,Y1,2,4,6,Y1,2,3,6,Y1,2,4,5,6,Y1,2,3,6,Y1,2,3,5,6,Y1,2,4,6,Y第51页，本讲稿共73页Sab012132214335464564635第52页，本讲稿共73页01426578910bbb3aa012473861247561427IIaIb0,1,2,4,73,8,6,7,1,2,45,6,7,1,2,41,2,3,4,6,7,83,8,6,7,1,2,45,9,6,7,1,2,41,2,4,5,6,73,8,6,7,1,2,45,6,7,1,2,41,2,4,5,6,7,93,8,6,7,1,2,45,10,6,7,1,2,41,2,4,5,6,7,103,8,6,7,1,2,45,6,7,1,2,4第53页，本讲稿共73页3.4.4 确定有穷自动机的化简确定有穷自动机的化简（最小化）（最小化）n化简条件：接受的语言必须相同n化简(最小化)算法基本思想划分法n1.将DFA M中的状态划分为互不相交的子集，每个子集内部的状态都等价状态都等价；而在不同子集间的状态状态均不等价不等价。n2.从每个子集中任选一个状态作为代表，消去其它等价状态。n3.把那些原来射入其它等价状态的弧改为射入相应的代表状态。第54页，本讲稿共73页n状态等价：设状态等价：设DFA M中有两个状态中有两个状态s,t，ns,t 等价：如果从等价：如果从s出发能识别字符串出发能识别字符串 而而停于终态，从停于终态，从t出发也同样能够识别这个出发也同样能够识别这个 而停于终态；反之，若从而停于终态；反之，若从t出发能识别出发能识别 而而停于终态，则从停于终态，则从s出发也能识别这个出发也能识别这个 而停而停于终态，则称于终态，则称s和和t是等价的。是等价的。ns,t可区别可区别：如果：如果s,t不等价，则称为不等价，则称为s,t可可区别。区别。第55页，本讲稿共73页DFA M的化简方法如下：的化简方法如下：(1)首首先先将将DFA M的的状状态态集集S中中的的终终态态与与非非终终态态分分开开，形形成成两两个子集，即得到基本划分。个子集，即得到基本划分。(2)对对当当前前已已划划分分出出的的I(1)、I(2)、I(m)子子集集（属属于于不不同同子子集集的的状状态态是是可可区区分分的的），看看每每一一个个I(i)是是否否能能进进一一步步划划分分；也也即即对对某某个个I(i)=s1,s2,sk，若若存存在在一一个个输输入入字字符符a（a）使使得得Ia(i)不不全全包包含含在在当当前前划划分分的的某某一一子子集集I(j)中中（即即跨跨越到两个子集），就将越到两个子集），就将I(i)一分为二。一分为二。第56页，本讲稿共73页(3)重重复复步步骤骤(2)，直直到到子子集集个个数数不不再再增增加加为为止止（即即每每个个子子集集已已是是不不可可再再分分的的了了）。所所谓谓不不能能划划分分，是是指指该该子子集集或或者者仅仅有有一一个个状状态态，或或者者虽虽有有多多个状态但这些状态均不可区分（即等价）。个状态但这些状态均不可区分（即等价）。第57页，本讲稿共73页假假定定当当前前子子集集I(i)=s1,s2,，且且状状态态s1和和s2经经过过有有向向边边a分分别别到到达达状状态态t1和和t2，而而t1和和t2又又分分属属于于当当前前已已划划分分出出的的两两个个不不同同子子集集I(j)和和I(k)，则则此此时时应应将将I(i)分分为为两两部部分分，使使得得一一部部分分含有含有s1：I(i1)=s sI(i)且且s经有向边经有向边a到达到达t1而另一部分含有而另一部分含有s2：I(i2)=I(i)I(i1)由由于于t1和和t2是是可可区区分分的的，即即存存在在一一个个字字符符串串，t1将将读读出出 而而停停于于终终态态，而而t2或或读读不不出出 或或者者可可以以读读出出 但但不不能能到到达达终终态态。因因此此，字字符符串串 将将把把状状态态s1和和s2区区分分开开来来，也也就就是是说说，I(i1)中中的状态与的状态与I(i2)中的状态是可区分的。中的状态是可区分的。若若I(i)中中含含有有原原来来的的初初态态，就就是是DFA M中中的的新新初初态态。若若I(i)中含有原来的终态，就是中含有原来的终态，就是DFA M中的新终态。中的新终态。第58页，本讲稿共73页例例3-10 化简由例化简由例3-9得到的得到的DFA。(1)首首先先将将状状态态集集S=0,1,2,3,4,5,6划划分分为为终终态态集集3,4,5,6和非终态集和非终态集0,1,2。(2)考考察察0,1,2a：因因0a=2a=1，而而1a=3，分分属属于于非非终终态态集和终态集，故将集和终态集，故将0,1,2划分为划分为0,2和和1。(3)考考察察0,2b：0b=2，2b=4，它它们们分分属属于于两两个个不不同同的的状态集，故状态集，故0,2划分为划分为0和和2。(4)考察考察3,4,5,6a：3a=6a=3 3,4,5,6；4a=5a=6 3,4,5,6，即都属于终态集，故不进行划分。，即都属于终态集，故不进行划分。(5)考察考察3,4,5,6b：3b=6b=5 3,4,5,6；4b=5b=4 3,4,5,6，即都属于终态集，故不进行划分。，即都属于终态集，故不进行划分。(6)按顺序重新命名状态子集按顺序重新命名状态子集0、1、2、3,4,5,6为为0、1、2、3，则得到化简后的状态转换矩阵和，则得到化简后的状态转换矩阵和DFA M。第59页，本讲稿共73页Sab012132213333第60页，本讲稿共73页3.4.5 从正规表达式到从正规表达式到NFA由正规表达式构造等价的由正规表达式构造等价的NFA M的方法如下：的方法如下：(1)将正规表达式将正规表达式R表示成如图所示的拓广转换图。表示成如图所示的拓广转换图。其中其中X为初始状态，为初始状态，Y为终止状态为终止状态(2)对对正正规规表表达达式式采采用用下下图图所所示示的的三三条条转转换换规规则则来来构造构造NFA M。第61页，本讲稿共73页转换规则转换规则第62页，本讲稿共73页对对于于给给定定的的正正规规表表达达式式R，首首先先将将其其表表示示成成拓拓广广转转换换图图的的形形式式；然然后后逐逐步步将将这这个个拓拓广广转转换换图图运运用用三三条条转转换换规规则则不不断断加加入入新新结结点点进进行行分分解解，直直至至每每条条有有向向边边上上仅仅标标识识有有 的的一一个个字字母母或或 为为止止，则则NFA M构造完成。构造完成。第63页，本讲稿共73页例例3-11 对给定正规表达式对给定正规表达式b*(d|ad)(b|ab)+构造其构造其NFA M。先用先用R+=RR*改造题设的正规表达式为改造题设的正规表达式为b*(d|ad)(b|ab)(b|ab)*，然后构造其，然后构造其NFA M，如图所示。，如图所示。第64页，本讲稿共73页正则文法与正则表达式的等价性n1.正则文法正则表达式n对于已给的正规文法G，构造一相应的正规式R，使L(R)=L(G)。n思路：将所给的正规文法G视为定义各非终结符号所产生的正规集的一个联立方程组，再通过解此联立方程组以求得相应的正规式。第65页，本讲稿共73页1.正则文法正则表达式规则1规则2规则3文法产生式正则表达式AxB,ByAxA|yAx,AyA=xyA=x*y A=x|y步骤1 将每条产生式改写为正则表达式；步骤2 用代入法解正则表达式方程组，最后只剩下一个开始符号定义的正则表达式，其中不含非终结符。正则文法与正则表达式的等价性正则文法与正则表达式的等价性第66页，本讲稿共73页【例】GS:SaA|a AdA|dS=aA|aA=d*d代入:S=ad*d|a ad*2022年10月7日67规则1规则2规则3文法产生式正则表达式AxB,ByAxA|yAx,AyA=xyA=x*y A=x|y第67页，本讲稿共73页例：有正则文法如下，将其换成等价的正则表达式。S aS|aBB bCC aCC a将文法改写成如下：S=a*aBB=bCC=a*a解方程组得：C=a*aB=ba*aS=a*aba*a最终转成正则表达式S=a*aba*a2022年10月7日68规则1规则2规则3文法产生式正则表达式AxB,ByAxA|yAx,AyA=xyA=x*y A=x|y第68页，本讲稿共73页 2022年10月7日 2.正则表达式正则文法(右线性)步骤1 构造 SR（正则表达式）步骤2 不断利用规则做变换,直到每个产生式最多含有一个终结符为止 规则1规则2规则3文法产生式正则表达式AxB,ByAxA|yAx,AyA=xyA=x*yA=x|y69第69页，本讲稿共73页【例】求正则表达式(a|b)(a|b|0|1)*对应的正则文法（右线性）S(a|b)(a|b|0|1)*S(a|b)AaA|bA|0A|1A|GS：SaA|bAAaA|bA|0A|1A|A(a|b|0|1)*规则1规则2规则3文法产生式正则表达式AxB,ByAxA|yAx,AyA=xyA=x