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

《第二章 词法分析确定有限自动机.ppt》由会员分享，可在线阅读，更多相关《第二章 词法分析确定有限自动机.ppt（37页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编译程序原理与实现张晶2013.02第2章 outlinep一、词一、词法分析概述法分析概述1 1，词法分析程序的功能，词法分析程序的功能2 2，词法分析相关的一些问题，词法分析相关的一些问题p二、正则表达式二、正则表达式p三、有限自动机三、有限自动机1 1，确定有限自动机，确定有限自动机DFADFA2 2，非确定有限自动机，非确定有限自动机NFANFA，NFANFA到到DFADFA的转换的转换3 3，DFADFA的化简的化简4 4，正则表达式到，正则表达式到NFANFA的转换的转换p四、词法分析程序构造四、词法分析程序构造三、有限自动机正则表达式正则表达式 -specification-sp

2、ecification有限自动机有限自动机 Implementation Implementation什么是有限自动机？什么是有限自动机？有限自动机是描述有限自动机是描述有限状态系统有限状态系统的的数学模型。数学模型。有限状态系统：有限状态系统：状态：是将事物状态：是将事物区分区分开的一种标识开的一种标识.具有离散状态的系统：如数字电路具有离散状态的系统：如数字电路(0,1);(0,1);电灯开关电灯开关(on,off);(on,off);十十字路口的红绿灯；其状态数是有限的。字路口的红绿灯；其状态数是有限的。具有连续状态的系统：水库的水位、室内的温度等可以连续发具有连续状态的系统：水库的水位

3、、室内的温度等可以连续发生变化；可以有无穷个状态生变化；可以有无穷个状态.有限状态系统是离散状态系统有限状态系统是离散状态系统。在很多领域，如网络协议分析、形式验证、代码安全、在很多领域，如网络协议分析、形式验证、代码安全、排版系统等有重要应用。排版系统等有重要应用。有限自动机的例子-经典的过河问题一个人一个人带着一头狼，一头羊，以及一棵白菜处于河带着一头狼，一头羊，以及一棵白菜处于河的左岸。人和他的伴随品都希望渡到河的右岸。有的左岸。人和他的伴随品都希望渡到河的右岸。有一条小船，每摆渡一次，只能携带人和其余三者之一条小船，每摆渡一次，只能携带人和其余三者之一。如果单独留下狼和羊，狼会吃羊；如

4、果单独留一。如果单独留下狼和羊，狼会吃羊；如果单独留下羊和白菜，羊会吃菜。怎样才能渡河，而羊和白下羊和白菜，羊会吃菜。怎样才能渡河，而羊和白菜不会被吃掉呢？菜不会被吃掉呢？过河问题模型化有限自有限自动动机的模型机的模型有限自动机有限自动机FAFA可以理解成状态控制器可以理解成状态控制器FAFA有有限个状态，其中有初始状态，终止状态有有限个状态，其中有初始状态，终止状态起始：处于初始状态，读头位于输入带开头起始：处于初始状态，读头位于输入带开头中间：从左到右依次读取字符，发生状态迁移中间：从左到右依次读取字符，发生状态迁移结束：读头到达输入带末尾，状态到达终态结束：读头到达输入带末尾，状态到达终

5、态10110状态控制器状态控制器读头输入带输入带输出输出有限自动机的五要素有限状态集有限状态集 SSSS有限输入符号集有限输入符号集 转移函数转移函数 (s,a)=t (s,a)=t 一个开始状态一个开始状态s0s0一个终止状态集一个终止状态集 TSTS输入：字符串输入：字符串输出：若输入字符串结束，且到达终止状态，则输出：若输入字符串结束，且到达终止状态，则接接受受，否则，否则拒绝拒绝。例如：例如：“101101”输出拒绝，输出拒绝，“10101010”输出接受。输出接受。1 1、确定有限自动机、确定有限自动机DFADFA确定有限自动机确定有限自动机DFADFA是一个五元组是一个五元组 M=

