编译原理词法分析(2).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章 词法分析（2）,有限自动机,华侨大学计算机学院 陈霞,编译原理,内容简介,记号的识别,有限自动机,不确定的有限自动机（,NFA,）,确定的有限自动机（,DFA,）,有限自动机的等价性,0.,示例：一个单词的识别,识别单词,fee,的代码可以简单地写成：,.,if(getchar()=f),if(getchar()=e),if(getchar()=e),return success;,else,return error;,0.,示例：一个单词的识别,更复杂的情况：同时识别单词,fee,和,fie,的代码,.,if(getchar()=f),tempChar=getchar();,if(tempChar=e),if(getchar()=e)return success1;,else,if(tempChar=i),if(getchar()=e),return success2;,return error;,0.,用程序流程图的观点看待上述程序,2.3 记号的识别 有限自动机,2.3.1,不确定的有限自动机,(Nondeterministic Finite Automata，NFA),定义2.4 NFA是一个五元组，M=(S，move，s0，F)：,S是有限个状态(state)的集合；,是有限个输入字符(包括)的集合；,move是一个状态转移函数，move(si，ch)=sj表示当前状态si下若遇到输入字符ch，则转移到状态sj；,s0是唯一的初态(也称开始状态)；,F是终态集(也称接受状态集)，它是S的子集，包含了所有的终态。,NFA,，可以用两种直观的方式来表示,状态转换图,：是一个有向图，每个状态对应转换图中的一个节点；每个move函数对应转换图中的一条有向边，字符ch(或)是边上的标记。初态是转换图中没有前驱的节点，终态节点可以用一个加粗的圆圈或者双圈表示。,状态转换矩阵,：是一个二维数组，其中每个元素Msi,sj中的内容是从状态si到状态sj的边上的标记ch(或)。在转换矩阵中，一般以矩阵第一行所对应的状态为初态，而终态需要特别指出。,例2.7,识别由正规式(a|b)*abb说明的记号的NFA定义如下：,S=0,1,2,3,=a,b，s0=0,F=3,move=move(0,a)=0,move(0,a)=1,move(0,b)=0,move(1,b)=2,move(2,b)=3,图2.5 识别(a|b)*abb的NFA,(a)转换图表示的NFA；(b)转换矩阵表示的NFA,例2.8,识别表2.1中记号id、num和relation的转换图如图2.6所示。id和num依据的是例2.6中简化的正规式。不难看出，转换图识别的每一个记号实质上是从初态开始到某个终态的路径上的标记。例如，在识别relation的转换图中，从0开始到2的路径标记是“=”，表示在终态2处识别出一个关系运算符，语句return(relation,LE)表示此处可以返回记号的种类relation和关系运算符的值LE(小于等于号)。,图2.6 状态转换图,(a)relation的转换图；(b)id的转换图；(c)num的转换图,NFA的特点,不确定性,即在当前状态下，对同一个字符ch，可能有多于一个的下一状态转移。不确定性反映在NFA的定义中，就是move函数是一对多的；反映在转换图中，就是从一个节点可通过多于一条标记相同字符的边转移到不同的状态；反映在转换矩阵中，就是Msi,sj中不是一个单一状态，而是一个状态的集合。,例2.9,用例2.7中的NFA来识别输入序列abb和abab。,图2.7 NFA识别输入序列abb和abab,(a)abb的识别过程；(b)abab的识别过程,NFA识别记号存在下述问题,：,(1)只有尝试了全部可能的路径，才能确定一个输入序列不被接受，而这些路径的条数随着路径长度的增长成指数增长。,(2)识别过程中需要进行大量的回溯，时间复杂度与输入序列成指数级增长，且算法复杂。,造成这种情况的原因是NFA的不确定性，即在当前的状态下，遇到的下一个字符可能有多于一条的路径可走，而在当前状态下，这些路径中哪条路径可以到达终态或者全部路径均不能到达终态都是不可知的。,2.3.2 确定的有限自动机(Deterministic Finite Automata,DFA),定义2.5 DFA是NFA的一个特例，其中：,没有状态具有状态转移(-transition)，即状态转换图中没有标记的边；,对每一个状态s和每一个字符a，最多有一个下一状态。,例2.10,识别由正规式(a|b)*abb说明的记号的DFA，其转换图和转换矩阵表示如图2.8所示。根据转换图，不难写出此DFA的定义。用它识别输入序列abb和abab的过程如图2.9所示。,图2.8 识别(a|b)*abb的DFA,(a)转换图表示的DFA；(b)转换矩阵表示的DFA,图2.9 DFA识别输入序列abb和abab,与NFA相比，DFA的特点就是它的确定性，即在当前状态下，对同一个字符ch，最多有一个下一状态转移。确定性反映在DFA的定义中，就是move函数是一对一的；反映在转换图中，就是从一个节点出发的任何不同的边上标记的字符均不同；反映在转换矩阵中，就是Msi,sj中是一个单一状态。,由于在DFA上识别输入序列时，在任何一个当前状态下遇到任何输入字符，其下一状态转移均是唯一确定的，因此，无论是接受还是不接受，均经历一条确定的路径，而无其他任何路径可走。也就是说，在DFA上识别输入序列无需回溯，从而大大简化了记号的识别过程。,DFA识别输入序列的过程总结为算法2.1，被称为模拟器(模拟DFA的行为)，也被称为驱动器(用DFA的数据驱动分析动作)。模拟DFA算法的最大特点是方法与模式无关，它仅根据DFA的当前状态和状态转移进行一系列的动作，直到回答yes或者no。而所有与模式相关的信息均包含在DFA中。,算法2.1 模拟DFA,输入：,DFA,D和输入字符串x。x由文件结束符eof终止，D的初态为s0，终态集为F。,输出,若D接受x，回答“yes”，否则回答“no”。,方法,用下述过程识别x：,s:=s0；a:=nextchar；,while a eof loop s:=move(s，a)；a:=nextchar;end loop；,if s is in F then return yes；else return no；end if；,2.3.3 有限自动机的等价,NFA和DFA统称为有限自动机(FA)。所谓有限，是指自动机的状态数是有限的，因此，有些教材中也称为有限状态自动机。与正规式的等价相似，FA之间也存在等价问题。,定义2.6,若有限自动机M和M识别同一个正规集，则称M和M是等价的，记为M=M。,图2.5和图2.8所示的FA均识别以正规式(a|b)*abb所表示的正规集，两个FA是等价的。由于DFA上识别记号的确定性和简单性，往往希望用DFA而不是NFA来识别记号。很幸运，对于任何一个NFA，均可以找到一个与它等价的DFA。这一结果意味着，对任何正规集，均可以构造一个DFA去识别它。,