资源描述：
《编译原理2词法分析ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章词法分析内容提要:状态转换图正规式与有限制动机词法分析器的自动生成词法分析器源程序单词序列第一节状态转换图一单词分类及表示编译中,把高级语言的单词分为五类:标识符,基本字,常数,运算符,界符基本字,运算符,界符都是有限可枚举的;而标识符,常数可认为是无限的.简单起见,单词可表示为如下二元组:(单词分类号,单词自身值);或者为:(单词种别码,单词自身值);标识符,常数各为一个种别码,而由于基本字,运算符,界符的有限性,可以设计为一字一个种别码.2例如:单词单词种别码分类号标识符11常数22if33then43end903,914;924=1515+1525保留字界符
2、运算符3二词法分析器的设计1源程序的预处理子程序源程序中,存在许多编辑用的符号,它们对程序逻辑功能无任何影响.例如:回车,换行,多余空白符,注释行等.在词法分析之前,首先要剔除掉这些符号,使得词法分析更为简单.源程序输入缓冲区预处理子程序扫描缓冲区2扫描缓冲区1缓冲区分为两部分,每个长度为256字节,这样单词的总长度可达到256字节.预处理子程序把处理好的字符串轮流放入两个缓冲区中,供词法分析程序使用.42词法分析程序词法分析程序又称为词法分析器或扫描器.可以单独为一个程序;也可以作为整个编译程序的一个子程序,当需要一个单词时,就调用词法分析子程序返回一个单词.这里,作
3、为子程序介绍.词法分析器的结构:源程序输入缓冲区预处理子程序扫描缓冲区2扫描缓冲区1词法分析子程序调用返回一单词数据53词法规则的表示--------状态转换图定义:状态转换图是一有向图,由有限个结点及有向边连接而成;每个结点称为状态;状态图有一个初态,多个终态;每条边上有相应的字符.状态转换图用于表示单词结构,从状态转换图的初态到终态间,每条路径上字符的连接,就构成了该状态图的合法单词.例如:012初态终态字母字母数字其它*1>标识符的状态图表示:星号表示单词尾部多跟一个字符,应该去掉.6012初态终态数字数字其它*2>整数的状态图表示:016初态终态数字数字其它*3
4、>实数的状态图表示:23456数字数字数字E+或—数字E其它数字74单词的识别状态图即可以表示单词规则,同时也可以用于识别单词.设有一字符串S=s1s2......sn,若状态图中存在一初态到终态的路径,且路径上字符的连接为:s1s2......sn,称S可被状态图识别.例如:S=‘var1’012初态终态var1其它*保留字由于满足标识符定义,因此可以跟标识符用同样的状态图表示与识别,只需增加一个保留字表,当识别出一个标识符时,通过查保留字表来区别保留字及普通标识符.因此var1是一个合法的标识符.85一个简单示例构造一个简单语言所有单词的状态转换图.该语言的单词种类
5、如下表所示:单词符号种别码助记符内码值DIMIFDOSTOPEND标识符正常数=+***,()1234567891011121314$DIM$IF$DO$STOP$END$ID$INT$ASSIGN$PLUS$STAR$POWER$COMMA$LPAR$RPAR(1,)(2,)(3,)(4,)(5,)(6,串值)(7,数值)(8,)(9,)(10,)(11,)(12,)(13,)(14,)9012初态终态字母字母数字其它*空白34终态数字数字非数字*5=6+7*98**非**10,11(12)13其它106状态转换图的程序实现为便于程序实现,假设每个单词间都有界符或运算
6、符或空格隔开,并引入下面的全局变量及子程序:1)CHAR字符变量2)TOKEN单词字符串3)GETCHAR读一个字符到CHAR中4)GETBC读一个非空白字符到CHAR中5)CONCAT把CHAR中字符连接到TOKEN之后6)LETTER判断CHAR中字符是否为字母7)DIGIT判断CHAR中字符是否为数字8)RESERVE用TOKEN中的字符串查找保留字表,并返回保留字种别码,若返回零,则非保留字9)RETRACT把CHAR中字符回送到缓冲区11下面分析状态图的结构特点.每个状态图都由三种结构构成:分支结构循环结构终结点1>分支结构程序设计ii2i1inc1c2cns
7、tatei:GETCHAR;CASECHAROFc1:CONCAT；statei1:.......c2:CONCAT；statei2:.......cn:CONCAT；statein:.......ELSEERROREND;122>循环结构程序设计ijC其它statei:GETCHAR;WHILECHAR=CDO{CONCAT;GETCHAR};RETRACT；statej:..........3>终结点程序设计一般对应一条返回语句:return(c,val);c为种别码,val为单词值.带*号的终结点,必须用RETRACT退还多余字符下
