编译原理词 法 分 析

《编译原理词 法 分 析》由会员分享，可在线阅读，更多相关《编译原理词 法 分 析（48页珍藏版）》请在金锄头文库上搜索。

1、2018年9月24日星期一,编译原理主讲：周有顺,版权所有 勿复制传播 1,第三讲 词 法 分 析,有限自动机(状态转换图)与词法分析程序设计,2018年9月24日星期一,编译原理主讲：周有顺,版权所有 勿复制传播 2, 对词法分析器的要求 词法分析器的设计思想 设计扫描器的好工具 高效词法分析器产生的理论基础 词法分析器的自动产生,2018年9月24日星期一,编译原理主讲：周有顺,版权所有 勿复制传播 3,通过本章的学习，不仅可以了解编译程序的词法分析子程序的构造和设计方法，并且可以学习到很多编程思想及技术。如： 预处理技术、 超前搜索确定法、 基于缓冲器上的扫描器技术、 识别状态转换图法、

2、 识别(词法)规则的形式描述法、 用最简自动机来优化扫描分析算法的技术等。 因此，学好本章，对提高大家的程序设计能力，开拓思维，开发智力都将会起到不可低估的作用。,2018年9月24日星期一,编译原理主讲：周有顺,版权所有 勿复制传播 4,一、对词法分析器的要求,回忆： 词法分析器的任务是从左至右逐个字符地对源程序进行扫描产生一个个单词符号。即 词法分析器 源程序由单词符号串组成的中间程序 (用户) (改造) (语法分析的原始数据),2018年9月24日星期一,编译原理主讲：周有顺,版权所有 勿复制传播 5, 词法分析器的功能和输出形式： 功能：首先是源程序的输入功能，对源程序的字符串的加工处

3、理(预处理)。产生单词符号串，输出中间程序。 单词符号是一个程序语言的基本语法符号。一般可分为五种： 基本字(关键字) 如IF, DO等； 标识符 如变量名, 数组名, 过程名等； 常数 如125, 0.178, TRUE等； 运算符 如+, -, *, /, 等； 界符 如逗点, 分号, 括号等。 一个程序语言的基本字，运算符和界符都是确定的，一般只有几十个或上百个。而对标识符，常数的使用由用户定义，个数没有什么限制，只是结构上可以稍加确定(构成规则)。,2018年9月24日星期一,编译原理主讲：周有顺,版权所有 勿复制传播 6, 词法分析器所输出的单词符号常常表示成二元式： (单词种别,

4、单词自身的值) -(内部编码或内码) 单词种别通常用整数编码。 基本字 运算符 界符 标识符 统归为一种，给一个种别编码。 常数 可按类型(整、实、布尔)分种编码。 单词自身的值当单词种别编码不能确定具体单词符号时，需给出单词自身。即 如果一个种别码只含一个单词符号，则该编码即代表它自身了。 如果一个种别码含多个单词符号，则还应给出单词自身的具体值。,它们因为是确定的，可以一符给它一个种别码，也可一类给一个种别码，还可更细一些，如有共性的算符给一个种别编码。(如关系符),2018年9月24日星期一,编译原理主讲：周有顺,版权所有 勿复制传播 7, 例子： 151-FORTRAN编译程序的词法分

5、析器在扫描输入串 IF (5.EQ.M) GOTO 100 后，它所输出的单词符号串是： 逻辑IF (34, -) 左括号 ( 2, -) 整常数 (20, CT:?即5的二进制内码表示) 等号 ( 6, -) 标识符 (26,SNT:?即M) 右括号 (16, -) GOTO (30, -) 标号 (19, LT:?即100),2018年9月24日星期一,编译原理主讲：周有顺,版权所有 勿复制传播 8, 词法分析器作为一个独立的子程序 把词法分析安排为一个独立阶段可使整个编译程序的结构更简洁、清晰和条理化。可用更有效的特殊方法和工具进行处理 (因为它比语法分析简单) 且可以集中力量考虑某些枝

