编译程序原理与实现：第2章 词法分析非确定有限自动机

1、第2章 outline一、词法分析概述1，词法分析程序的功能2，词法分析相关的一些问题二、正则表达式三、有限自动机1，确定有限自动机DFA2，非确定有限自动机NFA，NFA到DFA的转换3，DFA的化简4，正则表达式到NFA的转换四、词法分析程序构造2、非确定有限自动机确定有限自动机是五元组(SS,S0,TS)确定性体现：初始状态唯一、转换函数是单值函数非确定有限自动机：也是五元组(SS,S0,TS)其中 SS=S0,S1,Sn是状态集 是字母表 S0 SS是初始状态集,不能为空 是转换函数，但不要求是单值的 : SS ( ) 2SS TS SS是终止状态集，可为空。非确定有限自动机的例子 =

2、 a, b SS: S0, S1, S2, S3初始状态集: S0 , S1 终止状态集: S3 : (S0,a) S1, S3,(S0,) S2, (S1,b)S1, (S1, )S2, (S2, )S3, (S3, b)S3NFA也可以用状态转换图或状态转换矩阵表示非确定有限自动机的例子S0aS2S3abbS1abS+S1,S3S2S1+S1S2S2S3S3-S3状态集合NFA接受的字符串NFA接受的字符串如果M是一个NFA, a1 a2 an 是一个字符串，如果存在一个状态序列 (S0, S1 , ,Sn),满足 S0 S1 , S1 S2 , , Sn-1 Sn其中 S0 是开始状态之

3、一，Sn 是接受状态之一，则串a1 a2 an 被NFA M接受.NFA定义的串的集合(NFA接受的语言)NFA M接受的所有串的集合，称为M定义的语言，记为 L(M)a1a2anNFA与DFA的比较DFANFA初始状态一个初始状态初始状态集合边不允许允许 (S, a) S or S1, , Sn or 实现容易有不确定性对于确定的输入串，DFA只有一条路径接受它NFA则可能需要在多条路径中进行选择！NFA到DFA的转换例如输入串：100NFANFA需要在多条路径中选择，因此的效率低！但NFA描述问题方便。NFA和DFA都识别正则语言。NFA可转换成DFA。SPQ010101NFA到DFA的转

4、换对任意NFA，都存在一个DFA与之等价。转换的思想：消除不确定性合并初始状态集成一个状态消除边消除多重定义的边。123aa12,3a454，5-closure(空闭包)对于给定的 NFA A, 和它的一个状态集合 SS,SS的空闭包计算如下： 第一步：令-closure(SS) = SS;第二步：如果在状态集SS中存在状态s, s到状态s存在一条 边， 并且s -closure(SS ), 则将s 加入SS的空闭包-closure(SS);重复第二步,直到再没有状态可加入-closure(SS) .-closure的例子S0aS1S2S3abc -closure(S0, S1) = S0,

5、S1 S0, S1, S2 S0, S1, S2 S0, S1, S2,S3转向状态对于NFA A中的给定状态集合SS 和符号 a,NextStates(SS, a) = s | 对于状态集SS中的一个状态s1,如果A中存在一条从s1到s的a转换边SSS2S3S1SSaa(S1,S2,S3,a) = S, S转向状态的例子S0aS1S2S3abc NextStates(S0, S1, a) = S1, S3 NextStates(S0, S1, b) = S1NFA到DFA的转换算法(子集法)给定一个 NFA A = , SS, SS0, , TS生成等价的 DFA A = , SS,S0,

6、, TS步骤(1) 令S0 = -closure(SS0), 将S0 加入 SS;(2) 从SS中选择一个状态s, 对于任意 a, 若有 s = -closure(NextStates(s, a), 令 (s, a) s。若sSS,将s加入SS; (3) 重复第二步，直到SS 中的所有状态都被处理过;(4) 对于SS中的一个状态s, 如s = S1, ., Sn, 如果有状态 SiTS, 则s是 A的一个接受状态, 将s加入 TS;NFA到DFA转换的例子例1：= a, b, c,S0 = -closure(S0, S10) = S0, S10, S2,S* , abcS0, S1, S2,S

7、3 + -S1, S3,S2S1, S3,S2S3S1, S3,S2-S1, S3,S2S3S3-S3S0aS1S2S3abcNFA到DFA转换的例子例2： 01S0+S0,S1S0S0,S1-S0,S1,S2S0S0,S1,S2-S0,S1,S2S0S0S1S2SPQ010101NFA到DFA转换的例子例3：q0q1q4q6q2q3q5aaabbba,babq0+q1,q3q1,q3q1,q3q2,q4,q6,q5q2,q4,q6,q5-q4,q6,q5q6,q5,q4q4,q6,q5-q6,q5,q4q6,q5,q4DFA的化简NFA转换成的DFA，有时候会有一些等价状态，这些等价状态会使

8、分析效率降低，因此应合并。合并了所有等价状态后的DFA称为最简自动机。q0aqAqcqBaa,bbabDFA M1等价DFA和最简DFA的定义等价 DFAs如果两个DFA接受的字符串的集合是相同的;在接受相同字符串集的DFA中，最小DFA指的是状态数最少的DFAq0aqAqca,bbDFA M2a等价的DFAsS0aS1S4*bdS3*S2dS0aS1bdS*两个DFA等价，是因为在这两个DFA中存在接受相同字符串的状态!主要思想等价状态对于DFA中的任意两个状态 s1和 s2，如果分别将 s1和s2当作开始状态，它们接受的字符串集合相同，则称 s1 和 s2 是等价状态;DFA化简的两种方式

9、合并等价状态; (状态合并法)分离不等价状态;(状态分离法) 状态分离法化简DFA给定一个DFA A = , SS, S0, , TS：要生成与其等价的 DFA A = , SS,S0, , TS分离步骤：(1) 将A的所有状态分成两组： 非终止状态 , 终止状态 ;(2) 选择一组状态 SSi = Si1, Sin, 用split(SSi)替换SSi ;(3) 重复第(2)步，直到所有组都被处理过; (4) 令SS = 组的集合;(5) S0 ：包含S0 的组作为S0 ;(6) TS : 包含A的终止状态的组， 作为A的终止状态;(7) : （SSi, a）= SSj, 若在A中有Si Sj

10、, 且 si SSi, sj SSja分离状态 给定一个DFA A = , SS, S0, , TS：假定状态集合SS分成了m组： SS1, , SSm, SS1 SSm = SS, SS1 SSm = ; 任取一个状态组SSi = Si1, Sin, 考察SSi是否可继续分离split(SSi) ：判断SSi是否需要分裂，是则将SSi分裂成两组G1和G2, 过程如下：初始 G1 = Sip , 1 p n ,即任取SSi中的一个状态放入G1, G2 = .for j = 1 to n (假设 SSi 有n个状态)对于所有 a, 任意的Sij SSi,若有 (Sip,a ) = Sk ， (Sij, a) = Sq ，如果 Sk和Sq属于同一个组 SSt , 则将 Sij 加入组 G1;否则将 Sij 加入组 G2; 简单例子S0aS1S4*bdS3*S2dS0, S1, S2, S3*, S4*S0 , S1, S2, S3*, S4*DFA化简的例子例1：0，1，2，3和40,1,3,2和40,3,1,2和401234aabbabbb0124aabbbbDFA化简的例子例