,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Ch3.词法分析,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Ch3.词法分析,*,第,3,章 词法分析,词法分析,(Lexical Analysis),词法的表示,词法分析器的设计与实现,2,本章在编译程序中的地位,表,格,管,理,词法分析器,语法分析器,语义分析与中间代码产生,优化器,目标代码生成器,源程序,单词符号,语法单位,中间代码,中间代码,目标代码,出,错,处,理,主要教学内容,3.1 词法分析器的功能、输出形式和构造,3.2 词法分析程序的设计方法-重点,3.3 正规表达式与有穷状态自动机-重点难点,3.4 词法分析器的自动产生,2024/11/14,Ch3.词法分析,3,4,教学要求,把握：,正规式、状态转换图、有限自动机的概念,将NFA转换为DFA、DFA的化简、,正规式与有限自动机间的转换、,正规文法与有穷自动机间的转换，,词法分析程序的功能和设计方法。,了解理解：,词法分析器的自动产生工具LEX。,词法分析涉及的概念及关系,扫描识别,依据构词规则,源程序(字符串),单词符号串,词法分析程序(扫描器),输入,输出,输入,扫描,(3.2),预处理,超前搜索,单词分类,(3.1),内部表示,手工生成,(3.2),自动生成,(3.3),等价,状态转换图,用程序实现,即扫描器,正规式,正规集,有限自动机,DFA,NFA,自动生成工具,LEX,用正规式描述,扫描器象,FA,一样工作,(3.4),生成,描述,工具,等价,6,3.1 对词法分析器的要求,3.1.1 词法分析器的功能和输出形式,输入源程序，扫描识别,输出单词符号,程序语言的单词符号一般分为五种：,关键字(保存字或根本字)：如 begin,end,if,then,else,while,do等,标识符：用来表示各种名字，如 X1,字面常数：如 256，3.14，true,abc,运算符：如、*、/等等,分界符：如 逗号，分号，冒号等,7,while ij do,if ij then i:ij else j:=ji;,例,词法分析器,输入,输出,while i j do,if i j then i :=i j,else j :=j i,;,3.1.1 词法分析扫描器的功能,功能：,读源程序，产生记号序列,剥去源程序中的注释块、行和“空白”符,预处理宏处理与文件包含,单词符号的形式,依据最小的语义单位设计,通常表示为二元组：,单词符号种别，属性值,关键找出符号的分割符,1),单词符号的表示,常用单词符号种别分类P42,各关键字保存字、根本字，各种运算符，各种分界符各用一个种别码标识,其它标识符用一个种别码标识,常数用一个种别码标识,属性值单词符号的值,常数的值，标识符的名字等,保存字、运算符、分界符的属性值可以省略,单词的机内表示,编译器使用二元式标识特定的标识符：,又称种别码,单词值,单词值,关键字和分界符假设承受一字和一符一种编码时，单词值无意义；如果一类一种编码，单词值可取整数的内部编码或自身的符号串表示。标识符的单词值可取单词符号本身；常数的单词值通常取二进制表示。,2024/11/14,Ch3.词法分析,11,单词符号的内部表示是二元式：,(词类种别编码,单词符号自身的属性值),1.词类种别编码供给应语法分析程序使用；,2.单词自身的属性值供给应语义分析程序使用。,3.具体的分类设计方法以便利语法分析程序使用为原则。,单词符号的内部表示,12,例子,考虑下述,C,语言代码段：,while(i=j)i-;,经词法分析器处理后，它将转换为如下的单词符号序列：,id,指向,i,的符号表项的指针,=,-,100,i,地址,名字,符号表,10,如标识符单词,i,对应的二元组(6,10),13,3.1.2 词法分析器作为独立子程序,把词法分析设计成一个独立程序，每当语法分析器需要一个单词符号时就调用这个子程序。,每一次调用，词法分析器从源程序字符串中识别出一个单词符号，并把它的内部表示二元组交给语法分析器处理。如下图：,词法分析器,语法分析器,语义分析和,中间代码生成器,源程序,中间代码,14,3.2 词法分析器的设计,3.2.1 输入、预处理,处理源程序输入的技术,3.2.2 单词符号的识别：超前搜寻,识别单词符号的技术,3.2.3 状态转换图,单词符号构造的一种图形表示方法,识别单词符号的一种方法,3.2.4 状态转换图的实现,词法分析程序的一种手工构造方法,状态转换图 词法分析程序,15,3.2.1 输入、预处理,词法分析器工作的第一步是输入源程序文本。,输入串一般放在一个输入缓冲区中。但在很多状况下，可以先预处理输入串，识别工作将更便利。,预处理工作包括对空白符、跳格符、回车符和换行符等编辑性字符的处理，及删除注解等。,可以构造一个预处理子程序完成上面的工作。每当词法分析器调用它时就处理出一串确定长度的输入字符，并将其装入指定的缓冲区-扫描缓冲区中。,这样分析器就可以在扫描缓冲区中直接进展单词符号的识别工作。P40.图3.1词法分析器的构造,16,输入、预处理：词法分析第一步,扫描缓冲区,预处理程序,预处理,扫描识别,输入缓冲区,内存,源程序文本,外存,读入,词法分析程序,扫描识别,2相关问题,词法分析器可以作为一个独立的子程序，也可以作为一遍独立的扫描来安排。,输入缓冲区,工作区,(token),单词开始指针,扫描指针,正拼单词,双缓冲区,并行、捻接,每次移动向前指针都需要做两次测试,2相关问题,？如何设计和实现扫描器,大小问题,128Byte*2|1024Byte*2|4096Byte*2,forward:=forward+1;,if forward在缓冲区第一局部末尾 then 重装缓冲区其次局部,else if forward在缓冲区其次局部末尾 then begin,重装缓冲区第一局部;,将forward移到缓冲区第一局部开头,end,forward:=forward+1;,if forward！=eof then,if forward在第一局部末尾 then 重装其次局部,else if forward在其次局部末尾 then begin,重装第一局部;,将forward 移到第一局部开头,end,else终止词法分析 /*eof 在表示输入完毕*/,2024/11/14,Ch3.词法分析,19,下面通过单词符号：,关键字的识别,标识符的识别,常数的识别,算符的识别,界符的识别,介绍单词符号识别的一个简洁方法-超前搜寻,3.2.2 单词符号的识别：超前搜寻,2024/11/14,Ch3.词法分析,20,关键字的识别(1),像FORTRAN这样的语言，关键字的识别甚为麻烦。由于,1.关键字不加爱护只要不引起冲突，用户可以用它们作为一般标识符。,2.关键字和用户自定义的标识符或标号之间没有特殊的界符作间隔。,21,关键字的识别(2),下面是几个,FORTRAN,的正确语句，,空白可有可无，不作分隔符,：,1,DO99K=1,10,2 IF(5.EQ.M)I=10,3 DO99K=1.1,4 IF(5)=55,语句1和2分别是,DO,和,IF,语句,，它们都是以某关键字开头的。,语句3和4是,赋值语句,，它们都是以用户自定义的标识符开头的。,22,标识符、常数的识别,标识符的识别 (参考P40,P41),是字母开头的字母数字串，后跟算符或界符，识别不困难，例如 DO99K=1.10,常数的识别,算术常数的识别:多数语言很直接，有的须承受超前搜寻，如FORTRAN语言中：,IF(5.EQ.M)GOTO55-5.E08,规律(布尔)常数的识别:比较简洁,FORTRAN文字常数的识别:麻烦,须作特殊处理,2024/11/14,Ch3.词法分析,23,算符、界符的识别,(参考P40,P41),算符的识别,单个字符构成的算符的识别较简洁,如 i+j,多个字符构成的算符的识别须使用超前搜寻,如 i+界符的识别,界符的识别比较简洁,24,3.2.3 状态转换图,状态转换图用来：,描述单词符号的构造,识别单词符号串,是设计词法分析器的工具,手工生成词法分析器的方法:,转换 实现,词法分析程序,构造识别单词符号的状态转换图,2024/11/14,Ch3.词法分析,25,状态转换图,状态转换图是一张有限方向图，只包含有限个状态，即有限个结点。,1.结点代表状态，用圆圈表示,2.终止状态用双圈表示,3.初始状态前标记符号“”来表示,4.状态之间用箭弧连结,5.箭弧上的标记代表在射出结点即箭弧始结点状态下可能消失的输入字符或字符类，箭弧标记表示状态转换的条件。,26,状态转换图：例,例 P41.图3.2(a)表示：,在状态1下，假设输入字符为X，则读进X，并转换到状态2。,假设输入字符为y，则读进y，并转换到状态3。,假设输入字符非x和非y，则此转换图不工作。,2,3,1,Y,X,一个状态转换图可用于识别肯定的字符串,27,状态转换图识别字符串：例1,例1 P41.图3.2(b)，识别标识符的状态转换图。其中0为初态，2为终态。,这个转换图识别标识符的过程是:从初态0开头，假设在状态0下输入字符是字母，则读进它，并转入状态1。在状态1之下，假设输入字符为字母或数字，则读进它，并重新进入状态1。始终重复这个过程直到觉察输入字符不再是字母或数字时(这个字符已经被读进)就进入状态2。,1,2,字母或数字,0,*,其他,字母,28,状态转换图识别字符串:例,例1 P41.图3.2(b)，识别标识符的状态转换图。其中0为初态，2为终态。,状态2是终态，它意味着到此已经识别出一个标识符。终态上打个*号，表示多读进了一个不属于标识符局部的字符，应把它退还给输入串。假设在状态0时输入字符不为“字母”，则意味着这个转换图不工作。,1,2,字母或数字,0,*,其他,字母,2024/11/14,Ch3.词法分析,29,状态转换图识别字符串:例2,例2,P41.,图3.2(,c),是,识别整数,的转换图。其中0为初态，2为终态,打了*号。,识别的过程类似前例。,1,2,数字,0,*,其他,数字,30,例3,P41.,图3.2(,d),是一个,识别,FORTRAN,实型常数,的转换图。其中0为初态，7为终态。,状态转换图识别字符串:例3,该转换图可以识别下面形式的一些实,数,:,123.,.123,123,E3,123.456,.123,E+10,123.456E-3,等,5,其他,数字,6,1,7,数字,0,*,2,3,4,其他,E,或,D,.,E,或,D,+或-,数字,数字,.,数字,数字,数字,单词符号编码举例,单词符号,种别编码,内部值,助记符,DIM,1,$DIM,IF,2,$IF,DO,3,$DO,STOP,4,$STOP,END,5,$END,标识符,6,内部符号串,$IDN,整数,7,标准二进制,$INT,=,8,$ASG,+,9,$PLUS,*,10,$STAR,*,11,$POWER,，,12,$COMMA,（,13,$SLP,）,14,$SRP,状态图,letter,digit,letter,IDN，入口,digit,digit,(,其它,),(,其它,),NUM，值,ASG，_,=,*,STAR，_,s,*,POWER，_,其它,IDN,letter(letter|digit),*,NUM,digit(digit),*,ASG,=,POWER,*,STAR,*,空白,2024/11/14,Ch3.词法分析,33,3.3 正规表达式与有限自动机,为了更好地使用状态转换图构造词法分析器，为了争论词法分析器的自动生成，还需要将转换图的概念形式化。,本节主要争论词法分析器自动产生所需要的工具,引入：正规式，正规集，有限自动机等概念。,本节是本章的重点和难点。,本节内容及关系,单词符号结构的描述,状态转换图,词法分析器(扫描器),用,