第4章 词法分析.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第四章 词法分析,教学要求：,本章介绍编译程序的第一个阶段词法分析的设计原理，要求掌握正规文法、,DFA,、,NFA,、正规式和正规集的基本概念和词法分析器的设计原理。,教学重点：,词法分析器的任务与设计，状态转换图。,4.1 词法分析程序的设计,回顾：,1、词法分析的任务：,逐个读入源程序字符并按照构词规则切分成一系列单词。,2、词法分析程序：实现词法分析的程序。,一.,词法与语法分析程序的接口,方式,1、作为独立的一遍,2、语法分析结合在一起作为一遍,词法分析程序,源程序,词法分析程序,语法分析程序,Token,get token,.,主要任务：,读源程序，产生单词符号,其他任务：,滤掉空格，跳过注释、换行符,追踪换行标志，复制出错源程序，,宏展开，,单词符号,单词符号一般可分为下列五种：,基本字,（,关键字,）：,begin,end,if,while,等,标识符,：各种名称，如常量名、变量名、过程名等,常数,（量）：25,3.1415等,运算符,：如+-*/=等,界符,：逗号，分号，括号等,二、输出表示：（单词种别，单词自身的值）,A:=B+2,(,标识符,指向,A,的符号表的入口指针）,(,运算符,:=),(,标识符,指向,B,的符号表的入口指针),(,运算符,+),(数字,2),三、词法分析工作独立的原因：,1、简化设计,2、改进编译效率,3、增加编译系统的可移植性,4.2 单词的描述工具,一、正规文法：,文法,G=（V,N,，V,T,，P，S），P,中每一产生式的形式都为：,AaB,或,Aa,，,其中,AV,N,，BV,N,，,aV,T,几类单词的描述,标识符,：标识符,l|l,字母数字字母数字,l|d|l,字母数字|,d,字母数字,无符号整数,：无符号整数,d|d,无符号整数,运算符,：运算符+,|-|*|/|=|,=,界符,：界符,|;|(|)|,二、正规式(,regular expression),（一）定义（,正规式,和它所表示的,正规集,）：,设字母表为,，辅助字母表,=,，,，。,1、和都是上的正规式，它们所表示的正规集分别为和,；,2、任何,a,，,a,是上的一个正规式，它所表示的正规集为,a；,3、,假定,e,1,和,e,2,都是上的正规式，它们所表示的正规集分别为,L(e,1,),和,L(e,2,)，,那么，(,e,1,),e,1,e,2,e,1,e,2,e,1,也都是正规式,它们所表示的正规集分别为,L(e,1,),L(e,1,)L(e,2,),L(e,1,)L(e,2,),和(,L(e,1,),。,4、仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的字集才是上的正规集。,正规式中的符号说明：,“,”读为“或”,（,也有使用“+”代替,“,”,的）,“,”,读为,“连接”,；,“,”读为“闭包”,（即，任意有限次的自重复连接）。,在不致混淆时，括号可省去，但规定算符的优先顺序为：,“,”,、,“,”,、,“,”,。,连接符,“,”,一般可省略不写。,“,”,、,“,”,和,“,”,都是左结合的。,正规集是正规语言的另一种表示。,如：,字母(数字|字母),表示标识符。,例,4.2,令,=,a，b,，,上的正规式和相应的正规集的例子有：,正规式,正规集,a a,a,b,a,b,ab,ab,(a,b)(a,b),aa,ab,ba,bb,a,a,aa,任意个,a,的串,(,a,b),a,b,aa,ab,所有由,a,和,b,组成的串,(,a,b),(aabb)(a,b),上所有含有两个相继 的,a,或两个相继的,b,组成 的串,例,=,l，d，r,=,l(l,d),定义的正规集:,l,ll,ld,ldd,（,标识符）,其中：,l,代表字母,d,代表数字,正规式即是,字母(字母|数字),它表示的正规集是“字母打头的字母数字串”。,例4.3 ,=,d，.，e,，+，-,则上的正规式：,d,(.dd,)(e(+,-,),dd,),表示的是无符号数的集合。其中：,d,为0-9的数字。,（二）两个正规式,等价,若两个正规式,e,1,和,e,2,所表示的,正规集相同,则说,e,1,和,e,2,等价,写作,e,1,=,e,2,。,例如：,e,1,=(a,b)，e,2,=b,a,又如：,b(ab,),=(,ba),b,(a,b),=(a,b,),（三）正规式的运算律,设,r,s,t,为正规式，正规式服从的代数规律有：,1、,r,s=s,r “,或”服从交换律,2,、,r,(,s,t)=(,r,s,),t “,或”的可结合律,3、(,rs)t,=,r(st,)“,连接”的可结合律,4、,r(s,t)=,rs,rt,(s,t)r,=,sr,tr,分配律,5、,r=r,r=r,是“连接”的恒等元素,6、,r,r=rr,=,r,rr,“或”的抽取律,三、正规文法到正规式,1.将正规式转换成正规文法,V,T,=,S,V,N，,（1）对正规式,r，,生成,正规产生式,S,r,（2）若,x,和,y,都是正规式,对形如,Axy,的,正规产生式：,AxB，By，B,V,N,对形如,A,xy,的,正规产生式：,AxB，Ay，BxB，By，B,V,N,对形如,A,xy,的,正规产生式:,Ax，Ay,不断用上述规则做变换，到每个产生式右端,至多,含一个,V,T,对上的正规式,r,存在一个,G=(V,N,V,T,P,S),使得,L(G)=,L(r,)，,反之亦然。,例,r=,a(ad,),V,T,=,a,d,Sa(ad,),SaA,A(ad,),A,(ad)B,A,B(ad)B,B,Gs,:,SaA,A V,T,=,a,d,AaB,V,N,=S,A,B,AdB,BaB,BdB,B,2.将正规文法转换成正规式,使用如下规则，最后只剩下一个开始符号定义的产生式，并且右部不含非终结符。,规则1：,A-,xB,B,-y =A=,xy,规则2：,A-,xA|y,=A=x,*,y,规则3：,A-x,A-y =A=,x|y,例如：文法,GS,为：,S-,aA,S-a,A-,aA,A-,dA,A-a,A-d,S=,aA|a,A=(,aA|dA)|(a|d,),A=(,a|d)A|(a|d,),A=(,a|d,),*,(,a|d,)=(,a|d,),+,A,代入,S,得：,S=,a(a|d),+,|a,S=,a(a|d),+,|,）,S=,a(a|d,),*,所以，对应正规式为：,a(a|d,),*,4.3 有穷自动机,有穷自动机(也称有限自动机)是识别正规集的装置。,一、确定的有穷自动机（,DFA）,1、定义:,一个确定的有穷自动机（,DFA）M,是一个五元组：,M=（,K，f，S，Z,）,其中,1.,K,是一个有穷集，它,的每个元素,称,为,一个,状态,；,2.,是,一个有穷字母表，它的每个元素称为一个输入符号，所以也称,为,输入符号字母表,；,3.,f,是转换函数,，是在,K,K,上的映射，即如,f(ki,a,)=,kj，(ki,K，kj,K),就意味着，当前状态为,ki,，,输入符为,a,时，将转换为下一个状态,kj,，,我们把,kj,称作,ki,的一个后继状态；,4.,S,K,是唯一,的一个,初态,；,5.,Z,K,是,一个,终态集,，终态也称,可接受状态,或,结束状态,。,例：,DFA M=（S,U,V,Q,a,b,f,S,Q）,其中,f,定义为：,f（S，a,）=U,f（V，a,）=U,f（S，b,）=V,f（V，b,）=Q,f（U，a,）=Q,f（Q，a,）=Q,f（U，b,）=V,f（Q，b,）=Q,（1）,DFA 的状态图表示,f（S，a,）=U,f（V，a,）=U,f（S，b,）=V,f（V，b,）=Q,f（U，a,）=Q,f（Q，a,）=Q,f（U，b,）=V,f（Q，b,）=Q,b,S,U,V,a,a,a,b,a，b,Q,b,（2）DFA,的矩阵表示,f（S，a,）=U,f（V，a,）=U,f（S，b,）=V,f（,V,，b,）=Q,f（U，a,）=Q,f（Q，a,）=Q,f（U，b,）=V,f（Q，b,）=Q,a,b,S,U,V,U,Q,V,V,U,Q,Q,Q,Q,字符,状态,0,1,0,0,终态行在表的右端标以1，非终态标以0。,2、*上的符号串,t,在,M,上运行,一个输入符号串,t，（,我们将它表示成,Tt1,的形，,其中,T，t1,*）在,DFA M,上,运行,的定义为：,f（Q，Tt1）=f（f（Q，T），t1）,其中,QK。,扩充转换函数,f，,是,K,*,K,上的映射，且：,f（Q,，,）=Q,3、*上的符号串,t,被,M,接受,t,*，,f(S，t,)=P，,其中,S,为,DFA M,的开始状态，,P,Z，Z,为终态集。则称,t,为,DFA M,所,接受,（,识别,）。,例：证明,t=,baab,被如下的,DFA,所接受。,DFA M=（S,U,V,Q,a,b,f,S,Q）,其中,f,定义为,：,f（S，a,）=U,f（V，a,）=U,f（S，b,）=V,f（V，b,）=Q,f（U，a,）=Q,f（Q，a,）=Q,f（U，b,）=V,f（Q，b,）=Q,b,S,U,V,Q,a,a,a,b,a，b,b,证明,：,f（S，baab,）,=,f（f（S，b），aab,）,=,f（V，aab,）,=,f（f（V，a），ab,）,=,f（U，ab,）,=,f（f（U，a），b,）,=,f（Q，b,）,=Q,Q,属于终态。得证,。,DFA M,所能接受的符号串的全体记为,L(M),结论：,上一个字符串集,V,是正规的，当且仅当存在一个上的确定有穷自动机,M，,使得,V=L(M)。,DFA M=（,K，f，S，Z,）,的算法,:,K:=S；,c:=,getchar,;,while c,eof,do,K:=,f(K,c,);,c:=,getchar,;,;,if K is in Z then return(yes),else return(no),二、不确定的有穷自动机,NFA,定义,N=,K，,，f，S，Z,，,其中,K,为状态,的有穷非空,集,，,为,有穷输入,字母表,，,f,为,K,*,到,K,的,子集,的,映射,，,S,K,是初,始,状,态集,，,Z,K,为终,止状,态集,。,例,NFA N=（S，P，Z，0，1，f，S，P，Z）,其中,f（S，0）=P,f（S，1）=S，Z,f（P，1）=Z,f（Z，0）=P,f（Z，1）=P,S,P,Z,0,0,1,1,1,1,状态图表示,表格表示,简化为,NFA N=（S，P，Z，0，1，f，S，P，Z）,其中,f（S，0）=P,f（S，1）=S，Z,f（P，1）=Z,f（Z，0）=P,f（Z，1）=P,*上的符号串,t,在,NFA,N,上运行,一个输入符号串,t，（,我们将它表示成,Tt,1,的形式，其中,T，t,1,*,）,在,NFA M,上运行的定义为：,f（Q,，Tt,1,）=f（f（Q，T），t,1,），,其中,QK.,*上的符号串,t,被,NFA,N,接受（读出、识别）,若,t,*,，f(S,0,，t)=P，,其中,S,0,S，P,Z，,则称,t,为,NFA M,所接受（识别）,具有,转移的不确定的有穷自动机,NFA,f,为,K,（,）到,K,的子集的映射,.,对任何一个具有,转移的不确定的有穷自动机,NFA N，,一定存在一个,不具有,转移的不确定的有穷自动机,N,FA,，,使得,L(M)=L(N)。,状态集合,I,的有关运算：,1,、状态集合,I,的,-闭包，表示为,-,closure(I,),，,定义为一状态集，是状态集,I,中的任何状态,S,经,任意条,弧而能到达的状态的集合,(,状态集合,I,的任何状态,S,都属于,-,closure(I,)。,2,、状态集合,I,的,a,弧转换，表示为,move(I,a,),定义为状态集合,J，,其中,J,是所有那些可从,I,的某一状态经过,一条,a,弧而到达的状态的全体。,三、,NFA,到,DFA,的转换,例,I=1,-,closure(I,)=1,2；,I=5,-,closure(I,)=5,6,2；,-,closure(5,3,4)=2,3,4,5,6,7,8；,move(1,2,a)=5,3,4,1,2,5,3,4,6,8,7,a,a,a,NFADFA,的算法：,假设,NFA N=(K,f,K,0,K,t,),按如下办法构造一个,DFA M=(S,d,S,0,S,t,)，,使得,L(M)=L(N),：,1.M,的状态集,S,由,K,的一些子集组成。用,S,1,S,2,.,S,j,表示,S,的元素，其中,S,1,S,2,.,S,j,是,K,的状态。,2.,M,和,N,的输入字母表是相同的，即是,；,3.转换函数为：,d(,S,1,S,2,.,S,j,a,)=R,1,R,2,.,R,t,其中,R,1,R,2,.,R,t,=,-,closure(move,(,S,1,S,2,.,S,j,a),4.,S,0,=,-,closure(K,0,),为,M,的开始状态；,5.,S,t,=,S,i,S,k,.,S,e,|,S,i,S,k,.,S,e,S,且,S,i,S,k,.,S,e,K,t,构造,NFA N,的状态,K,的子集的算法：,假定所构造的子集族为,C，,即,C=(T,1,T,2,.,T,I,),其中,T,1,T,2,.,T,I,为状态,K,的子集。,1.开始，令,-,closure(K,0,),为,C,中唯一成员，并且它是未被标记的。,2.,while（C,中存在尚未被标记的子集,T）do,标记,T；,for,每个输入字母,a do,U:=,-,closure(move(T,a,)；if U,不在,C,中,then,将,U,作为未标记的子集加在,C,中,例4.8 将下图的,NFA N,转换成,DFA M,0,2,3,4,5,6,7,8,9,10,1,b,b,b,a,a,NFA N,0,2,3,4,5,6,7,8,9,10,1,b,b,b,a,a,状态,-,closure(move(T,i,a,),-,closure(move(T,i,b,),T,0,=,-,closure(0)=0,1,2,4,7,1,2,3,4,6,7,8,=T,1,1,2,4,5,6,7,=T,2,T,1,=,1,2,3,4,6,7,8,T,1,1,2,4,5,6,7,9,=T,3,T,2,=,1,2,4,5,6,7,T,1,T,2,T,3,=,1,2,4,5,6,7,9,T,1,T,4,T,4,=,1,2,4,5,7,10,T,1,T,2,-,closure(move(T,i,a,),-,closure(move(T,i,b,),T,0,=,-,closure(0)=0,1,2,4,7,1,2,3,4,6,7,8,=T,1,1,2,4,5,6,7,=T,2,T,1,=,1,2,3,4,6,7,8,T,1,1,2,4,5,6,7,9,=T,3,T,2,=,1,2,4,5,6,7,T,1,T,2,T,3,=,1,2,4,5,6,7,9,T,1,T,4,T,4,=,1,2,4,5,7,10,T,1,T,2,初态,终态,b,0,2,1,3,4,a,b,a,a,a,a,b,b,b,DFA M,四、,DFA,的最小化（化简）,最小状态,DFA,没有多余状态(死状态),没有两个状态是互相等价（不可区别）,多余状态：,从自动机的开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。,消除多余状态,s1 s5s2 s7s2 s5,s5,s7s5 s6s3 s1s8 s0,s0,s1s3 s6,0 1,011000110,s0s1s2s3s4s5s6s7s8,s1 s5s2 s7s2 s5,s5,s7s3 s1s0 s1,0 1,011001,s0s1s2s3s5s7,两个状态,s,和,t,等价,满足,:,一致性同是终态或同是非终态,蔓延性从,s,出发读入某个,a(,a,),和从,t,出发,读入某个,a,到达的状态等价。,状态,2,和4是不等价的,(,可区别的,),。,状态2和3是不等价的，因为读入,b,后分别到达2和4，而2和4是不等价的。,b,0,2,1,3,4,a,b,a,a,a,a,b,b,b,DFA M,对于一个,DFA M=（K,f,k,0,k,t,)，,存在一个最小状态,DFA M=（K,f,k,0,k,t,),使,L(M)=L(M).,DFA,的最小化算法的核心：,把一个,DFA,的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的,.,将下图中的,DFA M,最小化,1,2,3,4,5,6,7,Ia,:6,7,1,4,7,4,4,Ib,:3,3,5,6,3,1,2,1,3,5,2,7,4,6,a,a,a,a,a,a,a,b,b,b,b,b,b,b,a,1,3,5,4,6,a,a,a,a,b,b,b,b,b,1,2,3,4 5,6,7,1,2 3,4,1,2,5,6,7,3 4,5,6,7,4.4,正规,式,和,有穷自动机,的等价性,1.对于,上的NFA M，可以构造一个,上的正规式R,使得L(R)=L(M)。,2,.对于,上的一个正规式R，可以构造一个,上的NFA M，使得L,(,M)=L(R)。,1.,对于,上的NFA M，可以构造一个,上的正规式R,使得L(R)=L(M)。,第一步：在,M,的状态转换图上,加进两个结点,，一个为,x,结点，一个为,y,结点。从,x,结点用,弧连接到,M,的,所有初态结点,，从,M,的,所有终态结点,用,弧连接到,y,结点。形成一个与,M,等价的,M,M,只有,一个初态,x,和,一个终态,y,。,第二步：逐步消去,M,中的所有结点，直至只剩下,x,和,y。（,消去规则见下页）,最后,x,和,y,结点间的弧上的标记则为所求的正规式,R。,1,2,3,R,1,R,2,1,3,R,1,R,2,1,3,R,1,R,2,1,3,R,1,|,R,2,1,2,3,R,1,R,3,R,2,1,3,R,1,R,2,*,R,3,例：,0,3,1,2,4,a,b,a,a,a,b,a,b,b,b,求正规式,R,0,3,1,2,4,a,b,a,a,a,b,a,b,b,b,x,y,0,2,4,a|b,aa,a|b,a|b,bb,x,y,0,2,4,a|b,aa,a|b,a|b,bb,x,y,0,a|b,aa(a|b,)*,bb(a|b,)*,x,y,0,a|b,aa(a|b,)*,bb(a|b,)*,x,y,x,y,(,a|b,)*(,aa,|,bb)(a|b,)*,0,a|b,x,y,aa(a|b,)*|,bb(a|b,)*,(,aa,|,bb)(a|b,)*,R=(,a|b,)*(,aa,|,bb)(a|b,)*,2,.对于,上的一个正规式R，可以构造一个,上的NFA M，使得L,(,M)=L(R)。,(1)R=,(3)R=a,(2),R=,(4)R=,s|t,x,y,x,y,x,y,a,x,y,NFA(s,),NFA(t,),x,y,s,t,或,(5),R=,st,(6)R=s,*,NFA(s,),NFA(t,),NFA(s,),x,y,x,x,1,y,s,t,或,x,x,1,y,s,或,例：,为,R=(,a|b,)*,abb,构造,NFA N，,使得,L(N)=L(R)。,2,3,a,5,4,b,R=(,a,|b,)*,abb,R=(,a|,b,)*,abb,R=(,a|b,)*,abb,2,3,5,4,a,b,1,6,解法一：,R=(,a|b,)*,abb,2,3,5,4,a,b,1,6,R,=(,a|b,)*,abb,2,3,5,4,a,b,1,6,0,7,继续加上,abb,即可得到结果。,R,=(,a|b,)*,abb,x,i,y,(,a|b,)*,abb,x,j,y,abb,i,a|b,x,j,y,abb,i,a,b,继续对,abb,进行分解。,解法二：,4.5 正规文法和有穷自动机间的转换,采用下面的规则从正规文法,G,直接构造一个有穷自动机,NFA M，,使得,L(M)=L(G)：,1.字母表与,G,的终结符集相同；,2.为,G,中的每个非终结符生成,M,的一个状态，（不妨取相同的名字）,G,的开始符号是开始状态,S；,3.增加一个新状态,Z，,作为,NFA,的状态；,4.对,G,中的形如,AtB,的产生式（其中,t,为终结符或,，A,和,B,为非终结符），构造,M,的一个转换函数,f(A,t,)=B,；,5.对,G,中形如,At,的产生式，构造,M,的一个转换函数,f(A,t,)=Z,。,例：与文法,GS,等价的,NFA M,GS：SaA,SbB,S,AaB,AbA,BaS,BbA,B,S,A,B,Z,a,a,b,b,a,b,4.6,词法分析器的工作过程,词法分析器,（,Scanner）,输入流,词法描述（正规式）,NFA,DFA,TokenList,error,词法分析器的设计,人工构造词法分析器过程：,1.确定词法分析器的接口，即确定词法分析,器是作为语法分析的一个子程序还是作为,独立一遍。,2.确定单词分类和,Token,结构。,3.根据第2步，构造每一类单词的描述,正则表达式,NFA,DFA,。,4.根据第3步设计算法实现,DFA。,利用工具自动生成：,ScanGen,Lex,4.7,词法分析器的生成器,Lex,功能：,依据语言的正规式，自动生成该语言的词法分析程序。,执行过程：,正规式文件,Lex.l,Lex,词法分 析器,lexyy.c,C,编译器,a.out,输入流,Token,序列,以,Lex,可以理解的格式指定模式相关的动作,在这一文件上运行,Lex,，,生成扫描器的,C,代码。,编译和链接,C,代码，生成可执行的扫描器。,Lex,中的元字符,abc,：字符,a,、,b,或,c,中的任一个。,a?,：一个可选的,a,。,ab,：除了,a,、,b,外的任何一个字符。,.,：除了新行之外的任一字符。,.,：字符“,.”,。,xxx,：名字为,xxx,的正规式。,a-z,：,a,到,z,中的任一字符。,为了与减号区别，减号表示为,“-”,。,lex,源程序,lex,源程序由三部分组成,声明,%,翻译规则,%,辅助过程,第一段是,C,和,Lex,的全局声明，第二段包括模式（,C,代码），第三段是补充的,C,函数。,%LT,LE,IF,THEN,ELSE,#include,int,count=0;,%,letter A-,Za-z,digit 0-9,id letter(letter|digit)*,%,if return(IF);,id ,yylval,=,installid();return,(ID);,“”,yylval,=LT;return(RELOP);,%,installid,(),总结,两个工具：,有限自动机、正规式,三个算法：,正规式到,FA,的转换,NFA,到,DFA,的转换,DFA,的化简,一个实现：,DFA,的实现,