编译原理 第2章 词法分析1

第2章词法分析第2章词法分析2.1词法分析器设计方法2.2一个简单的词法分析器示例2.3正规表达式与有限自动机简介2.4正规表达式到有限自动机的构造2.5词法分析器的自动生成第2章词法分析2.1词法分析器设计方法词法分析是编译的第一个阶段，其任务是：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号，把字符串形式的源程序改造成为单词符号串形式的中间程序。执行词法分析的程序称为词法分析程序，也称为词法分析器或扫描器。词法分析器的功能是输入源程序，输出单词符号。第2章词法分析词法分析可以采用如下两种处理结构：(1)把词法分析程序作为主程序。将词法分析工作作为独立的一遍来完成，即把词法分析与语法分析明显分开，由词法分析程序将字符串形式的源程序改造成单词符号串形式的中间程序，以这个中间程序作为语法分析程序的输入。在这种处理结构中，词法分析和语法分析是分别实现的，如图2–1(a)所示。第2章词法分析(2)把词法分析程序作为语法分析程序调用的子程序。在进行语法分析时，每当语法分析程序需要一个单词时便调用词法分析程序，词法分析程序每一次调用便从字符串源程序中识别出一个单词交给语法分析程序。在这种处理结构中，词法分析和语法分析实际上是交替进行的，如图2–1(b)所示。由于把词法分析器安排成一个子程序比较自然，因此，词法分析程序通常采用第二种处理结构。第2章词法分析图2-1词法分析的两种处理结构(a)词法分析程序作为主程序；(b)词法分析程序作为子程序字符串形式的源程序字符词法分析器符号表单词符号串程序单词(a)字符串形式的源程序字符词法分析器语法分析器符号表(b)单词取下一单词第2章词法分析2.1.1单词符号的分类与输出形式1．单词符号分类词法分析程序简单地说就是读单词程序，该程序扫描用高级语言编写的源程序，将源程序中由单词符号组成的字符串分解出一个个单词来。因此，单词符号是程序语言的基本语法单位，具有确定的语法意义。程序语言的单词符号通常可分为下面五种：第2章词法分析(1)保留字(也称基本字)：如C语言中的if、else、while和do等，这些字保留了语言所规定的含义，是编译程序识别各类语法成分的依据。几乎所有程序语言都限制用户使用保留字来作为标识符。(2)标识符：用来标记常量、数组、类型、变量、过程或函数名等，通常由用户自己定义。(3)常数：包括各种类型的常数，如整型常数386、实型常数0.618、布尔型常数TRUE等。第2章词法分析(4)运算符：如“+”、“?”、“*”、“/”、“”、“”等。(5)界符：在语言中是作为语法上的分界符号使用的，如“，”、“；”、“（”、“）”等。一个程序语言的保留字、运算符和界符的个数是确定的，而标识符或常数的使用则不限定个数。第2章词法分析2．词法分析程序输出单词的形式我们知道，词法分析程序的输入是源程序字符串，而输出是与源程序等价的单词符号序列，并且所输出的单词符号通常表示成如下的二元式：（单词种别，单词自身的值）(1)单词种别。单词种别表示单词的种类，它是语法分析所需要的信息。一个语言的单词符号如何划分种类、分为几类、如何编码都属于技术性问题，主要取决于处理上的方便。通常让每种单词对应一个整数码，这样可最大限度地把各个单词区别开来。第2章词法分析对于保留字，可将其全体视为一种，也可一字一种，采用一字一种的分类方法处理起来比较方便；标识符一般统归为一种；常数可统归为一种，也可按整型、实型、布尔型等分为几种；运算符和界符可采用一符一种的分法，也可统归为一种。第2章词法分析(2)单词自身的值。单词自身的值是编译中其它阶段所需要的信息。对于单词符号来说，如果一个种别只含有一个单词符号，那么对于这个单词符号，其种别编码就完全代表了它自身的值。如果一个种别含有多个单词符号，那么对于它的每个单词符号，除了给出种别编码之外还应给出单词符号自身的值，以便把同一种类的单词区别开来。注意，标识符自身的值就是标识符自身的字符串，而常数自身的值是常数本身的二进制数值。此外，我们也可用指向某类表格中一个特定项目的指针来区分同类中的不同单词。例如，对于标识符，可以用它在符号表的入口指针作为它自身的值；而常数也可用它在常数表的入口指针作为它自身的值。第2章词法分析2.1.2状态转换图在词法分析中，可以用状态转换图来识别单词。状态转换图是有限的有向图，结点代表状态，用圆圈表示；结点之间可由有向边连接，有向边上可标记字符。例如，图2-2表示在状态i下，若输入字符为x，则读入x并转换到状态j；若输入字符为y，则读入y并转换到状态k。第2章词法分析图2–2不同输入字符的状态转换jkixyjkixy第2章词法分析状态（即结点）数是有限的，其中必有一初始状态以及若干终止状态，终止状态(终态)的结点用双圈表示以区别于其它状态。图2-3给出了用于识别标识符、无符号整数、无符号数的状态转换图，其初始状态均用0状态表示。第2章词法分析图2-3标识符及无符号数的状态转换图(a)标识符；(b)无符号整数；(c)无符号数0122(a)字母字母或数字其它*0122(b)数字数字其它*0127·2356数字数字数字数字E＋或－数字数字其它*数字其它其它(c)E4第2章词法分析当到达一类单词符号的终止状态时即可给出相应的单词编码。某些终止状态是在读入了一个其它不属于该单词的符号后才得到相应的单词编码的，这表明在识别单词的过程中多读入了一个符号，所以识别出单词后应将最后多读入的这个符号予以回退；我们对此类情况的处理是在终态上以“*”作为标识。第2章词法分析图2-4含有分支或回路的状态示意(a)含分支的状态i；(b)含回路的状态ijkiij数字字母字母或数字其它(a)(b)第2章词法分析对于不含回路的分支状态来说，可以让它对应一个switch()语句或一组if-else语句。例如，图2-4(a)的状态i所对应的switch语句如下：第2章词法分析s=getchar();switch(s){case'a':case'b':…case'z':…;/*实现状态j功能的语句*/case'0':case'1':…case'9':…;/*实现状态k功能的语句*/}第2章词法分析对于含回路的状态来说，可以让它对应一个while语句。例如，图2-4(b)的状态i所对应的while语句如下：getchar();while(letter()||digit())getchar();…;/*实现状态j功能的语句*/终态一般对应一个return()语句；return意味着从词法分析器返回到调用段，一般指返回到语法分析器。第2章词法分析2.2一个简单的词法分析器示例2.2.1C语言子集的单词符号表示一个非常重要的事实是：大多数程序语言的单词符号都可以用状态转换图予以识别。作为一个综合例子，我们来构造一个C语言子集的简单词法分析器。表2.1列出了这个C语言子集的所有单词符号以及它们的种别编码和内码值。由于直接使用整数编码不利于记忆，故该例中用一些特殊符号来表示种别编码。第2章词法分析表2.1C语言子集的单词符号及内码值单词符号种别编码助记符内码值while1while—if2if—else3else—switch4switch—case5case—标识符6idid在符号表中的位置常数7numnum在常数表中的位置+8+—−9−—*10*—=11relopLE11relopLT==11relopEQ=12=—；13；—第2章词法分析2.2.2C语言子集对应的状态转换图在设计的状态转换图中，首先对输入串做预处理，即剔除多余的空白符（在实际的词法分析中，预处理还包括剔除注释和制表换行符等编辑性字符的工作），使词法分析工作既简单又清晰。其次，将保留字作为一类特殊的标识符来处理，也即对保留字不专设对应的状态转换图，当转换图识别出一个标识符时就去查对表2.1的前五项，确定它是否为一个保留字。当然，也可以专设一个保留字表来进行处理。图2–5就是对应表2.1这个简单词法分析的状态转换图。第2章词法分析图2–5简单词法分析的状态转换图01*22开始空白字母字母或数字非字母与数字324数字数字*非数字返回(id,id在符号表中的位置)或返回(保留字,)返回(num,num在常数表中的位置)25＋2627－*82921011212213214215＜＝*其它＝＝其它*；其它*返回(＋,)返回(－,)返回(,)*返回(relop,LE)返回(relop,LT)返回(relop,EQ)返回(＝,)返回(；,)非法字符错第2章词法分析在状态2时，所识别出的标识符应先与表2.1的前五项逐一比较，若匹配，则该标识符是一个保留字，否则就是标识符。如果是标识符，应先查符号表，看表中是否有此标识符。若表中无此标识符，则将它登录到符号表中，然后返回其在符号表中的入口指针（地址）作为该标识符的内码值。在状态4时，应将识别的常数转换成二进制常数并将其登录到常数表，然后返回其在常数表中的入口指针作为该常数的内码值。第2章词法分析2.2.3状态转换图的实现状态转换图非常容易用程序实现，最简单的办法是让每个状态对应一小段程序。对于图2–5的状转换图，我们首先引进一组变量和过程如下：(1)character：字符变量，存放最新读入的源程序字符。(2)token：字符数组，存放构成单词符号的字符串。(3)getbe()：若character中的字符为空白，则调用getchar()，直至character为非空白符为止。第2章词法分析(4)concatenation()：将token中的字符串与character中的字符连接并作为token中新的字符串。(5)letter()和digit()：判断character中的字符是否为字母和数字的布尔函数，是则返回true，否则返回false。(6)reserve()：按token数组中的字符串查表2.1中的前五项(即判别其是否为保留字)，若是保留字则返回它的编码，否则返回0值。第2章词法分析(7)retract()：扫描指针回退一个字符，同时将character置为空白。(8)buildlist()：将标识符登录到符号表或将常数登录到常数表。(9)error()：出现非法字符，显示出错信息。相对于图2-5的词法分析器构造如下：第2章词法分析token='';/*对token数组初始化*/s=getchar();getbe();/*滤除空格*/switch(s){case'a':case'b':…case'z':while(letter()‖digit())第2章词法分析{concatenation();/*将当前读入的字符送入token数组*/getchar();}retract();/*扫描指针回退一个字符*/c=reserve();if(c==0){buildlist();/*将标识符登录到符号表中*/return(id，指向id的符号表入口指针);}第2章词法分析elsereturn(保留字码，null);break;case'0':case'1':…case'9':while(digit()){concatenation();getchar();}retract();第2章词法分析buildlist();/*将常数登录到常数表中*/return(num，num的常数表入口指针);break;case'+':return('+'，null);break;case'?':return('?'，null);break;case'*':return('*'，null);第2章词法分析break;case'':getchar();if(character=='=')return(relop,LE);else{retract();return(relop，LT);}break;case'=':getchar();if(character=='=')第2章词法分析return(relop,EQ);else{retract();return('=',_);}break;case'