6、(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 例1：DFA M=(0,1,2,3,4,a,b,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

7、,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)=4DFADFA的的两种两种表示形式表示形式n转换表转换表(transition table)(transition table)易于实现易于实现n转换图转换图(transition graph)(transition graph)直观，易于理解直观，易于理解转换表转换表行：行：状态状态列：字符列：字符元素：元素：表示状态转换，表示状态转换，状态状态或或 开开始始状态状态：默：默认认表的第一行表表的第一行表示示开开始始状态状态,或者状态

8、加上角标或者状态加上角标+终终止止状态状态：状态加状态加上上角标角标-a ab b0+0+1 14 41 14 42 23 3-3 33 3转换表转换表例例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

9、b0 0+1 14 41 14 42 22 23 34 43 3-3 33 34 44 44 4转换图转换图状态状态转换边转换边 f(S1,a)=S2f(S1,a)=S2开始状态开始状态终止状态终止状态S0SS aS1S2转换图转换图a ab b0+0+1 14 41 14 42 22 23 34 43 3-3 33 34 44 44 40213abababba4ab转换图转换图a ab b0+0+1 1 1 1 2 22 23 3 3 3-3 33 30213aabbaa ab b0+0+1 11 12 22 23 33 3-3 33 3DFA的例子例2：:a,b,c,d SS:S0,S1,

10、S2,S3开始状态开始状态:S0 终止状态集终止状态集:S3f:(S0,a)S1,(S0,c)S2,(S0,d)S3,(S1,b)S1,(S1,d)S2,(S2,a)S3,(S3,c)S3S0aS1S2S3cddabcDFADFA的确定性的确定性形式定义形式定义初始状态唯一：初始状态唯一：S0S0转换函数是单值函数，即对任一状态和输入符号，唯一地确定了下一个状态转换函数是单值函数，即对任一状态和输入符号，唯一地确定了下一个状态转换表转换表初始状态唯一：第一行初始状态唯一：第一行表元素唯一表元素唯一转换图转换图初始状态唯一初始状态唯一:每个状态最多发出每个状态最多发出n n条边，条边，n n是字

11、母表中字母的个数，且发出的任意两条边是字母表中字母的个数，且发出的任意两条边上标的字母都不同上标的字母都不同DFADFA的一些的一些概概念念DFADFA接受的字符串接受的字符串如果如果M M是一个是一个DFA,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-1 n-1 S Sn n其中其中 S S0 0 是开始状态，是开始状态，S Sn n 是接受状态之一，则串是接受状态之一，则串a a1

12、1 a a2 2 a an n 被被DFA MDFA M接受接受.DFADFA定义的串的集合定义的串的集合(DFA(DFA接受的语言接受的语言)DFA MDFA M接受的所有串的集合，称为接受的所有串的集合，称为M M定义的语言，记为定义的语言，记为 L(M)L(M)a1a2anDFA接受的语言例例1 1中自动机接受的语言是中自动机接受的语言是L L(aba(a|b)*)(aba(a|b)*)例例2 2中自动机接受的语言是中自动机接受的语言是L L(ab*da|ca|d(ab*da|ca|d)c*)c*)0213aabbaS0aS1S2S3cddabcDFA接受的语言若若DFA DFA M M

13、只有一个状态，既是开始状态又是终止状态，则只有一个状态，既是开始状态又是终止状态，则DFA DFA M M定义的串集是定义的串集是L L()=)=若若若若DFA MDFA M只有一个状态，并且是开始状态或只有一个状态，并且是开始状态或DFA DFA M M有若干个状态，但开始状态到终止状态之间没有通路，则有若干个状态，但开始状态到终止状态之间没有通路，则DFA DFA M M定义的串集是空集定义的串集是空集 SS0或S0SSS设计有限自动机自动机的设计是一个创造过程，没有固定的算法和过程自动机的设计是一个创造过程，没有固定的算法和过程例例1 1：=a,b,a,b,构造自动机识别由所有奇数个构造

14、自动机识别由所有奇数个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的个数是奇数还是偶数设计有限自动机例例2 2：设计有限自动机：设计有限自动机M M，识别，识别0,10,1上的语言上的语言 L=x000y|x,yL=x000y|x,y 0|1*0|1*分析：该语言的特点是每个串都包含连续分析：该语言的特点是每个串都包含连续3 3个个0 0的子串。的子串。自动机的任务就是识别自动机的任务就是识别/

15、检查检查 000000 的子串。的子串。q0q1q2q300011101设计有限自动机例例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。q0q1q2110210022DFADFA与与程序程序设计语设计语言的言的单词结构单词结构例例4 4：使用使用D

