编译原理 第二章词法分析-2.ppt

1、2.3.2 NFA的定义,NFA的必要 识别程序设计语言中所有记号的DFA遇到的问题 典型的程序设计语言中都有许多记号，每一个记号都能被其自己的DFA识别出来 理论上应该能将所有的记号都合并为一个巨大的DFA。,这不是一个DFA。如果不使用系统化的方法将所有的记号都合并为一个巨大的DFA，将非常复杂。,解决这个问题的方法 将DFA扩展到NFA (对于当前的输入，当前的状态将转换为多个状态) NFA 转换为 DFA的算法,不确定的有穷自动机（NFA) NFA M=(S,T,S0,A), 其中 S 是状态的集合 是字母表 T是转换函数: S X ()- S的子集 S0S 初始状态 A S 接受状态

2、集合,NFA 类似于 DFA，除了 扩展 包括 NFA 可以包含 -转换无需考虑输入串就有可能发生的转换,扩展T的定义 每一个字符都可以导致多个状态。因此T的值是状态的一个集合而不是单独的状态,例 NFA M=（S，P，Z,0，1,f,S,Z） 其中 f（S，0）=P f（S，1）=S，Z f（Z，0）=P f（Z，1）=P f（P，1）=Z,矩阵表示:,状态图表示:,L(M): 由自动机 M 所接受（识别）的语言 L(M) ：is the set of strings of character字符c1c2cn ，每一个ci 都属于 ， 且存在关系：s1 在T(S0,c1)中,s2在T(S1,

3、c2)中,Sn 在T(Sn-1,cn) 中， s0 是初始状态， Sn 是A的元素 c1c2cn 中的任一 ci 都可能是 真正被接受的串是删除了的串 c1c2cn,非确定性 接受特定串的转换序列并不由状态和下一个输入字符在每一步确定下来,例如,下面两个转换序列都可接受串 “abb” :,2.3.3 用代码实现有穷自动机,构建扫描程序（词法分析程序）的过程:,正则表达式表示一种模式，用来描述记号 DFAs 表示按照正则表达式描述的模式接受符号串的算法,从正则表达式到DFA（2.4节) 有穷自动机构造词法分析程序,1 用代码实现 DFA,用代码实现DFA的一般算法 用一个变量保持当前的状态 将转

4、换写成一个双层嵌套的case语句而不是一个循环 第一个case语句测试当前的状态 嵌套着的第2层测试输入字符及所给的状态,state:=1;start while state=1 or 2 do case state of 1:case input character of letter:advance the input; state:=2; else state:=error or other; end case,例如:接受标识符的DFA,2:case input character of letter,digit:advance the input; state:=2; else sta

5、te:=3; end case; end case; end while; if state=3 then accept else error;,2 用代码实现DFA的状态转换表,使用转换表，可以用代码实现任一DFA,代码图解中用到的变量 转换被保存在一个转换数组 “T”中，T由状态和输入字符索引； 先行输入的转换是由布尔数组 “Advance”给出, 它们也由状态和输入字符索引； 由布尔数组 “Accept”给出的接受状态由状态索引,代码图解 state:=1; ch:=next input character; while not Acceptstate and not error(sta

6、te) do newstate:=Tstate,ch; if Advancestate,ch then ch:=next input char; state:=newstate; end while; if Acceptstate then accept;,表驱动的优点 代码的长度缩短了 相同的代码可以解决许多不同的问题 代码较易改变（维护） 缺点 表格会变得非常大，使得程序要求使用的空间也变得非常大,3 代码的动作,进行转换时发生的典型动作是：将字符从输入串中移到属于单个记号累积字符的字符串中 在达到某个接受状态时的典型动作是：将刚被识别的记号及相关属性返回 遇到出错状态的典型动作是：在输入

