资源描述：
《第2章词法分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第2章词法分析2.1词法分析器设计方法2.2一个简单的词法分析器示例2.3正规表达式与有限自动机简介2.4正规表达式到有限自动机的构造2.5词法分析器的自动生成词法分析的任务:从左至右逐个字符地对源程序进行扫描,产生一个个单词符号,把字符串形式的源程序改造成为单词符号串形式的中间程序。词法分析程序也叫词法分析器或扫描器。其功能是输入源程序,输出单词符号。词法分析可采用如下两种处理结构：(1)把词法分析程序作为主程序。将词法分析作为独立的一遍来完成。字符串形式的源程序字符词法分析器符号表单词符号串程序单词(2)把词法分析程序作为语法分析程序调用的子程
2、序。进行语法分析时,每当需要一个单词时便调用词法分析程序。字符串形式的源程序字符词法分析器语法分析器符号表单词取下一单词2.1词法分析器设计方法2.1.1单词符号的分类与输出形式1.单词符号分类单词符号是程序语言的基本语法单位。程序语言的单词符号通常分为五种：(1)保留字：如if、while(2)标识符：标记常量、变量、函数等的名字(3)常数：如实型0.618、布尔型TRUE(4)运算符：如+、-、*、/、>、<(5)界符：分界符，如,、;、(、)注意：保留字、运算符和界符的个数确定，标识符和常数的个数不确定。2.单词符号的输出形式(单词种别,单词
3、自身的值)(1)单词种别:单词种别表示单词的种类。一个语言的单词符号如何分类、分为几类、如何编码主要取决于处理上的方便。通常，每种单词对应一个整数码。保留字：可全体视为一种，也可一字一种；标识符：统归为一种；常数：统归为一种,或按整、实、布尔等再分；运算符和界符：一符一种，或统归为一种。(2)单词自身的值单词自身的值是编译其它阶段需要的信息。对于单词符号,若一个种别只含一个单词,则其种别编码就代表它自身的值。若一个种别含多个单词,则除种别编码外,还应给出单词自身的值,以便把同一种类的单词区别开来。注意：标识符自身的值是标识符自身的字符串,常数自身的
4、值是常数本身的二进制数值。此外,也可用指向某类表格中一特定项目的指针来区分同类中的不同单词。例如,对于标识符,可用它在符号表的入口指针作为自身的值;常数可用它在常数表的入口指针作为自身的值。2.1.2状态转换图词法分析中,可用状态转换图识别单词。状态转换图中,结点代表状态；结点之间由有向边连接，有向边上可标记字符。如图,状态i下,若输入字符为x,则读入x并转到状态j;若输入字符为y,则读入y并转到状态k。jkixy状态转换图中状态的数目是有限的，其中必有一个初态和若干个终态，终态结点用双圈表示。识别标识符的状态转换图如下：0122(a)字母字母或数
5、字其它*0122(b)数字数字其它*识别无符号整数的状态转换图如下：*0127·2356数字数字数字数字E＋或－数字数字其它数字其它其它E4识别无符号数的状态转换图如下：在状态转换图中,到达单词符号的终态时即给出相应的单词编码。若到达终态时多读入了一个符号,则识别出该单词后再将多读入的那个符号退回。对此类情况的处理方法是在终态上以*作为标识。jki数字字母图2-4不含回路的分支状态对不含回路的分支状态，可让它对应一个switch()语句或一组if-else语句。状态i对应的switch语句如下：s=getchar();switch(s){case'
6、a':…case'z':…;/*实现状态j功能的语句*/case'0':…case'9':…;/*实现状态k功能的语句*/}对于含回路的状态，可让它对应一个while语句。ij字母或数字其它状态i对应的while语句如下：getchar();while(letter()
7、
8、digit())getchar();……;/*实现状态j功能的语句*/状态转换图中的终态一般对应一个return()语句。return意味着从词法分析器返回到调用段，一般指返回到语法分析器。2.2一个简单的词法分析器示例2.2.1C语言子集的单词符号表示大多数程序语言的单词符号都
9、可用状态转换图予以识别。下面构造一个C语言子集的简单词法分析器，该C语言子集的所有单词符号及其种别编码和内码值如下表所示。由于直接使用整数编码不利于记忆，故该例采用一些助记符表示种别编码。表2.1C语言子集的单词符号及内码值单词符号种别编码助记符内码值while1while—if2if—else3else—switch4switch—case5case—标识符6idid在符号表中位置常数7numnum在常数表中位置+8+—−9−—*10*—<=11relopLE<11relopLT==11relopEQ=12=—；13；—2.2.2C语言子集对应的
10、状态转换图的设计首先对输入串做预处理。即剔除多余的空格、注释等。其次把保留字作为一类特殊标识符处理。即对保留字不专设对应的
