自动机理论--词法分析-课件

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,医学课件,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,医学课件,*,第二章 词法分析,词法分析概述,正则表达式,自动机理论,词法分析器的设计与实现,第二章 词法分析词法分析概述,3,有限自动机,确定有限自动机,DFA,非确定有限自动机,NFA,NFA,到,DFA,的转换,DFA,的化简,2,3 有限自动机确定有限自动机DFA2,3,3,4,4,5,待机,待选择,冲调,待取,不足,投币,投币,选择恰当,/,金额充足,付咖啡,/,找零钱,取咖啡,/,取零钱,金额不足,超时,退款,退款,超时,5待机待选择冲调待取不足投币投币选择恰当/金额充足付咖啡/找,3.1,确定有限自动机,定义,1,：,一个确定有限自动机,DFA,为一个五元组,(,S,f,s,0,Z),，其中：,是有穷字母表，每个元素称为一个输入字符；,S,是一个有穷集，它的每个元素称为一个状态；,f,是在,SS,上的单值转换函数；,s,0,S,是唯一的一个初始状态；,Z,S,，是终止状态集，又称为接受状态集。,6,3.1 确定有限自动机定义1：一个确定有限自动机DFA为一个,7,0,1,2,3,4,c,c,e,f,g,d,b,a,a,b,0,3.1.1,DFA,实例,1,701234ccefgdbaab03.1.1 DFA实例1,3.1.1,DFA,实例,2,DFA M=(a, b, S, U, V, Q, f, S, Q),，其中,f,定义为：,f (S, a)=Uf (V, a)=U,f (S, b)=Vf (V, b)=Q,f (U, a)=Qf (Q, a)=Q,f (U, b)=Vf (Q, b)=Q,8,3.1.1 DFA实例2DFA M=(a, b, ,3.1.2,DFA,的两种表示方式,状态转换图,结点表示状态，转换边表示转换函数，边的箭头方向指向转换函数中定义的转换方向。标识出初始状态和终止状态。,状态转换矩阵,可用二维数组描述。标识出初始状态和终止状态。若,DFA,中有,f (S,I, a)=S,J,，则：,Trans (,S,I,，,a),S,J,9,3.1.2 DFA的两种表示方式状态转换图9,3.1.3,DFA,接受的字符串,定义,2,：,对于,*,中的任何字符串,t,若存在一条从初始结点到某一终止结点的路径，且这条路上所有弧的标记符连接成的字符串等于,t,则称,t,为,DFA M,所,接受（识别）的字符串,。,DFA M,所能接受的字符串的全体记为,L(M),称为,M,所能接受（识别）的,语言,。,10,3.1.3 DFA接受的字符串定义2：对于*中的任何字符串,思考,试用自动机描述银行ATM机的状态转换。,确定有限自动机名字中的“确定”二字含义、用途、局限？,11,思考试用自动机描述银行ATM机的状态转换。11,3.1.4,DFA,的确定性,初始状态,唯一,。,转换函数,f:S,S,是一个,单值,函数，也就是说，对任何状态,sS,和输入符号,a, f(s,a),唯一地确定了下一个状态。即转换函数至多确定一个状态。,没有空边,，即不接受任何输入就进行状态转换（没有输入为，有时用表示的边）。,12,3.1.4 DFA的确定性初始状态唯一。12,3.1.5 DFA的局限,13,3.1.5 DFA的局限13,3.2,非确定有限自动机,定义,3,：,一个非确定有限自动机,(NFA)A,是一个五元组,A=(,SS, f, S,0,TS).,其中,是字母表,SS,是状态集,f,是转换函数,f: SS () 2,SS,S,0,是初始状态集,TS,是终止状态集,14,3.2 非确定有限自动机定义3：一个非确定有限自动机(NFA,3.2.1,NFA,接受的字符串,定义,4,：,设,A,是一个,NFA,，,A= (,SS, f, S,0,TS),则定义,L(A),为从任意初始状态到任意终止状态所接受的字符串集合。,L(A)=|s,0,s, s,0,S,0,sTS,一个,NFA,的例子,S,P,Z,0,0,1,1,1,1,15,3.2.1 NFA接受的字符串定义4：设A是一个NFA，A=,3.2.2,等价和,NFA,的确定化转换,自动机等价,设,A,1,和,A,2,是同一个字母表上的自动机，如果有,L(A,1,)=L(A,2,),，则称,A,1,和,A,2,等价。,NFA,到,DFA,的转换（确定化）,定理：对于每一个非确定自动机,A,，存在一个确定自动机,A,，使得,L(A)=L(A),。,16,3.2.2 等价和NFA的确定化转换自动机等价16,3.2.2.1,NFA,的一种确定性方法,子集法,已知,NFA: A=(, S, f, S,0, Z),构造,DFA: A=(, S, f, S,0, Z),令,A,的,初始状态,为,S,0,=S,1,S,2,S,k,其中,S,1,S,k,是,A,的全部初始状态。,若,X=S,1,S,m,是,A,的一个状态，,a,则定义,f(X,a)=f(S,1,a),f(S,2,a),f(S,m,a)=Q,，将,Q,加入,S,，重复该过程，直到,S,收敛。,若,Y=S,1,S,n,是,A,的一个状态,且存在一个,S,i,是,A,的终止状态，则令,Y,为,A,的,终止状态,。,17,3.2.2.1 NFA的一种确定性方法子集法17,NFA确定化实例,18,1,3,2,5,6,4,NFA确定化实例18132564,带“空”边的自动机,19,0,1,2,space,D,+,-,.,D,4,D,3,带“空”边的自动机19012spaceD+-.D4D3,闭包？！,在数学中，一个集合被称为在某个运算下,闭合,，如果在这个集合的成员上的运算生成这个集合的成员。如自然数之与减法。,当一个集合,S,不闭合在某个运算下的时候，我们通常可以找到包含,S,的最小的闭合集合。这个最小闭合集合被称为,S,的,(,关于这个运算的,),闭包,。如在自然数集的减法下的闭包，是整数集。,20,闭包？！在数学中，一个集合被称为在某个运算下闭合，如果在这个,3.2.2.2,带空边的,NFA,的确定化,定义,5,：,设,I,是,NFA,的状态集的子集，则,I,的,闭包,为：,_CLOSURE(I)=Iq|f(p, )=q,p_CLOSURE(I),定义,6,：,设,I,是,NFA,状态集的子集，则,I,a,=_CLOSURE(J),，,J=q|f(p,a)=q,pI,21,3.2.2.2 带空边的NFA的确定化定义5：设I是NFA的,修改后的子集法,已知,A,：,NFA,构造,A,:DFA,令,A,的初始状态为,I,0,=,_CLOSURE(,S,1,S,2,S,k,),其中,S,1,S,k,是,A,的全部初始状态。,若,I=S,1,S,m,是,A,的一个状态，,a,则定义,f(I, a)=I,a,将,I,a,加入,S,，重复该过程，直到,S,收敛。,若,I=S,1,S,n,是,A,的一个状态,且存在一个,S,i,是,A,的终止状态，则令,I,为,A,的终止状态。,22,修改后的子集法22,带空边的,NFA,确定化的例子,23,带空边的NFA确定化的例子23,I,0,=1,2,I,1,=I,0a,=2,4,5,6,7,I,2,=I,0b,=3,8,I,3,=I,1a,=,I,4,=I,1b,=3,8,9,I,5,=I,2a,=9,I,6,=I,2b,=,I,7,=I,4a,=9=I,5,I,8,=I,4b,=,24,DFA M=,(,I,0,I,1,I,2,I,4,I,5,f(I,0,a)=I,1,f(I,0,b)=I,2,f(I,1,b)=I,4,f(I,2,a)=I,5,f(I,4,a)=I,5,I,0,I,1,I,4,I,5,),I0=1,224DFA M=,3.3,DFA,化简（极小化）,状态等价：,对,DFA,中的两个状态,S,1,和,S,2,，如果将它们看作是初始状态，所接受的符号串相同，则定义,S,1,和,S,2,是等价的。,无关状态：,从有限自动机的开始状态开始，任何输入序列都不能到达的状态。,最小,DFA,：,如果,DFA,中没有无关状态，也没有彼此等价的状态，则称该自动机是最小的。,25,3.3 DFA化简（极小化）状态等价：对DFA中的两个状态S,3.3.1,状态分离法,将,DFA,的所有状态,K,按终态和非终态划分成两个子集,Z,与,K-Z,，构成初始化分，记作：,=Z, K-Z,。,设当前的划分,中已经含有,m,个子集,: =I,1,I,2,I,m,对于每一个子集,I,i,=S,i1,S,i2,S,in,及每一个,a,，设,I,i,n,=f(I,i,a)=f(S,i1,a)f(S,i2,a)f(S,in,a),若,I,i,n,中的状态分别落在中,p,个不同的子集，则根据转移状态相同与否将,I,i,分为,p,个子集得到新的划分,new,。,若,new, ,则将,new,作为重复,2,，直到不能划分。,将最后所得到的划分中的每个子集看成一个状态，对边作相应修改，确定开始状态和结束状态。,26,3.3.1 状态分离法将DFA的所有状态K按终态和非终态划分,3.3.2,DFA,化简 例,1,27,3.3.2 DFA化简 例127,思考：将如下DFA化简,28,a,C,D,B,A,E,F,S,b,a,a,a,a,a,b,b,b,b,b,a,b,F,思考：将如下DFA化简28 aCDBAEFSbaaaaab,29,S,B,A,C,D,E,F,b,a,b,b,a,a,a,b,C,D,E,F,29SBAC,D,E,Fbabbaaa,bC,D,E,F,3.4,正则表达式与,FA,等价,定理：,对任一确定有限自动机,A,，存在一正,则表达式,e,使得,L(A)=L(e),反之亦然。,关系图：,30,DFA,正则表达式,NFA,3.4 正则表达式与FA等价定理：对任一确定有限自动机A，存,1,2,a b,1,2,a | b,1,2,b,*,1,2,3,a,b,1,2,a,b,1,2,3,b,X,W,3.4.1 正则表达式到DFA的转换,31,12a b12a | b12 b*123ab12ab123,3.4.2 DFA到正则表达式的转换,1,2,3,a,b,1,2,a,b,1,2,3,1,3,a b,1,2,a | b,1,3,a b,*,c,a,b,c,32,3.4.2 DFA到正则表达式的转换123ab12ab123,思考1,设计DFA以识别能够被4整除的二进制数。,33,0,1,2,0,0,1,1,1,0,3,1,0,0,思考1设计DFA以识别能够被4整除的二进制数。3301200,思考2,设计DFA以识别所有能被3整除的无符号十进制数。,34,0,1,2,3,6,9,3,6,9,1,4,7,0,2,5,8,2,5,8,1,4,7,2,5,8,3,6,9,1,4,7,思考2设计DFA以识别所有能被3整除的无符号十进制数。340,思考3,设计识别C语言实型常数的自动机。,35,思考3设计识别C语言实型常数的自动机。35,4,词法分析器的设计与实现,设计：单词分类、正则表达式法、自动机法,实现：转换矩阵法、转换图法、几个细节问题、构造步骤,36,4 词法分析器的设计与实现设计：单词分类、正则表达式法、自动,4.1,单词分类,标识符：,标识符一般是由字母开头，字母、数字或其它符号的任意组合构成的。,常量：,用来表示各种常量。主要包括整数常数实数常数、字符串常量等。,特殊符号：,包括保留字、运算符和界限符。,保留字一般是由语言系统自身定义的通常是由字母组成的字符串。,运算符表示序中算术运算、逻辑运算、字符运算、赋值运算的确定的字符或字符串。,界限符包括各种括号，命令结束符号等。,格式符包括,EOF,，回车等符号。,37,4.1 单词分类标识符：标识符一般是由字母开头，字母、数字或,4.1.1,正则表达式描述,标识符：,L(L|D)*,其中,L=a-z, A-Z, D=0-9,整数：,D,1,D*|0,其中,D,1,=1-9,特殊符号：,+|,；,|,：,|:= |= |,保留字：,if | else |,38,4.1.1 正则表达式描述标识符：L(L|D)* 其中L=,4.1.2,有限自动机描述,按,类,构造出相应的状态转换图。,合并各类单词的状态转换图，构成一个能识别语言所有单词的状态转换图。,将各类单词的状态转换图的初始状态合并为一个唯一的初始状态；,化简调整状态冲突和对冲突状态重新编号；,如果有必要，增加出错状态。,39,4.1.2 有限自动机描述按类构造出相应的状态转换图。39,自动机设计,实例,40,自动机设计实例40,抽象后的DFA,41,0,1,6,7,2,3,4,5,I,D,I,D,D,D,_,D,D,D,D,+,-,.,.,.,_,space,抽象后的DFA4101672345IDIDDD_DDDD+-,4.2.1,状态转换矩阵法,把自动机看作一种数据结构（状态转换矩阵），由控制程序控制字符在其上运行，从而完成词法分析。,State=InitState;,Read(CurrentChar);,While(T(State,CurrentChar),error &,CurrentChar,Eof)State=T(State, CurrentChar);,Read(CurrentChar);,if (State,FinalStates)Accept;,else Error;,特点,程序短小，但占用存储空间多。,42,4.2.1 状态转换矩阵法把自动机看作一种数据结构（状态转换,4.2.2,状态转换图法,每个状态对应一个带标号的,case,语句转向边对应,goto,语句,特点：程序长，但占用存储空间少,43,a,b,Li: case CurrentChar of,a:goto Lj,b:goto Lk,other:Error( ),i,j,k,4.2.2 状态转换图法每个状态对应一个带标号的case语句,4.3 特殊处理,保留字识别,符合单词、数,控制字符、注释,语义信息存储,44,4.3 特殊处理保留字识别44,4.3.1,保留字识别,统一识别,事先构造好,保留字表,。在进行词法分析时，把保留字也当作一般标识符来识别，然后查保留字表，若有，则把它作为保留字来处理；若没有，则按一般标识符来处理。,单独识别,在自动机中加入识别各个保留字的,状态,，即把保留字和一般标识符分开来识别而不统一识别。,45,4.3.1 保留字识别统一识别 事先构造好保留字表。在进行词,4.3.2,符合单词、数,复合单词的识别,在程序设计语言中，有一类单词是由两个或者两个以上的符号组成的，这类单词的前缀部分也可以是一个独立的单词。在处理这类单词时要特别加以注意。 有时候需要向前看若干个字符才能判断。,数的转换,词法分析程序应该把字符串转换成数，如“,123”,应该转换成,123,。,46,4.3.2 符合单词、数复合单词的识别 在程序设计语言中，,4.3.3,控制字符、注释,控制字符的处理,无用的空格符和制表符要删掉；,字符串内的空格不能删；,换行符不能直接删除，而需用于错误定位。,注释的处理,源程序中的注释没有任何语法和语义上的意义，因此在进行词法分析时可以直接将注释,删除,，而不必生成其,TOKEN,。,47,4.3.3 控制字符、注释控制字符的处理 47,4.3.4,语义信息存储,直接在语义信息部分存储,语义信息的长度有限制时，可直接将标识符或常量本身存储于其,TOKEN,中的语义信息部分。,设置标识符表和常量表,标识符和常量没有长度限制时，构造标识符或常量表，语义信息中为其在表中的地址（,节省存储空间）。,48,4.3.4 语义信息存储直接在语义信息部分存储 语义信息的长,4.4,构造词法分析器步骤,确定词法分析器的,接口,，即确定词法分析器是作为语法分析的一个子程序还是作为独立一遍。,确定单词,分类,和,Token,结构,。,构造每一类单词的描述正则表达式并,转换,。,正则表达式,NFA,DFA,设计算法,实现,DFA。,49,4.4 构造词法分析器步骤确定词法分析器的接口，即确定词法分,小结,自动机理论,正则语言与自动机的转换,词法分析器的设计,50,小结自动机理论50,