第2章词法分析

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第2章 词法分析,2.1 词法分析器设计方法,2.2 一个简单的词法分析器示例,2.3 正规表达式与有限自动机简介,2.4 正规表达式到有限自动机的构造,2.5 词法分析器的自动生成,词法分析的任务,:从左至右逐个字符地对源程序进行扫描,产生一个个单词符号,把字符串形式的源程序改造成为单词符号串形式的中间程序。,词法分析程序也叫词法分析器或扫描器。其功能是输入源程序,输出单词符号。,词法分析可采用如下两种处理结构,：,(1),把词法分析程序作为主程序,。将词法,分析作为独立的一遍来完成。,字符串形式,的源程序,字符,词,法,分,析,器,符号表,单词符号,串程序,单词,(2),把词法分析程序作为语法分析程序调,用的子程序,。进行语法分析时,每当需,要一个单词时便调用词法分析程序。,字符串形式,的源程序,字符,词,法,分,析,器,语,法,分,析,器,符,号,表,单词,取下一单词,2.1 词法分析器设计方法,2.1.1 单词符号的分类与输出形式,1.单词符号分类,单词符号是程序语言的基本语法单位。,程序语言的,单词符号,通常分为五种：,(1),保留字,：如,if、while,(2),标识符,：标记常量、变量、函数等的名字,(3),常数,：如实型0.618、布尔型,TRUE,(4),运算符,：如+、,-,、*、/、,(5),界符,：分界符，如,、;、(、),注意：保留字、运算符和界符的个数确定，,标识符,和,常数,的个数不确定。,2.单词符号的输出形式,(单词种别,单词自身的值),(1),单词种别,:单词种别表示单词的种类。,一个语言的单词符号如何分类、分为几类、如何编码主要取决于处理上的方便。通常，每种单词对应一个整数码。,保留字,：可全体视为一种，也可,一字一种,；,标识符,：统归为一种；,常数,：统归为一种,或按整、实、布尔等再分；,运算符,和,界符,：一符一种，或统归为一种。,(2),单词自身的值,单词自身的值是编译其它阶段需要的信息。,对于单词符号,若一个种别只含一个单词,则其种别编码就代表它自身的值。若一个种别含多个单词,则除种别编码外,还应给出单词自身的值,以便把同一种类的单词区别开来。,注意：标识符自身的值是标识符自身的字符串,常数自身的值是常数本身的,二进制数值,。,此外,也可用指向某类表格中一特定项目的,指针,来区分同类中的不同单词。例如,对于标识符,可用它在,符号表,的入口指针作为自身的值;常数可用它在,常数表,的入口指针作为自身的值。,2.1.2 状态转换图,词法分析中,可用,状态转换图,识别单词。状态转换图中,结点代表状态；结点之间由有向边连接，有向边上可标记字符。,如图,状态,i,下,若输入字符为,x,则读入,x,并转到状态,j;,若输入字符为,y,则读入,y,并转到状态,k。,j,k,i,x,y,状态转换图中状态的数目是有限的，其中必有一个,初态,和若干个,终态,，终态结点用双圈表示。,识别标识符的状态转换图,如下：,0,1,2,2,(,a,),字母,字母或数字,其它,*,0,1,2,2,(,b,),数字,数字,其它,*,识别无符号整数的状态转换图,如下：,*,0,1,2,7,2,3,5,6,数字,数字,数字,数字,E,或,数字,数字,其它,数字,其它,其它,E,4,识别无符号数的状态转换图如下：,在状态转换图中,到达单词符号的终态时即给出相应的单词编码。,若到达终态时多读入了一个符号,则识别出该单词后再将多读入的那个符号退回。对此类情况的处理方法是在终态上以*作为标识。,j,k,i,数字,字母,图2-4,不含回路的分支状态,对不含回路的分支状态，可让它对应一个,switch(),语句或一组,if-else,语句。,状态,i,对应的,switch,语句如下：,s=,getchar,();,switch(s),case a:,case z:,;,/*,实现状态,j,功能的语句*/,case 0:,case 9:,;,/*,实现状态,k,功能的语句*/,对于含回路的状态，可让它对应一个,while,语句。,i,j,字母或数字,其它,状态,i,对应的,while,语句如下：,getchar,();,while(letter()|digit(),getchar,();,;,/*,实现状态,j,功能的语句*/,状态转换图中的,终态,一般对应一个,return(),语句。,return,意味着从词法分析器返回到调用段，一般指返回到语法分析器。,2.2 一个简单的词法分析器示例,2.2.1,C,语言子集的单词符号表示,大多数程序语言的单词符号都可用状态转换图予以识别。下面构造一个,C,语言子集的简单词法分析器，该,C,语言子集的所有,单词符号,及其,种别编码,和,内码值,如下表所示。由于直接使用整数编码不利于记忆，故该例采用一些助记符表示种别编码。,表2.1,C,语言子集的单词符号及内码值,单词符号,种别编码,助记符,内码值,while,1,while,if,2,if,else,3,else,switch,4,switch,case,5,case,标识符,6,id,id,在符号表中位置,常数,7,num,num,在常数表中位置,+,8,+,9,*,10,*,=,11,relop,LE,11,relop,LT,=,11,relop,EQ,=,12,=,；,13,；,2.2.2,C,语言子集对应的状态转换图的设计,首先,对输入串做预处理。,即剔除多余的空格、注释等。,其次,把保留字作为一类特殊标识符处理。,即对保留字不专设对应的状态转换图，,当状态转换图识别出一个标识符时就,去查表，确定它是否为一个保留字。,C,语言子集对应的状态转换图,如下：,0,1,*,2,开始,空白,字母,字母或数字,非字母数字,3,4,数字,数字,*,非数字,返回(,id,id,在符号表中位置),或返回(保留字,-),返回(,num,num,在常数表中位置),5,6,7,*,8,9,10,11,12,13,14,15,*,其它,其它,*,；,其它,*,返回(+,-),返回(,-),返回(*,-),返回(,relop,LE),返回(,relop,LT),返回(,relop,EQ),返回(,-),返回(;,-),非法字符错,注意,:,(1)状态2识别出一个单词符号后需先查保留字表,若匹配则为保留字,否则为标识符。若为标识符,还需查符号表,看表中是否有此标识符。若符号表中无此标识符,则先将它登录到符号表中,再返回它在符号表中入口地址作为,内码值,;若表中有此标识符,则直接返回其入口地址作为,内码值,。,(2)状态4识别出一个常数后需先将它转换成,二进制常数,再登录到常数表,然后返回它在常数表中的入口指针作为,内码值,。,2.2.3 状态转换图的实现,状态转换图易于用程序实现,最简单的办法是,让每个状态对应一小段程序,。对图25,首先引进一组变量和过程：,(1),character,:,字符变量,存放最新读入,的源程序字符。,(2),token,:,字符数组,存放构成单词符号,的字符串。,(3),getbe,(),:,若,character,中字符为空,则,调用,getchar,(),直至,character,为非空。,(4),concatenation,():,将,token,中字符串与,character,中字符,连接,作为,token,中的新,字符串。,(5),letter(),和,digit():,判断,character,中的字,符是否为字母和数字的布尔函数,若是,则返回,true,否则返回,false。,(6)reserve():,按,token,数组中的字符串查,保留字表,若是保留字则返回其编码,否则返回0。,(7),retract():,扫描指针回退一个字符,同,时将,character,置为空白。,(8),buildlist,():,将标识符登录到符号表或,将常数登录到常数表。,(9),error():,进行出错处理。,C,语言子集对应的的词法分析器如下:,token=;,/*,对,token,数组初始化*/,s=,getchar,();,getbe,();,/*,滤除空格*/,switch(s),case a:,case z:,while(letter()digit(),concatenation();,/*,将当前读入,的字符送入,token,数组*/,getchar,();,retract();,/*,扫描指针回退一个字符*/,c=reserve();,if(c=0),buildlist,();,/*,将标识符登录到符号表*/,return,(id,id,在符号表中的入口指针),;,else return(,保留字码,null);,break;,case 0:,case 1:,case 9:,while(digit(),concatenation();,getchar,();,retract();,buildlist,();,/*,将,常数,登录到常数表中*/,return,(num,num,的常数表入口指针),;,break;,case+:return(+，null);break;,case-:return(-，null);break;,case*:return(*，null);break;,case,上的一个,字,指的是由,中字符构成的,一个有穷序列;,不包含任何字符的序列称为,空字,。,*,表示,上所有字的全体,包括空字,。,例如,若,=a,b,则,*,=,a,b,aa,ab,ba,bb,aaa,2,表示不含任何元素的空集。,注意,、,和,的区别,：,表示不包含任何字符的序列,它是正规集中的一个元素；表示不含任何字的集合,它是一个空的正规集；,表示由空字组成的集合。,3使用括号可改变运算符的运算次序。,若规定*优先于,优先于|,则在不混淆情况下,可省去括号。,4,*,的正规式,R,和,S,的,连接,可形式化为,RS=,|,R&,S,例如,R=a,b，S=1,2，,RS=a1,a2,b1,b2,5 R,自身的,n,次连接记为,R,n,=RR,R,6,R,0,=,R,*,=R,0,R,1,R,2,R,3,R,*,为,R,的闭包,R,+,=RR,*,称,R,+,是,R,的正闭包。,闭包,R,*,中的每个字都是由,R,中的字经过有限次连接而成的。,对于正规式,R,和,S,若它们表示的正规集,L(R)=L(S),则称,R,和,S,等价,记为,R=S。,正规式具有下列性质,：,(1)交换律：,R|S=S|R,(2),结合律：,R|(S|T)=(R|S)|T,R(ST)=(RS)T,(3),分配律：,R(S|T)=RS|RT,(R|S)T=RT|ST,(4),同一律：,R=R=R,例2.1,=a,b,R=a(a,|,b)*,是,上正规式,试求,R,表示的正规集。,解:,L(R)=L(a(a,|,b)*)=L(a)L(a,|,b)*),=L(a)(L(a,|,b)*=L(a)(L(a)L(b)*,=a(ab)*=aa,b*,=a,a,b,aa,ab,ba,bb,aaa,=a,aa,ab,aaa,aab,aba,abb,aaaa,例2.2,判断下述正规式之间是否等价：,(1)(,a|b)*,与,a*|b*(2)(,ab,)*,与,a*b*,(3)(a|b)*,与(,a*b*)*,解:(1)(,a|b)*,对应的正规集其,a,b,可任意交替出现,如,abbaaab,而(,a*|b*),对应的正规集只可出现任意个,a,或任意个,b,因此两者不等价。,(2)(,ab,)*,对应的正规集以任意个,ab,对出现，即,ababab,而,a*b*,对应的正规集则是任意个,a,后接任意个,b,即,a,ab,b,因此两者不等价。,(3)(,a|b)*,对应的正规集其,a,b,可任意交替出现,如,aababbb,而(,a*b*)*,可采用如下方法得到相应的字,