第四章词法分析.pptVIP

1 9 开始 ? 0 a b ? a b 6 7 8 2 3 4 5 ? ? ? ? ? ? r9 r7 r8 r4 r3 r5 r6 * ) ( r2 r1 a | b a b (a|b)*ab的分解 1 9 开始 ? 0 a b ? a b 6 7 8 2 3 4 5 ? ? ? ? ? ? r9 r7 r8 r4 r3 r5 r6 * ) ( r2 r1 a | b a b (a|b)*ab的分解 (a|b)*ab的两个NFA的比较 1 2 开始 a 0 a b b 1 9 开始 ? 0 a b ? a b 6 7 8 2 3 4 5 ? ? ? ? ? ? * * 例：正规式(a|b)*(aa|bb)(a|b)*转化为自动机 * * 4.5有穷自动机和正规文法 有穷自动机和正规文法的等价性： 1.对于一个NFA M，都存在 一个正规文法G，使得L(G)=L(M). 2.对于一个正规文法G,都存在一个NFA M， ，使得L(M)=L(G). * * 正规文法=自动机 字母表与G的终结符集相同； G中的非终结符对应状态，开始符对应开始状态 增加一个新的终结状态Z。 G中的A-tB构造转换函数f(A,t)=B G中的A-t构造转换函数f(A,t)=Z * * 例：求与G[S]等价的NFA： G[S]： S-aA S-bB S-? A-aB A-bA B-aS B-bA B-? * * 自动机?正规文法 对转换函数f(A,t)=B，对应产生式： A→tB 对终态Z，增加一产生式： Z→? NFA的初态对应文法的开始符号 NFA的字母表对应文法的终结符号集 * * 例：给出与下图NFA等价的正规文法G A B C D b b b a a b a G=({A,B,C,D},{a,b},P,A)，其中P为： A-aB C- ? A-bD D-aB B-bC D-bD C-aA D- ? C-bD 复习要点 词法输出的token表示法 词法记号、模式、词法单元的概念 词法输出的token表示 正规式的概念及其代数性质 词法分析中的单词符号的描述工具 正规式代表的集合 正规文法和正规式相互转换 NFA和DFA NFA和DFA 的组成 NFA和DFA的相互转换 正规式与NFA的相互转换 例： 例：构造正规式1(0|1)*101相应的DFA 先构造NFA： DFA的状态图： 例：构造一个DFA，它接收Σ={0,1}上所有满足如下条件的字符串：每个1都有0直接跟在右边，并给出该语言的正规式 答：正规表达式是(0*10)*0*，或0*(0 | 10)*0* NFA： * 比较手工构造的NFA和用教材上语法制导的算法构造的NFA。鼓励学生写出引入尽可能少的? 转换的语法制导的算法，在将来的解题中使用这个算法。 * * 例：一个NFA M=（{0,1,2,3,4},{a,b},f,{0},{2,4}）其中 f(0,a)={0,3} f(0,b)={0,1} f(1,b)={2} f(2,a)={2} f(2,b)={2} f(3,a)={4} f(4,a)={4} f(4,b)={4} 画出其状态图 ∑*上的符号串t在NFA N上运行一个输入符号串t，（我们将它表示成t1tx的形式，其中t1∈∑，tx∈∑*）在NFA N上运行的定义为：f(Q， t1tx)=f(f(Q, t1),tx) 其中Q∈K. ∑*上的符号串t被NFA N接受若t∈∑*，f(S，t)=P，其中S为 N的开始状态，P∈Z，Z为终态集。则称t为NFA N所接受（识别）　　 NFA N所能接受的符号串的全体记为L(N) * * * * 具有?转移的不确定的有穷自动机NFA f为 K?(?∪{?})到K的子集（2K）的一种映射 1 2 ? ? 3 a b c * * 对任何一个具有?转移的不确定的有穷自动机NFA N，一定存在一个不具有?转移的不确定的有穷自动机NFA Ｍ，使得L(M)=L(N)。 c 2 a c b b 3 1 a c a b b * * 4.3.3 NFA的确定化 DFA是NFA的特例