《词法分析副》PPT课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第2章 词法分析,2.1 词法分析器的设计考虑及手工构造,2.1.1,单词类型及二元式编码,单词类型,基本字、标识符、,常数、,运算符,、,界符,单词的性质,个数确定和不确定,单字符或多字符构成,2.1 词法分析器的设计考虑及手工构造,单词二元式编码,经词法分析后，单词用二元式,(,code,val),表示。,code,表示单词的种别，用整数码表示，在语法分析时使用。,val,表示单词的值，在本书中用字符串表示，在语义分析时使用。,2.1 词法分析器的设计考虑及手工构造,编码原则,通常将标识符归为一种，常数按类型分种，基本字、运算符及界符采用一符一种。,2.1 词法分析器的设计考虑及手工构造,实例-设有某一程序设计语言，其部分单词二元式编码如下所示：,2.1 词法分析器的设计考虑及手工构造,2.1 词法分析器的设计考虑及手工构造,用该程序设计语言编制的,计算园柱体表面积的源程序（输入输出略）如下所示：,Begin/*S=2*3.14* R* R +2*3.14* R*H */,Real r,h,s;,s=2*3.14*r*(r+h),End,2.1 词法分析器的设计考虑及手工构造,根据单词,二元式编码，,上述程序的单词二元式序列应为：,(,NUL)(c,NUL)(i,r)(,NUL) (i,h),(,NUL)(i, s),(;,NUL)(i, s)(=,NUL),(x, 2)(*,NUL)(y, 3.14)(*,NUL),(i, r)(*,NUL) (,NUL)(i, r),(+,NUL)(i, h)(),NUL)(,NUL),2.1 词法分析器的设计考虑及手工构造,2.1.2 源程序的输入及预处理,源程序的输入,l,分段读入处理（早期）,l,全部读入后处理,设源程序如下所示，其中,为续行符。,2.1 词法分析器的设计考虑及手工构造,2.1 词法分析器的设计考虑及手工构造,源程序读入后，输入缓冲区的内容如下所示：,2.1 词法分析器的设计考虑及手工构造,预处理,词法分析器通常由二个部分构成：,预处理程序,扫描器（单词识别程序）,2.1 词法分析器的设计考虑及手工构造,分成二部分的理由,词法分析可在输入缓冲区上直接进行，但从程序进行的角度来讲，若是把输入串预处理一下，则单词识别就会比较容易，故词法分析器通常由预处理程序和扫描器（单词识别程序）两部分组成。,2.1 词法分析器的设计考虑及手工构造,预处理主要工作,1.删除注释,2.删除续行符以及后续换行符（0,AH）,3.Tab,的作用相当于多个空格，换行符、,Tab,和空格具有界符作用，预处理时通常予以保留。在后面的分析中可以看到，它们的存在给后续的单词识别带来方便。为了简化判断，可在预处理时将换行符和,Tab,统一替换为空格。,4.大多数语言（除,C,语言外）不区分大小写，可在预处理时大写字母变换成小写字母，或相反，以方便后续处理。,5.对于受书写格式限制的语言（如,FORTRAN,和,COBOL），,还应识别标号区，正确给出语句标号；识别续行标志，把相继行连接在一起，给出语句结束符。,2.1 词法分析器的设计考虑及手工构造,上述源程序经预处理后，扫描缓冲区中的内容如下所示：,2.1 词法分析器的设计考虑及手工构造,预处理程序,下面用,C/C+,语言来编写一个预处理程序，其作用是去除源程序中的注释和续行符，将,Tab,和换行符替换为空格，将大写字母变换成小写字母。每调用一次，将经预处理的源程序全部送入内存中的扫描缓冲区，供扫描区识别单词。,2.1 词法分析器的设计考虑及手工构造,程序实现，由两个函数构成：,主函数main是测试驱动程序，调用预处理函数pro_process，模拟词法分析器工作；,函数pro_process执行预处理任务，借助于传地址获得扫描缓冲区的首址，将经预处理的源程序送入扫描缓冲区。,2.1 词法分析器的设计考虑及手工构造,由于算法需要，在源程序尾部添加字符#，这是一个特殊的单词，表示源程序的结束。,源程序中的注释用/*.*/标记，不允许嵌套使用，这和大多数高级语言的规定一致。,2.1 词法分析器的设计考虑及手工构造,源程序的输入及预处理,#,include ,#include ,void pro_process(char *);,void main( )/,测试驱动程序,/定义扫描缓冲区,char buf4048=0; /,缓冲区清0,/调用预处理程序,pro_process(buf);,/,在屏幕上显示扫描缓冲区的内容,coutbuf=A & cur_c=Z)/,大写变小写,cur_c+=32;,if(cur_c =t | cur_c =n)/,空格取代,TAB,换行,cur_c= ;,bufi+=cur_c ;,break;,case true:,if(old_c=* & cur_c=/) /,离开注释,in_comment=false;,/end of switch,old_c= cur_c; /,保留前一个字符,/,end of while,2.1 词法分析器的设计考虑及手工构造,数据说明,source.txt（,源程序文件）,char buf（,扫描缓冲区）,bool in_comment（,状态标志）,若,in_comment,的值为,false，,表示当前从文件读入的字符未处于注释中，此时应将读入的字符存入扫描区；若,in_comment,的值为,ture，,则表示当前读入的字符处于注释中，此时读入的字符应丢弃。,XXXXX/*XXXXX*/XXXXX,f .f/t. t/f f,当读入“/*”时，布尔变量,in_comment,的值由,false,变为,true；,当读入“*/”时，布尔变量,in_comment,的值由,ture,变为,false。,2.1 词法分析器的设计考虑及手工构造,上机练习,用高级语言编写一词法分析预处理程序。从文件读入源程序，去除源程序中的注释（注释用标记），用空格取代源程序中的,Tab,和换行符，将预处理结果显示在屏幕上。源程序中无续行符，字母无须处理，源程序尾部需要添加字符。,2.1 词法分析器的设计考虑及手工构造,2.1.3,基本字的识别和超前搜索,程序设计语言单词以基本字识别最为困难，原因如下：,有些语言对基本字不加保护，用户可用作普通标识符。,基本字、用户定义的标识符和常数之间没有分隔符。,2.1 词法分析器的设计考虑及手工构造,解决办法：,所有基本字均为保留字,(,Reserved word),，,用户不得使用它们作为标识符。,将空格、,TAB,和换行符视为界符。在基本字、用户定义的标识符和常数之间，若没有运算符或界符，则至少用一个空格（或,TAB,、,换行符）加以分隔。,2.1 词法分析器的设计考虑及手工构造,遍的基本概念,由外存获得前一遍的工作结果，完成后把结果存于外设。,遍引入的历史背景,早期内存较小，编译程序相对较大,遍和编译程序的结构,1.一遍工作后，内存大部分释放，下一遍后，可以使用全部存储空间,2.使得编译程序的逻辑结构比较清晰,3.但增加了输入输出所耗费时间,2.1 词法分析器的设计考虑及手工构造,2.1.5 状态转换图和词法分析器的手工构造,引入状态转换图的必要性,程序设计语言的无符号实型常数有三种书写形式：,无小数部分形式：134,无整数部分形式：.12,完全形式：3.14,直接编写识别程序有难度，使用状态转换图是构造单词识别程序的好途径。,2.1 词法分析器的设计考虑及手工构造,状态转换图基本概念及应用,状态转换图是一个有向图。,在状态转换图中，结点代表状态，用圆圈表示。,状态之间用箭弧连接,箭弧上的标记代表在射出结点状态下可能出现的合法的输入字符,2.1 词法分析器的设计考虑及手工构造,例,1,，识别标识符的状态转换图如下所示：,2.1 词法分析器的设计考虑及手工构造,例,2,，识别实常数和整常数的状态转换图,2.1 词法分析器的设计考虑及手工构造,例,3,，识别,#,、,+,和,+,的状态转换图,2.1 词法分析器的设计考虑及手工构造,利用状态转换图识别单词,状态转换图每次只能识别一个单词，若源程序中有,N,个单词，则需使用状态转换图,N,次。设源程序为,x+y#,（,#,是预处理程序添加的），单词识别程序（扫描器）共使用状态转换图,5,次。,2.1 词法分析器的设计考虑及手工构造,1.,从初态,0,出发，读入,x,进入状态,1,，在状态,1,读入,+,，进入终态,2,，识别出标识符,x,，,退回,+,；,2.,从初态,0,出发，读入,+,进入状态,10,，在状态,10,读入,+,，进入终态,11,，识别出运算符,+,；,2.1 词法分析器的设计考虑及手工构造,3.,从初态,0,出发，读入,+,进入状态,10,，在状态,10,读入,y,，,进入终态,12,，识别出运算符,+,，退回,y,；,4.,从初态,0,出发，读入,y,进入状态,1,，在状态,1,读入,#,，进入终态,2,，识别出标识符,y,，,退回,#,；,2.1 词法分析器的设计考虑及手工构造,5.从初态,0,出发，读入,#,进入状态,13,，识别出单词,“#”,，识别出单词,“#”,意味着整个源程序中字符处理完毕。,为什么在,C,语言中,x+y,解释为(,x+)+y,2.1 词法分析器的设计考虑及手工构造,根据状态转换图编制程序,（见“,识别标识符的状态转换图编制的扫描程序”,WORD,文件）,2.1 词法分析器的设计考虑及手工构造,词法分析器手工构造实例,1.字符集,a.z,0.9,+ = *,，； （ ） #,发现集合以外的字符，即非法字符，应终止词法分析器,2.1 词法分析器的设计考虑及手工构造,词法分析器手工构造实例,2.单词集,基本字：,begin,end,integer,real,标识符：以字母开始的数字字母串,无符号整常数,无符号实常数,运算符 + * + =,界符 ， ； （ ） #,错误形式 . 前后无数字字符的小数点,出现错误形式，终止词法分析器运行,2.1 词法分析器的设计考虑及手工构造,词法分析器手工构造实例,3.单词编码,基本字：,begin(,NUL),end(,NUL),integer(a,NUL),real(c,NUL),标识符,(,i,字符串) 无符号整常数(,x,字符串,),无符号实常数(,y,字符串,),运算符 +(+,NUL) *(*,NUL) +($,NUL) =(=,NUL),界符 , (,NUL),; (;,NUL),( (,NUL),) (),NUL),# (#,NUL),2.1 词法分析器的设计考虑及手工构造,词法分析器手工构造实例,4.状态转换图,对单字符单词可以不画状态转换图，,多字符单词需要画出状态转换图,2.1 词法分析器的设计考虑及手工构造,词法分析器手工构造实例,5.程序实现,词法分析器由5个函数构成：,主函数,main,预处理函数,pro_process,扫描函数,scanner,拼接函数,concat,查基本字表函数,reserve,2.1 词法分析器的设计考虑及手工构造,主函数先调用预处理函数进行预处理，然后不断调用扫描函数，获得单词二元式编码，然后将输出到文件Lex_r.txt，直到源程序全部处理完成。,2.1 词法分析器的设计考虑及手工构造,void main(),char buf4048=0;/,扫描缓冲区,pro_process(buf);,/预处理,coutbufendl; /,显示,buf,ofstream coutf(Lex_r.txt,ios:out); /,单词识别,code_val t;/,临时变量,dot=scanner(buf);/,调用一次扫描器获得一个单词二元式,coutt.codett.valendl;/,屏幕显示单词二元式,coutft.codett.valendl;/,单词二元式输出至文件,while(t.code!=#);,coutEnd of lexical analysis!0,2.2正规式、自动机及词法分析器的自动生成,6.符号串集合的闭包运算：设,A,是符号串集合，定义,A, A,1, A,2, A,3, A,n,称为集合,A,的,正闭包,。,A,*, A,0,A,称为集合,A,的,闭包,。,例：,A=x,y,A,？,A,*, ？,x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy, ,A,1,A,2,A,3,x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy, ,A,0,A,1,A,2,A,3,2.2正规式、自动机及词法分析器的自动生成,为什么对符号、符号串、符号串集合以及它们的运算感兴趣？,若,A,为某语言的基本字符集,Aa,b,z,0,1,9, +,_/, ( , ), =,B,为单词集,B =begin, end, if, then,else,for,则,B,A,*,。,语言的句子是定义在,B,上的符号串。,若令,C,为句子集合，则,C,B,*,程序,C,2.2正规式、自动机及词法分析器的自动生成,2.2.2,正规式与正规集,正规式和正规集的定义：,l,和,是上的正规式，相应的正规集为,、,。,l,若,a,，,则,a,是正规式，相应正规集为,a,。,l,若,、,为正规式，相应正规集分别记为,L(),和,L(),，,则,|,是正规式，其相应正规集记为,L(|),，,且令,L(|)=L(),L(),2.2正规式、自动机及词法分析器的自动生成,l,若,、,为正规式，相应正规集分别记为,L(),和,L()，,则,(,或,),是正规式，其相应正规集记为,L()，,且令,L()=L()L()。,正规式,自身的,n,次积,是正规式，记为,n,，,其相应正规集记为,L(,n,)，,显然,L(,n,)= L(),n,。,l,若,为正规式，相应正规集记为,L()，,则,*= ,0,|,1,|,2,|,n,是正规式，规定,0,=，,其相应正规集记为,L(*)，,且令,L(*) =L() *。,l,*,，,可用园括号改变运算顺序。,2.2正规式、自动机及词法分析器的自动生成,正规式有3个运算符：,|或，,连接，*闭包。,优先级依次为：*，,，|。,连接可以省略。,2.2正规式、自动机及词法分析器的自动生成,为什么要定义所谓的正规集和正规式,有穷字母表是程序设计语言所使用的字符集的抽象,正规集是程序设计语言单词集的抽象,正规式是程序设计语言构词规则的抽象,词法分析器自动构造的输入正是描述单词的正规式,Abcdef,dog,godn:dog,god,2.2正规式、自动机及词法分析器的自动生成,正规式相等原理,二个正规式是相等的，当且仅当二个正规式所表示的正规集是相等的。,2.2正规式、自动机及词法分析器的自动生成,正规式满足下列关系,交换律：,| = |,结合律：,|,(,|,),=,(,|,),|,，,(,),=,(,),分配律：,(,|,),= |,，,(|,), = |, = ,= ,2.2正规式、自动机及词法分析器的自动生成,正规式,，,其中,=a|b|z, =0|1|9,1.(| ),*,2.,*,3.,*,. ,*,.,*,*,. ,*(E|e)(+|-| ),. ,*,.,*(E|e)(+|-| ),. ,*,*,(E|e)(+|-| ),. ,*,4.(0|1)(0|1) *,标识符,无符号整常数,无符号实常数,二进制数,2.2正规式、自动机及词法分析器的自动生成,2.2.3 确定有限自动机（,DFA）,形式化状态转换图,DFA,定义,一个确定有限自动机,M,是一个五元式,M = ( S,，,f,，,s,0,，,Z ),l,S,是一个有限集，它的每一个元素称为状态。,l,是一个有穷字母表，它的每个元素称为一个输入字符。,l,f,是一个从,S,至,S,的映照，即，,f：SS（,单值函数）,有限自动机：一种识别器，准确识别正规集，是词法分析器自动构造所需要的特殊方法和工具。,2.2正规式、自动机及词法分析器的自动生成,例,f (s,i,a) = s,j,，,表示当现行状态为,s,i,，,若输入字符为,a,，,则转移到下一状态,s,j,，,s,j,称为,s,i,的后继状态。,l,s,0,S,，,是唯一的一个初态。,l,Z,S，,是一个,终态集,。,2.2正规式、自动机及词法分析器的自动生成,状态转换矩阵,函数,f,可以使用矩阵表示，行表示状态，列表示输入字符，矩阵元素表示下一个状态。,只要对初态和终态做标记，就可以用一个状态转换矩阵来表示,DFA,2.2正规式、自动机及词法分析器的自动生成,DFA M,也可用一个（确定的）状态转换图表示,假定,DFA M,含有,m,个状态和,n,个输入字符，那这个图含有,m,个状态结，每个状态结最多有,n,条箭弧射出和其他状态相连接，包括该状态本身。每条弧用,中的一个不同输入字符做标记，整个图含有唯一一个初态和若干个终态。,2.2正规式、自动机及词法分析器的自动生成,字,可为,DFA M,识别,对于一个字,，,如果存在一条从初态结到某一终态结的路径，且路径上的所有弧的标记按照顺序连接成的字为,，,则称,可为,DFA M,识别或接受。,若,DFA M,的初态结同时又是终态结，则称空字,可为,DFA M,所识别或接受。,DFA M,所识别的字的全体称为,L（M）,2.2正规式、自动机及词法分析器的自动生成,DFA,的确定性,表现在映射,SS,是一个单值函数。即对任何状态,s,S,和输入符号,a,，,f(s,a),唯一确定下一个状态。,从状态转换图来看，假定字母表,含有,n,个输入字符，那么一个状态最多只有,n,条弧射出，并且每条弧以不同的输入字符为标记。,2.2正规式、自动机及词法分析器的自动生成,2.2.4 非确定有限自动机（,NFA）,f,是一个多值函数，得到,NFA,定义,一个非确定的有限自动机,M,是一个五元式,M=,（,S,，,f,，,S,0,，,Z,）,l,S,是一个有限集，它的每一个元素称为状态。,l,是一个有穷字母表，它的每个元素称为一个输入字符。,2.2正规式、自动机及词法分析器的自动生成,l,f,是一个从,S,*,到,S,的子集影射，即，,f,：,S,*,2,S,（,多值函数）,2,S,表示幂集，若,S=0,，,1,，,则,2,S,=,，,0,，,1,，,0,，,1,。,l,S,0,S,，,是一个非空初态集，即,NFA,的初态不一定唯一。,l,Z,S，,是一个,终态集,。,2.2正规式、自动机及词法分析器的自动生成,NFA M,可用一个（非确定的）状态转换图表示,一个含有,m,个状态和,n,个输入字符的,NFA,可唯一表示成一个,（非确定的）状态转换图，,这个图含有,m,个状态结，每个结可射出若干个箭弧与别的结相连接，每条弧用,*,中的一个字做标记（输入字），不一定要不同的字，还可以是空字,。,一个,DFA,可以含有多个初态结，初态结同时也可以是终态结。,2.2正规式、自动机及词法分析器的自动生成,字,可为,NFA M,识别,对于,*,中一个字,，,如果,NFA M,中存在一条从某一初态到某一终态的路径，且路径上的所有弧的标记按照顺序连接成的字为,，,则称,可为,NFA M,识别或接受。,若,M,的某些结既是初态结同时又是终态结，或者存在一条从某个初态结到某个终态结的,道路，则称空字,可为,M,所识别或接受。,NFA M,所识别的字的全体称为,L（M）,2.2正规式、自动机及词法分析器的自动生成,DFA,是,NFA,的特例,对于任何两个有限自动机,M,和,M，,如果,L（M）=L（M），,那么称两个有限自动机,M,和,M,等价。,对于每个,NFA M,存在一个,DFA M，,使得,L（M）=L（M）,2.2正规式、自动机及词法分析器的自动生成,2.2.5,NFA,的确定化,设,I,是,NFAM,状态集的一个子集，定义状态集,-CLOSURE（I）,为：,（1）若状态,s I,则,s -CLOSURE（I）,（2）若状态,s I,则从状态,s,出发，经一条或多条,弧所能到达的状态,s,也属于,-CLOSURE（I）,-CLOSURE（I）,称为,I,的,闭包。,2.2正规式、自动机及词法分析器的自动生成,NFA,DFA,I,的,闭包,I,a,NFA,确定化算法,2.2正规式、自动机及词法分析器的自动生成,2.2.6 正规式的,NFA,表示,把正规式,表示成转换图的形式，然后通过加新结的方法对,分裂，直到每条弧的标记为,上的一个字符或,。,V,NFA,将,V,表示成拓广,NFA,根据三条规则对,V,进行分裂，直至每条弧上的标记为,上的一个字符或,。,2.2正规式、自动机及词法分析器的自动生成,2.2.7正规式与确定有限自动机的等价性,对于,上的每个正规式,V,，,存在一个,上的确定有限自动机,M,，,便得,L(V)=L(M),。,2.3,词法分析器的自动生成,输入正规式（构词规则），经自动生成器加工，其结果为,DFA,。,2.3,词法分析器的自动生成,2.3,词法分析器的自动生成,自动生成过程概述,构造描述每个单词的正规式,P,i,(1,i,N),。,根据正规式,P,i,构造,NFA M,i,(1,i,N),，,假定初态均为,0,。在构造,NFA M,i,的同时，逐步并且最终形成识别全部单词的,NFA M,。,NFA M,确定化,重新标记，构造,DFA M,。,2.3,词法分析器的自动生成,利用上述原理，构造一个识别简单程序设计语言单词的,DFA。,2.3,词法分析器的自动生成,扫描器控制程序工作原理,扫描器控制程序的实现,上机练习,