第三章有限自动机和词法分析器
主要内容：
? 词法分析过程涉及的几个问题
? 词法分析器的生成技术
正则表达式
有限自动机
词法分析概述
? 有关词法分析器的几个问题和处理方法：
词法分析器的功能、分类
单词的分类,Token表示
保留字
空格符、制表符和换行符
复合型符号
括号类匹配预检
字符串空间
词法错误校正
词法分析结束
?词法分析器的功能
? 词法分析器功能：
? 读源程序的字符序列,逐个拼出单词,并
构造相应的内部表示 TOKEN.同时检查源程序
中的词法错误,
? 引入 Token的原因：
? 编译程序总是用某种程序语言书写的程
序，语言的操作对象只能是该语言规定的各种
数据。而编译程序的操作对象是程序中的各种
语法单位，因此，必须把它们表示成某种数据
结构形式。
词法分析器的两种形式
CharList 独 立
词法分析器 语法分析
TokenList
附 属
词法分析器
语法分析
call
Token
CharList
? Token定义
?Token表示最小的语义单位 --单词的信息。
即单词内部表示的数据结构形式。
单词不是程序设计语言中的语法概念，是编译程
序中引进的一个概念。是最小的语义单位，不能
分割
?Token中需要记录有关单词的信息：
单词的标志码 ($id,$intC,… )标识单词的种类 ---
词法信息
单词的特征属性（标识符名，符号表地址等） --
-语义信息
Micro的 单词的分类
? 标识符：字母打头的字母 /数字串
? 整常数：数字打头的数字串
? 实常数：整数,整数
? 保留字,begin,end,var,read，
write,integer,real
? 符号, +,*,(,),:,:=,;
? 控制, ? (换行符）
Micro 语言的 Token结构
? 标识符的 Token,（ $id,标识符）如 ($id,x)
? 整常数的 Token,($intC,整常数）如
（ $intC,5)
? 实常数的 Token,($realC,实常数）如
$realC,0.5)
? 保留字的 Token,($begin,-),($end,-)
? 符号词的 Token,($plus,-),($mult,-),
($Lparen,-)
? 换行符的 Token,($line,-)
($begin,-)
($var,-)
($id,x)
($colon,-)
($real,-)
($semi,-)
……
?例如下述 Micro的代码：
begin var x, real;……
经词法分析器处理后，它将转换为如下的
Token序列：
? 标识符和常量的处理,
词法信息可确定，语义信息形式的确定,
a 语义信息的长度有限制时，直接用
标识符或常量本身
b 没有长度限制时，构造标识符或常
量表，语义信息中为其在表中的地
址（字符串空间 节省存贮空间）
? 保留字的处理,识别保留字的方法：
1.建立保留字表；顺序、散列、散列＋顺序
2.拼写的同时进行判断 自动机
? 运算符的处理,
不区分，统一成一类
区分，每个运算符为一类
? 空格符和制表符以及换行符的处理
1.无用的空格符和制表符要删掉；
2.字符串内的空格不能删；
3.换行符不能删。用于错误定位
? 复合型特殊符，如,:=”的处理
读到,:”时不能判断是否为冒号，必须读下
一字符。
? 括号类配对预检
? 括号类：
begin … end,if … then,[ ],{ },( )
? 处理方法：
对每类括号设置一个计数器（初值 =0）
每当遇到开括号，则计数器加 1
每当遇到闭括号时，计数器减 1
词法分析结束时，如果计数器 ?0，则
表明括号不匹配。
? 字符串空间
? 目的：减少冗余，节省空间，提高访问速度
? 方法：字符数组存放字符串，描述字符串信息：
下标 长度
?词法错误校正
? 词法错误种类：
? 语言不允许的符号,#
? 括号类配对错误：
? 单词的后继符错（偶尔）：
? 词法错误校正：
? a 删除已被读过的字符，并重新扫
? 描未被读过的字符
? b 删除已读过的第一个字符，重新
? 扫描它的后继部分的字符。
? 校正后的标示
?词法分析的结束
? 程序结束标志 ‘,’
? 文件结束符 Eof.
主要内容：
? 词法分析过程涉及的几个问题
? 词法分析器的生成技术
正则表达式
有限自动机
词法分析概述
? 有关词法分析器的几个问题和处理方法：
词法分析器的功能、分类
单词的分类,Token表示
保留字
空格符、制表符和换行符
复合型符号
括号类匹配预检
字符串空间
词法错误校正
词法分析结束
?词法分析器的功能
? 词法分析器功能：
? 读源程序的字符序列,逐个拼出单词,并
构造相应的内部表示 TOKEN.同时检查源程序
中的词法错误,
? 引入 Token的原因：
? 编译程序总是用某种程序语言书写的程
序，语言的操作对象只能是该语言规定的各种
数据。而编译程序的操作对象是程序中的各种
语法单位，因此，必须把它们表示成某种数据
结构形式。
词法分析器的两种形式
CharList 独 立
词法分析器 语法分析
TokenList
附 属
词法分析器
语法分析
call
Token
CharList
? Token定义
?Token表示最小的语义单位 --单词的信息。
即单词内部表示的数据结构形式。
单词不是程序设计语言中的语法概念，是编译程
序中引进的一个概念。是最小的语义单位，不能
分割
?Token中需要记录有关单词的信息：
单词的标志码 ($id,$intC,… )标识单词的种类 ---
词法信息
单词的特征属性（标识符名，符号表地址等） --
-语义信息
Micro的 单词的分类
? 标识符：字母打头的字母 /数字串
? 整常数：数字打头的数字串
? 实常数：整数,整数
? 保留字,begin,end,var,read，
write,integer,real
? 符号, +,*,(,),:,:=,;
? 控制, ? (换行符）
Micro 语言的 Token结构
? 标识符的 Token,（ $id,标识符）如 ($id,x)
? 整常数的 Token,($intC,整常数）如
（ $intC,5)
? 实常数的 Token,($realC,实常数）如
$realC,0.5)
? 保留字的 Token,($begin,-),($end,-)
? 符号词的 Token,($plus,-),($mult,-),
($Lparen,-)
? 换行符的 Token,($line,-)
($begin,-)
($var,-)
($id,x)
($colon,-)
($real,-)
($semi,-)
……
?例如下述 Micro的代码：
begin var x, real;……
经词法分析器处理后，它将转换为如下的
Token序列：
? 标识符和常量的处理,
词法信息可确定，语义信息形式的确定,
a 语义信息的长度有限制时，直接用
标识符或常量本身
b 没有长度限制时，构造标识符或常
量表，语义信息中为其在表中的地
址（字符串空间 节省存贮空间）
? 保留字的处理,识别保留字的方法：
1.建立保留字表；顺序、散列、散列＋顺序
2.拼写的同时进行判断 自动机
? 运算符的处理,
不区分，统一成一类
区分，每个运算符为一类
? 空格符和制表符以及换行符的处理
1.无用的空格符和制表符要删掉；
2.字符串内的空格不能删；
3.换行符不能删。用于错误定位
? 复合型特殊符，如,:=”的处理
读到,:”时不能判断是否为冒号，必须读下
一字符。
? 括号类配对预检
? 括号类：
begin … end,if … then,[ ],{ },( )
? 处理方法：
对每类括号设置一个计数器（初值 =0）
每当遇到开括号，则计数器加 1
每当遇到闭括号时，计数器减 1
词法分析结束时，如果计数器 ?0，则
表明括号不匹配。
? 字符串空间
? 目的：减少冗余，节省空间，提高访问速度
? 方法：字符数组存放字符串，描述字符串信息：
下标 长度
?词法错误校正
? 词法错误种类：
? 语言不允许的符号,#
? 括号类配对错误：
? 单词的后继符错（偶尔）：
? 词法错误校正：
? a 删除已被读过的字符，并重新扫
? 描未被读过的字符
? b 删除已读过的第一个字符，重新
? 扫描它的后继部分的字符。
? 校正后的标示
?词法分析的结束
? 程序结束标志 ‘,’
? 文件结束符 Eof.
