第三章词法分析及有穷自动机§1、词法分析程序得任务2、词法分析程序得处理方式词法分析程序与语法分析程序接口方式有两种:第一种方式:第二种方式:将词法分析程序编写成一个子程序,每当语法分析程序需要读一个新单词时,便去调用它。注:后一种方式比较好。因为不需要在内存中构造与保存中间文件。二、词法分析程序得I/O1、输入字符串表示得源程序2、输出单词符号序列或单词符号。1)程序语言得单词符号单词:指语言中具有独立意义得最小语法单位。语言中得单词符号:一般可归结为五种:保留字(基本字):如if,for,and等――个数确定标识符:表示常量、变量、类型、过程等名称――个数不确定常数:如34,-0、37等――个数不确定运算符:如+,-,*,/,<等――个数确定界线符:如逗号,分号,括号等――个数确定注:·保留字,运算符,界线符可列表,供词法分析程序查询;·标识符与常数可用正规文法或正规式描述,供词法分析程序识别。2)输出得单词形式二元组:(单词得种别码,单词自身值)1o单词得种别码:表示单词得种类分类得原则:处理简单分类得方法:使每一个单词对应一个整数码分类得目得:最大限度地区别各个单词单词地分类法有多种:一种一类一字一类或一符一类具体:保留字:一字一种。如:if1then2。。。标识符:统归一种。常数:整数,实数,布尔统为一种或按类型分整数11实数12布尔13+292o单词自身值(可有可无)单词自身值就是单词得机内代码或者单词在表格中得地址码。如:标识符:自身得字符串(1,’a’)常数:自身得二进制数(11,’100’得二进制数)例:一种一类得单词输出形式设保留字、标识符、常数、运算符、分界符得种别码分别为1,2,3,4,5;将ifa>1thenb:=10表示为一种一类得单词输出形式。ifa>1thenb:=10例:采用一字一类或一符一类地分类技术,则保留字单词自身值可无,但事先构造一个保留字单词对照表,其值可在词表中查到。大家学习辛苦了，还是要坚持表2、1保留字单词表§2、词法分析程序得设计过程二、用状态转换图设计词法分析程序1、词法分析程序得预处理词法分析程序在识别单词前,需要对输入到缓冲区得源程序进行预处理。预处理:删去无用得空格,跳格,回车与换行等编辑性字符;删去注释部分每次对一串定长(如120个字符)得输入字符进行预处理,并装入一个指定得扫描缓冲区中。扫描缓冲区就是一个一分为二得区域,每一个区域可容纳120个字符,且相互交替使用。搜索指针从单词起点开始搜索,如果遇到半区得边界但尚未达到单词得终点时,则可将后续得120个输入字符装进缓冲区得另一半中。2、状态转换图状态转换图就是为了识别正规文法或正规式而专门设计得有向图。她就是有穷自动机得非形式化表示。状态转换图得组成:1o有限个状态结点状态结点代表正规文法得非终结符(用单圈表示);开始状态结点:用双箭头指示;终止状态结点:用双圈表示。2o弧线→弧上得标记x指明在射出弧得结点状态下可能出现得输入字符或字符类,即终结符。(→表示机器得识别方向)、大多数单词结构就是用正规文法描述得例:<标识符>∷=<字母>|<标识符><字母>|<标识符><数字><整数>∷=<数字>|<整数><数字><运算符>∷=+|-|*|/|…、<界线符>∷=;|,|(|)|…、、。。。3、由正规文法构造状态转换图1)左线性正规文法构造状态转换图左线性正规文法得一般形式:U∷=a|wa左线性正规文法构造状态转换图得步骤如下:增加一个开始状态结点s(假定文法得词汇表中不含s);以每个非终结符为状态作结点;对于形如U∷=a得每一个规则,引一条从开始状态s到状态U得弧,弧上标记为a;对于形如U∷=wa得每一个规则,引一条从状态w到状态U得弧,弧上标记为a;以识别符号为终止状态。例:设有正规文法G[Z]:Z∷=U0|V1U∷=Z1|1V∷=Z0|0(描述得语言为L(G)={01,10})则状态转换图如下:例:标识符得转换图:从开始状态出发到某一终止状态结点为止,所经过得路径上得符号串,称能为该状态转换图所接收(识别)得符号串。如:标识符x26为上述转换图识别,识别路径为2)右线性正规文法构造状态转换图右线性正规文法U∷=a|aV构造状态转换图得步骤:增加一个终止状态结点z(假定文法得词汇表中不含z);以每个非终结符为状态作结点;对于形如U∷=a得每一个规则,引一条从开始状态U到终止状态z得弧,弧上标记为a;对于形如U∷=aV得每一个规则,引一