编译原理(第二版)第4章 词法分析.ppt

《编译原理(第二版)第4章 词法分析.ppt》由会员分享，可在线阅读，更多相关《编译原理(第二版)第4章 词法分析.ppt（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章第四章 词法分析词法分析n教学要求：教学要求：本章介绍编译程序的第一个阶本章介绍编译程序的第一个阶段词法分析的设计原理，要求掌握正则文段词法分析的设计原理，要求掌握正则文法、法、DFADFA、NFANFA、正规式和正规集的基本概、正规式和正规集的基本概念和词法分析器的设计原理。念和词法分析器的设计原理。n教学重点：教学重点：词法分析器的任务与设计，状词法分析器的任务与设计，状态转换图。态转换图。4.1 4.1 词法分析程序的设计词法分析程序的设计回顾：回顾：1 1、词法分析的任务：、词法分析的任务：逐个读入源程序字符并按逐个读入源程序字符并按照构词规则切分成一系列单词。照构词规则切分成一

2、系列单词。2 2、词法分析程序：实现词法分析的程序。、词法分析程序：实现词法分析的程序。一一.词法与语法分析程序的接口词法与语法分析程序的接口方式方式1 1、作为独立的一遍、作为独立的一遍2 2、语法分析结合在一起作为一遍、语法分析结合在一起作为一遍单词符号单词符号n单词符号一般可分为下列五种：单词符号一般可分为下列五种：n n基本字基本字基本字基本字（关键字关键字关键字关键字）：）：begin,end,if,whilebegin,end,if,while等等n n标识符标识符标识符标识符：各种名称，如常量名、变量名、过程：各种名称，如常量名、变量名、过程名等名等n n常数常数常数常数（量）：

