编译原理之有限自动机

1、源程序源程序字符流字符流词法词法单元单元词法词法记号记号非形式非形式化描述化描述形式化形式化描述描述正规式正规式字母字母串串语言语言字母表字母表名名字字词法记号的识别词法记号的识别词法记号的识别等同于对字符串的匹配过程这个匹配过程可以基于有限状态机来完成 简单的正则式d-a 正则式d-ab 正则式d-a|b正规式d-a*自动机的定义自动机的定义正规式d-a?字符a出现一次或者0次练习练习正规式d-a(a|b)*请画出它的状态转换图 051624837return(relop, LE)return(relop, NE)return(relop, LT)return(relop, GE)retur

2、n(relop, GT)return(relop, EQ)开始开始=*otherother91011开始开始letterother*letter或或digitreturn(install_id( )id letter (letter | digit )*开始开始1912131415161718digitdigitdigitdigitdigitdigitother.E+/ Edigitotherotherreturn( install_num( ) )*num digit+ (. .digit+)? (E (+ | )? digit+)? delim blank | tab | newline

3、ws delim+2122开始开始delimother*delim20正规式正规式状态转换图状态转换图识别器：是一个程序，取串x作为输入，当x是语言的句子时，它回答“是”，否则回答“不是”。状态转换图（有限自动机）识别器确定/不确定有限自动机时空权衡问题确定有限自动机：快，空间大12开始开始a0abb12开始开始a0abb12开始开始a0abb34 12开始开始a0abbab 19开始开始 0ab ab6782345 19开始开始 0ab ab6782345 19开始开始 0ab ab6782345 19开始开始 0ab ab6782345 19开始开始 0ab ab6782345 19开始开

4、始 0ab ab6782345 19开始开始 0ab ab6782345 19开始开始 0ab ab6782345 19开始开始 0ab ab6782345 19开始开始 0ab ab6782345 19开始开始 0ab ab6782345 BD开始开始aAabbabCba19开始开始 0ab ab6782345 _不是NFA的成分.(北航2000硕士研究生入学考题)A.有穷字母表 B.初始状态集合 C.终止状态集合 D.有限状态集合词法分析器的输入是_.A.单词符号 B.源程序 C.语法单位 D.目标程序正规式M1和M2 等价是指_AM1和M2 的状态数相等.BM1和M2的有向弧条数相等.C

5、M1和M2所表示的语言集相等.DM1和M2的有向弧条数与状态数相等.设=0,1,则上所有以1开头,后跟至少1个010的字符的集合对应的正规式为_.A.1(010)* B. 1(010)+ C. (010)*1 D. (010)+ 12.3.3 NFA到到DFA的变换（方法的变换（方法2） 子集构造法子集构造法1、DFA的一个状态是的一个状态是NFA的一个状态集合的一个状态集合2、读了输入、读了输入a1 a2 an后后， NFA能到达的所有状态：能到达的所有状态：s1, s2, , sk，则则 DFA到达状态到达状态s1, s2, , sk12a开始开始0abb00, 1a2.3 有 限 自 动

6、 机 2.3.3 NFA到到DFA的变换的变换 子集构造法子集构造法1、DFA的一个状态是的一个状态是NFA的一个状态集合的一个状态集合2、读了输入、读了输入a1 a2 an后后， NFA能到达的所有状态：能到达的所有状态：s1, s2, , sk，则则 DFA到达状态到达状态s1, s2, , sk12a开始开始0abb00, 1ab2.3 有 限 自 动 机 2.3.3 NFA到到DFA的变换的变换 子集构造法子集构造法1、DFA的一个状态是的一个状态是NFA的一个状态集合的一个状态集合2、读了输入、读了输入a1 a2 an后后， NFA能到达的所有状态：能到达的所有状态：s1, s2,

7、, sk，则则 DFA到达状态到达状态s1, s2, , sk12a开始开始0abb00, 1aba2.3 有 限 自 动 机 2.3.3 NFA到到DFA的变换的变换 子集构造法子集构造法1、DFA的一个状态是的一个状态是NFA的一个状态集合的一个状态集合2、读了输入、读了输入a1 a2 an后后， NFA能到达的所有状态：能到达的所有状态：s1, s2, , sk，则则 DFA到达状态到达状态s1, s2, , sk12a开始开始0abb00, 1aba0, 2b2.3 有 限 自 动 机 2.3.3 NFA到到DFA的变换的变换 子集构造法子集构造法1、DFA的一个状态是的一个状态是NF

8、A的一个状态集合的一个状态集合2、读了输入、读了输入a1 a2 an后后， NFA能到达的所有状态：能到达的所有状态：s1, s2, , sk，则则 DFA到达状态到达状态s1, s2, , sk12a开始开始0abb00, 1aba0, 2b2.3 有 限 自 动 机 abBD开始开始aAabbabCba19开始开始 0ab ab6782345 BD开始开始aAabbabCba12开始开始a0abbab19开始开始 0ab ab6782345 BD开始开始aAabbabCba12开始开始a0abbab19开始开始 0ab ab6782345 12开始开始a0abbDFA化简的途径根据状态是否

9、可以区分，将状态划分成若干个集合，每个集合内的状态之间都不可区分，而任意两个集合中的元素都是可以互相区分的。依据原始的DFA，在合并后的状态基础上，建立新的状态转换关系。BD开始开始aAabbaa, bCbaEbBD开始开始aAabbabCbaBD开始开始aAabbabCbaBD开始开始aAabbabCbaBD开始开始aAabbabCba12开始开始a0abbab正规式正规式状态转换图状态转换图i开始开始 识别正规式识别正规式 的的NFAafif开始开始识别正规式识别正规式a的的NFA fi开始开始识别正规式识别正规式s | t的的NFAN (s)N (t) iN (s)f开始开始识别正规式识

10、别正规式st 的的NFAN (t)N (s)f开始开始识别正规式识别正规式s* 的的NFAi 19开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab19开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab 19开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab19开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab19开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab19开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab19开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab12开始开始a0abb19开始开始 0ab ab6782345 0123开始开始40123开始开始400123开始开始4100123开始开始41000123开始开始410010123开始开始4100100123开始开始41001010123开始开始410010100123开始开始410010