编译原理2词法分析.

1内容提要:状态转换图正规式与有限制动机词法分析器的自动生成词法分析器源程序单词序列2第一节状态转换图一单词分类及表示编译中,把高级语言的单词分为五类:标识符,基本字,常数,运算符,界符基本字,运算符,界符都是有限可枚举的;而标识符,常数可认为是无限的.简单起见,单词可表示为如下二元组:(单词分类号,单词自身值);或者为:(单词种别码,单词自身值);标识符,常数各为一个种别码,而由于基本字,运算符,界符的有限性,可以设计为一字一个种别码.3例如:单词单词种别码分类号标识符11常数22if33then43end903,914;924=1515+1525保留字界符运算符4二词法分析器的设计1源程序的预处理子程序源程序中,存在许多编辑用的符号,它们对程序逻辑功能无任何影响.例如:回车,换行,多余空白符,注释行等.在词法分析之前,首先要剔除掉这些符号,使得词法分析更为简单.源程序输入缓冲区预处理子程序扫描缓冲区2扫描缓冲区1缓冲区分为两部分,每个长度为256字节,这样单词的总长度可达到256字节.预处理子程序把处理好的字符串轮流放入两个缓冲区中,供词法分析程序使用.52词法分析程序词法分析程序又称为词法分析器或扫描器.可以单独为一个程序;也可以作为整个编译程序的一个子程序,当需要一个单词时,就调用词法分析子程序返回一个单词.这里,作为子程序介绍.词法分析器的结构:源程序输入缓冲区预处理子程序扫描缓冲区2扫描缓冲区1词法分析子程序调用返回一单词63词法规则的表示--------状态转换图定义:状态转换图是一有向图,由有限个结点及有向边连接而成;每个结点称为状态;状态图有一个初态,多个终态;每条边上有相应的字符.状态转换图用于表示单词结构,从状态转换图的初态到终态间,每条路径上字符的连接,就构成了该状态图的合法单词.例如:012初态终态字母字母数字其它*1标识符的状态图表示:星号表示单词尾部多跟一个字符,应该去掉.7012初态终态数字数字其它*2整数的状态图表示:016初态终态数字数字其它*3实数的状态图表示:23456数字数字E+或—数字E其它数字84单词的识别状态图即可以表示单词规则,同时也可以用于识别单词.设有一字符串S=s1s2......sn,若状态图中存在一初态到终态的路径,且路径上字符的连接为:s1s2......sn,称S可被状态图识别.例如:S=‘var1’012初态终态var1其它*保留字由于满足标识符定义,因此可以跟标识符用同样的状态图表示与识别,只需增加一个保留字表,当识别出一个标识符时,通过查保留字表来区别保留字及普通标识符.因此var1是一个合法的标识符.95一个简单示例构造一个简单语言所有单词的状态转换图.该语言的单词种类如下表所示:单词符号种别码助记符内码值DIMIFDOSTOPEND标识符正常数=+***,()1234567891011121314$DIM$IF$DO$STOP$END$ID$INT$ASSIGN$PLUS$STAR$POWER$COMMA$LPAR$RPAR(1,)(2,)(3,)(4,)(5,)(6,串值)(7,数值)(8,)(9,)(10,)(11,)(12,)(13,)(14,)10012初态终态字母字母数字其它*空白34终态数字数字非数字*5=6+7*98**非**10,11(12)13其它116状态转换图的程序实现为便于程序实现,假设每个单词间都有界符或运算符或空格隔开,并引入下面的全局变量及子程序:1)CHAR字符变量2)TOKEN单词字符串3)GETCHAR读一个字符到CHAR中4)GETBC读一个非空白字符到CHAR中5)CONCAT把CHAR中字符连接到TOKEN之后6)LETTER判断CHAR中字符是否为字母7)DIGIT判断CHAR中字符是否为数字8)RESERVE用TOKEN中的字符串查找保留字表,并返回保留字种别码,若返回零,则非保留字9)RETRACT把CHAR中字符回送到缓冲区12下面分析状态图的结构特点.每个状态图都由三种结构构成:分支结构循环结构终结点1分支结构程序设计ii2i1inc1c2cnstatei:GETCHAR;CASECHAROFc1:CONCAT；statei1:.......c2:CONCAT；statei2:.......cn:CONCAT；statein:.......ELSEERROREND;132循环结构程序设计ijC其它statei:GETCHAR;WHILECHAR=CDO{CONCAT;GETCHAR};RETRACT；statej:..........3终结点程序设计一般对应一条返回语句:return(c,val);c为种别码,val为单词值.带*号的终结点,必须用RETRACT退还多余字符下面程序为简单示例语言的实现:14TYPEWORDTYPE=RECORDC：INTEGER；VAL：CHAR；END；FUNCTIONRETURN_WORD():WORDTYPE;{STATE0:TOKEN:=‘’;GETCHAR;GETBC;CASECHAROF‘A’..’Z’:{CONCAT;STATE1:GETCHAR;WHILE(LETTERORDIGIT)DO{CONCAT;GETCHAR};RETRACT；STATE2:C:=RESERVE;IFC=0THENRETURN($ID,TOKEN)ELSERETURN(C,__)}15‘0’..’9’:{CONCAT;STATE3:GETCHAR;WHILE(DIGIT)DO{CONCAT;GETCHAR};RETRACT；STATE4:RETURN($INT,TOKEN);}‘=’:{STATE5:RETURN($ASSIGN,__);}‘+’:{STATE6:RETURN($PLUS,__);}‘*’:{STATE7:GETCHAR;STATE9:IFCHAR=‘*’THENRETURN($POWER,__);STATE8:RETRACT;RETURN($STAR,__);}‘,’:{STATE10:RETURN($COMMA,__);}‘(’:{STATE11:RETURN($LPAR,__);}‘)’:{STATE12:RETURN($RPAR,__);}ELSE{STATE13:ERROR}}16这节介绍词法规则的形式表示(正规式),从正规式向有限自动机的转化.正规式有限自动机词法分析器控制程序自动生成器转化合成第二节正规式与有限自动机17一基本概念定义1字与字集假设:∑是一有穷字符集,它的每个元素称为一个字符;字------∑上的一个字,是由∑中的字符所构成的一个有穷序列;空串------不包含任何元素的序列称为空串,记为ε;闭包∑*---------∑上所有可能的字的全体;空字集-------不含任何字的集合称为空字集;记为φ={};例如:∑={a,b}则∑*={ε,a,b,aa,ab,ba,bb.......}注意:ε,φ,{ε}三者间的关系定义2连接运算设U,V∑*则UV={αβ|α∈U,β∈V}一般UV≠VUVn=VV.........V称为V的n次积18例如:设U={a,aa},V={b}则UV={ab,aab}VU={ba,baa}定义3V的闭包设V为字集,且V0={ε}令V*=V0∪V1∪V2∪........V+=V*-{ε}称V*为V的闭包称V+为V的正则闭包注意:∑*与V*的区别.19二正规式与正规集∑*是一个无穷集,在程序语言中,我们只研究满足词法规则(正规式)的单词集(正规集).定义1正规式与正规集的递归定义:1)ε,φ是∑上的正规式,所表示的正规集为{ε},{};2)若a∈∑,则a为正规式,所表示的正规集为{a};3)设U,V为∑上的正规式,所表示的正规集为L(U),L(V);则U|V为∑上的正规式,所表示的正规集为L(U)∪L(V);UV为∑上的正规式,所表示的正规集为L(U)L(V);V*为∑上的正规式,所表示的正规集为L(V)*;4)仅当有限次使用上述三步骤而定义的表达式,才是∑上的正规式,而这些正规式所表示的字集才是∑上的正规集.20示例:令∑={A..Z,0..9}则整数的正规式为:(0|1|2......|9)(0|1|2......|9)*所表示的正规集为所有整数;标识符的正规式为:(A|B|......Z)(A|B|......Z|0|1|......|9)*所表示的正规集为所有标识符定义2若两个正规式U,V所表示的正规集相同,即L(V)=L(U),则称两个正规式等价,记为U=V.正规式的运算:设UVW为正规式,则满足以下关系:1)U|V=V|U2)U|(V|W)=(U|V)|W3)U(VW)=(UV)W4)U(V|W)=UV|UW(U|V)W=UW|VW5)εU=Uε=U21三确定有限自动机一个确定有限自动机(DFAM)是一个五元式:DFAM=(S,∑,f,s0,Z)其中S是一有限集,每个元素称为一个状态;∑是一个有穷字母表,每个元素为一字符;f是一个单值映射函数,f(si,a)=sj(si,sj∈S,a∈∑);其含义为:在状态si,输入字符a时,将转换到下一状态sj.称sj为si的后继状态.s0∈S,是唯一的初态;ZS,是终态集.一个DFAM可用状态转换矩阵或状态图表示22例如:DFAM=({0,1,2,3},{a,b},f,0,{3})其中f为:f(0,a)=1f(1,a)=3f(2,a)=1f(3,a)=3f(0,b)=2f(1,b)=2f(2,b)=3f(3,b)=3状态转换矩阵可表示为:状态图可表示为:ab012132213333状态字符013初态终态2abbaaabb23四非确定有限自动机一个非确定有限自动机(NFAM)是一个五元式:NFAM=(S,∑,f,S0,Z)其中S是一有限集,每个元素称为一个状态;∑是一个由穷字母表,每个元素为一字符;f是一个多值映射函数,f(si,α)={si1,si2,.....sik}(si,si1,.....,sik∈S,α∈∑*);其含义为:在状态si,输入字串α时,将转换到下一状态集:{si1,si2,.....sik}S0S,是初态集;ZS,是终态集.一个NFAM也可用状态图表示,此时每条边用字串表示.24例如:01初态终态2aabba,ba,ba,b终态DFAM是NFAM的特例.定义:状态图中,从初态到终态任一路径上的字串连接α,称为该状态图可识别的单词,可识别单词的全体记为:L(M).若L(M)=L(M’),称M与M’等价.25五正规式与有限自动机的等价性前面,介绍了正规式,DFAM,NFAM,下面讨论这三个概念间的关系.定理1:对任意正规式V,存在一个NFAM,使得L(V)=L(NFAM);证明:(1)构造一个拓广转换图显然,该转换图能识别的单词集为:L(V)XYV26(2)进行如下等价变换,直到转换图的每条边上的标志为∑上的字符.ijV1V2ijV1kV2aijV1|V2iV1jV2bijV*ijεkεcV等价变换后的转换图M符合NFAM的定义,显然有L(V)=L(M).该定理说明,从正规式可逐步构造一个NFAM.27定义:设S是一个状态集,ε_CLOSURE(S)定义如下:a)若s∈S,则s∈ε_CLOSURE(S);b)若s∈S,则从s出发经过任意条ε边所能到达的状态s’都属于ε_CLOSURE(S).状态集ε_CLOSURE(S)称为S的ε_闭包.定理2:对任意NFAM,存在一个DFAM,使得L(DFAM)=L(NFAM);证明:(1)对NFAM进行等价变换,使得变换后的转换图NFAM’中仅含ε边和∑上的字符边;(2)用状态转换矩阵M表示NFAM’;28其中,I0为初态集的ε_闭包.Iia=ε_CLOSURE{f(si1,a)∪f(si2,a)∪f(sik,a)}si1,si2,......sik∈Ii(3)将M中的状态集换名,si=Ii得到一新的状态转换矩阵M’,M’满足DFAM的定义.Iabc....