6、节问题。如 FORTRAN源程序书写格式的分析处理。 把词法分析器安排成一个子程序，被语法分析器调用比较自然，从而不必作为一遍也就可以不在外存上保存整个源程序的内码形式。,2018年9月24日星期一,编译原理主讲：周有顺,版权所有 勿复制传播 9,二、词法分析器的设计思想,2018年9月24日星期一,编译原理主讲：周有顺,版权所有 勿复制传播 10, 输入源程序及预处理 任务： 建立输入缓冲区，输入源程序到输入缓冲区。 预处理(可省的)剔除无用的空白、跳格、回车和换行等编辑性字符；对于受书写格限制的语言(如FORTRAN)来说，还包括：区分标号区，捻接续行和给出句末符 (编译时引进的一个特殊符

7、号，表示语句结束)，剔除注解部分。 将预处理的结果送入扫描缓冲区中 (词法分析器所指定的缓冲区)。 预处理可作为一个子程序：是完成上述三项任务的被词法分析器所调用的子程序。每当调用一次，它就处理出一串确定长度(如120个字符)的输入字符，并将送进扫描缓冲区，这样，扫描器就可以在此缓冲区中直接进行单词符号的识别。,2018年9月24日星期一,编译原理主讲：周有顺,版权所有 勿复制传播 11, 扫描器词法分析器的主要部分 扫描器的构造原理：设置二个指针(起点指针和搜索终点指针)，一个可以互补使用的一分为二的扫描缓冲区(总长可为240个字符)。 扫描器对单词长度的要求： 如单词长度120个字符，常数

8、、标识符也是如此，否则缓冲区长度再长也无济于事。 扫描器的工作原理： (扫描算法) 起点 搜索 调用预处理子程序，把 120个输入字符装进扫描缓冲区某半区，搜索指针从起点指针开始向前寻找单词的终点。 如果在该半区内找查到单词的终点，便输出二元式，再起点指针移到此处的后一字符，继续搜索下一个单词。 如果在搜索到该半区边缘尚未到达单词的终点，那么就应调用预处理子程序，把后续的 120个输入字符装进另半区，然后继续搜索,2018年9月24日星期一,编译原理主讲：周有顺,版权所有 勿复制传播 12, 单词符号的识别(found(x)函数过程的算法)： 超前搜索方法 根据将来的情况确定现在 即从不定中找

9、查到确定的依据。 基本字（关键字或称保留字）的识别 有些语言的基本字的输入表示有特殊标态，如加双引号(“BEGIN”)或加底线 ( begin )，此时的识别是很直接的，不存在什么困难。对许多语言来说，事情就不那样简单了。 如FORTRAN语言，基本字就不加特殊保护，只要不引起矛盾，用户可以用它们作为普通标识符，且基本字、用户自定义的标识符、标号之间也可没有特殊的界符作为间隔。如： D O 9 9 K = 1 , 起点 终点 搜索,2018年9月24日星期一,编译原理主讲：周有顺,版权所有 勿复制传播 13, 单词符号的识别：-超前搜索方法 1 DO99K=1 , 10 句末符 搜索针碰到“,

10、”才可断言起点到终点DO为基本字 2 IF(5.EQ.M)GOTO 55句末符 搜索针碰到“G”才可断言起点到终点IF为基本字 3 DO99K=1.10句末符 没碰到“,”而碰到“句末符”才可断言DO不是基本字而DO99K标识符 D O 9 9 K = 1 . 1 0 句末符 起 终 终 搜索 4 IF(5)=55句末符 搜索针碰到“=”才可断言起点到终点IF不为基本字 以上它们均是正确的FORTRAN语句。 1,2是基本字开头； 3,4是用户定义标识符开头。 要区别开1,3;2,4就必须超前扫描许多个字符，超前到能够肯定词性的地方为止。,2018年9月24日星期一,编译原理主讲：周有顺,版权