7、中备份（回溯）或生成错误记号,2.4 从正则表达式到 DFAs,正则表达式与 DFA的等价性 从正则表达式到DFA 从正则表达式到 NFA(2.4.1) 从 NFA 到 DFA(2.4.2) DFA的最小化(2.4.3),2.4.1 从正则表达式到 NFA,“语法制导”法: 按正则表达式的语法结构指引构造过程,正则表达式构造NFA的基本语法结构的构造规则,2对于正则表达式 ,构造的NFA为:,3对于正则表达式a, a ，构造的NFA为,1对于正则表达式,构造的NFA为:,x,复合正则表达式e的构造规则,2 然后按下述三种情况进行分解，直至每条弧上标记一个字符,1 先构造如下的正则表达式 “e”

8、 的NFA:,例如: 将正则表达式 (a|b)*abb 翻译成NFA,2.4.2 从 NFA 到 DFA,1 转换需解决的问题 删除-转换（合并） 如果 ,则删除S2,状态合并（消除在单个字符上的多重转换）,2 转换方法子集法,让DFA 的每个状态对应NFA 的一个状态集合。 即DFA用它的一个状态记录在NFA读入一个输入符号后可能达到的所有状态。,3 对状态集合I的有关运算,状态集合 I 的闭包_closure( I ) 是状态集I中的任何状态S以及经任意条弧而能到达的状态的集合。,以下将_closure( I ) 简写为closure(I) Closure(I) =I Sk | if Sj

9、 Sk, Sj Closure(I) ， Sk Closure(I) 状态集合的空闭包_closure 总是包含状态集合本身,if I=0,the _closure( I )=,例如: NFA,10,0,1,2,4,5,3,6,7,8,9,a,b,a,b,b,7,4,2,1,0,Ia子集 I 是状态集合, a 是字母表的一个字符 Move（I，a）=t|sI,and s t Ia= _closure ( Move( I , a ) ),Ib = _closure( ,例如: NFA,10,0,1,2,4,5,3,6,7,8,9,a,b,a,b,b,if I=0,1,2,4,7 then,Ia

10、= _closure( , ),= ,3, 8,6,7,1,2,4,5,6, ) = ,5,7,2,1,4,4 由NFA M 构造DFA M 的算法,将M的初始状态的空闭包作为 M的初始状态,继续这个过程，直到没有新状态或转换生成,将包含M接受状态的状态标记为接受状态,0,1, 7,2,4,10,5,6,7,1,2,4,9,5,6,7,1,2,4,5,6,7,1,2,4,8,3,6,7,1,2,4,Ib,Ia,I,T0,T1,T2,T3,T4,重新命名 DFA的状态集合,我们得到,2.4.3 将DFA中的状态数最小化,它们都是正则表达式a*的DFA , 但是后者是最小的 理论 对于任何给定的D

11、FA，都有一个含有最少量状态的等价的DFA,而且这个最小状态的DFA是唯一的,等价状态 如果 s 和 t 是两个状态，它们是等价当且仅当: s 和 t 都是接受状态或非接受状态。 对于任何一个字符 a, s 和 t必须转换到等价的状态里,C和F同是终态, C和F读入a都到达C,读入b都到达E,所以 C和F等价 S和C不等价，因为C是终态，而S不是终态,例如,最小化算法分割法 把一个DFA的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的.,首先, 分割为两个状态集合，一个包含所有接受状态，一个包含所有非接受状态。 考虑每个子集中状态针对字母表中每个字符 a 的转换，来决定子集中的所有状态是等价的还是应该分割的。 如果一个子集中的两个状态s 和 t 在 a 上有转换且位于不同的集合，则我们称 a 区分了状态 s 和 t,必须根据考虑中状态集合的 a-转换的位置将它们分隔开 继续这个过程直到每个集合仅包含一个元素（原始DFA最小）或一直是到再没有集合可以分隔了,a,1.将状态分为接受状态和非接受状态 S,A,B C,D,E,F 2 继续分割（寻找子集中不等价状态） S,A,B=S,BA=SAB C,D,E,F 3 让 D 表示 C,D,E,F,P=S,A,B,D,考虑非接受的错误状态的错误转换 有两个状