编译原理第三章 词法分析.ppt

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第三章 词法分析,(Lexical Analysis),Lexical:of or relating to words or,the vocabulary of a language,as distinguished from its grammar,and construction,词法分析在编译程序中的逻辑位置,表 处 理,错 误 处 理,目,标,代,码,生,成,中,间,代,码,优,化,中,间,代,码,生,成,语,义,分,析,语,法,分,析,词,法,分,析,目,标,程,序,源,程,序,主要内容：,词法分析程序的功能,;,单词分类及内部表示,;,词法分析程序的设计与实现步骤。,3.1,词法分析介绍,例,某程序片段如下：,VAR sum,first,count:real;,BEGIN,sum:=first+count*10,END.,V,A,R,s,u,m,f,i,r,s,t,c,o,u,n,t,:,r,e,a,l,;,B,E,G,I,N,s,u,m,:,=,f,i,r,s,t,+,c,o,u,n,t,*,1,0,E,N,D,.,源程序,一般表现为字符序列的形式,;,例,某程序片段如下：,VAR sum,first,count:real;,BEGIN,sum:=first+count*10,END.,:=,first,+,count,;,sum,count,:,real,VAR,sum,first,.,*,10,END,BEGIN,期望的源程序表示形式,:=,:,END,3.1.1,词法分析程序的功能,单词,是字符的序列,是指语言中那些具有独立含义的最小语义单位。,单词不是程序设计语言中的语法概念，是编译程序中引进的一个概念。,编译程序的翻译工作,为提高效率，编译,应该在单词一级上进行,;,词法分析的主要任务,:,词法分析是编译的第一阶段，它的的主要任务是按语言的词法规则，从左至右逐个字符地对原程序进行扫描，从源程序中识别出每个单词，并把每个单词转换成它们的内部表示，即所谓的,TOKEN,，同时进行词法检查。,词法分析程序：,执行词法分析的程序称为词法分析程序,有时也称为词法分析器,(Lexical Analyzer),或者扫描器,(Scanner),。,3.1.2,词法分析程序的接口,词法分析程序与语法分析程序的接口有两种形式,:,词法分析程序作为编译器的独立一遍,遍（,Pass,）：所谓“遍”就是对源程序或源程序的中间表示形式从头到尾扫描一次，并作加工处理，生成新的中间结果或目标程序。,词法分析程序作为独立的一遍：读入源程序字符序列，识别出每一个单词并将其转换成相应的内部表示，形成一个,TOKEN,序列，这个,TOKEN,序列将作为语法分析程序的输入；,词法分析程序作为语法分析程序的一个子程序,语法分析程序每调用一次词法分析程序,词法分析程序就从源程序的字符序列中拼出一个单词，并将其,TOKEN,值返回给语法分析程序。,这种方式的好处是，它不需要存储源程序的内部表示。,词法分析器的接口,CharList,独 立,词法分析器,语法分析,TokenList,附 属,词法分析器,语法分析,call,Token,CharList,3.2,词法分析程序的设计,3.2.1,单词分类,一般常用程序设计语言的单词可以分为以下几类：,保留字：,保留字一般是由语言系统自身定义的,，,通常是由字母组成的字符串。如,C,语言中的,int,if,for,do,等等。这些字在语言中具有固定的意义，是编译程序识别各类语法成分的依据。,标识符：,用来标识程序中各个对象的名称。它们由用户定义，用来表示变量名、常量名、数组名和函数名等。,常量：,主要包括整数常数、实数常数、字符常量、字符串常量等。,特殊符号,：,包括运算符和界限符。,运算符表示程序中算术运算、逻辑运算、,字符运算、赋值运算的确定的字符或字符串。,如各类语言通用的,+,、,-,、*、,/,、,=,、,=,等。,界限符在语言中是作为语法上的分界符号使用的。,如逗号、分号、单引号等。,3.2.1,单词分类（续）,3.2.2,单词的内部表示,TOKEN,结构图,单词的内部表示,TOKEN,的结构一般由两部分组成：单词类别和语义信息。,单词类别，又称词法信息，用来区分单词的不同种类，通常可以用整数编码来表示。,单词的语义信息，应该是唯一确定其本身内容的编码。,词法信息,语义信息,一、标识符和常量的,TOKEN,结构,给出标识符和常量类别编码,;,给出标识符和常量的,语义信息。,关于语义信息可以有两种处理方法：,一种是在其,TOKEN,的语义信息部分直接存储这些值；,另外一种是设置标识符表和常量表来存储其值，这时,TOKEN,的语义信息部分就是一个指向相应表项的一个指针。,第一种方法处理起来比较简单，但是,TOKEN,的空间大小不好确定，可能造成空间浪费。因此，我们采取第二种策略。,标识符种类编码,语义信息,常量种类编码,语义信息,二、保留字、界限符和运算符的处理,可以有两种处理方法：,一种是保留字、界限符和运算符分别算作一类，除了要给出其类别外，还需在其,TOKEN,的语义信息部分直接存储这些值的串或整数编码；如：,另外一种是保留字、界限符和运算符采用一符一类的方法，不输出单词的值（其,TOKEN,的语义信息部分为空），只输出其类别码即可。如：,保留字种类编码,if,+,的 编码,单词名称,类别编码,(,词法信息,),类别编码的助记符,标识符,1,$id,无符号整数,2,$,int,，,30,$comma,；,31,$semi,:=,32,$,assi,+,33,$plus,.,34,$stop,：35,$colon,*,36,$,mult,n,37,$return,var,15,$,var,real,20,$real,begin,23,$begin,end,24,$end,单词名称,类别编码,(,词法信息,),类别编码的助记符,标识符,1,$id,无符号整数,2,$,int,，,30,$comma,；,31,$semi,:=,32,$,assi,+,33,$plus,.,34,$stop,：,35,$colon,*,36,$,mult,n,37,$return,var,15,$,var,real,20,$real,begin,23,$begin,end,24,$end,例,1,某程序片段如下：,VAR sum,first,count:real;,BEGIN,sum:=first+count*10,END.,不设置标识符表和常量表，词法分析程序扫描该程序段的字符序列，生成下列,TOKEN,序列：,1.(15,),2.(1,sum),3.(30,)4.(1,first),5.(30,)6.(1,count),7.(35,)8.(20,),9.(31,)10.(37,),11.(23,)12.(37,),13.(1,sum),14.(32,),15.(1,first),16.(33,),17.(1,count)18.(36,),19.(2,10 )20.(37,),21.(24)22.(34,),单词名称,类别编码,(,词法信息,),类别编码的助记符,标识符,1,$id,无符号整数,2,$,int,，,30,$comma,；,31,$semi,:=,32,$,assi,+,33,$plus,.,34,$stop,；,35,$colon,*,36,$,mult,n,37,$return,var,15,$,var,real,20,$real,begin,23,$begin,end,24,$end,例,1,某程序片段如下：,VAR sum,first,count:real;,BEGIN,sum:=first+count*10,END.,不设置标识符表和常量表，词法分析程序扫描该程序段的字符序列，生成下列,TOKEN,序列：,1.(,$var,),2.(,$id,sum),3.(,$comma,)4.(,$id,first),5.(,$comma,)6.(,$id,count),7.(,$colon,)8.(,$real,),9.(,$semi,)10.(,$return,),11.(,$begin,)12.(,$return,),13.(,$id,sum),14.(,$,assi,),15.(,$id,first),16.(,$plus,),17.(,$id,count)18.(,$,mult,),19.(,$,int,10 )20.(,$return,),21.(,$end,)22.(,$stop,),设置标识符表和常量表,词法分析程序扫描该程序段的字符序列，生成下列,TOKEN,序列：,1.(,$var,),3.(,$comma,),5.(,$comma,),7.(,$colon,)8.(,$real,),9.(,$semi,)10.(,$return,),11.(,$begin,)12.(,$return,),13.(,$id,p,1,),14.(,$,assi,),15.(,$id,p,2,),16.(,$plus,),17.(,$id,p,3,)18.(,$,mult,),20.(,$return,),21.(,$end,)22.(,$stop,),p,2,p,1,p,3,p,4,标识符表,常量表,例,1,某程序片段如下：,VAR sum,first,count:real;,BEGIN,sum:=first+count*10,END.,sum,2.(,$id,p,1,),first,count,10,4.(,$id,p,2,),6.(,$id,p,3,),19.(,$,int,p,4,),例,某程序片段如下：,VAR sum,first,count:real;,BEGIN,sum:=first+count*10,END.,(30,),(1,p3),(35,),(34,),(15,),(1,p1),(30,),(1,p2),(37,),(1,p1),(32,),(20,),(31,),(37,),(23,),(2,10),(37,),(24,),(1,p2),(33,),(1,p3),(36,),曾期望的形式,源程序,词法分析的结果,3.2.3,单词的形式描述,描述程序设计语言中单词的工具主要有：正则表达式、自动机和正则文法。,设计一个语言的词法分析器，通常是首先用正则表达式描述各类单词的组成，然后将其转换为确定有限自动机，最后根据这个自动机来构造词法分析器。,基于正则表达式的单词的形式化描述,一般的程序设计语言，各类单词的正则表达式可描述如下：,1,）,标识符,：,L(L|D),*,其中：,L=a-z,A-Z,D0-9,2,）,正整数,：,D,1,D,*,其中：,D,1,=1-9,，,D=0-9,3,）,特殊符号,：,+|,；,|,：,|:=|=|,4,）,保留字,：,begin|end|while|,基于有限自动机的单词的形式化描述,构造识别单词的有限自动机的方法与步骤如下：,1.,根据构成规则对程序语言的单词按类构造出相应的状态转换图，或将,各类单词的正则表达式转换成,相应的有限自动机。,2.,合并各类单词的状态转换图，构成一个能识别语言所有单词的,DFA,。合并方法为：,（,1,）将各类单词的状态转换图的初始状态合并为一个唯一的初始状态；,（,2,）化简调整状态冲突和对冲突状态重新编号；,（,3,）如果有必要，增加出错状态。,例：,标识符,D,1,D,无符号整数,+,界限符,、,运算符,：,=,图,3,.,4,各类单词的自动机,；,：,=,L,L,|,D,合并后的,DFA,0,1,L,L,|,D,2,D,1,D,：,=,6,5,3,+,4,；,=,9,7,8,0,7,10,6,other,other,3.2.4,自动机的实现,自动机实现的状态转换矩阵法（又称数据中心法）,把自动机看作一种数据结构（状态转换矩阵），由控制程序控制字符在其上运行，从而完成词法分析。转换矩阵法的优点是程序短，但占存储空间多。,State:=,InitState,;,Read(CurrentChar,);,while,T(State,CurrentChar),error,&,CurrentChar,Eof,do,begin State:=,T(State,CurrentChar,);,Read(CurrentChar,);,end;,if,State,FinalStates,then Accept else Error;,自动机实现的直接转向法（又称状态转换图方法、程序中心法、）,每个状态对应一个带标号的,switch,语句,转向边对应,goto,语句,特点：,程序长，但占用存储空间少,b,非终止状态对应的,switch,语句,i,j,k,a,L,i,:switch(,CurrentChar,)case a：,goto,L,j,;,case b:,goto,L,k,;,default :Error();,终止状态对应的,switch,语句,j,i,k,a,b,L,i,:,seitch,(,CurrentChar,),case a ：,goto,L,j,;,case b :,goto,L,k,;,case,Eof,:Accept;,default :Error();,3.3,词法分析程序的实现,3.3.1,实现词法分析程序应注意的问题,一般语言中常见的一些问题。,1.,保留字,识别保留字的实现方法可分为两大类：一类是设置保留字表，另一类是用自动机单独来识别。,设置保留字表方法的主要思想是事先构造好所谓的保留字表，在进行词法分析时，把保留字也当作一般标识符来识别，然后查保留字表，若有，则把它作为保留字来处理；若没有，则按一般标识符来处理。,用自动机单独来识别保留字的主要思想是在自动机中加入识别各个保留字的状态，即把保留字和一般标识符分开来识别而不统一识别。,b,e,g,i,n,e,n,d,Not(e,),Not(g,),Not(i,),Notn,),Not(n,),Not(d,),Not(b,e,),两种方式的比较：不用保留字表的优点是能提高速度，但它使得自动机的状态数随着保留字个数的增多而急剧变大。,2.,复合单词的识别,在程序设计语言中，有一类单词是由两个或者两个以上的符号组成的，这类单词的前缀部分也可以是一个独立的单词，如“,:=”,，在处理到“,:”,时，还不能断定这个单词是“,:”,，还是“,:=”,的前缀，这取决于“,:”,的下一个字符，如果下一个字符是“,=”,，则该单词为“,:=”,，否则为“,:”,。在处理这类单词时要特别加以注意。,3.,数的转换,词法分析程序应该把数字字符串转换成数，如“,123”,应该转换成,123,。,4.,向前看若干个字符的处理,在有些语言里，为了识别出一个单词需要向前看好几个字符。,5.,控制字符的处理,控制字符，如空格、,Tab,和回车换行等。这些字符将占用很大的空间，而且一般来说，它们只有词法意义而没有语法和语义上的意义（字符串内的控制字符例外）。,若,Tab,和空格符用来分隔源程序中不同的单词，则直接将它们删除。,回车换行本身并没有实际意义，但是对于错误处理起着重要的作用，因此回车换行不能直接删除。,需要注意的是不能删除掉字符串内的,Tab,和空格符，因为它们任何时候都是有意义的符号。,在处理,Tab,和空格符时，可以设置一个标志变量，每当进入字符串内部时令其为真，这样就可以根据此变量的值来判断是否在字符串内部，如果不是在字符串内部，可以直接将它们删除。,6.,注释的处理,源程序中的注释没有任何语法和语义上的意义，因此在进行词法分析时可以直接将注释删除，而不必生成其,TOKEN,。,3.3.4,实现算法,首先给出词法分析程序中用到的一些基本操作。,Append(string,char),：拼单词。,KeyWord(string,),：查保留字表，看,string,是否为保留字。若此函数返回,0,，则表示,string,是一个标识符，否则为保留字编码。,AddTable(table,string),：入表操作，检查,string,在,table,中有没有出现，若有则返回其位置指针，若没有则将其插入到,table,的末尾，并返回该位置的指针。,BACK,：源程序文件指针回退一个字符。,PROCEDURE Scanner();,BEGIN,LS,0,:string:=“”;,ReadChar(CurrentChar,);,case,CurrentChar,of,A.Z|,a.z,：,goto,LS,1,；,0.9,：,goto,LS,2,;,+,：,goto,LS,3,;,;,：,goto,LS,4,;,:,：,goto,LS,5,;,：,goto,LS,8,;,end;,0,1,L,L,|,D,2,D,1,D,：,=,6,5,3,+,4,；,=,9,7,other,10,other,8,LS,1,:string:=,Append(string,CurrentChar,);,ReadChar(CurrentChar,);,case,CurrentChar,of,A.Z,，,a.z,0.9,：,goto,LS,1,;,other,：,BEGIN,BACK;c:=,KeyWord(string,);,if(c!=0)then,return(c,“”);,else,begin,pID,:,=,AddTable(IdTable,string);,return($id,pID,);,end;,END,end;,0,1,L,L,|,D,2,D,1,D,：,=,6,5,3,+,4,；,=,9,7,other,10,other,8,LS,2,:string:=,Append(string,CurrentChar,);,ReadChar(CurrentChar,);,case,CurrentChar,of,0.9:,goto,LS,2,;,other:,BEGIN,BACK;,pNB,:,=,AddTable(NbTable,string);,return($int,pNB,);,END,end;,0,1,L,L,|,D,2,D,1,D,：,=,6,5,3,+,4,；,=,9,7,other,10,other,8,LS,3,:,return($plus,“”);,LS,4,:,return($semi,“”);,LS,5,:,ReadChar(CurrentChar,);,case,CurrentChar,of,=:,goto,LS,6,;,other:,goto,LS,7,;,end;,LS,6,:,return($assi,“”);,LS,7,:BACK;,return($colon,“”);,LS,8,:,ReadChar(CurrentChar,);,case,CurrentChar,of,=:,goto,LS,9,;,other:,goto,LS,10,;,end;,LS,9,:,return($le,“”);,LS,10,:BACK;,return($lt,“”);,END,0,1,L,L,|,D,2,D,1,D,：,=,6,5,3,+,4,；,=,9,7,other,10,other,8,3.4,词法分析程序自动生成,一个数的二进制表示后面加一个0”,得到的数相当于该数乘以,2,；,一个数的二进制表示后面加一个“,1”,得到的数相当于该数乘,2,加,1,。,练习题：用,正则表达式表示能被,3,整除,的二进制数的集合。,结果：,1(10*1|01*0)*10*|0,1,start,0,0,1,0,0,1,0,1,2,final,1,1,0,1,1,1,0,1,0,0,1,1,2,1,11,5,23,46,93,186,372,745,1491,1,start,0,0,1,0,0,1,0,1,2,final,1,01,*,0,01,*,0|,10*1,10,*,1,S,S,1(01*0|10*1)*1,1(01*0|10*1)*10*,1(01*0|10*1)*1|0,