编译原理 第3讲.ppt

,*,盛威网：专业的计算机学习网站,编 译 原 理,第四章词法分析,4.1,词法分析程序的设计,4.2,单词的描述工具,4.3,有穷自动机,4.4,正规式和有穷自动机的等价性,4.5,正规文法和有穷自动机的等价性,4.6,词法分析程序的自动构造工具,4.7,典型例题及解答,知识结构,词法分析,自动构造工具,正规集,正规式,有穷自动机（,NFA DFA),正规文法,知识结构,第四章 词法分析,4.1,词法分析程序的设计,源程序,词法分析程序,语法分析程序,Token,get token,.,主要任务：读源程序，产生单词符号,其他任务：,滤掉空格，跳过注释、换行符,追踪换行标志，复制出错源程序，,宏展开，,一,.,词法分析程序与语法分析程序的接口方式,词法分析工作可以是独立的一遍，把字符流的源程序,变为,单词序列,，输出在一个,中间文件,上，这个文件作,为语法分析程序的,输入,而继续编译过程,更通常情况，常将词法分析程序设计成一个,子程序,，,每当语法分析程序需要一个单词时，则调用该子程序。,词法分析程序每得到一次调用，便从源程序文件中读,入一些字符，直到识别出一个单词，或说直到下一单,词的第一个字符为止,二,.,词法分析程序的输出,1.,单词符号一般可分为下列五种：,基本字（关键字）：,begin,、,end,、,if,、,while,、,var,标识符：常量名、变量名、过程名,常数（量）：,25,、,3.1415,、,true,、“,ABC”,运算符：、*、,=,界符：逗点、分号、括号,2.,输出表示：,（单词种别，单词自身的值）,单词种别：语法分析需要的信息,单词自身的值：编译其他阶段需要的信息,（标识符，指向该标识符所在符号表中位置的指针）,单词的种别可以用整数编码表示，假如标识符编码为,1,，常数为,2,，关键字为,3,，运算符为,4,，界符为,5,if i=5 then x:=y,关键字,if(3,if),标识符,i(1,，,指向,i,的符号表入口,),等号,(4,=),常数,5(2,5),关键字,then(3,then ),标识符,x(4,指向,x,的符号表入口,),赋值号,:=(4,：,=),标识符,y(1,指向,y,的符号表入口,),分号,;(5,;),三,.,将词法分析工作分离的考虑,1.,使整个编译程序的结构更简洁、清晰和条理化：,2.,编译程序的效率会改进：,3.,增强编译程序的可移植性：,4.2,单词的描述工具,一,.,正规文法,程序设计语言中的几类单词可用下述规则描述：,l|l,l|d|l|d,d|d,+|-|*|/|=|,=,|;|(|)|,其中,l,表示,az,中的任何一个英文字母，,d,表示,09,中,的任何一个数字,例,4.1,：,d|.e,d|.e|,d,e|d|,d|s,d,d|,其中，,s,表示正或负号,(+,-),二,.,正规式,正规表达式（,regular expression,）,是说明单词的,pattern,的一种重要的表示法（记号），是定义正规集,的工具,定义（正规式和它所表示的正规集）：,设字母表为,，辅助字母表,=,，,和都是上的正规式，它们所表示的正规集分别为,和,任何,a,，,a,是上的一个正规式，它所表示的正规集,为,a,假定,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.2,令,=a,，,b,上的正规式和相应的正规集的例子有：,正规式 正规集,a a,ab a,b,ab,ab,(ab)(ab),aa,ab,ba,bb,a,a,a,任意个,a,的串,(,ab),a,b,aa,ab,所有由,a,和,b,组成的串,(,ab),(aabb)(ab,),上所有含有两个相继的,a,或两个,相继的,b,组成的串,例,4.3,=,d,，,.,，,e,，,+,，,-,则上的正规式,dd,(.dd,)(e(+-),dd,),其中,d,为,09,的数字,表示的是：,无符号数的集合,若两个正规式,e,1,和,e,2,所表示的正规集相同,则说,e,1,和,e,2,等价,写,作,e,1,=e,2,例如：,e,1,=(ab),，,e,2,=ba,又如：,e,1,=,b(ab,),e,2,=(,ba),b,e,1,=(ab),e,2,=(a,b,),设,r,s,t,为正规式，正规式服从的代数规律有：,r,s=sr“,或”服从交换律,r,(st)=(,r,s,),t“,或”的可结合律,(,rs)t,=,r(st,)“,连接”的可结合律,r(st)=,rsrt,(st)r=,srtr,分配律,r=r,r=r,是“连接”的恒等元素（零一律）,r,r=r,r,=,rrr,“,或”的抽取律,三,.,正规文法和正规式的等价性,1.,将上的一个正规式,r,转换成文法,G=(V,N,V,T,P,S),：,令,V,T,，,确定产生式和,V,N,的元素用如下办法,：,选择一个非终结符,S,生成产生式,S,r,，,并将,S,定为,G,的,识别符号。若,x,和,y,都是正规式，,B,V,N,，,则：,(R,1,),对形如,A,xy,的,正规产生式,，重写为,：,A,xB,，,B,y,(R,2,),对形如,A,x,*,y,的,正规产生式,，重写为：,A,xA,，,A,y,(R,3,),对形如,A,xy,的,正规产生式,，重写为,:,A,x,，,A,y,不断应用R做变换，直到每个产生式右端只含一个,V,N,例,4.4,将,r=a(a|d)*,转换成相应的正规文法,令,S,是文法的开始符号，形成,S,a(a|d)*,：,R1,S,aA,A,(a|d)*,R2,S,aA,A,(,a|d)A,A,R3,S,aA,A,aA,A,dA,A,2.,将正规文法转换成正规式：,基本上是上述过程的逆过程，最后只剩下一个开始符,号定义的正规式，其转换规则如表,4.1,所示：,例,4.5,Gs:,S,aA,S,a,A,aA,A,dA,A,a,A,d,S,aA|a,A,aA|dA|a|d,(a|d)A|(a|d),(a|d)*(a|d),s=a(a|d)*(a|d)|a=a(a|d)*(a|d)|,)=a(a|d)*|,),r=a(a|d)*,4.3,有穷自动机,一,.,确定的有穷自动机（,DFA,）（,有限自动机）,DFA,：,能准确地识别正规集,一个确定的,DFA,：,M=,（,K,，,，,f,，,S,，,Z,）,K,是一个有穷集，它的每个元素称为一个状态,是一个有穷字母表，它的每个元素称为一个输入符,号，所以也称,为输入符号字母表,f,是转换函数，是在,KK,上的映射，即，如,f,（,k,i,，,a,）,=,k,j,，（,k,i,K,，,k,j,K,）,就意味着，当前状,态为,k,i,，,输入符为,a,时，将转换为下一个状态,k,j,，,我们,把,k,j,称作,k,i,的一个后继状态,SK,是唯一的一个初态,Z,K,是一个终态集，终态也称可接受状态或结束状态,例,4.6,：,DFA M=,（,S,，,U,V,，,Q,，,a,，,b,，,f,，,S,，,Q,）,其中,f,定义为：,f,（,S,，,a,）,=U,f,（,V,，,a,）,=U,f,（,S,，,b,）,=Vf,（,v,，,b,）,=Q,f,（,U,，,a,）,=Qf,（,Q,，,a,）,=Q,f,（,U,，,b,）,=Vf,（,Q,，,b,）,=Q,一个,DFA,可以表示成一个,状态图,（状态转换图）,假定,DFA,M,含有,m,个状态，,n,个输入符号，那么这个,状态图含有,m,个结点，每个结点最多有,n,个弧射出，整,个图含有唯一一个初态结点,(,、,),和若干个终态结,点,(,双圈、,+),，若,f(k,i,a,)=,k,j,，,则从状态结点,k,i,到状态结点,k,j,画标记为,a,的弧,图,4.1,状态图表示,例,4.6,中的,DFA,的状态图表示如图,4.1,所示：,一个,DFA,可以表示成一个,矩阵表示,，该矩阵的行表示状,态，列表示输入符号，矩阵元素表示相应状态和输入符,号将转换成的新状态，即,k,行,a,列为,f(k,a),的值。用,标明初态；否则第一行即是初态，相应终态行在表的右,端标以,1,，非终态标以,0,图,4.2,矩阵表示,例,4.5,中的,DFA,的矩阵表示如图,4.2,所示：,若,t,*,，,f(S,，,t)=P,，,其中,S,为,M,的开始状态，,P,Z,，,Z,为终态集，则称,t,为,DFA M,所接受,（识别）,设,QK,，,函数,f(Q,)=Q,，,一个输入符号串,t,（,t,1,t,x,，,t,1,t,x,*,），在,DFA,M,上运行的定义为：,f(Q,t,1,t,x,)=f(f(Q,t,1,),t,x,),例如，证明,t=,baab,被例,4.6,的,DFA,所接受,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,的确定性表现在转换函数,f:KK,是一个单值,函数，也就是说,对任何状态,kK,和输入符号,a,，,f(k,a),唯一地确定了下一个状态,二,.,不确定的有穷自动机,NFA,一个,NFA,：,M=,（,K,，,f,，,S,，,Z,）,K,是一个有穷集，它的每个元素称为一个状态,是一个有穷字母表，它的每个元素称为一个输入符号,f,是一个从,K,*,到,K,的子集的映像，即：,K*,*,2,K,S,K,是一个非空初态集,Z,K,是一个终态集,例,4.7,：一个,NFA M=,（,0,，,1,，,2,，,3,，,4,，,a,，,b,，,f,，,0,，,2,4,）,其中,f(0,a)=0,3 f(2,b)=2,f(0,b)=0,1 f(3,a)=4,f(1,b)=2 f(4,a)=4,f(2,a)=2 f(4,b)=4,它的状态图表示如图,4.3,所示：,一个,NFA,也可以用一个矩阵表示,.,*,上的符,号,串,t,在,NFA N,上运行,.,*,上的符,号,串,t,被,NFA N,识别（读出、接受）,.,DFA,是,NFA,的特例,对每个,NFA,N,存在一个,DFA,使得,L(M)=L(N),对于任何两个有穷自动机,M,和,N,，,如果,L(M)=L(N),，,则称,M,与,N,是等价的,三,.NFA,转换为等价的,DFA,定理：,设,L,为一个由不确定的有穷自动机接受的集合，则,存在一个接受,L,的确定的有穷自动机,将,NFA,转换成接受同样语言的,DFA,，,这种算法称为,子集法,定义对状态集合,I,的几个有关运算：,1,.,状态集合,I,的,-,闭包，表示为,-closure(I),，,定义为一状态,集，是状态集,I,中的任何状态,S,经任意条弧而能到达的状,态的集合。,状态集合,I,的任何状态,S,都属于,-closure(I),2,.,状态集合,I,的,a,弧转换，表示为,move(I,a),定义为状态集合,J,，,其中,J,是所有那些可从,I,的某一状态经过一条,a,弧而到达,的状态的全体,使用图,4.4,的,NFA,N,的状态集合来理解上述两个运算：,-closure(0)=0,1,2,4,7,令A=0,1,2,4,7,move(A,a)=3,8,-closure(3,8)=1,2,3,4,6,7,8,图4.4NFAN,对于一个,NFA,N=,（,K,，,f,，,K,0,，,K,t,）,来说，若,I,是,K,的一个子集，设,I,s,1,s,2,s,j,，,a,是中的一个元素，则,move(I,a)=f(s,1,a)f(s,2,a),f(s,j,a,),假设,NFA N=(K,f,K,0,K,t,),按如下办法构造一个,DFA,M=(S,d,S,0,S,t,),，,使得,L(M)=L(N),：,M,的状态集,S,由,K,的一些子集组成。用,S,1,S,2,.,S,j,表示,S,的元素，其中,S,1,S,2,.,S,j,是,K,的状态。并且约定，状态,S,1,S,2,.,S,j,是按某种规则排列的，即对于子集,S,1,S,2,=S,2,S,1,来说，,S,的状态就是,S,1,S,2,M,和,N,的输入字母表是相同的，即是,转换函数是这样定义的：,D(,S,1,S,2,.,S,j,a,)=R,1,R,2,.,R,i,其中,R,1,R,2,.,R,i,=,-closure(move,(,S,1,S,2,.,S,j,a,),S,0,=,-closure(K,0,),为,M,的开始状态,S,t,=,S,j,S,k,.,S,e,，,其中,S,j,S,k,.,S,e,S,且,S,j,S,k,.,S,e,K,t,构造,NFA N,的状态,K,的子集的算法，见图,4.5,：,假定所构造的子集族为,C,，即,C=(T,1,T,2,.,T,i,),其中,T,1,T,2,.,T,i,为状态,K,的子集,例,4.8,应用图,4.5,的算法对图,4.4,的,NFA,N,构造子集,步骤如下：,1.,首先计算,-closure(0),：令,T,0,=-closure(0)=0,1,2,4,7,，,T,0,未,被标记，它现在是子集族,C,的唯一成员,2.,标记,T,0,：令,T,1,=-closure(move(T,0,a)=1,2,3,4,6,7,8,，将,T,1,加入,C,中，,T,1,未被标记。令,T,2,=-closure(move(T,0,b),=1,2,4,5,6,7,，将,T,2,加入,C,中，,T,2,未被标记,3.,标记,T,1,：,-closure(move(T,1,a)=1,2,3,4,6,7,8,，即,T,1,，,T,1,已,在,C,中。,T,3,=-closure(move(T,1,b)=1,2,4,5,6,7,9,，将,T,3,加,入,C,中，,T,3,未被标记,4.,标记,T,2,：,-closure(move(T,2,a)=1,2,3,4,6,7,8,，即,T,1,，,T,1,已,在,C,中。,-closure(move(T,2,b)=1,2,4,5,6,7,，即,T,2,，,T,2,已在,C,中,5.,标记,T,3,：,-closure(move(T,3,a)=1,2,3,4,6,7,8,，即,T,1,。,-,closure(move(T,3,b)=1,2,4,5,6,7,10,令其为,T,4,，,在入,C,中，,T,4,未被标记,6.,标记,T,4,：,-closure(move(T,4,a)=1,2,3,4,6,7,8,，即,T,1,。,-closure(move(T,4,b)=1,2,4,5,6,7,，即,T,2,a,b,0,01247,T,0,=01247,38,5,38,1234678,5,124567,T,1,=1234678,38,59,59,1245679,T,2,=124567,38,5,T,3,=1245679,38,5 10,5 10,12456710,T,4,=12456710,38,5,至此，算法终止共构造了,5,个子集：,T,0,=0,1,2,4,7,T,1,=1,2,3,4,6,7,8,T,2,=1,2,4,5,6,7,T,3,=1,2,4,5,6,7,9,T,4,=1,2,4,5,6,7,10,那么图,4.4,的,NFA,N,构造的,DFA,M,为：,1.S=T,0,T,1,T,2,T,3,T,4,2.=a,b,3.D(T,0,a)=T,1,D(T,3,a)=T,1,D(T,0,b)=T,2,D(T,3,b)=T,4,D(T,1,a)=T,1,D(T,4,a)=T,1,D(T,1,b)=T,3,D(T,4,b)=T,2,D(T,2,a)=T,1,D(T,2,b)=T,2,4.S,0,=T,0,5.S,t,=T,4,为便于书写，将,T,0,、,T,1,、,T,2,、,T,3,、,T,4,重新命名为,A,、,B,、,C,、,D,、,E,或用,0,、,1,、,2,、,3,、,4,分别表示，若采用后,者，该,DFA,M,的状态转换图如图,4.6,所示：,图4.6DFAM,四,.DFA,的化简,最小状态,DFA,：,没有多余状态,(,死状态,),没有两个状态是互相等价（,不可区别,）,一个有穷自动机可以通过消除无用状态和合并等价状态,而转换成一个最小的与之等价的有穷自动机,有穷自动机的无用状态：从该自动机的开始状态出发，,任何输入串也,不能到达,的那个状态或者从这个状态,没有,通路到达,终态,例如图,4.7,的有穷自动机,M,中的状态,s,4,便是无用状态,图,4.7,消除多余状态,在有穷自动机中，两个状态,s,和,t,等价的条件是：,一致性条件,必须同是为可接受状态或不可接受状态,蔓延性条件,对于所有输入符号，必须转换到等价的,状态里,分割法：,把一个,DFA,（,不含多余状态）的状态分成一些,不相交的子集，使得任何不同的两子集的状态都是可区,别的，而同一子集中的任何两个状态都是等价的,DFA,M,最小化方法,：,先分成终态集合和非终态集合,对每个集合中的符号分别用输出字母去查看它们到达状,态的集合是否在同一个集合中,如果不在同一个集合，将它们划分在不同的集合中,直到不能再划分为止,例,4.9,将图,4.8,中的,DFA,M,最小化,P,0,=(1,2,3,4,5,6,7),a,P,1,=(1,2,3,4,5,6,7),a,P,2,=(1,2,3,4,5,6,7),a,P,3,=(1,2,3,4,5,6,7),b,令,1,代表,1,2,消去,2,，令,6,代表,6,7,，消去,7,，得到图,4.8(b),的,DFA M,，,它是,4.8(a),的,DFA M,的最小化,图4.8DFAM和DFAM,4.4,正规式和有穷自动机的等价性,对于,上的一个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,例,4.10,以例,4.7,的,NFA,M,为例，,M,的状态图在图,4.3,，求,正规式,r,使,L(r)=L(M),对于,上的一个正规式R，可以构造一个,上的NFA,M，似的L,(M)=L(R),语法制导方法：按正规式的语法结构指引构造过程，首先,将正规式分解成一系列子表达式，然后使用下面规则为,r,构造,NFA,，对,r,的各种语法结构的构造规则具体描述如下：,1.,对于正规式,，,所构造的,NFA,为：,例,4.11,为,r=(a|b),*,abb,构造,NFA,N,使得,L(N)=L(r),从左到右分解,r,令,r,1,=a,第,1,个,a,则有,令,r,2,=b,则有,令,r,3,=r,1,|r,2,则有,令,r,4,=r,3,，,则有：,令,r,5,=a,，令,r,6,=b,，令,r,7,=b,，令,r,8,=r,5,r,6,，令,r,9,=r,8,r,7,，,则有：令,r,10,=r,4,r,9,，,则最终得到图,4.4,的,NFA N,即为所求。,其实，分解,R,的方式很多，用图,4.10(a)(b)(c)(d),分别表明另一种分解方式和所构造的,NFA,。,图,4.10,从正规式,r,构造,NFA,4.5,正规文法和有穷自动机的等价性,采用下面的规则可以从正规文法G直接构造一个有穷,自动机NFAM；使得L（M）L（G）：,M,的字母表与,G,的终结符集相同,为,G,中的每个非终结符生成,M,的一个状态，,G,的开始符,S,是开始状态,S,增加一个新状态,Z,，,作为,NFA,的终态,对,G,中的形如,A,tB,的规则（其中,t,为终结符或,，,A,和,B,为,非终结符的产生式），构造,M,的一个转换函数,f(A,t)=B,对,G,中形如,A,t,的产生式，构造,M,的一个转换函数,f(A,t)=Z,例,4.12,：与文法GS等价的NFAM如图,4.11,GS:,S,a A,S,bB,S,A,aB,A,bA,B,aS,B,bA,B,有穷自动机转换成等价的正规文法：,对转换函数,f(A,t)=B,可写一产生式：,A,tB,对可接受状态,Z,，,增加一产生式：,Z,有穷自动机的初态对应文法开始符,有穷自动机的字母表为文法的终结符集,例,4.13,：,给出与图,4.12,的,NFA,等价的正规文法,G,G,（,A,，,B,，,C,，,D,，,a,，,b,，,P,，,A,），,其中,P,为：,A,a B,C,A,bD,D,aB,B,bC,D,bD,C,aA,D,C,bD,4.6,词法分析程序的自动构造工具,以LEX为例介绍如何从正规式产生识别该正规式所描述的,单词的词法分析程序,LEX,是一个广泛使用的工具，,UNIX,系统中使用,lex,命令调,用。它用于构造各种各样语言的词法分析程序,图,4.13LEX,编译系统的作用,图,4.14,使用,LEX,生成词法分析器,LEX程序由三部分组成：,说明部分：变量说明、常量说明、正规定义,%,转换规则：,P,n,action,n,%,辅助过程：,容纳的是,action,所需要的辅助过程,图,4.15,给出一个识别,PL/O,单词的,LEX,程序片断：,IDENTa-zA-Z,a-zA-Z0-9*,NUMBER0-9 0-9*,%(,#include,stdio.h,#include code.h“,#include symbol.h“,#include y.tab.h“,extern,int,level;,int,cc=0;,%),%,cc+;,t,tablize,();/*,adjustcc,to tabposition*/,n cc=0;line-copy();/*copy a line of input file*/,cc+;return GT;,=cc+;return EQ;,#cc+;return NE;,cc+;return colon;,.cc+;return Period;,(cc+;return,Lparen,;,)cc+;return,Rparen,;,=cc+;cc+;return GE;,=cc+;cc+;return ASGN;,;cc+;return Semicolon;,NUMBER,intn,;,cc+=,yyleng,;,sscanf(yytext,%d,yylval.number,=n;,return NUMBER;,IDENT,Symbol*s;,cc+=,yyleng,;,if(s=,lookup(yytext,)=0)/*new identifier*/,s=install(yytext,VARIABLE,level,0);/*install symbol*/,if(stype=C),yylval.number,=,s-adr,;,else/*its a VARIABLE or PROC*/,yylval.sym,=s;,return s-type;,%,yywrap,(),;,图,4.15 LEX,程序例子,-,识别,PL/0,单词的,LEX,程序,【,本章小结,】,词法分析程序是编译第一阶段的工作，它读入字符流的源程序，按照词法规则识别单词,交由语法分析程序接下去。,本章讲述了词法分析程序设计原则，并介绍了正规式和有穷动机分别作为正规集描述和识别机制。在此基础上给出了词法分析程序自动构造工具如,LEX,的原理。,词法分析程序的设计技术可应用于其它领域，比如查询语言以及信息检索系统等，这种应用领域的程序设计特点是，通过字符串模式的匹配来引发动作，回想,LEX,，,说明词法分析程序的语言，可以看成是一个模式动作语言。,词法分析程序的自动构造工具也广泛应用于许多方面，如用以生成一个程序，可识别印刷电路板中的缺陷，又如开关线路设计和文本编辑的自动生成等。,