编译原理第三章 词法分析及词法分析程序

,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,单击此处编辑母版标题样式,编译原理,前后文无关,文法和语言,设计扫描器应注意的问题,词法分析（,3,型）,语法分析（,2,型）,单词的,(Class, Value),二元组表示,标识符的长度限制和按“尽可能长”的识别策略,超前搜索与回退, =, , ,状态转换图,设,G=(V,N,V,T,P,S),是一右线性文法,令,|V,N,|=K,，,1),则所要构造的状态转换图共有,K+,1,个状态,.,2),V,N,中的每个符号分别表示,K,个状态,2.1),G,的开始符,S,为初态状态,3),终止状态,用,F(,V,N,),标记,F,是新加,(,状态）节点,右线性文法,=,状态转换图,a,A -,aB,A,B,A - a,A,F,a,A -,消除,，重用上述规则,A,F,other,A,若,A,为起始符（,GA,）,A,产生式的消除,S,A,X,F,a,b,c,other,Y,e,S,A,X,F,a,b,c,Y,e,S -,aA,A -,b|bX,X -,c|eY,S -,aA,A -,bX,X - c|,|,eY,状态图,=,右线性文法,文法,G0,0-a1,S-,aA,1-d1,A-,dA,1-b,A-b,0-c,S-c,0-c2,S-,cB,，,2,有出弧,2-d,B-d,0,1,3,2,a,b,c,d,d,左线性文法,=,状态转换图,设,G=(V,N,V,T,P,S),是一左线性文法,令,|V,N,|=K,，,1),则所要构造的状态转换图共有,K+,1,个状态,.,2),V,N,中的每个符号分别表示,K,个状态,2.1),G,的开始符,S,为终止状态,3),起始状态,用,R(,V,N,),标记,R,是新加,(,状态）节点,左线性文法,=,状态转换图,a,A -,Ba,B,A,A -,的,消除,消除,，重用上述规则,R,A,other,若,A,为起始符（,GA,）,A,A - a,R,A,a,不存在这种转换,状态图,=,左线性文法,文法,G3,1 - a,Aa,1 - 1d,AAd,3 -1b,S,Ab,2 - c,B,c,3 - 2d,S,Bd,0,1,3,2,a,b,c,d,d,状态矩阵,状态矩阵,B,ij,=,BS,i,a,j,=,S,k,当前状态，扫视字符，语义动作，后续状态,程序,3-2,识别无符号数的状态矩阵,语义 动作中的返回值,ICON,、,FCON,分别为整型数、浮点型数的值；,一般说来，无符号数具有形式,d,m,d,m-1,d,0,.d,-1,d,-n,E,dd,即,d,m,d,m-1,d,0,d,-1,d,-n,*10(,dd-n);,程序,3-3,关于状态无符号数识别矩阵,DFA,的形式定义,DFA: Deterministic Finite Automata,一个,DFA M,定义为,M=(K, f, S,0, Z),，其中,1) K=,状态,i,2) =,字母表，即,输入字符,i,3) f : K - K,，,f,为函数，表示某状态接受某个,字母,所到达的状态，如：,f(p,a,) =q,p,qK, a ,4) S,0,K,，,S,0,为初态,5) Z K,，且,Z ,，,Z,为终态集合,DFA,例子,0,1,3,2,a,b,c,d,d,左侧的状态图，在数学上称作,DFA,，其形式化定义为,M=(K, f, S,0, Z),K=0 , 1 , 2 , 3 ,=a , b , c , d ,源状态,输入,目的状态,0,a,1,0,C,2,1,d,1,1,b,3,2,d,3,f:,S0=0,Z=2 , 3,函数,f,的推广定义,f,f,:,K * - K,，表示某状态接受一个字母,串,（而不是一个字母）所到达的状态，,f,的定义依赖于,f,的定义，,f,递归定义如下：,1,）,f(p, ) = p, if p K,，即任意一状态,p,接受（串长为,0,）的输入，状态不变,2,）,f(p, aw) = f(,f,(p,a,), w), if,p K, a , w *,函数,f,的推广定义,f :,例子,对于,x =,adb, x, *,，,那么从状态,0,可以迁移到的状态,p,可以这样求出：,P = f(0,adb,),= f(f(0,a), db),= f(1, db),= f(f(1,d), b),= f(1, b),= f(f(1,b),),= f(3,),= 3,0,1,3,2,a,b,c,d,d,因为从初态,0,接受输入字母串,adb,后，迁移到,f(0,adb)= 3,Z,，所以,adb,为,DFA,所识别,DFA,所识别的语言,令,M,为一,DFA,，我们：,定义,L(M)=x | f(S,0, x),Z, x *,L(M),称为,DFA M,所识别的语言,有定理：,L(M) = L(G),，其中,M,为一,DFA,，,G,为一正规文法,DFA,关键特征,状态迁移映射,f,是入射函数即,f(x,),f(y,),蕴含,x y,即对任意状态结点,p,，其出弧上的字母各不相同且不为,从状态图角度，如出现下述情况的状态结点，则不是,DFA,（而是,NFA,）,P,Q,N,a,a,Q, N,P,Q,P, Q,Why?,NFA,的形式定义,一个,NFA M,定义为,M=(K, f, S,0, Z),，,除,f,外其余成员与,DFA,相同，,f,定义为,f : K -,(K),，,其中,(K),为集合,K,的幂集合，即有,|(K)|=2|K|,f,表示某状态接受某个,字母,所到达的状态集合，如：,f(p,a,) =,q,m,p,q,mK, a ,映射,f,的推广定义,f,f,:,(,K), ,*,- (K),，,表示某状态,集合,接受一个字母,串,（而不是一个字母）所到达的状态,集合,，,f,递归定义如下,(,依赖于,f,),：,f(p, ) = p,f(p,a,) =,p1, p2,. if,f,(p,a,)=p1,p2, if,f,(p,a,) = ,f(p,aw,) =,f(f(p,a,), w),其中，,p,p1,p2,K, a , w *,属于什么？,NFA,所识别的语言,令,N,为一,NFA,，我们：,定义,L(N)=x | f(S,0, x),Z ,x *,L(N),称为,NFA N,所识别的语言,有定理：,L(N) = L(M) = L(G),，其中,N,为一,NFA,，,M,为一,DFA,，,G,为一正规文法,NFA,例子,写状态迁移表,f,S,A,B,C,a,b,a,a,a,b,b,a,为什么是,NFA,源状态,输入,目的状态,集合,-S,a,A,C,A,a,A,C,A,b,A,B,B,a,A,B,b,C,C,x, ,对每状态结点，按出弧上的字母写出状态迁移表,C,行可以不填,f : K - (K),NFA,例子,接受串,源状态,输入,目的状态,集合,-S,a,A,C,A,a,A,C,A,b,A,B,B,a,A,B,b,C,C,x, ,f : K - (K),当前状态 余留输入 后续状态 选择状态,S,ababb,A,C,A or C ?,注意,，,NFA,识别输入符号串时有一个试探过程，为了能走到终态，往往要走许多弯路（,带回溯,），这影响了,NFA,的效率。,解决办法？,NFA,与,DFA,的等价性,定理,3.1,对于字母表,上的任一,NFA N,，必存在与,M,等价的,DFA M,，,使,L(N)=L(M),有了该定理，为提高,NFA,识别字符串的效率提供了,tips,：,将,NFA,转换为,DFA,，,即,NFA,的确定化,基本,idea:,DFA,的,f : K - K,NFA,的,f : K - (K),，将其改造为,f :,(K) - (K),，,并证明,f,是入射函数,且,f,接收的串与,f,接收的串相同,例子,S,0,S,1,a,b,b,a,b,q,0,q,2,a,b,a,b,q,1,b,带有,动作的,N,FA,例子,a b c,S,0,S,0, S,1, S,2,S,1,S,1, S,3,S,2,S,2, S,3,S,3,b,S,0,S,1,S,3,a,S,2,c,b,带有,动作的,NFA,-,闭包,-closure(S,0,)=S,0, S,1, S,2, S,3,f(S, ) = -,closure(S,),f(S,wa,) = -closure(,f(f(S,w),a,) ),f(q, ),通常不等于,f(q, ),f(S,0, ) f(S,0, ),带有,动作的,N,FA,的确定化,1),令,K=,-closure(S,0,)(,给出,M,的初态,q,0,),2),对于,K,中任一尚未标记的状态,q,i,=S,i1,S,i2,S,im,，,S,ik,K,，作,2.1),标记,q,i,2.2),对于每个,a,，置,T=f(S,i1,S,i2,S,im,a,),q,j,=,-,closure(T,),2.3),若,q,j,不在,K,中，则将,q,j,作为一个未加标记的状态添加到,K,中，且把状态转移添加到,M,。,3),重复进行步骤,2),，直到,K,中不再含有未标记的状态为止，对于由此构造的,K,，我们把那些至少含有一个,Z,中的元素的,q,i,作为,M,的终态。,S,0,S,1,S,3,a,S,2,c,b,b,DFA,状态数最小化,可区分状态,A,B,a1,a2,an,a1,a2,状态,A,B,被某一输入串,w=a,1,a,2,.a,n,所区分，指,1,）从其中一个状态出发读入,w,，到达,终态,，,2,）而从另一个状态出发进入,非终态,可区分状态的递归定义,在一个,DFA,中，状态,A,与状态,B,可区分：,1,）,A,是终止状态，,B,是非终止状态,或,B,是终止状态，,A,是非终止状态,2,）对于字母,a,，有,f(A,a,)=C,f(B,a,)=D,2.1) C,与,D,可区分,2.2) C=NULL,且,D NULL,且,D,可达终态,或,C NULL,且,C,可达终态 且,D=NULL,DFA,状态数最小化,-,例子,S,0,S,1,S,3,S,2,b,a,b,b,a,a,a,b,S,4,a,b,复习,一个,DFA M=(K, f, S,0, Z),，函数,f : K - K,表示某状态,K,i,接受某字母,a,后，到达,状态,K,j,的转换,。,一个,NFA M=(K, f, S,0, Z),，函数,f : K -,(K),表示某状态,K,i,接受某字母,a,后，到达,状态集合,K,1, ,K,j,的转换,。,一个带动作的,NFA M,=(K, f, S,0, Z),，函数,f : K ,- (K),表示某状态,K,i,接受某字母,a,或空串,后，到达状态集合,K,1, ,K,j,的转换,。,试描述下述文法所产生的语言的特点,GS=(,V,N,=S, , , V,T,=AZ, az, 09, P, S),其中,P=,S, S,，,S, S,，,S, ,，, A,，,，, z,，, 0,，,，, 9 ,上述正规文法产生的语言的特点是,由字母开头，后接,0,个或多个字母和,(,或,),数字的符号串,即标识符的定义,如果使用型如,字母,(,字母,|,数字,)*,的式子来表示上述符号串构成的集合，那么这样的式子就称为正规表达式,(,正则式，,Regular Expression),，相应的符号串集合则称为该表达式对应的正规集。,正规表达式及正规集的定义,正规式 正规集,1. ,空集,2. ,3. a,，,a a,4.,(,r),(s,),L,r, L,s,(,r),|,(s,),L,r, L,s,(r),*,L,r,*,r,=(r)|(),L,r,(r),+,=(,r)(r,)*),L,r,+,算符优先级与正规式化简,算符优先级从高到低依次为,(), *,+, |,如,( (r) ( (s)* ) ) | ( r ),，可化简为,r s*|r,又因为连接符,通常可省略不写，,再化简为,rs,*|r,正规式与正规集的例子,=,a,b,正规式与正规集的多对一关系,给定一个正规式，它唯一确定一个正规集；反之不然。,即一个正规集可由多个不同的正规式表示。,我们称两个正规式,等价，,当且仅当它们所描述的正规集相同。,例如,a|b,与,b|a, (,a|b,)*,与,(,b|a,)*,等等,正规式的基本等价公理,A1.,r|s,=,s|r,A2.,r|r,=r,A3. r|,=r A4. (,r|s)|t,=,r|(s|t,),A5. (,rs)t,=,r(st,) A6.,r(s|t,)=,rs|rt,A7. (,s|t)r,=,sr|tr,A8. r = r = ,A9. r = r =rA10. r*=(|r)*=|,rr,*,由正规文法构造正规式,1/4,使用正规式描述下述右线性文法产生的语言,S,aS,| b,S ,aS,|,bS,| c (,或,S (,a|b)S,| c ),S ,abS,| c,总结出规律,:,S S | ,对应的正规式是 *,由正规文法构造正规式,2/4,使用正规式描述下述左线性文法产生的语言,S, Sa | b,S Sa |,Sb,| c (,或,S ,S(a|b,) | c ),S ,Sab,| c,总结出规律,:,S S | ,对应的正规式是 *,由正规文法构造正规式,3/4,如果将“,| ”,用 “,+ ”,替换，“ ” 用 “,= ”,替换，那么可以将产生式转换为方程的形式，于是对上述两个规律，我们得到论断：,论断,3.1,方程,X= X + ,（对应,S S | ,），有解,X= *,论断,3.2,方程,X= X + ,（对应,S S | ,），有解,X= *,由正规文法构造正规式,4/4,于是，对文法,GS,S,aS,|,bA,| b,AaS,我们可以将所有产生式的运算符“,| ”,用 “,+ ”,替换，“ ” 用 “,= ”,替换，再以我们习掼的线性方程组求解方法来求解,S,对应的正规式。,例子,1),S,aS|bA|b,AaS,2),SaA,AbA|aB|b,BaA,3),SbS|aA,AaA|bB,BaA|bC|b,CbS|aA,练习,1),S,aS|bA|c,AbS,2),SaA,AaA|bB|c,BcS,由正规式构造,FA,Thompson,法,S,0,S,f,S,0,S,0,S,f,a,当,n=0,r=,r=,r=a,根据正规式所含运算符个数,n,递归给出。,r= r,1,|r,2,r,1,S,01,r,2,S,02,s,0,S,f,不再是初态,不再是终态,S,f1,S,f2,r=r1,r2,r1,S,01,S,f1,r2,S,02,S,f2,r=r*,S,01,S,f1,s,S,f,例子与练习,例子：,1,）,a(b|aa,)*b,2,）,( (0*|1) (1*0) )*,练习：,1,）,ab|c,*,2,）,(,b|aa|ac|aaa|aac,)*,综合练习,1,对文法,GS=(S, A, B, a, b, P, S),，其中,P=, S,aS,|,aA,A ,bA,|,bB,B ,aB,| a,1),使用正规式描述该文法产生的语言,2),构造识别上述正规式的,NFA,3),对上述,NFA,确定化和最小化得到,DFA,4),对上述,DFA,，写出相应左线性文法,综合练习,2,对文法,GS=(S, A, B, a, b, P, S),，,P=, S,Aa,A a|,Ab,|,Ba,B ,Aa,1),使用正规式描述该文法产生的语言,2),构造识别上述正规式的,NFA,3),对上述,NFA,确定化和最小化得到,DFA,4),对上述,DFA,，写出相应右线性文法,