编译原理第3讲.ppt

1、温故知新,非形式化描述,形式化描述,正规式,名字,连接 指数,和 LUM 连接 LM 闭包 L* 正闭包 L+,?,计算机实现,状态转换图,词法记号的识别,词法记号的识别 等同于对字符串的匹配过程 这个匹配过程可以基于有限状态机来完成,简单的正则式d-a,0,1,a,正则式d-ab,0,2,a,1,b,正则式d-a|b,0,1,a,b,正规式d-a*,0,a,自动机的定义,正规式d-a? 字符a出现一次或者0次,0,1,a,练习,正规式d-a(a|b)* 请画出它的状态转换图,0,1,a,a,b,2.2 词法记号的描述与识别,2.2.4 转换图 关系算符的转换图,relop | | =,2.2

2、 词法记号的描述与识别,标识符和保留字的转换图,id letter (letter | digit )*,1、检查保留字表，如果在表中发现该词法单元则返回相应的记号并退出，否则转向2 2、该词法单元是标识符，在符号表中查找，若找到该词法单元则返回该条目的指针并退出，否则执行3 3、在符号表中建立一个新的条目，把该词法单元填入，并返回此新条目的指针,2.2 词法记号的描述与识别,无符号数的转换图,开始,num digit+ (.digit+)? (E (+ | )? digit+)?,2.2 词法记号的描述与识别,空白的转换图,delim blank | tab | newline ws del

3、im+,2.3 有 限 自 动 机,正规式,计算机实现,状态转换图,？,有限自动机,不确定有限自动机,确定有限自动机,等价,2.3 有 限 自 动 机,识别器：是一个程序，取串x作为输入，当x是语言的句子时，它回答“是”，否则回答“不是”。 状态转换图（有限自动机）识别器 确定/不确定有限自动机时空权衡问题 确定有限自动机：快，空间大,2.3 有 限 自 动 机,2.3.1 不确定的有限自动机（简称NFA） 一个数学模型，它包括: 状态集合S； 输入符号集合； 转换函数move : S () P(S)； 状态s0是开始状态； F S是接受状态集合。,识别语言 (a|b)*ab 的NFA,缺点：

4、1、输入字符包括 2、一个状态对于某个字符，可能有多条输出边,2.3 有 限 自 动 机,识别语言 (a|b)*ab 的NFA,状 态,NFA的转换表,优点：快速定位 缺点：字母表过大或大部分转换状态为空集时浪费空间,2.3 有 限 自 动 机,例 识别aa*|bb*的NFA,2.3 有 限 自 动 机,2.3.2 确定的有限自动机（简称DFA) 一个数学模型，包括：,状态集合S； 输入字母表； 转换函数move : S S； 唯一的初态 s S； 终态集合F S；,识别语言 (a|b)*ab 的DFA,优点：1、输入字符不包括 2、一个状态对于某个字符，只可能存在唯一条输出边,2.3 有 限

5、 自 动 机,2.3.3 NFA到DFA的变换 子集构造法 DFA的一个状态是NFA的一个状态集合 读了输入a1 a2 an后， NFA能到达的所有状态：s1, s2, , sk，则 DFA到达状态s1, s2, , sk,2.3 有 限 自 动 机,状态,2.3 有 限 自 动 机,状态,A = 0, 1, 2, 4, 7,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,2.3 有 限 自 动 机,状态,A

6、 = 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, 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、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, 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,

8、2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9,2.3 有 限 自 动 机,状态,_不是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(010)* B. 1(010)+

9、 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,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、

10、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、DFA的一个状态是NFA的一个状态集合 2、读了输入a1 a2 an后， NFA能到达的所有状态：s1, s

11、2, , sk，则 DFA到达状态s1, s2, , sk,0,0, 1,a,b,a,0, 2,b,2.3 有 限 自 动 机,a,b,2.3 有 限 自 动 机,状态,2.3 有 限 自 动 机,识别语言 (a|b)*ab 的自动机,2.3 有 限 自 动 机,识别语言 (a|b)*ab 的自动机,2.3.4 DFA的化简,DFA化简的途径 根据状态是否可以区分，将状态划分成若干个集合，每个集合内的状态之间都不可区分，而任意两个集合中的元素都是可以互相区分的。 依据原始的DFA，在合并后的状态基础上，建立新的状态转换关系。,2.3 有 限 自 动 机,2.3.4 DFA的化简 死状态 左图无

12、须加死状态，右图加入死状态E。,2.3 有 限 自 动 机,可区别的状态 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

13、, b = C,2.4 从正规式到有限自动机,正规式,计算机实现,状态转换图,有限自动机,不确定有限自动机,确定有限自动机,等价,？,本节内容,2.4 从正规式到有限自动机,首先构造识别和字母表中一个符号的NFA,2.4 从正规式到有限自动机,构造识别主算符为选择的正规式的NFA,2.4 从正规式到有限自动机,构造识别主算符为连接的正规式的NFA,2.4 从正规式到有限自动机,构造识别主算符为闭包的正规式的NFA,2.4 从正规式到有限自动机,对于加括号的正规式(s)，使用N(s)本身作为它的NFA。,2.4 从正规式到有限自动机,本方法产生的NFA有下列性质: N(r)的状态数最多是r中符号

14、和算符总数的两倍。 N(r)只有一个开始状态和一个接受状态，接受状态没有向外的转换。 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、从各个状态出发，构造边及输入字符记号

15、,例：识别 =0,1上能被能5整除的二进制数,号外：从语言到确定的有 限 自 动 机,例：识别 =0,1上能被能5整除的二进制数,号外：从语言到确定的有 限 自 动 机,例：识别 =0,1上能被能5整除的二进制数,号外：从语言到确定的有 限 自 动 机,例：识别 =0,1上能被能5整除的二进制数,号外：从语言到确定的有 限 自 动 机,例：识别 =0,1上能被能5整除的二进制数,号外：从语言到确定的有 限 自 动 机,例：识别 =0,1上能被能5整除的二进制数,号外：从语言到确定的有 限 自 动 机,例：识别 =0,1上能被能5整除的二进制数,号外：从语言到确定的有 限 自 动 机,例：识别 =0,1上能被能5整除的二进制数,号外：从语言到确定的有 限 自 动 机,例：识别 =0,1上能被能5整除的二进制数,号外：从语言到确定的有 限 自 动 机,例：识别 =0,1上能被能5整除的二进制数,号外：从语言到确定的有 限 自 动 机,例：识别 =0,1上能被能5整除的二进制数,号外：从语言到确定的有 限 自 动 机