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