第二章词法分析确定有限自动机优秀PPT.ppt

第二章词法分析确定有限自动机第一页，本课件共有37页第2章 outlinep一、词法分析概述一、词法分析概述1 1，词法分析程序的功能，词法分析程序的功能2 2，词法分析相关的一些问题，词法分析相关的一些问题p二、正则表达式二、正则表达式p三、有限自动机三、有限自动机1 1，确定有限自动机，确定有限自动机DFA2 2，非确定有限自动机，非确定有限自动机NFA，NFA到到DFA的转换的转换3 3，DFA的化简的化简4 4，正则表达式到，正则表达式到NFA的转换的转换p四、词法分析程序构造四、词法分析程序构造 第二页，本课件共有37页三、有限自动机正则表达式正则表达式 -s specificationecification有限自动机有限自动机 Imple lementationentation什么是有限自动机？什么是有限自动机？有限自动机是描述有限自动机是描述有限状态系统有限状态系统的的数学模型。数学模型。有限状有限状态系系统：状状态：是将事物：是将事物区分区分开的一种开的一种标识.具有离散状具有离散状态的系的系统：如数字：如数字电路路(0,1);(0,1);电灯开关电灯开关(on,off);(on,off);十十字路口的字路口的红绿灯；其状灯；其状态数是有限的。数是有限的。具有具有连续状状态的系的系统：水：水库的水位、室内的温度等可以的水位、室内的温度等可以连续发生生变化；可以有无化；可以有无穷个状个状态.有限状有限状态系系统是离散状是离散状态系系统。在很多领域，如网络协议分析、形式验证、代码安全、在很多领域，如网络协议分析、形式验证、代码安全、排版系统等有重要应用。排版系统等有重要应用。第三页，本课件共有37页有限自动机的例子-经典的过河问题一个人一个人带着一着一头狼，一狼，一头羊，以及一棵白菜羊，以及一棵白菜处于河于河的左岸。人和他的伴随品都希望渡到河的右岸。有的左岸。人和他的伴随品都希望渡到河的右岸。有一条小船，每一条小船，每摆渡一次，只能携渡一次，只能携带人和其余三者之人和其余三者之一。如果一。如果单独留下狼和羊，狼会吃羊；如果独留下狼和羊，狼会吃羊；如果单独留独留下羊和白菜，羊会吃菜。怎下羊和白菜，羊会吃菜。怎样才能渡河，而羊和白才能渡河，而羊和白菜不会被吃掉呢？菜不会被吃掉呢？第四页，本课件共有37页过河问题模型化第五页，本课件共有37页有限自有限自动动机的模型机的模型有限自有限自动机机FA可以理解成状可以理解成状态控制器控制器FA有有限个状有有限个状态，其中有初始状，其中有初始状态，终止状止状态起始：起始：处于初始状于初始状态，读头位于位于输入入带开开头中中间：从左到右依次：从左到右依次读取字符，取字符，发生状生状态迁移迁移结束：束：读头到达到达输入入带末尾，状末尾，状态到达到达终态10110状态控制器状态控制器读头输入带输入带输出输出第六页，本课件共有37页有限自动机的五要素有限状有限状态集集 SSSS有限有限输入符号集入符号集 转移函数移函数 (s,a)(s,a)=t t 一个开始状一个开始状态s0s0一个一个终止状止状态集集 TS S输入：字符串输入：字符串输出：若输入字符串结束，且到达终止状态，则输出：若输入字符串结束，且到达终止状态，则接接受受，否则，否则拒绝拒绝。例如：例如：“101101”输出拒绝，输出拒绝，“10101010”输出接受。输出接受。第七页，本课件共有37页1 1、确定有限自动机、确定有限自动机DFADFA确定有限自动机确定有限自动机DFADFA是一个五元是一个五元组 M=(SS,M=(SS,S,S0 0,TS),TS)，nSS SS：有限的状：有限的状态集合集合 SS0 0，S S1 1，S S2 2，n ：有限的：有限的输入字符表入字符表n ：状：状态转换函数，函数，SS SS SS SS 是是单值全映射函数；全映射函数；nS S0 0：初始状：初始状态，S S0 0 SSSSnTS TS：终止状止状态集，集，TSTS SSSS 第八页，本课件共有37页例1：DFA M=(0,1,2,3,4,a,b,0,3)其中为：(0,a)(0,a)=1 1 (0,b)(0,b)=4 4 (1,a)(1,a)=4 4 (1,b)(1,b)=2 2 (2,a)(2,a)=3 3 (2,b)(2,b)=4 4 (3,a)(3,a)=3 3 (3,b)(3,b)=3 3 (4,a)(4,a)=4 4 (4,b)(4,b)=4 4第九页，本课件共有37页DFADFA的的两种两种表示形式表示形式n转换表表(transition table)(transition table)易于易于实现n转换图(transition gra(transition graph)h)直直观，易于理解，易于理解第十页，本课件共有37页转换表转换表行：状行：状态列：字符列：字符元素：元素：表示状态转换，表示状态转换，状状态或或 开始状开始状态：默：默认表的第一行表示表的第一行表示开始状开始状态,或者状态加上角标或者状态加上角标+终止状止状态：状态加状态加上上角标角标-a ab b0+0+1 14 41 14 42 23 3-3 33 3第十一页，本课件共有37页转换表转换表例例1 1：DFA M=(0,1,2,3,4,a,b,DFA M=(0,1,2,3,4,a,b,0,3),0,3)其中其中为：(0,a)=1 (0,a)=1 (0,b)=4(0,b)=4 (1,a)=4 (1,a)=4 (1,b)=2(1,b)=2 (2,a)=3 (2,a)=3 (2,b)=4(2,b)=4 (3,a)=3 (3,a)=3 (3,b)=3(3,b)=3 (4,a)=4 (4,a)=4 (4,b)=4(4,b)=4a ab b0 0+1 14 41 14 42 22 23 34 43 3-3 33 34 44 44 4第十二页，本课件共有37页转换图转换图状状态转换边 f(S1,a)f(S1,a)=S2 S2开始状开始状态终止状止状态S S0 0S SS S a aS1S1S2S2第十三页，本课件共有37页转换图转换图a ab b0+0+1 14 41 14 42 22 23 34 43 3-3 33 34 44 44 40 02 21 13 3abababba4 4ab第十四页，本课件共有37页转换图转换图a ab b0+0+1 1 1 1 2 22 23 3 3 3-3 33 30 02 21 13 3aabbaa ab b0+0+1 11 12 22 23 33 3-3 33 3第十五页，本课件共有37页DFA的例子例2：:a,b,c,d :a,b,c,d SS:S0,S1,S2,SS:S0,S1,S2,S3S3 开始状态开始状态:S0S0 终止状态集终止状态集:S3:S3f:(S0,a)f:(S0,a)S1,(S0,c)S1,(S0,c)S2,S2,(S0,d)(S0,d)S3,(S1,b)S3,(S1,b)S1,S1,(S1,d)(S1,d)S2,(S2,a)S2,(S2,a)S3,S3,(S3,c)(S3,c)S3S3S0S0a aS1S1S2S2S3S3c cd dd da ab bc c第十六页，本课件共有37页DFADFA的确定性的确定性形式定义形式定义初始状态唯一：初始状态唯一：S0S0转换函数是单值函数，即对任一状态和输入符号，唯一地确定了下一个状态转换函数是单值函数，即对任一状态和输入符号，唯一地确定了下一个状态转换表转换表初始状态唯一：第一行初始状态唯一：第一行表元素唯一表元素唯一转换图转换图初始状态唯一初始状态唯一:每个状态最多发出每个状态最多发出n n条边，条边，n n是字母表中字母的个数，且发出的任意两条边上标的字母都是字母表中字母的个数，且发出的任意两条边上标的字母都不同不同第十七页，本课件共有37页DFADFA的一些的一些概概念念DFA接受的字符串接受的字符串如果如果M是一个是一个DFA,a a1 1 a a2 2 a an n 是一个字符串，如果存在一个状态序列是一个字符串，如果存在一个状态序列 (S S0 0,S,S1 1,S,Sn n),),满足满足 S S0 0 S S1 ,1 ,S S1 1 S S2 ,2 ,S Sn n-1 1 S Sn n其中其中 S S0 0 是开始状态，是开始状态，S Sn n 是接受状态之一，则串是接受状态之一，则串a a1 1 a a2 2 a an n 被被DFA M接受接受.DFA定定义的串的集合的串的集合(DFA接受的接受的语言言)DFA M接受的所有串的集合，称为接受的所有串的集合，称为M定义的语言，记为定义的语言，记为 L(L(M)a1a1a2a2anan第十八页，本课件共有37页DFA接受的语言例例1 1中自动机接受的语言是中自动机接受的语言是L L(aba(a(aba(a|b)b)*)例例2 2中自动机接受的语言是中自动机接受的语言是L L(ab(ab*da da|ca ca|d)c d)c*)0 02 21 13 3aabbaS0S0a aS1S1S2S2S3S3c cd dd da ab bc c第十九页，本课件共有37页DFA接受的语言若若DFA M只有一个状只有一个状态，既是开始状，既是开始状态又是又是终止状止状态，则DFA M定定义的串集是的串集是L L()=若若若若DFA M只有一个状只有一个状态，并且是开始状，并且是开始状态或或DFA M有若干个状有若干个状态，但开始状，但开始状态到到终止状止状态之之间没有通路，没有通路，则DFA M定定义的串集是的串集是空集空集 S SS S0 0或S S0 0S SSSS S 第二十页，本课件共有37页设计有限自动机自自动机的机的设计是一个是一个创造造过程，没有固定的算法和程，没有固定的算法和过程程例例1 1：=a,b,a,b,构造自构造自动机机识别由所有奇数个由所有奇数个a a和奇数个和奇数个b b组成成的字符串。的字符串。S S奇奇a,a,奇奇b bS S奇奇a,a,偶偶b bS S偶偶a,a,奇奇b bS S偶偶a,a,偶偶b bbbbaabaa关键：不需要记住所看到的整个字符串，只需记住至此所看到的a和b的个数是奇数还是偶数第二十一页，本课件共有37页设计有限自动机例例2 2：设计有限自动机：设计有限自动机M M，识别，识别0,10,1上的语言上的语言 L=x000y|x,yL=x000y|x,y 0|1*0|1*分析：该语言的特点是每个串都包含连续分析：该语言的特点是每个串都包含连续3 3个个0 0的子串。的子串。自动机的任务就是识别自动机的任务就是识别/检查检查 000000 的子串。的子串。q0q1q2q300011101第二十二页，本课件共有37页设计有限自动机例例3 3：设计有限自动机：设计有限自动机M M，识别，识别0,1,20,1,2上的语言，每个字符串上的语言，每个字符串代表的数字能整除代表的数字能整除3 3。分析分析:(1):(1)一个十进制数除以一个十进制数除以3 3，余数只能是，余数只能是0,1,20,1,2；(2)(2)被被3 3整除的十进制数的特点：十进制数的所有位数整除的十进制数的特点：十进制数的所有位数字的和能整除字的和能整除3 3。q0q1q2110210022第二十三页，本课件共有37页DFADFA与与程序程序设计语设计语言的言的单词结构单词结构例例4 4：使用使用DFA定定义程序程序设计语言的言的无符号实数无符号实数 0.12,34.10.12,34.15 接受接受 00.12,00.,.,33.00.12,00.,.,33.拒绝拒绝S S0 0S3S30,1,90,1,90,1,2,90,1,2,9S1S10 0S2S2.1,2,91,2,9S4S4.0,1,90,1,9第二十四页，本课件共有37页DFADFA与与程序程序设计语设计语言的言的单词结构单词结构例例5：使用使用DFA定定义程序程序设计语言的言的标识符符x,Xy,x123,123,xYz 接受接受2323x,12,12_ _x，_ _x 拒绝拒绝q0q1letterletterdigit第二十五页，本课件共有37页DFADFA与与程序程序设计语设计语言的言的单词结构单词结构例例6：使用使用DFA定定义程序程序设计语言的言的保留字保留字 if,else,while,forif,else,while,for ifseelilhewrof第二十六页，本课件共有37页DFADFA的的实现实现目的目的给定一个定一个DFA M定定义了一个串集了一个串集编写一个程序，写一个程序，检查给定的串是否被定的串是否被DFA M所所识别或接受或接受两种途径两种途径基于基于转换表表基于基于转换图第二十七页，本课件共有37页基于基于转换转换表的表的DFADFA实现实现主要思想主要思想输入入 :一个字符串一个字符串,以以#结尾尾.输出出:如果接受如果接受则输出出truetrue 否否则输出出 falsefalse数据数据结构：构：转换表表 (二二维数数组 T)两个两个变量量StateState:记录当前状当前状态;CurrentCharCurrentChar:记录串串 中当前正在被中当前正在被读的字符的字符;第二十八页，本课件共有37页基于基于转换转换表的表的DFADFA实现实现算法算法主要思想主要思想1.1.StateState =InitStatenitState;2.Read(CurrentChar);2.Read(CurrentChar);3.while 3.while T(State,CurrentChar)(State,CurrentChar)error error&CurrentChar CurrentChar#do do begin State begin State=T(State,CurrentChar);(State,CurrentChar);Read(CurrentChar);Read(CurrentChar);end;end;4.if 4.if CurrentCharCurrentChar =#&StateState FinalStatesinalStates，return return truetrue;otherwise,return otherwise,return falsefalse.第二十九页，本课件共有37页S0(c)S2(a)S3(b)S0(a)S1(b)S1(d)S2(a)S3(c)S3(c)S3abcdS0+S1S2S3S1S1S2S2S3S3-S31)cab 1)cab 接受接受 or or 拒绝？拒绝？2 2）abdacc abdacc 接受接受 or or 拒绝？拒绝？拒绝拒绝接受接受第三十页，本课件共有37页基于基于转换图转换图的的DFADFA实现实现每个状态对应一个带标号的case case 语句每条边对应一个 gotogoto 语句对于每个终止状态，增加一个分支，如果当前字符是字符串的结束符#，则接受;i ib bj jk ka aLi:case CurrentChar ofLi:case CurrentChar of a a ：goto Ljgoto Lj b :goto Lk b :goto Lk other :Error()other :Error()第三十一页，本课件共有37页基于基于转换图转换图的的DFADFA实现实现每个状态对应一个带标号的case case 语句每条边对应一个 gotogoto 语句对于每个终止状态，增加一个分支，如果当前字符是字符串的结束符#，则接受;b bj jk ka ai iLi:case CurrentChar ofLi:case CurrentChar of a a ：goto Ljgoto Lj b :goto Lk b :goto Lk#:return true;#:return true;other :return false;other :return false;第三十二页，本课件共有37页S0S0a aS1S1S2S2S3S3c cd dd da ab bc cLS0:LS0:Read(Read(CurrentChar);CurrentChar);switchswitch(CurrentChar)(CurrentChar)case a:goto LS1;case a:goto LS1;casecase c:goto LS2:c:goto LS2:casecase d:goto LS3;d:goto LS3;other:return false;other:return false;LS1:LS1:Read(Read(CurrentChar);CurrentChar);switch switch(CurrentChar)(CurrentChar)case b:goto LS1;case b:goto LS1;case d:goto LS2:case d:goto LS2:other:return false;other:return false;第三十三页，本课件共有37页S0S0a aS1S1S2S2S3S3c cd dd da ab bc cLS2:LS2:Read(Read(CurrentChar);CurrentChar);switch switch(CurrentChar)(CurrentChar)case a:goto LS3;case a:goto LS3;other:return false;other:return false;LS3:LS3:Read(Read(CurrentChar);CurrentChar);switch switch(CurrentChar)(CurrentChar)case c:goto LS3:case c:goto LS3:case#:return true;case#:return true;other:return false;other:return false;第三十四页，本课件共有37页两种实现两种实现方式的比方式的比较较转换表方式：表方式：是通用的算法，不同的语言，只需改变输入的转换表，识别是通用的算法，不同的语言，只需改变输入的转换表，识别程序不需改变；程序不需改变；转换图方式：方式：不需要存储转换表不需要存储转换表(通常转换表是很大的通常转换表是很大的)，但当语言改变即，但当语言改变即自动机的结构改变时，整个识别程序都需要改变。自动机的结构改变时，整个识别程序都需要改变。第三十五页，本课件共有37页小结确定有限自动机确定有限自动机定义的语言确定有限自动机的实现第三十六页，本课件共有37页作作 业业构造一个构造一个DFADFA，使它能够识别出所有能，使它能够识别出所有能被被3 3整除整除的的二二进制进制数。数。分别用转换表方式和转换图方式编程实现上述自动分别用转换表方式和转换图方式编程实现上述自动机，并用实例验证上述自动机是否正确。机，并用实例验证上述自动机是否正确。第三十七页，本课件共有37页