编译原理之有限自动机

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

2、urn(relop, LT) return(relop, GE) return(relop, GT) return(relop, EQ) 开始开始 = = * * other other 91011 开始开始 letterother * letter或或digit return(install_id( ) id letter (letter | digit )* 开始开始 19 12 131415161718 digit digit digit digit digit digit other . E+/ E digit other other return( install_num( ) )

3、* num digit+ (. .digit+)? (E (+ | )? digit+)? delim blank | tab | newline ws delim+ 21 22 开始开始delimother * delim 20 正规式正规式状态转换图状态转换图 识别器：是一个程序，取串x作为输入，当 x是语言的句子时，它回答“是”，否则回 答“不是”。 状态转换图（有限自动机）识别器 确定/不确定有限自动机时空权衡问题 确定有限自动机：快，空间大 12 开始开始a 0 a b b 12 开始开始a 0 a b b 12 开始开始 a 0 a b b 3 4 12 开始开始a 0 a b b

4、 a b 1 9 开始开始 0 a b ab 678 23 45 1 9 开始开始 0 a b ab 678 23 45 1 9 开始开始 0 a b ab 678 23 45 1 9 开始开始 0 a b ab 678 23 45 1 9 开始开始 0 a b ab 678 23 45 1 9 开始开始 0 a b ab 678 23 45 1 9 开始开始 0 a b ab 678 23 45 1 9 开始开始 0 a b ab 678 23 45 1 9 开始开始 0 a b ab 678 23 45 1 9 开始开始 0 a b ab 678 23 45 1 9 开始开始 0 a b

5、ab 678 23 45 BD 开始开始a A a b b a b C b a 1 9 开始开始 0 a b ab 678 23 45 _不是NFA的成分.(北航2000硕士研究生入学考题) A.有穷字母表 B.初始状态集合 C.终止状态集合 D.有限状 态集合 词法分析器的输入是_. A.单词符号 B.源程序 C.语法单位 D.目标程序 正规式M1和M2 等价是指_ AM1和M2 的状态数相等. BM1和M2的有向弧条数相等. CM1和M2所表示的语言集相等. DM1和M2的有向弧条数与状态数相等. 设=0,1,则上所有以1开头,后跟至少1个010的字符 的集合对应的正规式为_. A.1(0

6、10)* B. 1(010)+ C. (010)*1 D. (010)+ 1 2.3.3 NFA到到DFA的变换（方法的变换（方法2） 子集构造法子集构造法 1、DFA的一个状态是的一个状态是NFA的一个状态集合的一个状态集合 2、读了输入、读了输入a1 a2 an后后， NFA能到达的所有状态：能到达的所有状态：s1, s2, , sk，则则 DFA到达状态到达状态s1, s2, , sk 1 2 a 开始开始 0 a b b00, 1 a 2.3 有 限 自 动 机 2.3.3 NFA到到DFA的变换的变换 子集构造法子集构造法 1、DFA的一个状态是的一个状态是NFA的一个状态集合的一个

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

8、00, 1 a b a 2.3 有 限 自 动 机 2.3.3 NFA到到DFA的变换的变换 子集构造法子集构造法 1、DFA的一个状态是的一个状态是NFA的一个状态集合的一个状态集合 2、读了输入、读了输入a1 a2 an后后， NFA能到达的所有状态：能到达的所有状态：s1, s2, , sk，则则 DFA到达状态到达状态s1, s2, , sk 1 2 a 开始开始 0 a b b00, 1 a b a 0, 2 b 2.3 有 限 自 动 机 2.3.3 NFA到到DFA的变换的变换 子集构造法子集构造法 1、DFA的一个状态是的一个状态是NFA的一个状态集合的一个状态集合 2、读了输

9、入、读了输入a1 a2 an后后， NFA能到达的所有状态：能到达的所有状态：s1, s2, , sk，则则 DFA到达状态到达状态s1, s2, , sk 1 2 a 开始开始 0 a b b00, 1 a b a 0, 2 b 2.3 有 限 自 动 机 a b BD 开始开始a A a b b a b C b a 1 9 开始开始 0 a b ab 678 23 45 BD 开始开始a A a b b a b C b a 12 开始开始a 0 a b b a b 1 9 开始开始 0 a b ab 678 23 45 BD 开始开始a A a b b a b C b a 12 开始开始a

10、 0 a b b a b 1 9 开始开始 0 a b ab 678 23 45 12 开始开始a 0 a b b DFA化简的途径 根据状态是否可以区分，将状态划分成若干个 集合，每个集合内的状态之间都不可区分，而 任意两个集合中的元素都是可以互相区分的。 依据原始的DFA，在合并后的状态基础上，建 立新的状态转换关系。 BD 开始开始a A a b b a a, b C b a E b BD 开始开始a A a b b a b C b a BD 开始开始a A a b b a b C b a BD 开始开始a A a b b a b C b a BD 开始开始a A a b b a b C

11、 b a 12 开始开始a 0 a b b a b 正规式正规式状态转换图状态转换图 i 开始开始 识别正规式识别正规式 的的NFA a fif 开始开始 识别正规式识别正规式a的的NFA f i 开始开始 识别正规式识别正规式s | t的的NFA N (s) N (t) i N (s) f 开始开始 识别正规式识别正规式st 的的NFA N (t) N (s) f 开始开始 识别正规式识别正规式s* 的的NFA i 1 9 开始开始 0 a b ab 678 23 45 r9 r7 r8 r4 r3 r5 r6 * )( r2r1 a | b a b 1 9 开始开始 0 a b ab 67

12、8 23 45 r9 r7 r8 r4 r3 r5 r6 * )( r2r1 a | b a b 1 9 开始开始 0 a b ab 678 23 45 r9 r7 r8 r4 r3 r5 r6 * )( r2r1 a | b a b 1 9 开始开始 0 a b ab 678 23 45 r9 r7 r8 r4 r3 r5 r6 * )( r2r1 a | b a b 1 9 开始开始 0 a b ab 678 23 45 r9 r7 r8 r4 r3 r5 r6 * )( r2r1 a | b a b 1 9 开始开始 0 a b ab 678 23 45 r9 r7 r8 r4 r3 r

13、5 r6 * )( r2r1 a | b a b 1 9 开始开始 0 a b ab 678 23 45 r9 r7 r8 r4 r3 r5 r6 * )( r2r1 a | b a b 1 2 开始开始a 0 a b b 1 9 开始开始 0 a b ab 678 23 45 0123 开始开始 4 0123 开始开始 4 0 0123 开始开始 4 1 0 0123 开始开始 4 1 0 0 0123 开始开始 4 1 0 0 1 0123 开始开始 4 1 0 0 1 0 0123 开始开始 4 1 0 0 1 0 1 0123 开始开始 4 1 0 0 1 0 1 0 0123 开始开始 4 1 0 0 1 0 1 0 1 0123 开始开始 4 1