11、所有 勿复制传播 14, 标识符的识别：多数语言的标识符是字母开头“字母/数字”串，且程序中标识符的出现都后跟着算符或界符。所以大多没困难。 常数的识别： 算术常数的识别以及将其转换成二进制内码形式是扫描器比较费时的工作。大多数算术常数的识别是很直接的，但有些也需超前搜索。如上述FORTRAN例中第2句，5.EQ.M只有当超前到Q时才能断定5的词性，因为如5.E08和5.EQ.M。 逻辑常数是很容易识别的。 用撇号括起来的字符串常数也是容易识别的。但如FORTAN中的文字常数的识别有点麻烦。它也属字符串常数。 (如3HABC)，这单依靠形式规则是不够了，需理解词头的词义了，再继续识别了。即当扫

12、描器请到尾跟H 的无符号整型常数时，将其值译出，再把后续的三个字符取出来，作为“字串常数”输出。 算符和界符的识别：扫描器应把那些由多个字符复合成的算符和界符(如PASCAL中的:=, FORTAN的*, .EQ.等)拼合成一个单一的单词符号。因为它们分开即失去原来的意义。这同样需要超前搜索。,2018年9月24日星期一,编译原理主讲：周有顺,版权所有 勿复制传播 15,可见, 为了展望到所期望的字符, 需超前搜索一个甚至多个字符后,才能定, 若被否定又得重新寻找新的单词终点, 再次超前搜索, 故程序编制繁杂, 程序工作效率低, 速度慢。 但, 由上面的分析可见, 在识别和超前搜索的过程中存在

13、很多次回退, 反复多次, 但每一次返回重新开始, 都不是在原来的位置上, 而是在一个全新的状态不继续进行, 真是“循环往复, 螺旋式上升”。这种识别某一单词的过程可以用一个状态图来表示。,2018年9月24日星期一,编译原理主讲：周有顺,版权所有 勿复制传播 16,三、 设计扫描器的好工具,2018年9月24日星期一,编译原理主讲：周有顺,版权所有 勿复制传播 17, 使用状态转换图是设计扫描器的一种好途径。我们可以根据词法规则, 画出一些状态转换图, 再根据图编程序。 如识别基本字DO 的状态转换图是 (上例中): 此处“*”表示要吐出从开始多吃进的所有字符; 此处“*”表示吐出所有字符,

14、转到标识符识别图表. 这都是超前搜索的太远的原故。以后我们只讨论超前一个字符的情况,因为道理是一样的何况只要在语言的定义上稍加限制, 即可。,2018年9月24日星期一,编译原理主讲：周有顺,版权所有 勿复制传播 18, 状态转换图- 一张有限结点的方向图 定义: 结点-代表识别时的状态, 用图圈表示。 箭弧-代表状态之间的连结, 但箭弧上需有标记(字符)代表在射出状态不可能出现的输入字符或类。 初态-代表识别某一类字符串的开始。一般只有一个。 终态-代表识别出了某一单词。一般至少一个，用双圈示。 例子1: 例子2: 识别标识符的转换图: 例子3: 识别整数的转换图: （如上图）,2018年9

15、月24日星期一,编译原理主讲：周有顺,版权所有 勿复制传播 19, 例子4: 识别一个FORTRAN实型常数的转换图: 一个综合例子。要求构造出一个识别某简单语言的所有单词符号的转换图。,2018年9月24日星期一,编译原理主讲：周有顺,版权所有 勿复制传播 20,某个小语言的所有单词符号种别码和内部值如下表: -词法规则的一种表示方法,2018年9月24日星期一,编译原理主讲：周有顺,版权所有 勿复制传播 21,某个小语言的所有单词符号种别码和内部值如上表(词法规则): 三点限制, 以便不必使用超前搜索技术或仅超前一位。它仅仅是为了例子做得简单而已, 其实完全可以用转换图描述符号。(除FORTRAN语言中的文字常数) 保留字用户不得使用它作为标识符的基本字。即基本字为保留字 预先安排有保留字表, 以确定识别出的标识符是否为基本字。 清空白符也作为隔的界符。(这样可以不必预处理了) 依据可以画出扫描程序工作的状态转换图(即识别所有单词符号的状态转换图)(如上图右边) 注：状态13是出错情形，转入出错信息输出处理。,