第三章 词法分析
一、词法分析程序的任务
➢ 从左至右逐个字符地扫描源程序，产生一 个个单词符号。把作为字符的源程序改造为 单词符号串组成的中间程序，执行词法分析 任务的程序称为词法分析器或称扫描器。
2020/7/1
中南大学软件学院 陈志刚
4
第三章 词法分析
3.1 词法分析概述
二、词法分析程序的功能
单词种别：表示单词种类，常用整数编码，它是语 法分析需要的
单词自身的值：是编译中其他阶段所需要的信息
如果一个种别只含一个单词符号，那么该单词符号的种 别编码就完全代表它自身的值。
如果一个种别含有多个单词符号，那么还应给出该单词 符号的自身值：标识符自身值是标识符自身的字符串； 常数自身值是常数的二进制数值。
第三章 词法分析
3.1 词法分析概述 3.2 词法分析程序的设计 3.3 正规式与有限自动机 3.4 词法分析程序的实现 3.5 词法分析器的自动生成
3.1 词法分析概述
第三章 词法分析
一、词法分析程序的任务 二、词法分析程序的功能 三、词法分析程序的安排 四、词法分析程序的实现方式 五、词法分析程序的输出形式
注意：一种语言的单词如何分类、怎样编码，主要取决于技 术上的方便。
2020/7/1
中南大学软件学院 陈志刚
13
3.1 词法分析概述
五、词法分析程序的输出形式
例：若分类表为：
第三章 词法分析
试分析输入串：IF a1>0
THEN b1:=c1*d1
ELSE b1:=5
经词法分析后的输出。
2020/7/1
单词--是程序语言的基本语法符号。 如：基本字、标识符、常数、运算符、界符等。 词法分析器中单词的输出形式：
（单词类别、单词内部码值）
2020/7/1
中南大学软件学院 陈志刚
11
第三章 词法分析
3.1 词法分析概述
五、词法分析程序的输出形式
词法分析程序输出的单词符号通常用二元式表示： （单词种别，单词自身的值）
2020/7/1
中南大学软件学院 陈志刚
8
3.1 词法分析概述
第三章 词法分析
四、词法分析程序的实现方式
相对独立方式
当采用递归下降分析等技术实现一趟编译程 序时常采用这种方式。
源程序
Token
词法分析程序
语法分析程序….
get token
2020/7/1
中南大学软件学院 陈志刚
9
3.1 词法分析概述
中南大学软件学院 陈志刚
7
3.1 词法分析概述
第三章 词法分析
四、词法分析程序的实现方式
相对独立方式：把词法分析程序作为语法分析 程序的一个独立子程序。语法分析程序需要新 符号时调用这个子程序。
完全独立方式：词法分析程序作为单独一趟来 实现。词法分析程序读入整个源程序，它的输 出作为语法分析程序的输入。
常常把词法分析程序作为独立的一遍或作 为被语法分析程序所调用的子程序。
1、作为独立的一遍：
语法分析前进行词法分析，把单词符号 串形成中间文件存贮。
2020/7/1
中南大学软件学院 陈志刚
6
3.1 词法分析概述
第三章 词法分析
三、词法分析程序的安排
2、作为被语法分析器词用的子程序：
2020/7/1
2020/7/1
中南大学软件学院 陈志刚
2
3.1 词法分析概述 词法分析程序
第三章 词法分析
词法分析是编译过程中的一个阶段，在语法分 析前进行 ，也可以和语法分析结合在一起作 为一遍。
输入：源程序字符串
输出：等价的属性字序列（内部表示形式）
2020/7/1
中南大学软件学院 陈志刚Βιβλιοθήκη 33.1 词法分析概述
例2：
0
1
U
数字
非数字
3
4
=
5
0
01
+
6
0
V
Z
1
*
7
非*
8
*
9
例3：
,
10
(
11
)
12
2020/7/1
中南大学软件学院 陈志刚
其它
13
17
二、状态转换图的实现
第三章 词法分析
方法：每个结点对应一段程序，前面状态结的程 序调用其后继结点的程序。
例1：
字母
1
0
数字
2
PROCEDURE Proc0; Getchar; case char of ‘A’…‘Z’ : proc1; ‘0’…‘9’: proc2; otherwise error; end of case;
第三章 词法分析
四、词法分析程序的实现方式
完全独立方式
采用词法分析工作完全独立的原因： 简化设计，降低语法分析的复杂性 提高编译效率 增加编译系统的可移植性
属性字序列
源程序
词法分析程序
语法分析程序….
2020/7/1
中南大学软件学院 陈志刚
10
3.1 词法分析概述
第三章 词法分析
五、词法分析程序的输出形式
中南大学软件学院 陈志刚
14
3.1 词法分析概述
五、词法分析程序的输出形式
解：输出的单词串为：
第三章 词法分析
2020/7/1
中南大学软件学院 陈志刚
15
第三章 词法分析
3.2 词法分析程序的设计
一、状态转换图
状态转换图是一张有限方向图。用结点代表状态， 状态之间用箭弧连接，箭弧上的标记（字符）代表 在射出结状态下可能出现的输入字符或字符类。
一个状态转换图只包含有限个状态，有一个初态，
终态用双圈表示。一个状态转换图可识别一定的字
符串。
状态都是非终结符号
例1：
字母或数字
S：开始状态 E：终止状态，用双圈表示 I：标识符状态
S
I
E
字母 数字
2020/7/1
中南大学软件学院 陈志刚
16
一、状态转换图
空白
0
字母
第三章 词法分析
字母或数字
1 非字母或数字 2
2020/7/1
中南大学软件学院 陈志刚
12
第三章 词法分析
3.1 词法分析概述
五、词法分析程序的输出形式
语言的单词符号
单词符号是程序语言的基本语法单位，一般分为下面5种： 关键字（基本字）：（个数确定，可全体编为一类，也 可一字一类) 标识符：（个数不确定，作为一类） 常数：各种类型的常数 。(个数不确定，按类型分类) 运算符：如+、-、*、/、<等。(个数确定，一符一类) 界符：如，、；、（、）、: 等。(个数确定,一符一类)
词法分析程序主要执行以下功能： 读入源程序字符串，识别开具有独立含义的最 小语法单位——单词（符号）； 把单词变换成长度统一的且为定长的属性字；
其他功能： 滤掉空格，跳过注释、换行符 某些预加工处理
2020/7/1
中南大学软件学院 陈志刚
5
3.1 词法分析概述
三、词法分析程序的安排
第三章 词法分析