第四章词法分析

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第4章,词法分析,本章目的,本章将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。,描述程序设计语言的词法的机制是,3,型文法,和,正则表达式,，,识别机制是,有穷状态自动机,。,4.1,词法分析程序的设计,词法分析,(,lexical analysis),逐个读入源程序字符并按照构词规则切分成一系列单词。,单词是语言中具有独立意义的最小单位,，包括保留字、标识符、运算符、标点符号和常量等。,词法分析是编译过程中的一个阶段,，在语法分析前进行。也可以和语法分析结合在一起作为一遍。,4.1.1,词法分析程序与 语法分析程序的接口方式,主要任务：读源程序，产生单词符号,其他任务：,滤掉空格，跳过注释、换行符,追踪换行标志，复制出错源程序，,宏展开，,源程序,词法分析程序,语法分析程序,Token,get token,.,帮助理解术语,常常遇到的术语,Token,单词,词标，符号,lexeme,词素，词位,pattern,模式，式样,In,general，there,is a set of strings in the input for which the same,token,is produced as output.,帮助理解术语,This set of strings is described by a rule called a,pattern,associated with the token.The pattern is said to match each string in the set.A,lexeme,is a sequence of characters in the source program that is matched by the pattern for a token.e.g.,Const pi=3.14159；,中的,pi,是,token“identifier”,的,lexeme，,其,pattern,为,letter followed by letters and/or digit.,4.1.2,词法分析程序的输出,单词符号一般可分为下列五种：,基本字,(,关键字,),begin end if while,var,标识符,常量名、变量名、过程名,常数,(,量,),数值常量、字符串、逻辑值,运算符,+,、,-,、*、,/,、,、,=,界符,，；,(),词法分析程序的输出,输出表示采用单词的,二元式,形式：,(,单词种别，单词自身的值,),语句,：,Const i=25,yes=1,(Id,指向,i,的符号表的入口指针,),(Id,指向,yes,的符号表的入口指针,),词法分析程序的输出,单词的种别用整数编码表示：,编码 单词,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 (1,指向,x,的符号表入口,),:=(4,:=),y (1,指向,y,的符号表入口,),;(5,;),4.1.3,将词法分析工作分离的考虑,词法分析工作独立的原因：,1.,简化设计,2.,改进编译效率,3.,增加编译系统的可移植性,4.2,单词的描述工具,单词,基本语法符号,描述工具,程序设计语言的单词的语法都能用正规文法或,3,型文法来描述。,词法分析技术,基于描述工具建立的,4.2.1,正规文法,3,型文法,G=(V,N,V,T,P,S),P,中的每一条规则都有：,A,aB,或,A,a,其中,A,，,B,V,N,a,V,T,正规文法描述的是,V,T,上的,正规集,正规文法的例,单词的描述,l,l,l,d,l,d,d,d,+-*/=,=,，,；,(),正规文法的例,单词的描述,例,4.1,无符号数的单词描述,d,.,e,d,.,e,d,e,d,正规文法的例,单词的描述,d,s,d,d,其中,s,表示,+,或,-,号,用实数,25.55e+5,和,2.1,进行分析,4.2.2,正规式,正规式,也称,正则表达式，,正规表达式,正规表达式,(regular expression),是说明单词的,pattern(,词法,),的一种重要的表示法,(,记号,),，是定义正规集的,数学,工具。,正规式的定义,正规式和它所表示的正规集的递归定义：,设字母表为,辅助字母表,=,，,，*，,(,，,),。,其中的,“,”读为“或”,，亦可用,“,+”,“,”,读为,“连接”,；,“,*,”读为“闭包”,，即任意有限次自重复连接。,正规式的定义,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,、,仅由有限次使用上述三步骤而定义的表达式才是,上的正规式,，仅由这些正规式所表示的字集才是,上的正规集,。,正规式与正规集,在不致混淆时，括号可省略。,规定算符的优先顺序为,“,(,”,、,“,),”,、,“,*,”,、,“,”,、,“,”,。,连接符,“,”,一般可省略不写。,“,*,”,、,“,”,和,“,”,都是左结合的。,review,Regular expressions on the alphabet,are defined by the following recursive rules:,1)Every symbol of,is a regular expression,2),and,is a regular expression,3)if,r1,and,r2,are regular expressions,so are,(,r1,),r1 r2 r1,|,r2 r1,*,review,4)Nothing else is a regular expression.,=,0,1,2,3,4,5,6,7,8,9,(1|2|3|4|5|6|7|8|9|0),*is a regular expression,(1|2|3|4|.8|9|0)(1|2|3.|8|9|0),*is a regular expression,(1|2|3.|8|9|0),+,正规式与正规集的例,例,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,，,+,，,-,，,则上的正规式：,d*(.,dd,*,)(e(+-,),dd,*,),表示的是无符号数的集合。,其中,d,为,09,的数字，,“,.,”,为小数点,。,上的正规式：,e,2,=,dd,*,定义的正规集：无符号整数,可以简单的导出具体的数，例如：,正规式与正规集的例,例：,=,l,，,d,则上的正规式：,r=l(l d)*,定义的正规集：,l,ll,ld,ldd,例：,=,字母，数字,=,l,，,d,则上的正规式：,e,1,=,字母,(,字母,数字,)*,e,1,=l(l d)*,定义的正规集：所有标识符的集合,正规式的等价,若两个正规式,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,为正规式，有：,1.r,s=sr,“,或”服从交换律,2,.,r,(st)=(,r,s,),t,“,或”的可结合律,3.(,rs)t,=,r(st,),“,连接”的可结合律,4.r(st)=,rsrt,(st)r=,srtr,分配律,5.,r=r r=r,是“连接”的恒等元素零一律,6.r,r=r r*=,rrr,“,或”的抽取律,4.2.3,正规文法到正规式,一个正规语言可以由正规文法定义，也可以由正规式定义。,对任意一个文法，存在一个定义同一个语言的正规式。反之亦然。,两者之间的转换,结构的等价性,。即：,对于上的一个正规式,r,，,存在一个文法,G=(V,N,V,T,P,S),且语言,L(G)=L(r),反之亦然。,正规式到正规文法,1.,将,上的一个正规式转换成,文法,：,G=V,N,V,T,P,S,所谓转换就是确定：,非终结符的非空有穷集,V,N,终结符的非空有穷集,V,T,产生式的非空有穷集,P,开始符号,S,正规式到正规文法,令,V,T,=,确定产生式和,V,N,的,元素,对任何的正规式,r,，,S,V,N,，,生成正规产生式：S,r,，,同时确定,V,N,和,P,。,将,S,定为,G,的识别符号。,不断应用上述规则做变换，直到每个产生式右端,最多,只含一个终结符为止。,正规式到正规文法,若,x,和,y,都是正规式，对形如,Axy,的,正规产生式，重写为：,AxB,By,并且新非终结符,B,V,N,对形如,Ax,*,y,的,正规产生式，,可,重写为：,AxB,Ay,BxB,By B,V,N,形如,Ax y,的,产生式，,可,重写为：,Ax Ay,正规式到正规文法,例,4.4,将,R=a(a,d)*,转换成,G1=(S,A,B,a,d,S,P,其中,P,：,S,aA,B,(a,d),B,A,(a,d),B A,B,令,S,为文法的开始符号，,V,T,=a,d V,N,=S,A,B,正规式到正规文法,R=a(a,d)*,Sa(ad)*,SaA,A(ad)*,SaA,AaB,AdB,A,BaB,BdB,B,SaA,A,(ad)B,A,B(ad)B,B,正规文法到正规式,2.,将正规文法转换成正规式,转换结果为形如：,开始符,S,终结符,的形式,转换规则：,文法产生式,正规式,规则,1,规则,2,规则,3,AxB,By,AxAy,Ax Ay,A=,xy,A=x,*,y,A=xy,正规文法到正规式,例,4.5,文法,Gs,：,S,aA,S,a,AaA,AdA,Aa,Ad,S,=,aAa,A,=(,aAdA)(ad,),A=,(ad)A(ad),A,=(ad)*(ad),应用规则,转换,S=a,(ad),*,(ad)a,=a(ad)*(ad),),=a(ad)*,),=a(ad)*,正规式,r,应用代数,规律,4.3,有穷自动机,有穷自动机,(,也称,有限自动机,),作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，,有穷自动机分为两类：,确定的有穷自动机,DFA,(Deterministic Finite Automata),不确定的有穷自动机,NFA,(Nondeterministic Finite Automata),4.3.1,确定的有穷自动机,(DFA),DFA,定义：,一个确定的有穷自动机,(DFA)M,是一个五元组,：,M=(K,，,，,f,，,S,，,Z),其中：,1.K,是一个有穷集，它的每个元素称为一个状态；,2.,是一个有穷字母表，它的每个元素称为一个输入符号，也称,为输入符号字母表