编译原理-词法分析.ppt

《编译原理-词法分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1本章在编译程序中的地位表格管理词法分析器语法分析器语义分析与中间代码产生优化器目标代码生成器源程序单词符号语法单位中间代码中间代码目标代码出错处理2词法分析任务：从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词符号。逻辑上紧密相连的一组字符，这些字符具有集体含义。单词：标识符，保留字，常数，算符，界符词法分析阶段的工作所依循的是语言的词法规则。描述词法规则的有效工具是正规式和有限自动机。33.1对词法分析器的要求3.1.1词法分析器的功能和输出形式输入源程序，扫描识别,输出单词符号程序语言的单词符号一般分为五种：关

2、键字(保留字或基本字)：如begin,end,if,then,else,while,do等标识符：用来表示各种名字，如X1字面常数：如256，3.14，true,‘abc’运算符：如＋、－、*、/等等分界符：如逗号，分号，冒号等4单词符号的内部表示是二元式：(词类种别编码,单词符号自身的属性值)1.词类种别编码提供给语法分析程序使用；2.单词自身的属性值提供给语义分析程序使用。3.具体的分类设计方法以方便语法分析程序使用为原则。单词符号的内部表示5例子考虑下述C语言代码段：while(i>=j)i--;经词法分析器处理后，它将转换为如下的单词符号序列：

3、e,-><(,->=,-><),-><--,-><;,->……100i……地址类型名字符号表10如标识符单词i对应的二元组(6,10)63.1.2词法分析器作为独立子程序把词法分析设计成一个独立程序，每当语法分析器需要一个单词符号时就调用这个子程序。每一次调用，词法分析器从源程序字符串中识别出一个单词符号，并把它的内部表示二元组交给语法分析器处理。如图所示：词法分析器语法分析器语义分析和中间代码生成器源程序中间代码7输入、预处理：词法分析第一步扫描缓冲区预处理程序

4、预处理扫描识别输入缓冲区内存源程序文本外存读入词法分析程序扫描识别预处理用于删除空白符、回车符、换行符及注释等。2）相关问题词法分析器可以作为一个独立的子程序，也可以作为一遍独立的扫描来安排。扫描缓冲区双缓冲区↑↑搜索起点指示器指示器↑↑起点搜索指示器指示器89关键字的识别(1)、超前搜索像FORTRAN这样的语言，关键字的识别甚为麻烦。因为1.关键字不加保护（只要不引起矛盾，用户可以用它们作为普通标识符）。2.关键字和用户自定义的标识符或标号之间没有特殊的界符作间隔。10关键字的识别(2)下面是几个FORTRAN的正确语句，空白可有可无，不作分隔符：1DO99

5、K=1,102IF(5.EQ.M)I=103DO99K=1.14IF(5)=55语句1和2分别是DO和IF语句，它们都是以某关键字开头的。语句3和4是赋值语句，它们都是以用户自定义的标识符开头的。11标识符、常数的识别标识符的识别是字母开头的字母数字串，后跟算符或界符，识别不困难，例如DO99K=1.10常数的识别算术常数的识别:多数语言很直接，有的须采用超前搜索，如FORTRAN语言中：IF(5.EQ.M)GOTO55---5.E08逻辑(布尔)常数的识别:比较容易FORTRAN文字常数的识别:麻烦,须作特殊处理12算符、界符的识别算符的识别单个字符构成的算符

6、的识别较容易如i+j多个字符构成的算符的识别须使用超前搜索如i++界符的识别界符的识别比较简单133.2.3状态转换图状态转换图用来：描述单词符号的结构识别单词符号串是设计词法分析器的工具手工生成词法分析器的方法:转换实现词法分析程序构造识别单词符号的状态转换图14状态转换图状态转换图是一张有限方向图，只包含有限个状态，即有限个结点。1.结点代表状态，用圆圈表示2.终止状态用双圈表示3.初始状态前标记符号“”来表示4.状态之间用箭弧连结5.箭弧上的标记代表在射出结点即箭弧始结点状态下可能出现的输入字符或字符类，箭弧标记表示状态转换的条件。231YX15状态转换

7、图：例在状态1下，若输入字符为X，则读进X，并转换到状态2。若输入字符为y，则读进y，并转换到状态3。若输入字符非x和非y，则此转换图不工作。231YX一个状态转换图可用于识别一定的字符串16状态转换图识别字符串：例1识别标识符的状态转换图。其中0为初态，2为终态。这个转换图识别标识符的过程是:从初态0开始，若在状态0下输入字符是字母，则读进它，并转入状态1。在状态1之下，若输入字符为字母或数字，则读进它，并重新进入状态1。一直重复这个过程直到发现输入字符不再是字母或数字时(这个字符已经被读进)就进入状态2。12字母或数字0*其他字母17状态转换图识别字符串:例

8、识别标识符的状态转换图。