3、（量）：25,3.1415,25,3.1415,TRUE,“ABC”TRUE,“ABC”等等n n运算符运算符运算符运算符：如：如+-*/=+-*/=等等n n界符界符界符界符：逗号，分号，括号等：逗号，分号，括号等二、输出表示：（单词种别，单词自身的值）二、输出表示：（单词种别，单词自身的值）A:=B+2A:=B+2(id,(id,指向指向A A的符号表的入口指针）的符号表的入口指针）(id,(id,指向指向B B的符号表的入口指针的符号表的入口指针)(num,2)num,2)三、词法分析工作独立的原因：三、词法分析工作独立的原因：1 1、简化设计、简化设计2 2、改进编译效率、改进编译效率

4、3 3、增加编译系统的可移植性、增加编译系统的可移植性 4.2 4.2 单词的描述工具单词的描述工具一、正规文法：一、正规文法：文法文法G=G=（V VN N，V VT T，P P，S S），），P P中每一中每一产生式的形式都为：产生式的形式都为：AaBAaB或或AaAa，其中其中AVAVN N ，BVBVN N ，aVaVT T几类单词的描述几类单词的描述n n标识符标识符标识符标识符：标识符标识符标识符标识符l|ll|ll|ll|l字母数字字母数字字母数字字母数字字母数字字母数字字母数字字母数字l|d|ll|d|ll|d|ll|d|l字母数字字母数字字母数字字母数字|d d d d字母数

5、字字母数字字母数字字母数字n n无符号整数无符号整数无符号整数无符号整数：无符号整数无符号整数无符号整数无符号整数d|dd|dd|dd|d无符号整数无符号整数无符号整数无符号整数n n运算符运算符运算符运算符：运算符运算符运算符运算符+|-|*|/|=|=|-|*|/|=|=|-|*|/|=|=|-|*|/|=|=n n界符界符界符界符：界符界符界符界符,|;|(|)|,|;|(|)|,|;|(|)|,|;|(|)|二、正规式二、正规式(regular expression)regular expression)（一）定义（一）定义（一）定义（一）定义（正规式正规式正规式正规式和它所表示的和它

6、所表示的和它所表示的和它所表示的正规集正规集正规集正规集）：）：）：）：设字母表为设字母表为设字母表为设字母表为 ，辅助字母表，辅助字母表，辅助字母表，辅助字母表 =，(，)。1 1 1 1、和和和和 都是都是都是都是 上的正规式，它们所表示的正规集分别为上的正规式，它们所表示的正规集分别为上的正规式，它们所表示的正规集分别为上的正规式，它们所表示的正规集分别为 和和和和 ；2 2 2 2、任何、任何、任何、任何a a a a ，a a a a是是是是 上的一个正规式，它所表示的正规集上的一个正规式，它所表示的正规集上的一个正规式，它所表示的正规集上的一个正规式，它所表示的正规集为为为为 aa

7、aa；3 3 3 3、假定假定假定假定e e e e1 1 1 1和和和和e e e e2 2 2 2都是都是都是都是 上的正规式，它们所表示的正规集分上的正规式，它们所表示的正规集分上的正规式，它们所表示的正规集分上的正规式，它们所表示的正规集分别为别为别为别为L(eL(eL(eL(e1 1 1 1)和和和和L(eL(eL(eL(e2 2 2 2)，那么，那么，那么，那么，(e e e e1 1 1 1),),),),e e e e1 1 1 1 e e e e2 2 2 2,e e e e1 1 1 1 e e e e2 2 2 2,e e e e1 1 1 1 也都也都也都也都是正规式是

8、正规式是正规式是正规式,它们所表示的正规集分别为它们所表示的正规集分别为它们所表示的正规集分别为它们所表示的正规集分别为L(eL(eL(eL(e1 1 1 1),L(e),L(e),L(e),L(e1 1 1 1)L)L)L)L(e(e(e(e2 2 2 2),L(e),L(e),L(e),L(e1 1 1 1)L(e)L(e)L(e)L(e2 2 2 2)和和和和(L(eL(eL(eL(e1 1 1 1)。4 4 4 4、仅由有限次使用上述三步骤而定义的表达式才是、仅由有限次使用上述三步骤而定义的表达式才是、仅由有限次使用上述三步骤而定义的表达式才是、仅由有限次使用上述三步骤而定义的表达式才

9、是 上的上的上的上的正规式，仅由这些正规式所表示的字集才是正规式，仅由这些正规式所表示的字集才是正规式，仅由这些正规式所表示的字集才是正规式，仅由这些正规式所表示的字集才是 上的正规上的正规上的正规上的正规集。集。集。集。正规式中的符号说明：正规式中的符号说明：正规式中的符号说明：正规式中的符号说明：“”读为读为读为读为“或或或或”（也有使用也有使用也有使用也有使用“+”“+”“+”“+”代替代替代替代替 “”的）的）的）的）“”读为读为读为读为“连接连接连接连接”；“”读为读为读为读为“闭包闭包闭包闭包”（即，任意有限次的自重复连接）。（即，任意有限次的自重复连接）。（即，任意有限次的自重复

10、连接）。（即，任意有限次的自重复连接）。在不致混淆时，括号可省去，但规定算符的优先顺序为：在不致混淆时，括号可省去，但规定算符的优先顺序为：在不致混淆时，括号可省去，但规定算符的优先顺序为：在不致混淆时，括号可省去，但规定算符的优先顺序为：“”、“”、“”。连接符连接符连接符连接符“”一般可省略不写。一般可省略不写。一般可省略不写。一般可省略不写。“”、“”和和和和“”都是左结合的。都是左结合的。都是左结合的。都是左结合的。正规集是正规语言的另一种表示。正规集是正规语言的另一种表示。正规集是正规语言的另一种表示。正规集是正规语言的另一种表示。如：如：如：如：字母字母字母字母(数字数字数字数字|

11、字母字母字母字母)表示标识符。表示标识符。表示标识符。表示标识符。例令例令例令例令 =a a，b b，上的正规式和相应的正规集上的正规式和相应的正规集上的正规式和相应的正规集上的正规式和相应的正规集的例子有：的例子有：的例子有：的例子有：正规式正规式正规式正规式 正规集正规集正规集正规集a a aaa a b b a,ba,b abab abab(a(a b)(ab)(a b)b)aa,ab,ba,bbaa,ab,ba,bb a a ,a,aaa,aa,任意个任意个任意个任意个a a的串的串的串的串(a a b)b),a,b,aa,aba,b,aa,ab 所有由所有由所有由所有由a a 和和和

12、和b b组成的串组成的串组成的串组成的串(a a b)b)(aa(aa bb)(abb)(a b)b)上所有含有两个相上所有含有两个相上所有含有两个相上所有含有两个相继继继继 的的的的a a或两个相或两个相或两个相或两个相继的继的继的继的b b组成组成组成组成 的串的串的串的串 例例例例 =l l l l，dddd，r r r r=l(ll(ll(ll(l d)d)d)d)定义的正规集定义的正规集定义的正规集定义的正规集:l,ll,ld,lddl,ll,ld,lddl,ll,ld,lddl,ll,ld,ldd,（标识符）标识符）标识符）标识符）其中：其中：其中：其中：l l l l代表字母代表

13、字母代表字母代表字母,d d d d代表数字代表数字代表数字代表数字,正规式即是正规式即是正规式即是正规式即是 字母字母字母字母(字母字母字母字母|数字数字数字数字)它表示的正规集是它表示的正规集是它表示的正规集是它表示的正规集是“字母打头的字母数字串字母打头的字母数字串字母打头的字母数字串字母打头的字母数字串”。例例例例4.3 4.3 4.3 4.3 =d d d d，.，e e e e，+，-,-,-,-,则则则则 上的正规式上的正规式上的正规式上的正规式 ：d d d d (.dd(.dd(.dd(.dd )(e(+)(e(+)(e(+)(e(+-)dddddddd )表示的是无符号数的

14、集合。其中：表示的是无符号数的集合。其中：表示的是无符号数的集合。其中：表示的是无符号数的集合。其中：d d d d为为为为0-90-90-90-9的数字。的数字。的数字。的数字。（二）两个正规式（二）两个正规式等价等价n n若两个正规式若两个正规式e e1 1和和e e2 2所表示的所表示的正规集相同正规集相同,则说则说e e1 1和和e e2 2等价等价,写作写作e e1 1=e e2 2。例如：例如：例如：例如：e e e e1 1 1 1=(a=(a=(a=(a b)b)b)b)，e e e e2 2 2 2=b=b=b=b a a a a又如：又如：又如：又如：b(abb(abb(a

15、bb(ab)=(=(=(=(ba)ba)ba)ba)b b b b (a (a (a (a b)b)b)b)=(a=(a=(a=(a b b b b )（三）正规式的运算律（三）正规式的运算律n设设r,s,tr,s,t为正规式，正规式服从的代数规律有：为正规式，正规式服从的代数规律有：1 1、r r s=ss=s r r “或或”服从交换律服从交换律2 2、r r(s s t)=(t)=(r r s s)t “t “或或”的可结合律的可结合律3 3、(rs)trs)t=r(str(st)“连接连接”的可结合律的可结合律4 4、r(sr(s t)=t)=rsrs rtrt (s(s t)rt)r

16、=srsr trtr 分配律分配律 5 5、r=r,rr=r,r=r=r 是是“连接连接”的恒等元素的恒等元素6 6、r r r=rr=rr r=r r rrrr “或或”的抽取律的抽取律 三、正规文法到正规式三、正规文法到正规式n n1.1.1.1.将正规式转换成正规文法将正规式转换成正规文法将正规式转换成正规文法将正规式转换成正规文法 V V V VT T T T=,S S S S V V V VN N N N，（1 1 1 1）对正规式）对正规式）对正规式）对正规式r r r r，生成生成生成生成正规产生式正规产生式正规产生式正规产生式 S S S Sr r r r （2 2 2 2）若

17、）若）若）若x x x x和和和和y y y y都是正规式都是正规式都是正规式都是正规式 对形如对形如对形如对形如A A A Axyxyxyxy的的的的正规产生式：正规产生式：正规产生式：正规产生式：A A A AxBxBxBxB，B B B By y y y，B B B B V V V VN N N N 对形如对形如对形如对形如A A A Ax x x x y y y y的的的的正规产生式：正规产生式：正规产生式：正规产生式：A A A AxBxBxBxB，A A A Ay y y y，B B B BxBxBxBxB，B B B By y y y，B B B B V V V VN N N N

18、 对形如对形如对形如对形如A A A Ax x x x y y y y的的的的正规产生式正规产生式正规产生式正规产生式:A A A Ax x x x，A A A Ay y y y 不断应用上述规则做变换，直到每个产生式右端只含一个不断应用上述规则做变换，直到每个产生式右端只含一个不断应用上述规则做变换，直到每个产生式右端只含一个不断应用上述规则做变换，直到每个产生式右端只含一个V V V VT T T T对对对对 上的正规式上的正规式上的正规式上的正规式r,r,r,r,存在一个存在一个存在一个存在一个G=(VN,VT,P,S)G=(VN,VT,P,S)G=(VN,VT,P,S)G=(VN,VT

19、,P,S)使得使得使得使得L(G)=L(G)=L(G)=L(G)=L(rL(rL(rL(r)，反之亦然。反之亦然。反之亦然。反之亦然。n例例 r=a(a d)VT=a,d Sa(a d)SaA A(a d)A(a d)B A B(a d)B BGsGs:S SaAaA A A V VT T=a,da,d A AaBaBV VN N=S,A,B=S,A,B A AdBdB B BaBaB B BdBdB B Bn n2.2.2.2.将正规文法转换成正规式将正规文法转换成正规式将正规文法转换成正规式将正规文法转换成正规式 使用如下规则，最后只剩下一个开始符号定义使用如下规则，最后只剩下一个开始符号

20、定义的产生式，并且右部不含非终结符。的产生式，并且右部不含非终结符。规则规则1 1：A-A-xB,BxB,B-y =A=-y =A=xyxy规则规则2 2：A-A-xA|yxA|y =A=x =A=x*y y规则规则3 3：A-x,A-y =A=A-x,A-y =A=x|yx|y例如：文法例如：文法GSGS为：为：S-S-aAaA,S-a,A-,S-a,A-aAaA,A-,A-dAdA,A-a,A-d,A-a,A-dS=S=aA|aaA|aA=(A=(aA|dA)|(a|daA|dA)|(a|d)A=(A=(a|d)A|(a|da|d)A|(a|d)A=(A=(a|da|d)*(a|da|d)

21、=()=(a|da|d)+A A代入代入S S得：得：S=S=a(a|d)a(a|d)+|a|aS=S=a(a|d)a(a|d)+|）S=S=a(a|da(a|d)*所以，对应正规式为：所以，对应正规式为：a(a|da(a|d)*4.3 4.3 有穷自动机有穷自动机 有穷自动机有穷自动机(也称有限自动机也称有限自动机)是识别正规是识别正规集的装置。集的装置。一、确定的有穷自动机（一、确定的有穷自动机（一、确定的有穷自动机（一、确定的有穷自动机（DFADFADFADFA）1 1 1 1、定义、定义、定义、定义:一个确定的有穷自动机（一个确定的有穷自动机（一个确定的有穷自动机（一个确定的有穷自动机

22、（DFADFADFADFA）M M M M是一个五元组：是一个五元组：是一个五元组：是一个五元组：M=M=M=M=（K K K K，f f f f，S S S S，Z Z Z Z）其中其中其中其中1.1.1.1.K K K K是一个有穷集，它的每个元素称为一个状态；是一个有穷集，它的每个元素称为一个状态；是一个有穷集，它的每个元素称为一个状态；是一个有穷集，它的每个元素称为一个状态；2.2.2.2.是一个有穷字母表，它的每个元素称为一个输入符号，是一个有穷字母表，它的每个元素称为一个输入符号，是一个有穷字母表，它的每个元素称为一个输入符号，是一个有穷字母表，它的每个元素称为一个输入符号，所以也

23、称所以也称所以也称所以也称为输入符号字母表；为输入符号字母表；为输入符号字母表；为输入符号字母表；3.3.3.3.f f f f是转换函数，是在是转换函数，是在是转换函数，是在是转换函数，是在K K K KK K K K上的映射，即如上的映射，即如上的映射，即如上的映射，即如f(ki,af(ki,af(ki,af(ki,a)=)=)=)=kjkjkjkj，(ki(ki(ki(kiK K K K，kjkjkjkjK)K)K)K)就意味着，当前状态为就意味着，当前状态为就意味着，当前状态为就意味着，当前状态为kikikiki，输入符为输入符为输入符为输入符为a a a a时，将转换为下一个状态时，

24、将转换为下一个状态时，将转换为下一个状态时，将转换为下一个状态kjkjkjkj，我们把我们把我们把我们把kjkjkjkj称作称作称作称作kikikiki的一个后的一个后的一个后的一个后继状态；继状态；继状态；继状态；4.4.4.4.S S S SK K K K是唯一的一个初态；是唯一的一个初态；是唯一的一个初态；是唯一的一个初态；5.5.5.5.Z Z Z Z K K K K是一个终态集，终态也称是一个终态集，终态也称是一个终态集，终态也称是一个终态集，终态也称可接受状态可接受状态可接受状态可接受状态或或或或结束状态结束状态结束状态结束状态。例：例：DFA M=DFA M=（S,U,V,Q,S

25、,U,V,Q,a,ba,b,f,S,Q,f,S,Q）其其中中 f f 定义为：定义为：f f（S S，a a）=U=Uf f（V V，a a）=U=Uf f（S S，b b）=V=Vf f（V V，b b）=Q=Qf f（U U，a a）=Q=Qf f（Q Q，a a）=Q=Qf f（U U，b b）=V=Vf f（Q Q，b b）=Q=Q（1 1）DFA DFA 的状态图表示的状态图表示f（S，a）=Uf（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=QbSUVaaaba，bQb（2 2）DFA DFA 的矩阵表示的矩阵表示f（S，

26、a）=Uf（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=QabSUVUQVVUQQQQ字符字符状态状态0100终态行在表的右端标以终态行在表的右端标以1 1，非终态标以，非终态标以0 0。2 2 2 2、*上的符号串上的符号串上的符号串上的符号串t t t t在在在在M M M M上运行上运行上运行上运行一个输入符号串一个输入符号串t t，（，（我们将它表示成我们将它表示成Tt1Tt1的形，的形，其中其中TT，t1t1*）在）在DFA MDFA M上上运行运行运行运行的定义为：的定义为：f f f f（Q Q Q Q，Tt1Tt1T

27、t1Tt1）=f=f=f=f（f f f f（Q Q Q Q，T T T T），），），），t1t1t1t1）其中其中QKQK。扩充转换函数扩充转换函数f f，是是K K*K K上的映射，且：上的映射，且：f f（Q Q，）=Q=Q3 3、*上的符号串上的符号串t t被被M M接受接受t t*，f(Sf(S，t t)=P)=P，其中其中S S为为DFA MDFA M的开始状态，的开始状态，P P Z Z，Z Z为终态集。则称为终态集。则称t t为为DFA MDFA M所所接受接受接受接受（识别识别识别识别）。）。例：证明例：证明t=t=baabbaab被如下的被如下的DFADFA所接受。所接受

28、。DFA M=（S,U,V,Q,a,b,f,S,Q）其中其中 f 定义为定义为：f（S，a）=Uf（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=QbSUVQaaaba，bb证明证明：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属于终态。得证属于终态。得证。nDFA MDFA M所能接受的符号串的全体记为所能接受的符号串的全体记为L(M)L(M)DFA M=（K，f，S，Z）的算法的算法:K:=S；c:=getchar

29、;while ceof do K:=f(K,c);c:=getchar;if K is in Z then return(yes)else return(no)二、不确定的有穷自动机二、不确定的有穷自动机NFANFAn定义定义 N=N=K K，f f，S S，Z Z，其中其中K K K K为状态为状态为状态为状态的有穷非的有穷非空空集集集集，为为为为有穷输入有穷输入字母表字母表字母表字母表，f f f f为为为为K K*到到K K的的子集子集的的映射映射映射映射，S S S S K K是初是初是初是初始始状状态集态集态集态集，Z Z Z Z K K为终为终为终为终止止状状态集态集态集态集。例例

30、NFA N=（S，P，Z，0，1，f，S，P，Z）其中其中 f（S，0）=Pf（S，1）=S，Zf（P，1）=Zf（Z，0）=Pf（Z，1）=PSPZ00,1111状态图表示状态图表示表格表示表格表示简化为简化为NFA N=（S，P，Z，0，1，f，S，P，Z）其中其中 f（S，0）=Pf（S，1）=S，Zf（P，1）=Zf（Z，0）=Pf（Z，1）=Pn*上的符号串上的符号串t t在在NFANFA N N上运行上运行 一个输入符号串一个输入符号串t t，（，（我们将它表示成我们将它表示成TtTt1 1的形式，的形式，其中其中TT，t t1 1*）在在NFA MNFA M上运行的定义为：上运行

31、的定义为：f f（Q Q，Tt Tt1 1）=f=f（f f（Q Q，T T），），t t1 1），），其中其中QK.QK.n*上的符号串上的符号串t t被被NFANFA N N接受（读出、识别）接受（读出、识别）若若t t*，f(Sf(S0 0，t)=Pt)=P，其中其中S S0 0SS，P P Z Z，则称则称t t为为NFA MNFA M所接受（识别）所接受（识别）n具有具有 转移的不确定的有穷自动机转移的不确定的有穷自动机NFANFAf f为为 K K（）到）到K K的子集的映射的子集的映射.n对任何一个具有对任何一个具有 转移的不确定的有穷自动转移的不确定的有穷自动机机NFA NNF

32、A N，一定存在一个一定存在一个不具有不具有 转移的不确转移的不确定的有穷自动机定的有穷自动机N NFAFA，使得使得L(M)=L(N)L(M)=L(N)。状态集合状态集合I I的有关运算：的有关运算：n n1 1 1 1、状态集合、状态集合、状态集合、状态集合I I I I的的的的 -闭包，表示为闭包，表示为闭包，表示为闭包，表示为 -closure(Iclosure(Iclosure(Iclosure(I)，定义为一状态集，是状态集定义为一状态集，是状态集定义为一状态集，是状态集定义为一状态集，是状态集I I I I中的任何状态中的任何状态中的任何状态中的任何状态S S S S经经经经任任

33、任任意条意条意条意条 弧而能到达的状态的集合弧而能到达的状态的集合弧而能到达的状态的集合弧而能到达的状态的集合(状态集合状态集合状态集合状态集合I I I I的任何的任何的任何的任何状态状态状态状态S S S S都属于都属于都属于都属于 -closure(Iclosure(Iclosure(Iclosure(I)。n n2 2 2 2、状态集合、状态集合、状态集合、状态集合I I I I的的的的a a a a弧转换，表示为弧转换，表示为弧转换，表示为弧转换，表示为move(I,amove(I,amove(I,amove(I,a)定义定义定义定义为状态集合为状态集合为状态集合为状态集合J J J

34、 J，其中其中其中其中J J J J是所有那些可从是所有那些可从是所有那些可从是所有那些可从I I I I的某一状的某一状的某一状的某一状态经过态经过态经过态经过一条一条一条一条a a a a弧而到达的状态的全体。弧而到达的状态的全体。弧而到达的状态的全体。弧而到达的状态的全体。三、三、NFANFA到到DFADFA的转换的转换例例I=1,-closure(I)=1,2；I=5,-closure(I)=5,6,2；-closure(5,3,4)=2,3,4,5,6,7,8；move(1,2,a)=5,3,412534687aaaNFADFANFADFA的算法：的算法：n假设假设NFA N=(K,

35、NFA N=(K,f,K,f,K0 0,K,Kt t)按如下办法构造一个按如下办法构造一个DFA DFA M=(S,M=(S,d,S,d,S0 0,S,St t)，使得使得L(M)=L(N)L(M)=L(N)：1.M 1.M的状态集的状态集S S由由K K的一些子集组成。用的一些子集组成。用 S S1 1 S S2 2.S Sj j 表示表示S S的元素，其中的元素，其中S S1 1,S,S2,2,.,.S Sj j是是K K的的状态。状态。2.2.M M和和N N的输入字母表是相同的，即是的输入字母表是相同的，即是；3.3.转换函数为：转换函数为：d(d(S S1 1,S,S2 2,.,.,

36、S Sj j,a,a)=R)=R1 1,R R2 2,.,.,R Rt t 其中其中 RR1 1,R R2 2,.,.,R Rt t =-closure(moveclosure(moveclosure(moveclosure(move(S S S S1 1 1 1,S,S,S,S2 2 2 2,.,.,.,.,S S S Sj j j j ,a)a)a)a)4.4.S S S S0 0 0 0=-closure(Kclosure(Kclosure(Kclosure(K0 0 0 0)为为M M的开始状态；的开始状态；5.5.S St t=S Si i,S Sk k ,.,.,S Se e|S

37、Si i ,S Sk k ,.,.,S Se e S S且且 S Si i ,S Sk k,.,.S Se e K Kt t 构造构造NFA NNFA N的状态的状态K K的子集的算法：的子集的算法：假定所构造的子集族为假定所构造的子集族为C C，即即C=(TC=(T1 1,T,T2,2,.,.T TI I),),其中其中T T1 1,T,T2,2,.,.T TI I为状态为状态K K的子集。的子集。1.1.开始，令开始，令-closure(Kclosure(K0 0)为为C C中唯一成员，并且中唯一成员，并且它是未被标记的。它是未被标记的。2.2.while while（C C中存在尚未被标

38、记的子集中存在尚未被标记的子集T T）dodo 标记标记T T；for for 每个输入字母每个输入字母a doa do U:=U:=-closure(move(T,aclosure(move(T,a)；if Uif U不在不在C C中中 then then 将将U U作为未标记的子集加在作为未标记的子集加在C C中中 例例4.8 4.8 将下图的将下图的NFA NNFA N转换成转换成DFA MDFA M023456789101bbbaaNFA N023456789101bbbaa 状态状态-closure(move(Ti,a)-closure(move(Ti,b)T0=-closure(0

39、)=0,1,2,4,71,2,3,4,6,7,8=T11,2,4,5,6,7=T2T1=1,2,3,4,6,7,8T11,2,4,5,6,7,9=T3T2=1,2,4,5,6,7T1T2T3=1,2,4,5,6,7,9T1T4T4=1,2,4,5,7,10T1T2-closure(move(Ti,a)-closure(move(Ti,b)T0=-closure(0)=0,1,2,4,7 1,2,3,4,6,7,8=T1 1,2,4,5,6,7=T2T1=1,2,3,4,6,7,8 T1 1,2,4,5,6,7,9=T3T2=1,2,4,5,6,7 T1 T2T3=1,2,4,5,6,7,9 T

40、1 T4T4=1,2,4,5,7,10 T1 T2b02134abaaaabbbDFA M四、四、DFADFA的最小化（化简）的最小化（化简）n最小状态最小状态DFADFAn没有多余状态没有多余状态(死状态死状态)n没有两个状态是互相等价（不可区别）没有两个状态是互相等价（不可区别）多余状态：多余状态：从自动机的开始状态出发，任何输从自动机的开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态入串也不能到达的那个状态；或者从这个状态没有通路到达终态。没有通路到达终态。消除多余状态消除多余状态s1 s5s2 s7s2 s5s5 s7s5 s6s3 s1s8 s0s0 s1s3 s60 1

41、011000110s0s1s2s3s4s5s6s7s8s1 s5s2 s7s2 s5s5 s7s3 s1s0 s10 1011001s0s1s2s3s5s7n两个状态两个状态s s和和t t等价等价,满足满足:n一致性一致性同是终态或同是非终态同是终态或同是非终态n蔓延性蔓延性从从s s出发读入某个出发读入某个a(a(a a)和从和从 t t出发出发读入某个读入某个a a到达的状态等价。到达的状态等价。n状态状态2 2和和4 4是不等价的是不等价的(可区别的可区别的)。n状态状态2 2和和3 3是不等价的，因为读入是不等价的，因为读入b b后分别后分别到达到达2 2和和4 4，而，而2 2和和

42、4 4是不等价的。是不等价的。b02134abaaaabbbDFA Mn对于一个对于一个DFA M=DFA M=（K,f,kK,f,k0 0,k,kt t)，存在一存在一个最小状态个最小状态DFA M DFA M=（K,f,kK,f,k0 0,k,kt t),),使使L(M)=L(M).L(M)=L(M).nDFADFA的最小化算法的核心：的最小化算法的核心：把一个把一个DFADFA的状态分成一些不相交的子集，的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的而同一子集中的任何两个状态都是等价的.将下

43、图中的将下图中的DFA MDFA M最小化最小化 1,2,3,4,5,6,7Ia:6,7,1,4,7,4,4Ib:3,3,5,6,3,1,21352746aaaaaaabbbbbbba13546aaaabbbbb1,2,3,4 5,6,71,2 3,41,256,73 4 56,74.4 4.4 正规正规式式和和有穷自动机有穷自动机的等价性的等价性n1.1.对于对于上的上的NFA MNFA M，可以构造一个，可以构造一个上上的正规式的正规式R,R,使得使得L(R)=L(M)L(R)=L(M)。n2 2.对于对于上的一个正规式上的一个正规式R R，可以构造一，可以构造一个个上的上的NFA MNF

44、A M，使得，使得L L(M)=L(R)M)=L(R)。n1.1.对于对于上的上的NFA MNFA M，可以构造一个，可以构造一个上的正规式上的正规式R,R,使得使得L(R)=L(M)L(R)=L(M)。第一步：在第一步：在M M的状态转换图上的状态转换图上加进两个结点加进两个结点加进两个结点加进两个结点，一，一个为个为x x结点，一个为结点，一个为y y结点。从结点。从x x结点用结点用弧连接弧连接到到M M的的所有初态结点所有初态结点所有初态结点所有初态结点，从，从M M的的所有终态结点所有终态结点所有终态结点所有终态结点用用弧连接到弧连接到y y结点。形成一个与结点。形成一个与M M等价

45、的等价的M,MM,M只只有有一个初态一个初态一个初态一个初态x x x x和和一个终态一个终态一个终态一个终态y y y y。第二步：逐步消去第二步：逐步消去MM中的所有结点，直至只剩中的所有结点，直至只剩下下x x和和y y。（。（消去规则见下页）消去规则见下页）最后最后x x和和y y结点间的弧上的标记则为所求的正规式结点间的弧上的标记则为所求的正规式R R。123R1R213R1 R213R1R213R1|R2123R1R3R213R1 R2*R3例：例：03124a,baaa,ba,bbb求正规式求正规式R R03124a,baaa,ba,bbbxy024a|baaa|ba|bbbxy

46、024a|baaa|ba|bbbxy0a|baa(a|b)*bb(a|b)*xy0a|baa(a|b)*bb(a|b)*xyxy(a|b)*(aa|bb)(a|b)*0a|bxyaa(a|b)*|bb(a|b)*(aa|bb)(a|b)*R=(a|b)*(aa|bb)(a|b)*2 2.对于对于上的一个正规式上的一个正规式R R，可以构造一个，可以构造一个上的上的NFA MNFA M，使，使得得L L(M)=L(R)M)=L(R)。(1)R=(1)R=(3)R=a(3)R=a(2)(2)R=R=(4)R=(4)R=s|ts|txyxy xya axyNFA(sNFA(s)NFA(tNFA(t)

47、xys st t或或(5)R=st(6)R=s*NFA(sNFA(s)NFA(tNFA(t)NFA(sNFA(s)xy xx1yst或或xx1y s或或例：例：为为R=(R=(R=(R=(a|ba|ba|ba|b)*)*)*)*abbabbabbabb构造构造NFA NNFA N，使得使得L(N)=L(R)L(N)=L(R)。23a54bR=(R=(a a|b|b)*)*abbabbR=(R=(a|a|b b)*)*abbabbR=(R=(a|ba|b)*)*abbabb2354ab16解法一：解法一：R=(R=(a|ba|b)*)*abbabb2354ab16R R=(=(a|ba|b)*)

48、*abbabb2354ab1607继续加上继续加上abbabb即可得到结果。即可得到结果。R R=(=(a|ba|b)*)*abbabbxiy(a|b)*abbxjyabbia|bxjyabbiab继续对继续对abbabb进行分解。进行分解。解法二：解法二：4.5 4.5 正规文法和有穷自动机间的转换正规文法和有穷自动机间的转换n采用下面的规则从正规文法采用下面的规则从正规文法G G直接构造一个有穷自直接构造一个有穷自动机动机NFA MNFA M，使得使得L(M)=L(G)L(M)=L(G)：1.1.字母表与字母表与G G的终结符集相同；的终结符集相同；2.2.为为G G中的每个非终结符生成中

49、的每个非终结符生成M M的一个状态，（不的一个状态，（不妨取相同的名字）妨取相同的名字）G G的开始符号是开始状态的开始符号是开始状态S S；3.3.增加一个新状态增加一个新状态Z Z，作为作为NFANFA的状态；的状态；4.4.对对G G中的形如中的形如AtBAtBAtBAtB的产生式（其中的产生式（其中t t为终结符或为终结符或，A A和和B B为非终结符），构造为非终结符），构造M M的一个转换函数的一个转换函数f(A,tf(A,tf(A,tf(A,t)=B)=B)=B)=B；5.5.对对G G中形如中形如AtAtAtAt的产生式，构造的产生式，构造M M的一个转换函的一个转换函数数f(A,tf(A,tf(A,tf(A,t)=Z)=Z)=Z)=Z。n例：与文法例：与文法GSGS等价的等价的NFA MNFA MGS：SaASbBSAaBAbABaSBbABSABZaabbab 总结总结两个工具：两个工具：有限自动机、正规式有限自动机、正规式三个算法：三个算法：正规式到正规式到FAFA的转换的转换 NFA NFA到到DFADFA的转换的转换 DFADFA的化简的化简一个实现：一个实现：DFADFA的实现的实现