第三章有限自动机和词法分析器

1、主要内容：主要内容：l 词法分析过程涉及的几个问题词法分析过程涉及的几个问题l 词法分析器的生成技术词法分析器的生成技术 正则表达式正则表达式 有限自动机有限自动机l 有关词法分析器的几个问题和处理方法：有关词法分析器的几个问题和处理方法： 词法分析器的功能、分类词法分析器的功能、分类 单词的分类、单词的分类、Token表示表示 保留字保留字 空格符、制表符和换行符空格符、制表符和换行符 复合型符号复合型符号 括号类匹配预检括号类匹配预检 字符串空间字符串空间 词法错误校正词法错误校正 词法分析结束词法分析结束l词法分析器功能：词法分析器功能：l 读源程序的字符序列读源程序的字符序列, ,逐个

2、拼出单词逐个拼出单词, ,并并构造相应的内部表示构造相应的内部表示TOKEN.TOKEN.同时检查源程序同时检查源程序中的词法错误中的词法错误. .l引入引入TokenToken的原因：的原因：l 编译程序总是用某种程序语言书写的程编译程序总是用某种程序语言书写的程序，语言的操作对象只能是该语言规定的各序，语言的操作对象只能是该语言规定的各种数据。而编译程序的操作对象是程序中的种数据。而编译程序的操作对象是程序中的各种语法单位，因此，必须把它们表示成某各种语法单位，因此，必须把它们表示成某种数据结构形式。种数据结构形式。 CharList 独独 立立词法分析器词法分析器语法分析语法分析Toke

3、nList 附附 属属词法分析器词法分析器语法分析语法分析callTokenCharListlTokenToken表示最小的语义单位表示最小的语义单位- - -单词的信息。单词的信息。即单词内部表示的数据结构形式。即单词内部表示的数据结构形式。 单词不是程序设计语言中的语法概念，是编译程单词不是程序设计语言中的语法概念，是编译程序中引进的一个概念。是最小的语义单位，不能序中引进的一个概念。是最小的语义单位，不能分割分割lTokenToken中需要记录有关单词的信息：中需要记录有关单词的信息： 单词的标志码单词的标志码($($id,$intCid,$intC, ,) )标识单词的种类标识单词的种

4、类-词法信息词法信息 单词的特征属性（标识符名，符号表地址等）单词的特征属性（标识符名，符号表地址等） - - -语义信息语义信息l标识符：字母打头的字母标识符：字母打头的字母/ /数字串数字串l整常数：数字打头的数字串整常数：数字打头的数字串l实常数：整数实常数：整数. .整数整数l保留字：保留字：beginbegin，endend，varvar，readread，writewrite，integerinteger，realreall符号符号 ：+ +，* *，( (，) )，: :，:=:=，; ;l控制控制 ： ( (换行符）换行符）l标识符的标识符的TokenToken: : （$id

5、,$id,标识符）如标识符）如($($id,x)id,x)l整常数的整常数的Token: ($Token: ($intCintC, ,整常数）如整常数）如 （$ $intC,5)intC,5)l实常数的实常数的Token: ($Token: ($realCrealC, ,实常数）如实常数）如 $ $realC,0.5)realC,0.5)l保留字的保留字的Token: ($begin,-),($end,-)Token: ($begin,-),($end,-)l符号词的符号词的Token: ($plus,-),($Token: ($plus,-),($multmult,-),-), ($ ($L

6、parenLparen,-),-)l换行符的换行符的Token: ($line,-)Token: ($line,-) ($begin,-) ($var,-) ($id, x) ($colon,-) ($real,-) ($semi,-) l例如下述例如下述MicroMicro的代码：的代码： begin begin varvar x : real; x : real; 经词法分析器处理后，它将转换为如下的经词法分析器处理后，它将转换为如下的 TokenToken序列：序列：v标识符和常量的处理标识符和常量的处理： 词法信息可确定，语义信息形式的确定词法信息可确定，语义信息形式的确定： a a

7、语义信息的长度有限制时，直接用语义信息的长度有限制时，直接用 标识符或常量本身标识符或常量本身 b b 没有长度限制时，构造标识符或常没有长度限制时，构造标识符或常 量表，语义信息中为其在表中的地量表，语义信息中为其在表中的地 址（字符串空间址（字符串空间节省存贮空间）节省存贮空间）v保留字的处理保留字的处理：识别保留字的方法：识别保留字的方法： 1.建立保留字表；顺序、散列、散列顺序建立保留字表；顺序、散列、散列顺序 2.拼写的同时进行判断拼写的同时进行判断 自动机自动机 v 运算符的处理运算符的处理： 不区分，统一成一类不区分，统一成一类 区分，每个运算符为一类区分，每个运算符为一类v 空

8、格符和制表符以及换行符的处理空格符和制表符以及换行符的处理 1.无用的空格符和制表符要删掉；无用的空格符和制表符要删掉； 2.字符串内的空格不能删；字符串内的空格不能删； 3.换行符不能删。用于错误定位换行符不能删。用于错误定位v 复合型特殊符，如复合型特殊符，如“:=”的处理的处理 读到读到“:”时不能判断是否为冒号，必须读下时不能判断是否为冒号，必须读下 一字符。一字符。v括号类配对预检括号类配对预检l括号类：括号类： begin begin end ,if end ,if then, , ,( ) then, , ,( )l处理方法：处理方法： 对每类括号设置一个计数器（初值对每类括号设

9、置一个计数器（初值=0=0） 每当遇到开括号，则计数器加每当遇到开括号，则计数器加1 1 每当遇到闭括号时，计数器减每当遇到闭括号时，计数器减1 1 词法分析结束时，如果计数器词法分析结束时，如果计数器 0 0，则，则 表明括号不匹配。表明括号不匹配。v字符串空间字符串空间l目的：减少冗余，节省空间，提高访问速度目的：减少冗余，节省空间，提高访问速度l方法：字符数组存放字符串，描述字符串信息：方法：字符数组存放字符串，描述字符串信息： 下标下标 长度长度 l词法错误种类：词法错误种类：l 语言不允许的符号：语言不允许的符号：# #l 括号类配对错误：括号类配对错误：l 单词的后继符错（偶尔）：单词的后继符错（偶尔）：l词法错误校正：词法错误校正：l a a 删除已被读过的字符，并重新扫删除已被读过的字符