第二章 词法分析4 词法分析程序实现 构造词法分析器步骤 单词的形式化描述 词法分析程序的实现

构造词法分析器步骤 确定词法分析器的接口：即确定词法分析器是作为语法分析的一个子程序还是作为独立一遍； 确定单词分类和存储结构； 单词的形式化描述：构造每一类单词的描述正则表达式并转换为DFA； 正则表达式NFADFA 4. 设计算法实现DFA。

（一）词法分析器的接口 一类是仅作为语法分析的子程序： call 附 属 字符序列 词法分析器 Token 附 属 词法分析器 语 法 分 析 call Token 字符序列 另一类是作为编译器的独立一遍处理器： 字符序列 独 立 词法分析器 Token 语 法 分 析

（二）单词的分类及内部表示 TOKEN结构图 单词类别 语义信息

1、保留字、特殊符号的TOKEN处理 可以有两种处理方法： 保留字种类编码 if ‘+’的 编码

2、标识符和常量的TOKEN结构 语义信息 语义信息 关于语义信息可以有两种处理方法： 一种是在其TOKEN的语义信息部分直接存储这些值； 标识符种类编码 语义信息 常量种类编码 语义信息 关于语义信息可以有两种处理方法： 一种是在其TOKEN的语义信息部分直接存储这些值； 另外一种是设置标识符表和常量表来存储其值，这时TOKEN的语义信息部分就是一个指向相应表项的一个指针. 第一种方法处理起来比较简单，但是TOKEN的空间大小不好确定，可能造成空间浪费.

例1：不设置标识符表和常量表 某程序片段如下： int sum, first, count; sum=first + count * 10; 单词名称 类别编码 (词法信息) 类别编码的助记符 标识符 1 $id 整型常量 2 $num ， 30 $comma ； 31 $semi = 32 $assi + 33 $plus 34 $colon * 35 $mult \n 36 $return int 37 $int 生成下列TOKEN序列： 1.($int, ) 2. ($id, sum ) 3. ($comma, ) 4. ($id, first ) 5. ($comma, ) 6. ($id, count ) 7. ($semi, ) 8. ($return, ) 9. ($id, sum ) 10. ($assi, ) 11. ($id, first ) 12. ($plus, ) 13. ($id, count ) 14. ($mult, ) 15. ($num, 10 ) 16. ($semi, ) 17 . ($return, )

例2：设置标识符表和常量表 如果单词为标识符，则类型填1 如果单词为常量，则类型填2 如果类型为保留字或特殊符号，则类型填该保留字或特殊符号所对应的数字 类型 内容 （符号表地址） TOKEN结构图 标识符索引表 1 2 3 ... n 常量索引表 1 2 3 ... n 保留字、特殊符号表 3 while 4 if 5 % ... 56 } 这个方法肯定是不止一种，我们给出一种可行的，也是在实践中检验过的，绝对不是唯一的，不管怎么设计只要把需要的信息表示出来就可以 这是我们给出的一种TOKEN结构，反映了语法信息和语义信息。第一部分称作种类信息，反映的是语法信息；第二部分称作内容信息，反映的是值。 我们分析过单词可以分成那4大类。因为那些类单词的数量是有限的，我们就可以用编码把它区分开

（三）单词的形式化描述 构造识别单词的有限自动机的方法与步骤如下： 1. 根据构成规则对程序语言的单词按类构造出相应的状态转换图，或将各类单词的正则表达式转换成相应的有限自动机. 2. 合并各类单词的状态转换图，构成一个能识别语言所有单词的DFA.合并方法为： （1）将各类单词的状态转换图的初始状态合并为一个唯一的初始状态； （2）化简调整状态冲突和对冲突状态重新编号； （3）如果有必要，增加出错状态.

例： L | D D D + ； ： = ： < < = 标识符 无符号整数 界限符 、 运算符 各类单词的自动机 图 3 . 1 无符号整数 + 界限符 、 运算符 ； ： = ： < < = 各类单词的自动机 图 3 . 4