16、FADFA定定义义程序程序设计语设计语言的言的无符号实数无符号实数 0.12,34.15 0.12,34.15 接受接受 00.12,00.,.,33.00.12,00.,.,33.拒绝拒绝S0S30,1,90,1,2,9S10S2.1,2,9S4.0,1,9DFADFA与与程序程序设计语设计语言的言的单词结构单词结构例例5 5：使用使用DFADFA定定义义程序程序设计语设计语言的言的标识标识符符x,Xy,x123,xYz x,Xy,x123,xYz 接受接受23x,1223x,12_ _x x，_ _x x 拒绝拒绝q0q1letterletterdigitDFADFA与与程序程序设计语设计

17、语言的言的单词结构单词结构例例6 6：使用使用DFADFA定定义义程序程序设计语设计语言的言的保留字保留字 if,else,while,forif,else,while,for ifseelilhewrofDFADFA的的实现实现目的目的给定一个给定一个DFA MDFA M定义了一个串集定义了一个串集编写一个程序，检查给定的串是否被编写一个程序，检查给定的串是否被DFA MDFA M所识别或接受所识别或接受两种途径两种途径基于转换表基于转换表基于转换图基于转换图基于基于转换转换表的表的DFADFA实现实现主要思想主要思想输入输入 :一个字符串一个字符串,以以#结尾结尾.输出输出 :如果接受则输

18、出如果接受则输出truetrue 否则输出否则输出 falsefalse数据结构：数据结构：转换表转换表 (二维数组二维数组 T T)两个变量两个变量StateState:记录当前状态记录当前状态;CurrentCharCurrentChar:记录串记录串 中当前正在被读的字符中当前正在被读的字符;基于基于转换转换表的表的DFADFA实现实现算法算法主要思想主要思想1.1.StateState=InitStateInitState;2.Read(CurrentChar);2.Read(CurrentChar);3.while 3.while T T(State,CurrentChar)erro

19、r&(State,CurrentChar)error&CurrentChar CurrentChar#do do begin State=begin State=T T(State,CurrentChar);(State,CurrentChar);Read(CurrentChar);Read(CurrentChar);end;end;4.if 4.if CurrentCharCurrentChar=#&StateState FinalStatesFinalStates，return return truetrue;otherwise,return otherwise,return falsef

20、alse.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 拒绝？拒绝？拒绝拒绝接受接受基于基于转换图转换图的的DFADFA实现实现每个状态对应一个带标号的case case 语句每条边对应一个 gotogoto 语句对于每个终止状态，增加一个分支，如果当前字符是字符串的结束符#，则接受;ibjkaLi:case CurrentChar of a ：goto Lj b :goto

21、Lk other :Error()基于基于转换图转换图的的DFADFA实现实现每个状态对应一个带标号的case case 语句每条边对应一个 gotogoto 语句对于每个终止状态，增加一个分支，如果当前字符是字符串的结束符#，则接受;bjkaiLi:case CurrentChar of a ：goto Lj b :goto Lk#:return true;other :return false;S0aS1S2S3cddabcLS0:Read(CurrentChar);switch(CurrentChar)case a:goto LS1;case c:goto LS2:case d:goto

22、 LS3;other :return false;LS1:Read(CurrentChar);switch(CurrentChar)case b:goto LS1;case d:goto LS2:other :return false;S0aS1S2S3cddabcLS2:Read(CurrentChar);switch(CurrentChar)case a:goto LS3;other:return false;LS3:Read(CurrentChar);switch(CurrentChar)case c:goto LS3:case#:return true;other:return fal

23、se;两种实现两种实现方式的比方式的比较较转换表方式：转换表方式：是通用的算法，不同的语言，只需改变输入的转换表，识别是通用的算法，不同的语言，只需改变输入的转换表，识别程序不需改变；程序不需改变；转换图方式：转换图方式：不需要存储转换表不需要存储转换表(通常转换表是很大的通常转换表是很大的)，但当语言改变即，但当语言改变即自动机的结构改变时，整个识别程序都需要改变。自动机的结构改变时，整个识别程序都需要改变。小结确定有限自动机确定有限自动机确定有限自动机定义的语言确定有限自动机定义的语言确定有限自动机的实现确定有限自动机的实现作作 业业构造一个构造一个DFADFA，使它能够识别出所有能，使它能够识别出所有能被被3 3整除整除的的二二进制进制数。数。分别用转换表方式和转换图方式编程实现上述自动分别用转换表方式和转换图方式编程实现上述自动机，并用实例验证上述自动机是否正确。机，并用实例验证上述自动机是否正确。