资源描述：
《编译原理词法分析(2)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章词法分析（2）——有限自动机华侨大学计算机学院陈霞编译原理内容简介记号的识别——有限自动机不确定的有限自动机（NFA）确定的有限自动机（DFA）有限自动机的等价性0.示例：一个单词的识别识别单词fee的代码可以简单地写成：....if(getchar()==‘f’)if(getchar()==‘e’)if(getchar()==‘e’)returnsuccess;elsereturnerror;0.示例：一个单词的识别更复杂的情况：同时识别单词fee和fie的代码....if(getchar()==‘f’){tempChar=getchar();if(tempChar==‘e’
2、){if(getchar()==‘e’)returnsuccess1;}else{if(tempChar==‘i’)if(getchar()==‘e’)returnsuccess2;}returnerror;0.用程序流程图的观点看待上述程序2.3记号的识别——有限自动机2.3.1不确定的有限自动机(NondeterministicFiniteAutomata，NFA)定义2.4NFA是一个五元组，M=(S，∑，move，s0，F)：①S是有限个状态(state)的集合；②∑是有限个输入字符(包括ε)的集合；③move是一个状态转移函数，move(si，ch)=sj表示当前状态si下
3、若遇到输入字符ch，则转移到状态sj；④s0是唯一的初态(也称开始状态)；⑤F是终态集(也称接受状态集)，它是S的子集，包含了所有的终态。NFA，可以用两种直观的方式来表示——状态转换图：是一个有向图，每个状态对应转换图中的一个节点；每个move函数对应转换图中的一条有向边，字符ch(或ε)是边上的标记。初态是转换图中没有前驱的节点，终态节点可以用一个加粗的圆圈或者双圈表示。——状态转换矩阵：是一个二维数组，其中每个元素M[si,sj]中的内容是从状态si到状态sj的边上的标记ch(或ε)。在转换矩阵中，一般以矩阵第一行所对应的状态为初态，而终态需要特别指出。例2.7识别由正规式(a
4、
5、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
6、b)*abb的NFA(a)转换图表示的NFA；(b)转换矩阵表示的NFA例2.8识别表2.1中记号id、num和relation的转换图如图2.6所示。id和num依据的是例2.6中简化的正规式。不难看出，转换图识别的每一个记号实质上是从初态开始到某个终态的路径上的标记。例如，在识别relation的转换图中，从0开始到2的路径标记是“
7、<=”，表示在终态2处识别出一个关系运算符，语句return(relation,LE)表示此处可以返回记号的种类relation和关系运算符的值LE(小于等于号)。图2.6状态转换图(a)relation的转换图；(b)id的转换图；(c)num的转换图NFA的特点——不确定性即在当前状态下，对同一个字符ch，可能有多于一个的下一状态转移。不确定性反映在NFA的定义中，就是move函数是一对多的；反映在转换图中，就是从一个节点可通过多于一条标记相同字符的边转移到不同的状态；反映在转换矩阵中，就是M[si,sj]中不是一个单一状态，而是一个状态的集合。例2.9用例2.7中的NFA来识别
8、输入序列abb和abab。图2.7NFA识别输入序列abb和abab(a)abb的识别过程；(b)abab的识别过程NFA识别记号存在下述问题：(1)只有尝试了全部可能的路径，才能确定一个输入序列不被接受，而这些路径的条数随着路径长度的增长成指数增长。(2)识别过程中需要进行大量的回溯，时间复杂度与输入序列成指数级增长，且算法复杂。造成这种情况的原因是NFA的不确定性，即在当前的状态下，遇到的下一个字符可能有多于一条的路径可走，而在当前状态下，这些路径中哪条路径可以到达终态或者全部路径均不能到达终态都是不可知的。2.3.2确定的有限自动机(DeterministicFiniteAut
9、omata,DFA)定义2.5DFA是NFA的一个特例，其中：①没有状态具有ε状态转移(ε-transition)，即状态转换图中没有标记ε的边；②对每一个状态s和每一个字符a，最多有一个下一状态。例2.10识别由正规式(a
10、b)*abb说明的记号的DFA，其转换图和转换矩阵表示如图2.8所示。根据转换图，不难写出此DFA的定义。用它识别输入序列abb和abab的过程如图2.9所示。图2.8识别(a
11、b)*abb的DFA(a)转换图表示的DFA；(b)转换
