第3章词法分析和词法分析程序课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,东华大学计算机学院,第,*,页,编 译 原 理,第 三 章,词法分析和词法分析程序,编 译 原 理第 三 章,Principles of Compiler Design,Chapter 3.Lexical Analysis,Principles of Compiler DesignC,3.1 设计扫描器时应考虑的问题,词法分析程序亦称为扫描器,任务：扫描程序，识别单词,扫描器的输出是语法分析程序的输入,东华大学计算机学院,3.1 设计扫描器时应考虑的问题词法分析程序亦称为扫描器东华,3,3.1,How to construct a lexical analyzer,A lexical analyzer is also called Scanner,The main task of the lexical analyzer is to read the input characters of the source program,and group them into lexemes.,The lexical analyzer outputs a sequence of tokens for each lexeme in the source program to the parser for syntax analysis.,东华大学计算机学院,3.1 How to construct a lexical,4,3.1.1 词法分析的必要性,描述单词的结构比其它语法结构简单，仅用3型文法就够了；,将单词识别从语法分析识别分离出来，可采用更有效的工具实现；,有些语言的单词识别与前后文相关，不宜将其与语法分析合并；,使编译程序各部分独立出来，有利于设计、调试和维护,东华大学计算机学院,3.1.1 词法分析的必要性描述单词的结构比其它语法结构简单,5,3.1.1,Lexical Analysis Versus Parsing,The separation of lexical and syntactic analysis often leads to a cleaner overall design.,Compiler efficiency is improved.A separate lexical analyzer allows us to apply specialized techniques that serve only the lexical task,not the job of parsing.,Compiler portability is enhanced.Input-device-specific peculiarities can be restricted to the lexical analyzer.,东华大学计算机学院,3.1.1 Lexical Analysis Versus,6,3.1.2 单词符号的内部表示,常用的内部表示方法:,(,class,value),为便于阅读，常用,助记符,（或,常量标识符、宏定义等）,表示,class,。,单词的分类方法：可,一词一类,（,+,、,-,、,begin,、,end,等）或,多词一类,（如关键字类、操作符类、分隔符类、变量名类、常数类等）。,在识别出变量名、函数（过程）名时，还应进行,查填符号表,的工作。,东华大学计算机学院,3.1.2 单词符号的内部表示常用的内部表示方法:(cla,7,3.1.2 Tokens,A token is a pair consisting of a token name and an optional attribute value,(,class,value),The token name is an abstract symbol representing a kind of lexical unit,e.g.,a particular keyword,or a sequence of input characters denoting an identifier.,The token names are the input symbols that the parser processes.We will often refer to a token by its token name.,东华大学计算机学院,3.1.2 TokensA token is a pair,8,3.1.3 识别标识符的若干约定和策略,一般来说，单词的长度是有限制的。,在允许长度下，应按最长匹配原则进行识别,有时需要超前扫描来进行单词识别。,在进行超前扫描时，还应注意“回退”字符，即将多吃掉的字符退还回输入缓冲区。,东华大学计算机学院,3.1.3 识别标识符的若干约定和策略一般来说，单词的长度是,9,3.1.3,Token Recognition,All tokens have finite length.,Tokens are recognized when all possible symbols are scanned.,Sometimes we need to look at least one additional character ahead.,东华大学计算机学院,3.1.3 Token RecognitionAll tok,10,3.2 正规文法和状态转换图,3.2 正规文法和状态转换图,3.2,Regular Expressions&Transition Diagrams,3.2 Regular Expressions&Tra,3.2.1 由正规文法构造状态转换图,程序设计语言的单词都能用正规文法描述,一般说来，凡能用正规文法描述的语言，均可,由某种有限状态算法,状态转换图,进行分析,状态转换图：,有向图（一个初态+,N,个终态）,射出结点，进入结点,东华大学计算机学院,3.2.1 由正规文法构造状态转换图程序设计语言的单词都能用,13,3.2.1,Conversion from regular-expression patterns to transition diagrams,Tokens can be described by regular-expression,Such tokens can therefore be analyzed by transition diagrams.,Transition diagram:,Directed flowcharts with one,(one state of lexemeBegin and some states called final),东华大学计算机学院,3.2.1 Conversion from regular-,14,构造状态转换图（一）,由右线性文法构造状态转换图,G=(V,N,V,T,P,S),是右线性文法，,|,V,N,|=K,。,状态转换图共有,K+1,个状态(结点)。,构造规则：,AaB，,从结点,A,引一有向边到结点,B,并用,a,标记这一有向边,;,Aa，,从结点,A,引一有向边到终态结点,F,并用,a,标记这一有向边,;,A,，,则将结点,A,设为终态。,东华大学计算机学院,构造状态转换图（一）由右线性文法构造状态转换图东华大学计算机,15,Transition diagram construction,(,1),From collections of regular expressions.,Given,G=(V,N,V,T,P,S),a,set of regular expressions,with,|V,N,|=K,.,There are,K+1,states in the diagram.,For,AaB,an edge from states,A,t,o,B,it also be labeled with,a,.,For,Aa,an edge from,A,to final state,F,it is labeled with,a,.,When,A,state,A,is final itself.,东华大学计算机学院,Transition diagram constructio,16,构造状态转换图（一）,无符号数的文法对应的,状态转换图,0,4,5,2,1,3,6,d,.,d,d,d,d,.,E,+|-,E,d,d,东华大学计算机学院,构造状态转换图（一）无符号数的文法对应的状态转换图04521,17,Transition diagram construction,(,1),Diagram for grammar of numeric,0,4,5,2,1,3,6,d,.,d,d,d,d,.,E,+|-,E,d,d,东华大学计算机学院,Transition diagram constructio,18,构造状态转换图（一）,由右线性文法构造状态转换图,识别串：字符串,w=a,1,a,2,a,n,a,i,V,T,从初态出发,分别沿一切可能的路径到达终态结点,并将所有矢线上所标记的字符依次连接起来，便得到状态转换图所能识别的全部符号串，这些符号串组成的集合构成了该文法识别的语言。,东华大学计算机学院,构造状态转换图（一）由右线性文法构造状态转换图东华大学计算机,19,Transition diagram construction,(,1),From regular expression,Recognition of input string:,w=a,1,a,2,a,n,a,i,V,T,Begins in the initial state,advance along any available edges and reaches the final state.All such strings formed by concatenating all edge labels form the collection of sentences that can be recognized by the diagram.,东华大学计算机学院,Transition diagram constructio,20,构造状态转换图（一）,由右线性文法构造状态转换图,识别串：字符串,w=a,1,a,2,a,n,a,i,VT,实际：建立推导,S*w,第一步,S,下扫描到,a,1,而过渡到下一状态,A,1,，由构造规则可知，,G,中必有产生式,Sa,1,A,1,。后续步骤中，由状态,A,i,识别,a,i+1,后过渡到,A,i+1,恰好对应了使用产生式,A,i,a,i+1,A,i+1,最后在状态,A,n-1,识别,a,n,后到达终态,F,，对应了使用产生式,A a,n,进行推导：,S a,1,A,1,a,1,a,2,A,2,a,1,a,2,a,n-1,A,n-1,a,1,a,2,a,n,东华大学计算机学院,构造状态转换图（一）由右线性文法构造状态转换图东华大学计算机,21,右线性文法与状态转换图,右线性文法,G,相应的,状态转换图,M,：,(1),利用,M,对符号串,w,进行识别,M,中状态转换模拟一步直接推导,即识别方法,(,或称分析方法,),为,“,”,(2),右线性文法,只有产生式,AaB,、,A a,，每一步推导结果只含一个非终结符，,规范,推导,(3),M,所识别的任一符号串,x,，存在,G,中的一个推导,S*x,(,即有,xL(G),；反之,对于,L(G),中任一句子,y,，必存在一条从初态,S,到终态,F,的路径,此路径上各矢线标记依次拼接组成的符号串为,y,东华大学计算机学院,右线性文法与状态转换图右线性文法G相应的状态转换图M：东华大,22,构造状态转换图（二）,由左线性文法构造状态转换图,用,G,的,V,N,符标记,M,的结点，其中，开始符,S,对应的结点为终态结点。引入一个新结点：初态,R(,V,N,),东华大学计算机学院,构造状态转换图（二）由左线性文法构造状态转换图东华大学计算机,23,构造状态转换图（二）,矢线的连接规则为,:,对于,G,中形如,Aa,的产生式,引矢线,R,A,且标记为,a,;,对于,G,中形如,ABa,的产生式,引矢线,B,A,且标记为,a,.,东华大学计算机学院,构造状态转换图（二）矢线的连接规则为:东华大学计算机学院,24,构造状态转换图（二）,例：,文法,G=(S,U,0,1,S,S1|U1,UU0|0,S),东华大学计算机学院,构造状态转换图（二）例：文法G=(S,U,0,1,25,构造状态转换图（二）,文法,G=(S,U,0,1,S,S1|U1,UU0|0,S),识别句子,00011，,就识别的方法而言,它属于“,”分析,.,步骤 当前状态 余留的符号串,1,R,00011,2,U,0011,3,U,011,4,U,11,5,S,1,6,S,(,识别结束),东华大学计算机学院,构造状态转换图（二）文法G=(S,U,0,1,S,26,识别符号串与归约,从初态,R,到下一状态,A,对应,B,a,，即终结符,a,归约成非终结符,B,;,从状态,B,转换到状态,A,对应,ABa,即将,Ba,归约为,A,;,状态,A,转换到状态,S,(,终态,),对应,S Aa,即将,Aa,归约为开始符,S,.,归约成功,恰好进入终态,即状态转换图识别了,(,或接受,),该符号串,.,识别,00011,的例子的归约过程,东华大学计算机学院,识别符号串与归约从初态R到下一状态A对应Ba，即终结符a归,27,3.2.2 状态矩阵法,构造状态矩阵，,控制程序,对单词加以识别,开始,初始化,getchar(),查状态矩阵（,state,symbol）,end?,回退一个字符,东华大学计算机学院,3.2.2 状态矩阵法构造状态矩阵，控制程序对单词加以识别开,28,3.2.2 状态矩阵法,例：有,DFA,M=(0,1,2,3,a,b,0,3),其中,为,:(0,a)=1(0,b)=2(1,a)=3(1,b)=2,(2,a)=1(2,b)=3(3,a)=3(3,b)=3,它所对应的状态转移矩阵如图：,状态,a,b,0,1,2,1,3,2,2,1,3,3,3,3,状态,输入字符,后继,状态,东华大学计算机学院,3.2.2 状态矩阵法例：有DFA M=(0,1,2,3,29,词法分析程序构造过程,正规表达式,构造识别该正规表达式的带,的自动机,将-自动机转化为,DFA，,并且最小化,根据最小化的,DFA,构造状态矩阵,编写控制程序，对词法进行识别,东华大学计算机学院,词法分析程序构造过程正规表达式构造识别该正规表达式的带的自,30,3.3,有限自动机,状态转换图,实际上是,有限自动机,的图形表示,3.3 有限自动机状态转换图实际上是有限自动机的图形表示,3.3.1 确定的有限自动机DFA,五要素,M=(K,f,S,0,Z),状态集合,字母表,状态映射,初态,终态集,状态映射,f：K K,可将,f,定义域推广为,K*K,(1),f(s,)=s,sK,;,(2),f(s,aw)=f(f(s,a),w),sK,a,w*;,所以，,f,与,f,不可区分,东华大学计算机学院,3.3.1 确定的有限自动机DFA五要素 M=(,32,识 别,DFA,M,识别,*中的,x,：,从初态,S,0,出发,，,经一恰好标有,x,的路径后可达到某终态,SZ,即：,f(S,0,x)=S，SZ,M,的接受集,L(M),=,x,|f,(,S,0,x,),Z,x,*,DFA：,给一状态，一字符，则唯一确定下一状态,任一正规文法,G，,都存在一个,DFA M，,使得：,L(G)=L(M),东华大学计算机学院,识 别DFA M识别*中的x：从初态S0出发，经一恰好标,33,习 题,对于文法：,G=(S,A,B,C,D,a,b,c,d,P,S),，,P,由如下产生式组成：,S,aA|B AabS|bB Bb|cC CD Dd|bB,（,1,）构造该文法的状态转换图,（,2,）构造一等价的左线性文法,东华大学计算机学院,习 题对于文法：G=(S,A,B,C,D,a,b,c,34,3.3.2 非确定的有限自动机,NFA,M=(K,f,S,0,Z),f,：,K(K)，,即将,(,S,i,a,j,),映射到,K,的一个子集,S,k,1,S,k,m,即下一状态不唯一,可类似地，把,f,的定义域拓广到,K*,(1),f(S,)=S;,(2),f(S,aw)=f(f(S,a),w)a,w*,东华大学计算机学院,3.3.2 非确定的有限自动机NFA M=(K,35,NFA,的接受集,L(M),=,x|f(S,0,x),Z,x,例：,S,A,B,C,a,a,b,a,b,b,a,a,识别符号串,ababb,东华大学计算机学院,NFA的接受集L(M)=x|f(S0,x)Z,36,3.3.3 NFA与DFA的等价性,NFA,的确定化：构造一,DFA，,使得它们有相同的接受集,思路：使,DFA,的状态与,NFA,某一状态子集相同,S,0,S,1,a,b,b,a|b,定理3.1,例：,M=(S,0,S,1,a,b,f,S,0,S,1,),此确定化算法的弱点,东华大学计算机学院,3.3.3 NFA与DFA的等价性NFA的确定化：构造一DF,37,3.3.4 具有,动作的,FA,允许对,作转移,例：,0,1,2,3,a,b,b,c,f,也可以拓广到,f:,K*(K),.,f(S,x),是由这样的状态,Q,组成,存在从,S,到,Q,的路径,该路径上的连线标记组成的符号串恰好为,x,其中,允许有有限个标记为,串,aacc,可被接受,东华大学计算机学院,3.3.4 具有 动作的FA允许对作转移0123a,38,状态,S,的,-闭包：,-,CLOSURE(S),定义,(1),S-CLOSURE(S);,(2),设,S,j,-CLOSURE(S),且,S,j,S,k,则,S,k,-CLOSURE(S);,(3),有限地使用规则,（2）,所得的集合为,-,CLOSURE(S).,例,0,1,2,3,a,b,b,c,东华大学计算机学院,状态S的-闭包：-CLOSURE(S)定义0123,39,f的定义,东华大学计算机学院,f的定义东华大学计算机学院,40,f,与,f,不相等,f(S,a),-CLOSURE(f(S,a)f(S,a),只走一步,a,矢线,|,多步，第一步必须走,a,矢线,|,路径,a：,第一步可以是,矢线,-NFA,的接受集：,L(M)=w|f(S,0,w),Z,-,NFA,的用途：构造更复杂的,FA,东华大学计算机学院,f与f不相等-NFA的接受集：L(M)=w|f(S,41,3.3.,5,-,FA,的确定化,构造一,DFA，,使得它与,-,FA,等价。,例,0,1,2,3,a,b,b,c,东华大学计算机学院,3.3.5-FA的确定化构造一DFA，使得它与-FA等,42,习题,试将下面的,-,FA,确定化为,DFA:,S,1,2,5,6,3,4,a,a,a,a,b,b,b,b,F,东华大学计算机学院,习题试将下面的-FA确定化为DFA:S125634,43,习题,试将下面的,-,FA,确定化为,DFA:,S,1,2,5,6,3,4,a,a,a,a,b,b,b,b,F,-,CLOSURE(S)=S,1,2=q0,F(q0,a)=1,2,3=q1,F(q0,b)=1,2,4=q2,F(q1,a)=1,2,3,5,6,F=q3,F(q1,b)=1,2,4=q2,F(q2,a)=1,2,3=q3,F(q2,b)=1,2,4,5,6,F=q4,F(q3,a)=1,2,3,5,6,F=q3,F(q3,b)=1,2,4,6,F=q5,F(q4,a)=1,2,3,6,F=q6,F(q4,b)=1,2,4,5,6,F=q4,F(q5,a)=1,2,3,6,F=q6,F(q5,b)=1,2,4,5,6,F=q4,F(q6,a)=1,2,3,5,6,F=q3,F(q6,b)=1,2,4,6,F=q5,东华大学计算机学院,习题试将下面的-FA确定化为DFA:S125634,44,3.3.,6,DFA,状态数的最小化,对一个,DFA M,，构造另一个,DFA M,，使得：,L(M)=L(M),，后者有最小的状态数,可区分状态：,s,t,K,，若,w,*,，,f(s,w)=q Z,，而,f(t,w)=p,Z,，则,s,t,为一串,w,所区分,s,和,t,等价：,w,，,f(s,w)Z,，,f(t,w)Z,所以，可以将等价的状态合并,东华大学计算机学院,3.3.6 DFA状态数的最小化对一个DFA M，构造另一个,45,最小化算法,算法主要思想：将,K,划分为,r,个,互不相交,的子集，子集内任何两个状态是等价的，而不同子集任两个状态可区分。,例：,S,2,S,4,b,a,a,a,b,b,S,0,S,1,S,3,b,a,a,b,东华大学计算机学院,最小化算法算法主要思想：将K划分为r个互不相交的子集，子集内,46,3.4 正规表达式及正规集,L（G）L（M），即：正规文法与FA等价,所以，现在来为一个正规表达式构造一等价的FA,东华大学计算机学院,3.4 正规表达式及正规集L（G）L（M），即：正规文法,47,3.4.1正规表达式及正规集的定义,设,是一字母表,则上的正规表达式,(,正则表达式,正规式,),及其表示的正规集可递归定义如下,:,(1),是一正则表达式,相应的正规集为,;,(2),是一正则表达式,相应的正规集为,;,(3)a,a,是一正则表达式,相应的正规集为,a;,(4),设,r,s,是正则表达式,且它们所表示的正规集为,Lr,Ls,则,1.,(,r)(s),是正则表达式,相应的正规集为,LrLs;,2.(r)|(s),是正则表达式,相应的正规集为,Lr,Ls;,3.(r)*,是正则表达式,相应的正规集为,Lr*,有限地使用上面的规则,(4),所得的表达式均是正规表达式,东华大学计算机学院,3.4.1正规表达式及正规集的定义 设是一字母表,则上的,48,例子,a*,aa*,a|ba*,(a|b)(a|b)(a|b)*,正规集,1,：,n,正规式,正规式,r=,正规式,s,L,r,=L,s,东华大学计算机学院,例子a*,aa*,a|ba*,(a|b)(a|b),49,正规式的基本等价关系（公理）,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|st,A8.,r=r=,A9.,r=r=r,A10.,r*=(|r)*=|rr*,东华大学计算机学院,正规式的基本等价关系（公理）A1.r|s=s|r,50,3.4.2,由正规文法构造相应的正规式,例：,S,aS|bA|b,，,AaS,改写为：,S,=aS+bA+b,，,A=aS,S,=aS+baS,+b =(a+ba)S,+b,结果：,S,=(a+ba)*b (a|ba)*b,或：,S=a*(baS,+b)=a*baS,+a*b =(a*ba)*a*b,东华大学计算机学院,3.4.2 由正规文法构造相应的正规式例：SaS|,51,3.4.2,由正规文法构造相应的正规式,论断,3.1,方程,x=rx+t,有解,x=r*t,左线性文法,：,x=xr,+t,的方程，有解,x=tr*,东华大学计算机学院,3.4.2 由正规文法构造相应的正规式论断3.1 方程x=,52,3.4.3,正规式构造,FA,Thompson,法,对运算符个数,n,进行递归,算法：,1,、,n=0,时：,r=r=r=a,s,f,f,s,f,a,2,、设当,n=1,2,k-1,时,M,均可构造,当,n=k,时,根据正规式的定义,r,只能是,r,1,|r,2,r,1,r,2,r,1,*,这三种形式之一,.,其中,r,1,r,2,中最多含,k-1,个运算符,且设相应的自动机为,M1=(K,1,f,1,S,01,S,f1,)L(M,1,)=L,r1,M2=(K,2,f,2,S,02,S,f2,)L(M,2,)=L,r2,K,1,K,2,=,东华大学计算机学院,3.4.3 正规式构造FAThompson法对运算符个数n,53,Thmopson,法(续),(1)r=r,1,|r,2,引入新开始状态,S,0,终态,S,f,将,M,1,M,2,并联,:,S,01,S,f1,S,02,S,f2,s,S,f,(2)r=r,1,r,2,将,M,1,M,2,串联,S,01,S,f1,S,02,S,f2,(3)r=r*,引入新开始状态,S,0,终态,S,f,令原,M,1,构成循环,S,01,S,f1,S,S,f,东华大学计算机学院,Thmopson 法(续)(1)r=r1|r2,引入新,54,习 题,3-,21,3-,22(1),(2),东华大学计算机学院,习 题3-21东华大学计算机学院,55,习 题,3-7,的右线性文法为：,A0D,B0A|1C,C1F|0A,|1,F0E|1A,|0,D0B|1C,E1C|0B,构成正规式：,B=0A+1C;E=1C+0,B,=1C+0,0A,+0,1C,=00A+(1+01)C;D=0,B,+1C=0,0A,+0,1C,+1C=00A+(01+1)C;,C=1,F,+0A,+1,=1,0,E,+1,1A,+10,+0A,+1,=10,00A+(101+1001)C,+11A+0A,+10+1,=,(101+1001),C,+10,00A+,11A+0A,+10+1,=(101+1001)*,(,(1000+11+0)A,+10+1),;,A=0,D,=0,00A+(001+01),C,=000A+(001+01)(101+1001)*,(,(1000+11+0)A,+10+1,),=(000+(001+01)(101+1001)*(1000+11+0)A,+10+1,=(000+(001+01)(101+1001)*(1000+11+0)*,(10+1),东华大学计算机学院,习 题3-7的右线性文法为：东华大学计算机学院,56,习 题,S=a(a+b)*b(a+b)*a(a+b)*b(a+b)*,解：,A,=(a+b)*b(a+b)*a(a+b)*b(a+b)*,;S=aA;,A=(a+b)A+,b(a+b)*a(a+b)*b(a+b)*,;,B=,(a+b)*a(a+b)*b(a+b)*,;A=(a+b)A+bB;,B=(a+b)B+,a(a+b)*b(a+b)*,;,C=,(a+b)*b(a+b)*,;B=(a+b)B+,a,C;,C=(a+b)C+,b(a+b)*,;,D=,(a+b)*,;C=(a+b)C+bD;,D=(a+b)D;,东华大学计算机学院,习 题S=a(a+b)*b(a+b)*a(a+b)*b(a,57,