第3章-词法分析2课件

,词法分析,词法分析程序概述,正规文法与正规式,有穷自动机,正规式与有穷自动机的等价性,正规文法与有穷自动机的等价性,一个简单的词法分析器示例,词法分析词法分析程序概述,状态图的形式化描述,3.3 有穷自动机,S,1,非字母数字,字母,字母、数字,2,非数字,数字,数字,3,其他字符,+*，,（）,出口,4,其他字符,5,=,非,=,出错,其他,标识符,无符号整数,单界符,双界符,读字符,返回,S,状态图的形式化描述3.3 有穷自动机S1非字母数字字母字母、,有穷自动机是一种,数学模型,，具有离散的输入与输出，系统可处于有穷状态中的任何一个；,它能准确地,识别正规集,，即识别正规文法所定义的语言和正规式所表示的集合；,引入有穷自动机这个理论，正是为,词法分析程序的自动构造,寻找特殊的方法和工具。,有穷自动机分为两类：,确定的有穷自动机,（,DFA）,(Deterministic Finite Automata),不确定的有穷自动机,（,NFA）,(Nondeterministic Finite Automata),3.3 有穷自动机,有穷自动机是一种数学模型，具有离散的输入与输出，系统可处于有,2型文法,（不确定的下推自动机）,1型文法,（不确定的界限自动机）,0型文法,（图灵机）,3型文法,（有限自动机）,3.3 有穷自动机,2型文法1型文法（不确定的界限自动机）0型文法（图灵机）3型,1.确定的有穷自动机（DFA）,M=(,Q,f,S,Z),：有穷字母表，它的每个元素称为一个输入符号；,Q：有穷集，它的每个元素称为一个状态；,SK，是唯一的初态；,Z,K是一个终态集，终态也称可接受状态或结束状态；,f 是转换函数，是QQ上的单值映射：,f（q1，a）=q2,3.3 有穷自动机,1.确定的有穷自动机（DFA）：有穷字母表，它的每个元素称,状态转移函数,f可用一矩阵来表示：,输入字符,状态,a,b,0 1 2,1 3 2,2 1 3,3 3 3,例如,:M:（0,1,2,3,a,b,f，0，3）,f（0，a）=1 f（0，b）=2,f（1，a）=3 f（1，b）=2,f（2，a）=1 f（2，b）=3,f（3，a）=3 f（3，b）=3,所谓确定的状态机，,其确定性表现在状,态转移函数是单值,函数！,M=(,Q,f,S,Z,),3.3 有穷自动机,状态转移函数f可用一矩阵来表示：例如:M:（0,1,2,一个,DFA也可以用一状态转换图表示：,DFA的状态图表示：,1,0,3,2,a,a,b,b,a,b,b,a,3.3 有穷自动机,输入字符,状态,a,b,0 1 2,1 3 2,2 1 3,3 3 3,字母表,含有n个输入字符，那末任何一个状态结,点最多有n条弧射出，而且每条弧以一个不同的输,入字符标记。,一个DFA也可以用一状态转换图表示：DFA的状态图表示：10,换言之：若存在一条初始状态到某一终止状态的路径，且这条路径上所有弧的标记符号连接成符号串,，则称为DFA M（接受）识别。,DFA M所接受的语言为：L(M)=|f(S,)=Sn,Sn Z,DFA M所能接受的符号串的全体记为L(M),若,M的初态结点同时为终态，或者存在一条从初态到某个终态结点的通路，则为M所识别。,3.3 有穷自动机,换言之：若存在一条初始状态到某一终止状态的路径，且这条路径上,（0，abaab）,=（1，baab）,=（2，aab）,=（1，ab）,=（3，b）,=3(接受),（0，abab）,=（1，bab）,=（2，ab）,=（1，b）,=2(拒绝),对于符号串,abaab,对于符号串,abab,3.3 有穷自动机,DFA的状态图表示：,1,0,3,2,a,a,b,b,a,b,b,a,（0，abaab）（0，abab）对于符号串abaab对,f是一个多值函数，是从Q,*,到,Q的子集的映射：,f：Q,2,Q,其中,2,Q,是,Q的幂集，即Q中所有子集组成的集合。,2.不确定的有穷自动机（NFA）,M=(,Q,f,S,Z),有穷自动机的不确定性表现在在某个状态下，对于某个输入字符存在多个后继状态，即状态的转向是不确定的。,3.3 有穷自动机,f是一个多值函数，是从Q*到Q的子集的映射：2.不确定的,例：,NFA N=(a,b,c,1,2,3,4,f,1,4),符号,状态,a b c,1,4 2，3 ,2 2,4,3 ,3，4,4 ,3.3 有穷自动机,例：NFA N=(a,b,c,1,2,3,4,对于,*,上的任何符号串,，若存在一条从某一初态到某一终态,的通路，且该通路上所有弧的标记字符依次连接成的串等于,，,则称,可以被,NFA N所识别或接受。,若N的初态结点同时为终态，或者存在一条从初态到某个终态,结点的,通路，则,为,N所识别。,NFA N所能识别的符号串的全体记为L(N)，称为NFA N所识别的语言。,3.3 有穷自动机,对于*上的任何符号串，若存在一条从某一初态到某一终态N,上例题相应的状态图为：,1,2,3,4,a,b,a,c,a,c,N所接受的语言（正规式）R=aa,*,b|ac*c|,3.3 有穷自动机,例：,NFA N=(a,b,c,1,2,3,4,f,1,4),符号,状态,a b c,1 4 2，3 ,2 2 4 ,3 3，4,4 ,上例题相应的状态图为：1234abacacN所接受的语言（,能接受,000,111,1010001,110000001,(0|1),*,(000|111)(0|1),*,不能接受,00,01100,3.3 有穷自动机,能接受(0|1)*(000|111)(0|1)*不能接受3.,画出能够识别,C语言注释/*/的DFA,3.3 有穷自动机,1,2,4,5,3,others,others,/,*,*,*,/,6,others,others,all,画出能够识别C语言注释/*/的DFA3.3 有穷自动机,状态,1：注释开始状态。,状态,2：进入注释体前的中间状态。,状态,3：表明目前正在注释体中的状态。,状态,4：离开注释前的中间状态。,状态,5：注释结束状态，即接受状态。,3.3 有穷自动机,1,2,4,5,3,others,others,/,*,*,*,/,状态1：注释开始状态。3.3 有穷自动机12453other,用于某些重要软件的设计和构造,设计和检查数字电路行为的软件;,扫描如网页族等大规模文本以发现字、词或其它,结构的出现频率的软件;,验证所有只有有限多个不同状态的系统的软件，,这类系统包括通信协议和信息安全交换协议。,有穷自动机的其它应用,3.3 有穷自动机,用于某些重要软件的设计和构造有穷自动机的其它应用3.3 有穷,已证明：非确定的有穷自动机与确定的有穷自动机从功能,上来说是等价的，也就是说，我们能够从：,NFA N,DFA M,构造成一个,使得,L(M)=L(N),DFA是NFA的特例。有一种算法，将NFA转换成接受同样语言的DFA。,这种算法称为,子集法,。,与某一,NFA等价的DFA不唯一。,3.3 有穷自动机,3.NFA的确定化,已证明：非确定的有穷自动机与确定的有穷自动机从功能NFA N,从NFA的矩阵表示中可以看出，表项通常是一状态的集合，而在DFA的矩阵表示中，表项是一个状态。,NFA到相应的DFA的构造的基本思路是：,DFA的每一个状态对应NFA的一组状态。,1,2,3,4,a,b,a,c,a,c,3.3 有穷自动机,例：,NFA N=(a,b,c,1,2,3,4,f,1,4),符号,状态,a b c,1 4 2，3 ,2 2 4 ,3 3，4,4 ,从NFA的矩阵表示中可以看出，表项通常是一状态的集合,(1)合并,如果有 ，则把S,2,合并到,S,1,S,1,S,2,转换需解决的问题：,i,j,k,m,a,b,a,n,（,a）,i,j,m,k,a,a,b,n,（,b）,3.3 有穷自动机,(1)合并S1S2转换需解决的问题：ijkmaban,(2)状态合并,0,1,2,3,a,a,b,c,（,a）,0,1,2,3,a,b,c,（,b）,3.3 有穷自动机,(2)状态合并0123aabc（a）01,23abc（b）,定义,1：状态集合I的,-闭包，表示为,-closure(I),若qI，则q,-closure(I)；,若qI，则从q出发经过任意条,弧而能到达的任何状态,q都属于,-closure(I)。,为了使得,NFA确定化，我们首先给出两个定义：,_,closure(I),I,I,S,2,S,2,S,1,S,1,S,3,S,3,3.3 有穷自动机,定义1：状态集合I的-闭包，表示为-closure(I),例：,如图所示的状态图：,令I=1，,求-closure（I）=？,1,5,6,4,3,2,a,a,a,根据定义：,-closure（I）=1，3,课堂练习：令,I=1,2,求：-closure（I）=？,3.3 有穷自动机,-closure（I）,=1、2、3、6,例：156432aaa根据定义：课堂练习：令I=1,2,I是状态集，由I中的状态出发，经过一条a弧可能到达的状态的集合称为move（I，a），则：,I,a,=_closure(move(I,a),定义,2：I,a,子集,3.3 有穷自动机,I是状态集，由I中的状态出发，经过一条a弧可能到达的状态的集,例：令,I=1,Ia=-closure(move（I，a）),=-closure(f（1，a）,=-closure(2，4）=2，4，6,1,5,6,4,3,2,a,a,a,课堂练习：令,I=1,2,3,求Ia=？,3.3 有穷自动机,Ia=-closure（move(I,a）,=-closuref(1,a)、f(2,a)、f(3,a),=-closure2、4、5=2、6、3、5,例：令I=1156432aaa课堂练习：令I=1,课堂练习：,令,I=1，设,S,=-closure（I），,求：,S,？,S,a,=？,1,2,3,4,a,b,a,c,a,c,3.3 有穷自动机,S,=-closure（I）,=1、4,S,a,=(2、3,课堂练习：令I=1，设S=-closure（I），1,（,1）将从状态S出发经过任意条,弧所能到达的状态,作为,DFA的初态S,;,（,2）从S,出发，把遇到输入符号,a所转移到的后继状态,集作为DFA的新状态;,（3）如此重复，直到不再有新的状态出现为止,。,NFA转换为DFA的思想,3.3 有穷自动机,-closure(S,对于每一个输入符号啊，求,Ia,对于每一个新状态，重复（,2）,（1）将从状态S出发经过任意条 弧所能到达的状态NFA转,（,1）构造一张表，它共有+1列；,（2）第一行第一列为,-closure(S)；,（3）对于每一个输入符，求Ia；,（4）重复步骤（3）；,（5）将状态子集重新命名。,1,2,3,4,a,b,a,c,a,c,3.3 有穷自动机,I I,a,I,b,I,c,1,4 2,3 ,2,3 2 4 3,4,2 2 4 ,4 ,3,4 3,4,-closure(S,新状态,新状态,新状态,（1）构造一张表，它共有+1列；1234abacac,将求得的状态转换矩阵重新编号，得到,DFA M状态转换矩阵：,符号,状态,a,b,c,0,2,3,4,1,2,2,1,_,_,_,_,_,_,_,_,3,3,4,4,3.3 有穷自动机,I I,a,I,b,I,c,1,4 2,3 ,2,3 2 4 3,4,2 2 4 ,4 ,3,4 3,4,0,1,2,3,4,1,2,2,-,-,-,3,3,-,-,-,4,-,-,4,a b c,将求得的状态转换矩阵重新编号，得到DFA M状态转换矩阵：,DFA M的状态图：,0,1,4,2,3,1,4,2,3,4,2,a,c,a,b,b,c,3,4,1,2,3,4,a,b,a,c,a,c,3.3 有穷自动机,注意：包含原初始状态,1的状态子集为DFA M的初态,包含原终止状态4的状态子集为D