《编译原理课程第3讲》由会员分享，可在线阅读，更多相关《编译原理课程第3讲（65页珍藏版）》请在金锄头文库上搜索。
1、温故知新,非形式化描述,形式化描述,正规式,名字,连接 指数,和 LUM 连接 LM 闭包 L* 正闭包 L+,?,计算机实现,状态转换图,2.2 词法记号的描述与识别,2.2.4 转换图 关系算符的转换图,relop | | =,2.2 词法记号的描述与识别,标识符和保留字的转换图,id letter (letter | digit )*,1、检查保留字表，如果在表中发现该词法单元则返回相应的记号并退出，否则转向2 2、该词法单元是标识符，在符号表中查找，若找到该词法单元则返回该条目的指针并退出，否则执行3 3、在符号表中建立一个新的条目，把该词法单元填入，并返回此新条目的指针,2.2 词法
2、记号的描述与识别,无符号数的转换图,开始,num digit+ (.digit+)? (E (+ | )? digit+)?,2.2 词法记号的描述与识别,空白的转换图,delim blank | tab | newline ws delim+,2.3 有 限 自 动 机,正规式,计算机实现,状态转换图,？,有限自动机,不确定有限自动机,确定有限自动机,等价,2.3 有 限 自 动 机,识别器：是一个程序，取串x作为输入，当x是语言的句子时，它回答“是”，否则回答“不是”。 状态转换图（有限自动机）识别器 确定/不确定有限自动机时空权衡问题 确定有限自动机：快，空间大,2.3 有 限 自 动
3、机,2.3.1 不确定的有限自动机（简称NFA）一个数学模型，它包括:状态集合S；输入符号集合；转换函数move : S () P(S)；状态s0是开始状态；F S是接受状态集合。,识别语言 (a|b)*ab 的NFA,缺点：1、输入字符包括 2、一个状态对于某个字符，可能有多条输出边,2.3 有 限 自 动 机,识别语言 (a|b)*ab 的NFA,状 态,NFA的转换表,优点：快速定位 缺点：字母表过大或大部分转换状态为空集时浪费空间,2.3 有 限 自 动 机,例 识别aa*|bb*的NFA,2.3 有 限 自 动 机,2.3.2 确定的有限自动机（简称DFA)一个数学模型，包括：,状态
4、集合S；输入字母表；转换函数move : S S；唯一的初态 s S；终态集合F S；,识别语言 (a|b)*ab 的DFA,优点：1、输入字符不包括 2、一个状态对于某个字符，只可能存在唯一条输出边,2.3 有 限 自 动 机,2.3.3 NFA到DFA的变换 子集构造法 DFA的一个状态是NFA的一个状态集合 读了输入a1 a2 an后，NFA能到达的所有状态：s1, s2, , sk，则DFA到达状态s1, s2, , sk,2.3.3 NFA到DFA的变换 子集构造法1、DFA的一个状态是NFA的一个状态集合2、读了输入a1 a2 an后，NFA能到达的所有状态：s1, s2, , s
5、k，则DFA到达状态s1, s2, , sk,2.3 有 限 自 动 机,2.3.3 NFA到DFA的变换 子集构造法1、DFA的一个状态是NFA的一个状态集合2、读了输入a1 a2 an后，NFA能到达的所有状态：s1, s2, , sk，则DFA到达状态s1, s2, , sk,2.3 有 限 自 动 机,2.3.3 NFA到DFA的变换 子集构造法1、DFA的一个状态是NFA的一个状态集合2、读了输入a1 a2 an后，NFA能到达的所有状态：s1, s2, , sk，则DFA到达状态s1, s2, , sk,2.3 有 限 自 动 机,2.3.3 NFA到DFA的变换 子集构造法1、D
6、FA的一个状态是NFA的一个状态集合2、读了输入a1 a2 an后，NFA能到达的所有状态：s1, s2, , sk，则DFA到达状态s1, s2, , sk,2.3 有 限 自 动 机,2.3.3 NFA到DFA的变换 子集构造法1、DFA的一个状态是NFA的一个状态集合2、读了输入a1 a2 an后，NFA能到达的所有状态：s1, s2, , sk，则DFA到达状态s1, s2, , sk,0,0, 1,a,b,a,0, 2,b,2.3 有 限 自 动 机,a,b,2.3 有 限 自 动 机,状态,2.3 有 限 自 动 机,状态,A = 0, 1, 2, 4, 7,2.3 有 限 自 动
7、 机,状态,A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8,2.3 有 限 自 动 机,状态,A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8,2.3 有 限 自 动 机,状态,A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7,2.3 有 限 自 动 机,状态,A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7,2.3 有 限 自 动 机,状态,A = 0, 1, 2, 4,
8、7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7,2.3 有 限 自 动 机,状态,A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9,2.3 有 限 自 动 机,状态,A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9,2.3 有 限 自 动 机,状态,A = 0, 1, 2, 4, 7 B = 1, 2,
9、3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9,2.3 有 限 自 动 机,状态,A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9,2.3 有 限 自 动 机,状态,2.3 有 限 自 动 机,识别语言 (a|b)*ab 的自动机,2.3 有 限 自 动 机,识别语言 (a|b)*ab 的自动机,2.3 有 限 自 动 机,2.3.4 DFA的化简 死状态 左图无须加死状态，右图加入死状态E。,2.3
10、有 限 自 动 机,可区别的状态 A和B是可区别的状态 A和C是不可区别的状态,2.3 有 限 自 动 机,方法 1. A, B, C, D move(A, B, C, a = B move(A, B, C, b = C, D 2. A, C, B, D move(A, C, a = B move(A, C, b = C,2.3 有 限 自 动 机,方法 1. A, B, C, D move(A, B, C, a = B move(A, B, C, b = C, D 2. A, C, B, D move(A, C, a = B move(A, C, b = C,2.4 从正规式到有限自动机,正
11、规式,计算机实现,状态转换图,有限自动机,不确定有限自动机,确定有限自动机,等价,？,本节内容,2.4 从正规式到有限自动机,首先构造识别和字母表中一个符号的NFA,2.4 从正规式到有限自动机,构造识别主算符为选择的正规式的NFA,2.4 从正规式到有限自动机,构造识别主算符为连接的正规式的NFA,2.4 从正规式到有限自动机,构造识别主算符为闭包的正规式的NFA,2.4 从正规式到有限自动机,对于加括号的正规式(s)，使用N(s)本身作为它的NFA。,2.4 从正规式到有限自动机,本方法产生的NFA有下列性质:N(r)的状态数最多是r中符号和算符总数的两倍。 N(r)只有一个开始状态和一个
12、接受状态，接受状态没有向外的转换。 N(r)的每个状态有一个用的符号标记的指向其它结点的转换，或者最多两个指向其它结点的转换。,2.4 从正规式到有限自动机,2.4 从正规式到有限自动机,2.4 从正规式到有限自动机,2.4 从正规式到有限自动机,2.4 从正规式到有限自动机,2.4 从正规式到有限自动机,2.4 从正规式到有限自动机,2.4 从正规式到有限自动机,(a|b)*ab的两个NFA的比较,号外：从语言到确定的有限自动机,例：识别 =0,1上能被5整除的二进制数,方法： 1、列出全部可能的状态 2、从各个状态出发，构造边及输入字符记号,例：识别 =0,1上能被能5整除的二进制数,号外
13、：从语言到确定的有 限 自 动 机,例：识别 =0,1上能被能5整除的二进制数,号外：从语言到确定的有 限 自 动 机,例：识别 =0,1上能被能5整除的二进制数,号外：从语言到确定的有 限 自 动 机,例：识别 =0,1上能被能5整除的二进制数,号外：从语言到确定的有 限 自 动 机,例：识别 =0,1上能被能5整除的二进制数,号外：从语言到确定的有 限 自 动 机,例：识别 =0,1上能被能5整除的二进制数,号外：从语言到确定的有 限 自 动 机,例：识别 =0,1上能被能5整除的二进制数,号外：从语言到确定的有 限 自 动 机,例：识别 =0,1上能被能5整除的二进制数,号外：从语言到确
14、定的有 限 自 动 机,例：识别 =0,1上能被能5整除的二进制数,号外：从语言到确定的有 限 自 动 机,例：识别 =0,1上能被能5整除的二进制数,号外：从语言到确定的有 限 自 动 机,例：识别 =0,1上能被能5整除的二进制数,号外：从语言到确定的有 限 自 动 机,小结,正规式,计算机实现,状态转换图,不确定有限自动机,确定有限自动机,等价,用正规式语法结构来指导构造过程,子集构造法,合并不可区别状态,最简确定有限自动机,等价,语言,确定有限自动机,状态列举法,习 题,2.7 (c) (d), 2.8 ( 仅为2.7(c) )， 2.12（a）,练习：构造 DFA，接受 0和1的个数都是偶数的二进制串。 eg: 0011, 00, 1100, 1010, 111100,例：DFA,接受 0和1的个数都是偶数的字符串,2.3 有 限 自 动 机,
