编译原理之有限自动机解析.ppt

温故知新,非形式化描述,形式化描述,正规式,名字,连接指数,和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词法记号的描述与识别,标识符和保留字的转换图,idletter(letter|digit)*,1、检查保留字表，如果在表中发现该词法单元则返回相应的记号并退出，否则转向22、该词法单元是标识符，在符号表中查找，若找到该词法单元则返回该条目的指针并退出，否则执行33、在符号表中建立一个新的条目，把该词法单元填入，并返回此新条目的指针,2.2词法记号的描述与识别,无符号数的转换图,开始,numdigit+(.digit+)?(E(+|)?digit+)?,2.2词法记号的描述与识别,空白的转换图,delimblank|tab|newlinewsdelim+,2.3有限自动机,正规式,计算机实现,状态转换图,？,有限自动机,不确定有限自动机,确定有限自动机,等价,2.3有限自动机,识别器：是一个程序，取串x作为输入，当x是语言的句子时，它回答“是”，否则回答“不是”。状态转换图（有限自动机）识别器确定/不确定有限自动机时空权衡问题确定有限自动机：快，空间大,2.3有限自动机,2.3.1不确定的有限自动机（简称NFA）一个数学模型，它包括:状态集合S；输入符号集合；转换函数move:S()P(S)；状态s0是开始状态；FS是接受状态集合。,识别语言(a|b)*ab的NFA,缺点：1、输入字符包括2、一个状态对于某个字符，可能有多条输出边,2.3有限自动机,识别语言(a|b)*ab的NFA,状态,NFA的转换表,优点：快速定位缺点：字母表过大或大部分转换状态为空集时浪费空间,2.3有限自动机,例识别aa*|bb*的NFA,2.3有限自动机,2.3.2确定的有限自动机（简称DFA)一个数学模型，包括：,状态集合S；输入字母表；转换函数move:SS；唯一的初态sS；终态集合FS；,识别语言(a|b)*ab的DFA,优点：1、输入字符不包括2、一个状态对于某个字符，只可能存在唯一条输出边,2.3有限自动机,2.3.3NFA到DFA的变换子集构造法DFA的一个状态是NFA的一个状态集合读了输入a1a2an后，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,7B=1,2,3,4,6,7,8,2.3有限自动机,状态,A=0,1,2,4,7B=1,2,3,4,6,7,8,2.3有限自动机,状态,A=0,1,2,4,7B=1,2,3,4,6,7,8C=1,2,4,5,6,7,2.3有限自动机,状态,A=0,1,2,4,7B=1,2,3,4,6,7,8C=1,2,4,5,6,7,2.3有限自动机,状态,A=0,1,2,4,7B=1,2,3,4,6,7,8C=1,2,4,5,6,7,2.3有限自动机,状态,A=0,1,2,4,7B=1,2,3,4,6,7,8C=1,2,4,5,6,7D=1,2,4,5,6,7,9,2.3有限自动机,状态,A=0,1,2,4,7B=1,2,3,4,6,7,8C=1,2,4,5,6,7D=1,2,4,5,6,7,9,2.3有限自动机,状态,A=0,1,2,4,7B=1,2,3,4,6,7,8C=1,2,4,5,6,7D=1,2,4,5,6,7,9,2.3有限自动机,状态,A=0,1,2,4,7B=1,2,3,4,6,7,8C=1,2,4,5,6,7D=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)+C.(010)*1D.(010)+1,2.3.3NFA到DFA的变换（方法2）子集构造法1、DFA的一个状态是NFA的一个状态集合2、读了输入a1a2an后，NFA能到达的所有状态：s1,s2,sk，则DFA到达状态s1,s2,sk,2.3有限自动机,2.3.3NFA到DFA的变换子集构造法1、DFA的一个状态是NFA的一个状态集合2、读了输入a1a2an后，NFA能到达的所有状态：s1,s2,sk，则DFA到达状态s1,s2,sk,2.3有限自动机,2.3.3NFA到DFA的变换子集构造法1、DFA的一个状态是NFA的一个状态集合2、读了输入a1a2an后，NFA能到达的所有状态：s1,s2,sk，则DFA到达状态s1,s2,sk,2.3有限自动机,2.3.3NFA到DFA的变换子集构造法1、DFA的一个状态是NFA的一个状态集合2、读了输入a1a2an后，NFA能到达的所有状态：s1,s2,sk，则DFA到达状态s1,s2,sk,2.3有限自动机,2.3.3NFA到DFA的变换子集构造法1、DFA的一个状态是NFA的一个状态集合2、读了输入a1a2an后，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|b)*ab的自动机,2.3有限自动机,识别语言(a|b)*ab的自动机,2.3.4DFA的化简,DFA化简的途径根据状态是否可以区分，将状态划分成若干个集合，每个集合内的状态之间都不可区分，而任意两个集合中的元素都是可以互相区分的。依据原始的DFA，在合并后的状态基础上，建立新的状态转换关系。,2.3有限自动机,2.3.4DFA的化简死状态左图无须加死状态，右图加入死状态E。,2.3有限自动机,可区别的状态A和B是可区别的状态A和C是不可区别的状态,2.3有限自动机,方法1.A,B,C,Dmove(A,B,C,a)=Bmove(A,B,C,b)=C,D2.A,C,B,Dmove(A,C,a)=Bmove(A,C,b)=C,2.3有限自动机,方法1.A,B,C,Dmove(A,B,C,a=Bmove(A,B,C,b=C,D2.A,C,B,Dmove(A,C,a=Bmove(A,C,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中符号和算符总数的两倍。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、从各个状态出发，构造边及输入字符记号,例：识别=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整除的二进制数,号外：从语言到确定的有限自动机,小结,正规式,计算机实现,状态