资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章 词法分析,词法分析的,任务,：,从左至右逐个字符地扫描源程序，产生一个个的,单词符号,，把作为字符串的源程序改造成为单词符号串的,中间程序,。,词法分析器,/,扫描器,：,执行词法分析的程序。,源程序,扫描器,scanner,1,、关键字,词法分析器的,功能,如下图所示：,2,、标识符,5,、界符,4,、运算符,3,、常数,由程序语言定义的具有固定意义的标识符。也可称为保留字或基本字。例如：,Pascal,中的,begin,，,end,，,if,等。,界符：如逗号、分号、括号、,/*,，*,/,等。它是确定的。,运算符：如,+,、,-,、*、,/,等。它是确定的。,常数的类型一般有整型、实型、布尔型、文字型等。它是不限的。,用来表示各种名字，如变量名、数组名、过程名等。它是不限的。,3.1,对词法分析器的要求,词法分析器的功能和输出形式,词法分析器的,功能,：输入源程序，输出单词符号。,单词符号,：一个程序语言的基本语法符号。分为以下,5,种。,1,、,关键字,：由程序语言定义的具有固定意义的标识符。也可称为保留字或基本字。例如：,Pascal,中的,begin,，,end,，,if,等。它是,确定,的。,2,、,标识符,：用来表示各种名字，如变量名、数组名、过程名等。它是,不限,的。,3,、,常数,：常数的类型一般有整型、实型、布尔型、文字型等。它是,不限,的。,4,、,运算符,：如,+,、,-,、*、,/,等。它是,确定,的。,5,、,界符,：如逗号、分号、括号、,/*,，*,/,等。它是,确定,的。,确定,不限,单词符号的表示形式,：词法分析器所输出的单词符号常常表示成,二元式（单词种别，单词自身的值）,。,单词种别,可以用以下形式表示：,1,、一类单词统一用一个整数值代表其属性。例如：,1,代表关键字，,2,代表标识符等。,2,、每一个单词一个类别。例如：,1,代表,BEGIN,，,2,代表,END,等。,单词自身的值,可以表示成：常量的二进制表示；常量、变量等在符号表种的地址码，等等。,注意：,一个语言的单词符号如何分种，分几种，怎样编码，是一个技术问题。标识符一般同归为一种。常数则宜按类型（整、实、布尔）分。关键字可以将其全体视为一种，也可,一字一种,。,运算符可采用一符一种，但也可把具有一定共性的视为一种。界符则一般采用,一符一种,。如何进行分种主要取决于处理上的方便。,若是一符一种分种，单词自身值就不需要了。否则，要查符号表。,例：,151,FORTRAN,编译程序的词法分析器在扫描输入串,IF(5EQ,M)GOTO 100,后，它输出的,单词符号串,是：,逻辑,IF,（,34,，,_,）,左括号 （,2,，,_,）,整常数 （,20,，,5,的二进制表示）,等号 （,6,，,_,）,标识符 （,26,，,M,）,右括号 （,16,，,_,）,GOTO,（,30,，,_,）,标号 （,19,，,100,的二进制表示）,IF为关键字，种别编码34，接受一符一种的编码方式。,常数类型，种别编码,20,，单词自身的值为,5,的二进制表示。,(为界符，种别编码2，接受一符一种的编码方式。,等号为运算符，种别编码6，接受一符一种的编码方式。,M,为标识符，种别编码,26,，单词自身值为,M,。,)为界符，种别编码16，接受一符一种的编码方式。,GOTO为关键字，种别编码30，接受一符一种的编码方式。,100,为标号，种别编码,19,，单词内部的值用,100,的二进制表示。,例：下述,C+,代码段：,while(i=j)i-,；,经词法分析器处理以后，它将被转换为如下的,单词符号串,(while,，,_),(,，,_),(id,，指向,i,的符号表指针,),(=,，,_),(id,，指向,j,的符号表指针,),(),，,_),(id,，指向,i,的符号表指针,),(-,，,_,),(,；，,_),词法分析与语法分析的关系,1,、把词法分析从语法分析中脱离出来的,优点,：,使编译程序的,结构,更加简洁、清晰和条理化。,词法分析和语法分析,方法,不同，词法分析可以使用正则文法自动构造,scanner,简单。,有利于提高语法分析的,效率,。,可以改善词法分析的细节，甚至于一个语法分析配几个,scanner,，把不同的输入变成一种内部表示。,2,、把词法分析作为独立的一,遍,scanner,当作一遍。,把,scanner,当作子程序。,外存,scanner,语法分析,源程序,单词符号,scanner,作为一遍,语法,分析,scanner,源程序,scanner,作为子程序,3.2,词法分析器的设计,设计前提,：,把,scanner,作为一个独立的子程序；,词法分析器的任务为输出单词符号。,预处理,必要性,：,编辑性字符如空白符、回车符等，除了出现在文字和,常数中以外，在别处出现都没有意义。,功 能,：剔除无用字符。,实 现,：预处理子程序。,输入,列表,预处理,子程序,扫描器,扫描缓冲区,输入缓冲区,单词符号,图,2.1,词法分析器,语法分析器,预处理部分,扫描器,若,识别,输入语句,IF(5.EQ.M)GOTO 100,，若缓冲区情况如下所示：,IF(5.EQ.M)GO,起点指示器,搜索指示器,输入缓冲区,TO 100,IF(5.EQ.M)GO,起点指示器,搜索指示器,输入缓冲区,TO 100,IF(5.EQ.M)GO,起点指示器,搜索指示器,两 个 互 补 输 入 缓 冲 区,120,个字符,扫描缓冲区的,结构,：,缓冲区大小,：,120,个字符。,采用两个,指示器,：起点指示器、搜索指示器。,两个互补区,。,3.2.2单词符号的识别超前搜寻,单词符号识别的简单方法：,超前搜索,。,关键字识别,：,例如：在标准,FORTRAN,中,1,、,DO99K,=1,10,2,、,IF,(5.EQ.M)I=10,3,、,DO99K,=1.10,4,、,IF,(5)=55,其中的,DO,、,IF,为关键字,其中的,DO,、,IF,为标识符的一部分,标识符的识别,多数语言的标识符是字母开头的“字母,/,数字”串，而且在程序中标识符的出现后都跟着算符或界符。因此，不难识别。,常数的识别,对于某些语言的常数的识别也需要使用超前搜索。,算符和界符的识别,对于诸如,C+,语言中的“,+”,、“,-”,，这种复合成的算符，需要超前搜索。,状态转换图,转换图,：是一张有限方向图。在状态转换图中，,结点,代表,状态,，用圆圈表示。状态之间用,箭弧,连接。箭弧上的,标记（字符）,代表在射出结状态下可能出现的输入字符或字符类。,状态转换图的功能,:,用于识别一定的字符串。,初态,：一张转换图的启动条件，至少有一个,用圆圈表示。,终态,：一张转换图的结束条件，至少有一个，用双圈表示。,*,：表示多读进了一个字符。,X,Y,(a),转换图示例,2,字母,其他,字母或数字,*,（,b,）识别标识符的转换图,其他,2,数字,数字,*,（,c,）识别整数的转换图,例：简单的状态转换图示例：,初态,终态,从,0,状态到,1,状态可能出现字母,图,2.2,状态转换图,7,*,数字,数字,数字,数字,E,或,D,+,或,数字,其他,E,或,D,数字,其他,数字,例：识别,FORTRAN,实型常数,的转换图：,例如下列实型常数可以被以下转换图识别：,1.23E+4,.56E-7,一般，我们可以让每,一个状态结,对应,一个程序段,。,例如：我们可以让不含回路的分叉结，对应一个,CASE,语句，或者是一组,IFTHENELSE,语句。具体见后面实例。,终态结,一般对应一个,RETURN(C,VAL),语句。其中,C,为单词种别编码；,VAL,是字符数组的,TOKEN,，或者是一个整数值，或者无定义。具体见后面实例。,状态转换图的实现二 程序中心法,例,2,6,：以下,CASE,语句段对应的状态图,:,state i,：,GETCHAR,；,CASE,CHAR,OF,A.Z,：,state j,；,0.9,：,state k,；,/,：,state l,；,END,；,FAIL,数字,字母,/,字符变量，存放最新读进的源程序字符。,过程，将下一输入字符读入CHAR，搜寻指示器前移一个字符。,为了把,状态转换图,转化成,程序,，每个,状态,要建立一段,程序,，它要做的工作如下：,第一步,：从输入缓冲区中取一个字符。为此，我们使用函数,GETCHAR,，每次调用它，推进先行指针，送回一个字符。,第二步,：确定在本状态下，哪一条箭弧是用刚刚来的输入字符标识的。如果找到，控制就转到该弧所指向的状态；若找不到，那么寻找该单词的企图就失败了。,失 败,：先行指针必须,重新回到,开始指针处，并用另一状态图来搜索,另一,单词。如果所有的状态转换图都试过之后，还没有匹配的，就表明这是一个词法错误，此时，调用错误校正程序。,GETCHAR是过程，将下一输入字符读入CHAR，搜寻指示器前移一个字符。,对于如上的状态转换图，,状态,0,的代码如下所示：,state 0,：,C:=,GETCHAR,;,if,LETTER(C),then goto state 1,else,FAIL(),2,字母,其他,字母或数字,LETTER(),是布尔函数过程，当且仅当,C,中的字符是字母，它返回真假值,TRUE,。,FAIL()是例子程序，它移回先行指针（lookahead pointer）,起先下一状态转换图，或调用出错程序。,例,2-7,：示例,如何把,状态结,对应于一段,程序,：,*,对于如上的状态转换图，,状态,1,的代码如下所示：,state 1,：,C:=,GETCHAR,;,if,LETTER(C),or,DIGIT(C),then goto state,1,else if,DELIMITER(C),then goto state 2,else,FAIL(),2,字母,其他,字母或数字,DIGIT(),是布尔函数过程，当且仅当,C,中的字符是数字，它返回真假值,TRUE,。,DELIMITER(C)是过程，只要遇到标识符后的分界符，它返回TRUE。分界符一般为：空格、算术、逻辑符号，括号、；、.、，。,*,对于如上的状态转换图，终态,状态,2,的代码如下所示：,state 2,：,RETRACT(),;,RETURN($id,，,INSTALL(),2,字母,其他,字母或数字,RETRACT(),是过程，由于分界符不属于标识符，所以我们要把先行指针,回调,一个字符。,INSTALL(),是过程，如我们识别出的标识符不在符号表中，我们把它装入,符号表,。我们还要给语法分析程序返回一个,二元式,。,*,假犹如时识别,标识符和定义符，,则须要修改为,State2：,修改之后，,状态,2,的代码如下所示：,state 2,：,RETRACT(),;,c:=,RESERVE();,if c=0,then,RETURN($id,，,INSTALL),else,RETURN(C,_),RESERVE(),整型函数过程,针对,TOKEN,中的字符串进行查找，看其是否是,保留字,，是保留字给出它的编码，否则回送,0,（假定,0,不是保留字编码）。,人有了学问，就会具备各种分析实力，,明辨是非的实力。,所以我们要勤恳读书，广泛阅读，,古人说“书中自有黄金屋。,”通过阅读科技书籍，我们能丰富学问，,培育逻辑思维实力；,通过阅读文学作品，我们能提高文学鉴赏水平，,培育文学情趣；,通过阅读报刊，我们能增长见识，扩大自己的学问面。,有很多书籍还能培育我们的道德情操，,给我们巨大的精神力气，,鼓舞我们前进。,
展开阅读全文