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

第二章 词法分析（2）;内容简介;0.示例：一个单词的识别;0.示例：一个单词的识别;0.用程序流程图的观点看待上述程序;2.3 记号的识别 —— 有限自动机; NFA，可以用两种直观的方式来表示 ——状态转换图：是一个有向图，每个状态对应转换图中的一个节点；每个move函数对应转换图中的一条有向边，字符ch(或ε)是边上的标记。初态是转换图中没有前驱的节点，终态节点可以用一个加粗的圆圈或者双圈表示。 ——状态转换矩阵：是一个二维数组，其中每个元素M[si, 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函数是一对多的；反映在转换图中，就是从一个节点可通过多于一条标记相同字符的边转移到不同的状态；反映在转换矩阵中，就是M[si, 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.9 DFA识别输入序列abb和abab; 与NFA相比，DFA的特点就是它的确定性，即在当前状态下，对同一个字符ch，最多有一个下一状态转移。确定性反映在DFA的定义中，就是move函数是一对一的；反映在转换图中，就是从一个节点出发的任何不同的边上标记的字符均不同；反映在转换矩阵中，就是M[si, sj]中是一个单一状态。 由于在DFA上识别输入序列时，在任何一个当前状态下遇到任何输入字符，其下一状态转移均是唯一确定的，因此，无论是接受还是不接受，均经历一条确定的路径，而无其他任何路径可走。也就是说，在DFA上识别输入序列无需回溯，从而大大简化了记号的识别过程。; DFA识别输入序列的过程总结为算法2.1，被称为模拟器(模拟DFA的行为)，也被称为驱动器(用DFA的数据驱动分析动作)。模拟DFA算