1 L | D 2 ： = 6 5 3 + 4 ； 9 < 7 8 10 other 合并后的DFA

（四）词法分析程序的实现 实现词法分析程序应注意的问题 保留字识别 符合单词、数 控制字符、注释

1、 保留字识别 统一识别 事先构造好保留字表。分析时把保留字也当作一般标识符来识别，然后查保留字表，没有则按一般标识符来处理。 单独识别 在自动机中单独加入识别各个保留字的状态。 13

2、 符合单词、数 复合单词的识别 在程序设计语言中，有一类单词是由两个或者两个以上的符号组成的，这类单词的前缀部分也可以是一个独立的单词。在处理这类单词时要特别加以注意。 有时候需要向前看若干个字符才能判断。 数的转换 词法分析程序应该把表示数的字符串转换成数，如“123”应该转换成123。 14

3、 控制字符、注释 控制字符的处理 无用的空格符和制表符要删掉； 字符串内的空格不能删； 换行符不能直接删除，而需用于错误定位。 注释的处理 源程序中的注释没有任何语法和语义上的意义，因此在进行词法分析时可以直接将注释删除，而不必生成其TOKEN。 15

实现算法 首先给出词法分析程序中用到的一些基本操作. Append(string, char)：拼单词. KeyWord(string)：查保留字表，看string是否为保留字.若此函数返回0，则表示string是一个标识符，否则为保留字编码. AddTable(table, string)：入表操作，检查string在table中有没有出现，若有则返回其位置指针，若没有则将其插入到table的末尾，并返回该位置的指针. BACK：源程序文件指针回退一个字符.

ReadChar(CurrentChar); case CurrentChar of PROCEDURE Scanner(); BEGIN LS0: string:=“”; ReadChar(CurrentChar); case CurrentChar of ‘A’..‘Z’ | ‘a’..‘z ’：goto LS1； ‘0’..‘9’：goto LS2; ‘+’：goto LS3; ‘;’： goto LS4; ‘:’： goto LS5; ‘<’ ： goto LS8; end; 1 L | D 2 ： = 6 5 3 + 4 ； 9 < 7 other 10 8

LS1: string:=Append(string, CurrentChar); ReadChar(CurrentChar); 1 L | D 2 ： = 6 5 3 + 4 ； 9 < 7 other 10 8 LS1: string:=Append(string, CurrentChar); ReadChar(CurrentChar); case CurrentChar of ‘A’..‘Z’ ，‘a’..‘z’ ， ‘0’..‘9’：goto LS1; other： BEGIN BACK; c:=KeyWord(string); if (c!=0) then return(c, “”); else begin pID:=AddTable(IdTable, string); return($id, pID); end; END

ReadChar(CurrentChar); case CurrentChar of ‘0’..‘9’: goto LS2; other: 1 L | D 2 ： = 6 5 3 + 4 ； 9 < 7 other 10 8 LS2: string:=Append(string, CurrentChar); ReadChar(CurrentChar); case CurrentChar of ‘0’..‘9’: goto LS2; other: BEGIN BACK; pNB:=AddTable(NbTable, string); return($int, pNB); END end;

‘=’: goto LS9; other: goto LS10; LS3: return($plus, “”); LS4: return($semi, “”); LS5: ReadChar(CurrentChar); case CurrentChar of ‘=’ : goto LS6; other: goto LS7; end; LS6: return($assi, “”); LS7: BACK; return($colon, “ ”); LS8: ReadChar(CurrentChar); ‘=’: goto LS9; other: goto LS10; LS9: return($le, “ ”); LS10: BACK; return($lt, “ ”); END 1 L | D 2 ： = 6 5 3 + 4 ； 9 < 7 other 10 8

词法分析总结 这一章的内容需要掌握的是以下几点： 一个核心：词法分析器的设计 两个工具：正则表达式和自动机 三个转换算法：NFA到DFA，自动机的极小化，正则表达式和自动机的互相转换