1
第三章
词法分析及词法分析程序
2
主要内容
3.1 设计扫描器时应考虑的问题
符号的内部表示、识别约定和策略、源程序的输入和预处理
3.2 正规文法和状态转换图
正规文法 —— 状态转换图，状态转换图的实现
3.3 有限自动机（ FA）
DFA,NFA以及二者的等价性；具有 ?动作的 NFA的确定化；
DFA状态数的最小化
3.4 正规表达式与正规集
正规文法 —— 正规式 —— FA
3.5 词法分析程序的实现（自学）
编写、自动生成
3
词法分析的任务
? 词法分析的任务
?扫描输入串中的字符，从中识别出具有独立意义的基本
语法单位：单词，生成单词序列。
?剥去源程序中的注释（块、行）和, 空白, 符
?预处理 —— 宏处理与文件包含
? 词法分析程序亦称为扫描器
? 设计和实现扫描器的相关问题,
?描述语言中各种单词的结构,3型文法及其正规式
?识别源程序中的各个单词：状态转换图或有限自动机
4
扫描器的功能
词法分
析器
语法分
析器
get_next_token
编译器其
它阶段
符号表
高级语言
源程序
字符流
token
单词
（流）
5
程序语言的单词（ 1）
单词 词文 模式
关键字 WHILE while while FOR for for
标识符 ID temp,i,max 字母开头的字母数字串
常数 NUM 3.14 100 数字串 {.数字串 }
单词：同类词文的总称
词文：源程序中能匹配某一记号的字符串
模式：描述用字符串构成单词的规则
6
程序语言的单词（ 2）
单词 词文 模式
运算符
MUL * *
GT > >
界符,,,
串常量 STRING ―hello‖ ?there‘ 双（单）引号中间的字符 串（不包括引号本身）
7
3.1 设计扫描器时应考虑的问题
3.1.1 词法分析的两种处理方式
? 将词法分析纳入到语法分析中进行
? 词法分析与语法分析分开来进行
– 描述单词结构比描述语法结构简单，仅用 3型文法就够了；
– 将单词识别从语法分析中分离出来，可采用更有效的工
具（状态转移图、有限自动机等）实现；
– 有些语言（如 FORTRAN）的单词识别与前后文相关，将词
法分析独立出来，有利于实现统一的语法分析；
– 使编译程序各部分独立出来，有利于设计、调试和维护
? 逻辑上的划分，不是指编译程序的执行流程
8
? 词法分析作为单独的一遍（ 多遍扫描 ）
①大部分编译时间花在扫描字符上，独立出来便于集
中处理,
② 单词的词法规则简单, 可建立特别适用于这种文法
的有效技术, 实现词法分析的自动生成,
③ 整个编译程序结构简单, 清晰, 产生中间文件, 占
内存,
? 词法分析作为一个独立的子程序, 供语法分析程序调
用 （ 单遍扫描 ）
① 语法分析调用时, 返回一个单词符号,
② 无中间文件, 省内存, 编译效率高,
两种具体的实现方式
9
3.1.2 单词符号的内部表示
— 词法分析器的输出形式
(1) 单词符号的种类
① 保留字,如 begin,end,do等用户不能使用
② 标识符,由用户定义
③ 无符号整数,如 124
④ 单字符分界符, +,－, *,/, ；,,,
（, ）,,
⑤ 双字符分界符, //,/*,*/,:=等
10
(2)单词符号的表示形式 —— 二元组
二元组,（ 单词类别, 单词自身值 ）
① 单词类别,说明单词属于哪一类, 常用助记符或
整数编码表示,
例：标识符用 4 表示
′ + ′ 用 8表示
′ * ′ 用 10表示
② 单词自身值
一种类只有一个单词, 不必给出单词自身值,因为
根据类别编码能完全确定,
一种类含有多个单词, 必须给出单词自身值予以
区别 。
11
一般,
① 保留字, 运算符和分界符都是一个符号一
种类别, 不需单词自身值,
如 ′ + ′ 类别 8,
′ + ′ 的二元组 （ 8,-）
② 标识符整体作为一个类别,其单词自身值采
用自身的字符串编码表示,
如标识符类别为 5,‘ AB’的二元组 (5,‘ AB’）
③ 常数按类型分类别：单词自身值采用自身
的 二进制 形式,
如整数类别为 20,整数 4的二元组 (20,100）
12
3.1.3 识别标识符的若干约定和策略
? 约定,
(1)标识符中的字符个数超过最大允许长度, 截去尾部,
(2)不超过最大长度的标识符, 则按, 尽可能长, 的原
则匹配,
如：如果标识符最大长度为 6,则 identifier识别为
identi,而不是 identifier;
而 NO23A可识别出 NO23A标识符,而不是 NO,23和 A
13
? 禁止关键字作为标识符的前缀的语言系统（如
标准 FORTRAN和 PASCAL）
– DO10I会识别为 DO 10 I，而不是将之识别为一个标
识符。
? 若允许关键字作为标识符的前缀（非标准
FORTRAN）
① DO99K=1,10 DO循环语句
② DO99K=1.10 变量赋值
③ IF(5.EQ.M)X=5 IF语句
④ IF(5)=55 函数赋值
14
单词符号的识别 —— 超前扫描技术
? 超前扫描技术：在无法判别和识别当前单词时, 先向
前扫描若干个字符, 直到可以进行判断和识别为止 。
? 嵌套括号的分层
– 由外向内编号：第一层，第二层,……
? 语句内容的分层
– 按包含它的括号层次确定
– 不被括号包含的语句内容称为属于第零层
– 不被括号包含的等号和逗号分别称为零层等号和零
层逗号
? 利用超前扫描到的零层等号和零层逗号来识别
单词符号
15
超前扫描技术示例
① DO99K=1,10 DO循环语句
② DO99K=1.10 变量赋值
③ IF(5.EQ.M)X=5 IF语句
④ IF(5)=55 函数赋值
? 包含零层等号的语句：赋值语句,DO语句、函数定
义语句以及某些逻辑 IF语句
? 既包含零层等号，也包含零层逗号的语句,DO语句
? 如，函数或数组赋值语句 f(a1,a2,…,an)=e
– 函数语句,f不出现在数组说明符中
– 数组赋值语句,f出现在数组说明符中
? 再如，扫描到字符 <,还需继续向前扫描
– <,<<（左移）,<=,<<=（复合赋值）
16
回退字符
? 在超前扫描结束后，还要, 回退, 字符，即将
超前扫描的字符退回输入缓冲区。
? 实现回退的数据结构：堆栈
– 回退：将要回退的字符依次压入堆栈。
– 扫描：检查堆栈是否为空，如果不为空，则从栈顶
读取后续字符，否则从输入字符串读取。
? 书中 P45程序 3-1给出了使用堆栈实现多字符
回退的算法。
17
3.1.4 源程序的输入及预处理
? 缓冲输入：将磁盘上的源程序分批送入缓冲
区，等待扫描器处理。可以提高读盘效率和
方便扫描器工作。
? 输入系统：一组完成源程序输入的函数或者
子程序，支持读盘、超前搜索、多字符回退
等操作
? Lex中的扫描缓冲区实例,P46,图 3-2
? 预处理,消除无用空白、回车、换行、制表、
注释、区分标号区、续行号（ FORTRAN）等,
18
3.2 正规文法和状态转换图
单词的描述：正规文法定义了 3型语言,常见
的单词可由正规文法定义。
单词的识别：状态转换图可用于识别 3型语言,
它是设计和实现扫描器的一种有效工具，是有
限自动机的直观图示。
19
3.2.1 由正规文法构造状态转换图
? 程序设计语言的单词都能用正规文法描述，例如，
标识符可定义为,
<标识符 >?<标识符 >字母
<标识符 >?<标识符 >数字
<标识符 > ?字母
? 若把字母、数字视为终结符，则上述产生式为左
线性文法，是正规文法。
? 若我们用 d表示 0-9间的数字，则 C语言的 <无符
号数 >的文法是右线性文法，也是正规文法（见
P48）
20
状态转换图
? 状态转换图,由一组矢线连接的有限个 结点 所
组成的有向图。
– 每个 结点 代表在识别分析过程中扫描器所处的 状态,
其中含有一个 初始状态 和若干个 终态 。在图中,状
态 用 圆圈 表示,终态 用 双层圆圈 表示。
– 状态 之间可用 有向边 连接，其上标记一字符 a??，
表示从有向边的射出状态出发，识别一字符 a后，
将进入箭头所指状态（结点）
? 凡能用正规文法描述的语言，均可 由某种有限
状态算法 ——状态转换图 进行分析。
21
由右线性文法构造状态转换图
设 G=(VN,VT,P,S)是一右线性文法，并设 |VN|=k,
则所要构造的状态转换图共有 k+1个状态 (结
点 )。用 VN中的每个符号分别标记其中的 k个
结点，且令 G的开始符 S为初态结点；余下
的一个结点作为终态结点，用 F(?VN)标记。
22
A
状态转换图的构造原则
① G的每一个非终结符号代表一结点 (状态 )
② 开始符号 S作为初始状态
设一符号 F不属于 V作为终止状态
③形如 A→aB 的规则 a
④ 形如 A→a 的规则 a
特别,A →ε 未曾在 A的射出弧中
出现过的终结符号
某些情况下也可考虑直接将 A作为终态
B
S
F
B A
A F
A F
A
23
无符号数文法举例
0,<无符号数 > ? d <余留无符号数 > | ? <小数部分 > | d
1,<余留无符号数 > ? d <余留无符号数 > | ? <十进小数 > |
E <指数部分 > | ? | d
2,<十进小数 > ? E <指数部分 > | d <十进小数 > | d
3,<小数部分 > ? d <十进小数 > | d
4,<指数部分 > ? d <余留整指数 > | + <整指数 > |
- <整指数 > | d
5,<整指数 > ? d <余留整指数 > | d
6,<余留整指数 >? d <余留整指数 > | d
d表示 0~9之间的数字
24
无符号数文法对应的状态转换图
? 例如,P48中定义的无符号数的文法对应的状态
转换图为 (化简后 ),
? 可识别的无符号数形式,dmdm-1… d0, d-1… d-n E ? dd… d
0 4 5
3
1 2 6 d,
d
d
d
d
,
E +|-
E d d
25
利用状态转换图识别符号串的方法
对于已给的字符串 w=a1a2… an,ai?VT,利用状态转换图
对 w 识别的步骤如下,
(1)从初始状态 S出发,自左至右逐个扫描 w的各个字符
(当前为 a1),此时在结点 S所射出的诸矢线中,寻找标
记为 a1的矢线 (若不存在,则表明 w有语法错误 ),读入
a1并沿矢线所指方向前进,过渡到下一状态 (设为 A1),
(2)设当前处在 Ai状态,所扫描的字符为 ai+1,在结点 Ai所
射出的诸矢线中,寻找标记为 ai+1的矢线 (若不存在,则
表明 w有语法错误 ),读入 ai+1,并进入状态 Ai+1;
(3)重复 (2),直到 w中所有字符被读完且恰好进入终态 F
时,宣告整个识别结束,w可被接受,
26
状态转换图识别的语言
? 显然,若从 初态 出发,分别沿 一切可能 的 路径 到达 终态
结点,并将路径中 矢线上所标记的字符 依次连接起来,
便得到 状态转换图 所能识别的 全部符号串,这些符号串
组成的集合构成了该 状态转换图 识别的语言。
27
状态转换图与文法推导
? 用状态转换图识别符号串 w的过程，就是为 w建立一个
推导 S?* w的过程。
? 在第一步（在初始状态 S下，扫描到 a1而过渡到下一状
态 A1），由状态转换图的构造规则可知,G中必有产生
式 S?a1A1;
? 对于识别过程的后续步骤，由状态 Ai 识别 ai+1后过渡到
Ai+1恰好对应了使用产生式 Ai ?ai+1Ai+1 。
? 最后在状态 An-1识别 an后到达终态 F，对应了使用产生
式 A ?an。
? 整个推导过程,S ?a1A1 ?a1a2A2 ?……
?a1a2… an-1An-1 ?a1a2… an
28
例,G[Z],状态转换图,
Z→0U ∣ 1V
U →1Z ∣ 1 1
V →0Z ∣ 0 0 1
初态
1 0
0
例, ω=011001
通过状态图可以确定 ω 是文法的句子,
② 此过程是一种推导过程,
Z=>0U=>01Z=>011V=>0110Z=>01100U=>011001
Z
U
V
F
29
右线性文法与状态转换图
设 G是一 右线性文法,M是相应的 状态转换图,则从前面的讨
论可以看出如下事实,
(1)在利用 M对符号串 w进行识别时,M中每次状态的转换都模拟了一
步直接推导,即识别方法 (或称分析方法 ) 是, ?” 的 ;
(2)因 右线性文法 只有形如 A?aB,A ?a的产生式，所以推导的每
一步所得句型只含一个非终结符，且必出现在句型的最右端，所
以推导是 规范推导,每步所得的句型也必为 规范句型 ；
(3)对于 M所识别的任一符号串 x,必存在 G中的一个推导 S ?* x (即有
x?L(G);反之,对于 L(G)中任一句子 y,必存在一条从初态 S到终态 F
的路径,此路径上各矢线的标记依次拼接起来所组成的符号串恰为
y。
30
由左线性文法构造状态转换图
? 设 G=(VN,VT,P,S)是一左线性文法,构造相应的状态转换
图的方法是,
首先用 VN中的非终结符标记 M的结点，其中，开始符 S
对应的结点为终态结点。引入一个新结点 R(?VN)标记初
态。矢线的连接规则为,
(1)对于 G中形如 A?a 的产生式，引矢线 R?A,且标记
为 a；
(2)对于 G中形如 A?Ba 的产生式，引矢 线 B?A，且标
记为 a。
31
由左线性文法构造状态转换图
已给文法 G=({S,U},{0,1},{S?S1 |U1,U?U0 | 0},S)
R U S 0
0
1
1
用左线性文法构造出的状
态转换图识别文法的句子
与前面的过程一样,
就识别的方法而言,属于自
底向上的分析,
以句子 00011为例,给出其
识别的的步骤,见右表,
步骤 当前状态 余留的符号串
1 R 00011
2 U 0011
3 U 011
4 U 11
5 S 1
6 S (识别结束 )
32
例,G[Z],
Z→U0 ∣ V1
U →Z1 ∣ 1
V →Z0 ∣ 0
状态转换图,
0
初态 1 1
0 0
1
R
U
V
Z
(2)状态转换图的使用
① 识别句子 (单词符号 )
例,100110通过状态图可
以确定是文法的句子,
② 识别过程对应着归约
过程
100110
U00110
Z0110
V110
Z10
U0
Z
33
识别符号串与归约过程
? 由构造状态转换图的方法可知,从初态 R
到下一状态 A的转换,对应了形如 A?a
的产生式,即将终结符 a归约成非终结符
A;
? 从状态 B转换到状态 A,对应了形如
A?Ba的产生式,即将 Ba归约为 A;
? 如此下去,直到从某状态 A转换到状态
S(终态 ),对应了形如 S ?Aa的产生式,即
将 Aa归约为开始符 S.此时归约成功,也
恰好进入了终态,即状态转换图识别了
(或接受 )该符号串,
? 前面识别 00011的例子对应的归约过程
见右图
0 0 0 1 1
U
U
U
S
S
R U S 0
0
1
1
34
3.2.2 状态转换图的实现 -状态矩阵法
? 状态转换图 可方便地用于识别单词,但是,如何让计算机
利用状态转换图来进行词法分析呢?
? 一个简单实用的方法就是将图以矩阵的形式保存在内存
中,这就是所谓的 状态矩阵法,
? 状态矩阵 以图中各个状态 S1,S2,…,Sn为行,以各个输入符
号 a1,a2,…,am为列,组成一个 n?m矩阵 B,其元素
Bij=B[Si,aj]指明扫描器此时应完成的语义动作和要转换
到的下一状态 Sk,其含义是,在 Si状态下,扫描到 aj符时,按
序偶 (Si,aj)查矩阵 B,扫描器根据 Bij的指示,先执行相应的
语义动作,再转换到下个状态 Sk,
? 若 Bij为, 出错,,则说明输入符号串有误,拒绝接受,扫描
器将调用出错处理程序进行处理
35
程序 3-2 状态矩阵驱动程序
CurStat=0;
FlagOfFS=NoneSeen; /*将终态标志置为, 未经历, */
if(CurChar==EOF) return 0;
while (CurChar != EOF){
if(Stat=TransMat[CurStat][CurChar]!=NULL) {
/*能进行状态转换 */
CurStat=Stat; advance( );
if( CurStat 是终态 ){
FlagOfFS=HasSeen; /*标记经历过的终态 */
记下输入串中当前位置及该状态相关联的动作 ;
}/*end if CurStat 是终态 */
}
36
else{ /*不能继续进行状态转换 */
if(FlagOfFS==NoneSeen) { /*未经历过 终态 */
报告词法错误 ;
略过当前词文及输入字符 ;
CurStat=0;
}
else { /*经历过 终态 */
回退到最近经历的那个终态的输入字符位置 ;
执行所记录的该终态的相关动作 ; /*执行经历过的终态 */
} /*end if FlagOfFS==NoneSeen */
} /*end if Stat !=NULL*/
}/*end while*/
37
贪心策略
? 目的是获得最长匹配单词
（ 1）若当前状态对输入符号有后继动作，则继续进行状
态转移；
（ 2）若当前状态为终态，记下该状态和当前输入字符的
位置，并继续向前扫描；
（ 3）若当前状态已无后继状态，并且此前经历过终态，
则执行曾经历的最近的终态所对应的语义动作；
（ 4）若当前状态已无后继状态，并且此前没有经历过终
态，则表明输入字符串有词法错误，报错，并略过余
下的部分词文，从状态 0开始继续下一单词的识别。
? 状态矩阵是稀疏的，应该采用紧凑的数据结构
38
识别无符号数 的语义操作
? 功能：把识别出的无符号数转换成整数（ ICON） 和实数
（ FCON）。
? 无符号数的输入形式,dmdm-1… d0, d-1… d-n E ? dd… d
可改写为 dmdm-1… d0 d-1… d-n ?10^(? dd… d -n);
? 用 w,p,n,e分别计录尾数、指数、小数位及指数的符号。
因此数值为,N=w ? 10^(e?p-n)
? 语义加工过程,
– w,p,n初值为 0,e初值为 1；
– 处理整数部分时，对于每个 di,令 w=w?10+di ;
– 处理小数部分时，对于每个 di,令 w=w?10+di ;及 n++;
– 处理指数时,E后若有 ‘ -‘号，令 e=-1；计算指数值
p=p?10+d;
– 在出口处，令 ICON=w或 FCON=w?10^(e?p-n),
39
识别 无符号数 的状态矩阵
当 前 状
态
扫 描 字 符 语 义 处 理 操 作 或 接 受 动 作 后 继 状
态
d { w = 0 ; n = 0 ; p = 0 ; e = 1 ; w = w * 1 0 + d } 1
,{ w = 0 ; n = 0 ; p = 0 ; e = 1 ; } 30
t h e r e r r o r
d { w = w * 1 0 + d ; } 1
,2
E 41
o t h e r { r e t u r n ( I C O N = w ) ; e n d
d { n + + ; w = w * 1 0 + d ; } 2
E 42
o t h e r { r e t u r n ( F C O N = w * p o w ( 1 0,e * p - n ) ) ; } e n d
d { n + + ; w = w * 1 0 + d ; } 2
3 o t h e r e r r o r
d { p = p * 1 0 + d ; } 6
+ 5
- e = - 1 ; 54
o t h e r e r r o r
d { p = p * 1 0 + d ; } 6
5 o t h e r e r r o r
d { p = p * 1 0 + d ; } 6
6 o t h e r { r e t u r n ( F C O N = w * p o w ( 1 0,e * p - n ) ) ; e n d
40
3.3 有限自动机
状态转换图 实际上是 有限自动机 的图形
表示
41
3.3.1 确定的有限自动机 DFA
? 抽象地看,状态转换图 由五个部分组成,
(1)有限个状态之集,记作 K;
(2)有限个输入符号组成的字母表,记作 ?;
(3)从 K??到 K的 转换函数 f,K???K,f(p,a)=q表示若
当前状态为 p,且输入符号为 a,则进入下一个状态为 q;
(4)S0?K,初始 (开始 )状态 ;
(5)若干个终态之集, Z(?K)
由上述五个要素组成的五元式 M=(K,?,f,S0,Z )称为
一个 确定的有限自动机 (DFA,Deterministic Finite
Automata)
由此可见,DFA实际上是状态转换图的形式描述 (数学定
义 ),状态转换图是 DFA的几何 (图形 )表示,
42
DFA的接受集
? DFA M的接受集 我们把一 DFA M所接受的符号串的
全体称为 M的接受集或 M接受的语言，记为 L(M),即
L(M)={ x | f^(S0,x) ?Z,x??* }
? M接受 (或识别 )某符号串 x??*：从初态 S0出发,经一恰
好标有 x 的路径后可达到某终态 S?Z 。 用 f^描述就是,
?S?Z,f^(S0,x)=S
? 将转换函数 f 的定义域拓广到 K??*,可以得到 f^,
(1) f^ (s,?)=s,s?K;
(2) f^ (s,aw)=f^ ( f(s,a),w),s?K,a??,w??*;
? 对于 x??*,f^(s,x)=t 的含义是,当 M从状态 s出发,依次扫
描完 x的各个符号后将进入状态 t,
? 只要 f有定义,f^与 f的效果是一致的，以后不再区分。
43
确定的有限自动机
? 确定的 FA,在状态转换的每一步，根据 FA当前的状态
及扫描的输入字符，便能 唯一地 确定 FA的下一状态。
在转换图上看，若 |?|=n，则任何结点所引出的矢线至
多有 n条，且矢线上的标记均不同。
? 例如,P51图 3-4所对应的 DFA为
M=({R,U,S},{0,1},f,R,{S}) 其中,f的定义如下：
f(R,0)=U f(U,0)=U f(U,1)=S f(S,1)=S
? 由 DFA与状态转换图的关系可知，构造状态转换图的
算法，同样适用于构造 DFA。
? 可以证明,?正规文法 G,? DFA M，使
L(M)=L(G)，反之亦然。
44
3.3.2非确定的有限自动机
? 若 在一右线性文法中同
时含有形如
U?aA U?aB U?aC
? U?aX 的产生式,
? 或 在一左线性文法中含
有多个右部相同的产生
式，如 A?Ua
B?Ua C?Ua ?
X?Ua,
? 在相应的状态转换图中，
就会出现这样的结点 U，
它具有多条标记为同一
输入符号 a的矢线
图 3-8 NFA的状态转换图
在 U状态下，输入符号为 a时，
FA的下一状态不唯一，而是
在状态集 {A,B,C,…,X} 中任选
其一。具有这种性质的 FA称
为非确定的 FA（ NFA,
Nondeterministic FA）
U
A
B
C
X
a
a
a
a
..,
45
非确定有限自动机的定义
? NFA M 也可用五元式定义,M=(K,?,f,S0,Z)，其中,K,
?,S0,Z的含义同 DFA,转换函数 f的定义为 f,K????(K),
即将 (Si,aj)映射到 K的一个子集 {Sk1,…,Skm}
? 类似地，我们可把 f的定义域拓广到 K??*,
(1) f^(S,?)={S};
(2) f^(S,aw)=f^(f(S,a),w) a??,w??*,
? 将定义域进一步扩大到 ?(K) ??*,定义
?
??
m
i
k
m
i
kkkk
wSfwaSffawSf
wSfwSSSf
i
im
1
1
),(^)),,((^),(^
:则有
),(^)},,,,({^
21
?
?
??
?
46
NFA的接受集
? 所有为 NFA M所接受的符号串之集称为 NFA M的接受
集（或识别集），记作 L(M).即
L(M)={x|f（ S0,x） ? Z ? ?,x??* }
? x??* 为 M所接受：集合 f(S0,x)中含有 Z中的元素
（终态），即至少存在一条从初态 S0到某一终态的路
径，此路径上的符号之连接恰为 x。
例 3.1 给定 M=({S,A,B,C},
{a,b},f,S,{C}),其状态转
换图见右。由图可知 M是一
NFA。
S A B
C
a
a,b
a
b
b
a
a
47
识别符号串 ababb的路径
? 注意, NFA识别输入符号串时有一个试探过程，为了能
走到终态，往往要走许多弯路（ 带回溯 ），这影响了
FA的效率。
? 能否提高其工作效率就是下一小节讨论的课题。事实
上，对任一 NFA M,总可构造一个 DFA M’，使
L(M’)=L(M)成立。这就是 NFA与 DFA的等价性 。
S A B
C
a
a|b
a
b
b
a
a
? 符号串 ababb的识别路径
S(a)?A(b)?B(a)?A(b)
?B(b)?C(接受 )。
(参见书中 P60)
48
3.3.3 NFA与 DFA的等价性
? 可将 DFA看作 NFA的特殊情况,即 DFA所接受
的语言类包含在 NFA所接受的语言类中。因
此，要证明 NFA与 DFA的等价性，只需证明
每一个 NFA都可以确定化。
? 确定化：对任意 NFA M，构造一个 DFA M’，
使得 L(M)=L(M’)。
? 思路：令 M’的某个状态与 M的某个状态子集
相对应，并使得在 M’扫描与 M相同的输入符
号时，保持对 M的状态进行跟踪（能根据 M
的状态确定 M’的状态）。
49
证明 NFA与 DFA的等价性
? 定理 3.1 对于字母表 ?上的任一 NFA M，必存
在与 M等价的 DFA M’ 。
? 证明 设 M=(K,?,f,S0,Z) 是 ?上的 NFA，现构造 ?上
DFA M’=（ K’,?,f’,S0’,Z’).方法如下,
1.K’=?(K).为表示方便,如 K某子集为 {S1,S2,…,Si},
记相应的状态为 [S1,S2,…,Si].特别地,令 S0’=[S0],
2.映射 f’的定义,
f’([S1,S2,…,Si],a)=[R1,R2,…,Rj] iff
f({S1,S2,…,Si},a)={R1,R2,…,Rj}
3.M’的终态集 Z’={[Sp,Sq,…,Sr]|[Sp,Sq,…,Sr]?
K’并且 {Sp,Sq,…,Sr}?Z??}
50
现在,证明 M’与 M等价的等价性,为此,对输入符号串 |x|=n
的长度进行 归纳,以证明如下论断,
f(S0,x)= {S1,S2,…,Si} ?
f’(S0’,x)=[S1,S2,…,Si] (S0’=[S0])
当 |x|=0 (即 x=?)时,由于总有 f(S0,?)={S0},f’(S0’,?)=S0’,即
f’([S0],?)=[S0],故论断成立,
设对于长度小于或等于 m的任何输入串 x论断均成立,即
f(S0,x)={S1,S2,…,Si}?f’([S0],x)=[S1,S2,…,Si]
现证明对于输入串 xa,其中,|x|=m,a?? 论断也成立,即
f(S0,xa)={R1,R2,…,Rj} ?
f’([S0],xa)=[R1,R2,…,Rj]
51
f(S0,xa)= f(f(S0,x),a)=f({S1,S2,…,Si},a)
={R1,R2,…,Rj}
f’(S0’,xa)=f’(f’(S0’,x),a)=f’([S1,…,S i],a) (归纳假设 )
=[R1,…,R j] (f’的构造定义 )
? 最后,若 f(S0,x)?Z?? 及由 Z’的定义,f’(S0,x)?Z’.即
x ?L(M) ? x ?L(M’) 得证。由于 NFA与 DFA是等价的,
今后统称 FA,
? 还应指出，确定化时所得的 DFA的状态数是很大的，
往往有许多无用状态（ 即那些从初态 S0不可达的状态
或那些从其出发不能到达终态的状态 ），这些状态可
从 DFA中删除。
52
NFA确定化的例子
例 3.2 M=({S0,S1},{a,b},f,S0,{S1})
S0 S1
a
b
b a|b 构造 M的 DFA M’=(K’,{a,b},f’,[S0],Z’}),
其中 K’={[S0],[S1],[S0,S1],?}
f’([S0],a)=[S0,S1] f’([S0],b)=[S1]
f’([S1],a)= ? f’([S1],b)=[S0,S1]
因为 f({S0,S1},a)= f(S0,a)? f(S1,a)= {S0,S1}
f({S0,S1},b)= f(S0,b)? f(S1,b)= {S0,S1}
所以 f’([S0,S1],a)= f’([S0,S1],b)=[S0,S1]
_f_|_a____ b___
S0 |{S0,S1} {S1}
S1 | ? {S0,S1}
53
NFA确定化的例子（续）
f’(?,a)= f’(?,b)= ?
f’ | a b | new state
? | ? ? |
[S0] | [S0,S1] [S1] | 1
[S1] | ? [S0,S1] | 2
[S0,S1]| [S0,S1] [S0,S1] | 3
Z’= {[S1],[S0,S1]}
M’=(K’,{a,b},f’,[S0],{[S1],[S0,S1]})
1 2
3
a b
b|a
b
54
3.3.4 具有 ? 动作的 FA
? 若在一 FA中,允许对 ?也作状
态转移,则这样的 FA称为具有
?动作的 FA,
? 右图就是一个 具有 ?动作的
FA。 其中,有的矢线上标记
为 ?（ 在此看作一个符号 ）。
标记为 ? 的矢线 对识别符号
串无影响,但却 改变了当前的
状态,
0 1
2
3
?
?
?
a b
b
c
例如,上图的 FA中,从状态 0到状态 3存在路径,
0(a)?0(a)?0(?)?2(c)?2(c)?2(?)?3,
即 M识别了 aa?cc?=aacc,
55
具有 ? 动作的 FA的定义
? 具有 ? 动作的 FA 定义为 M=(K,?,f,S0,Z),其中,f定义
为 f:K?(??{?})??(K),
? 在 具有 ? 动作的 FA中,?视为一个 输入符号,在矩阵表
示中,也有相应的列 。 例如，对于前面 具有 ? 动作 的
FA，相应的状态转换矩阵如 P63表 3-2所示。
? 同理可以定义 f^:K??*??(K),f^(S,x)是由这
样的状态 q组成,存在从 S到 q的路径,该路径上矢线
的标记组成的符号串恰好为 x,标记中可以包含若
干个 ?。
56
状态 S的 ?-闭包,?-CLOSURE(S)
? 状态 S的 ?-闭包,记为 ?-CLOSURE(S),它是从 S出发经过
若干标记为 ?的矢线所能达到的全部状态之集，其归纳定
义如下,
(1)S??-CLOSURE(S);
(2)设 Sj??-CLOSURE(S),且 Sj ?? Sk,则 Sk??-CLOSURE(S);
(3)重复使用规则 （ 2） 所得的集合为 ?-CLOSURE(S),
? ?-CLOSURE还可定义在状态集上，设 Q?K,则
?
QS
SC L O S U R EQC L O S U R E
?
????? )()(
57
?-CLOSURE示例
? 例 如,对于右图的 NFA,
?-CLOSURE(0)={0,1,2,3}；
?-CLOSURE(1)={1}；
?-CLOSURE(2)={2,3}；
?-CLOSURE(3)={3},
0 1
2
3
?
?
?
a b
b
c
58
转换函数 f和 f^ 的拓广
? 利用 ?-CLOSURE(S),可定义 f^如下,
?
?
?
Rq
Rq
wSfq
wqfwRf
aqfaRf
KRKRKKf
KKf
ffaqfawSffP
PC L O S U R EwaSf
SC L O S U R ESf
waKS
?
?
?
?
?
??????
????
??
??
??
??????
),(),(^)4(
),(),(3
)(:^
}{:
^)2(),()),,(^(,
);(),(^)2(
);(),(^)1(
,,
*
),(^
*
）（
有：）（）。对（）（
）和（）（）（定义分别拓广到
的及将。其中
???
???
?
??
59
f与 f^的区别
? 由 f^的定义可知,f^(S,a) 与 f(S,a) 不同,f^(S,a)是从 S
出发经过路径 a所达的状态集（可走若干步）；而
f(S,a)是从 S出发经过矢线 a所达的状态集（只走一步）
? 显然,f(S,a) 只走一步 a矢线
? ?-CLOSURE(f(S,a)) 多步，第一步必须走 a矢线
? f^(S,a) 路径 a, 第一步可以是 ?矢线
? ?-NFA的接受集, L(M)={w|f^(S0,w)?Z??}
60
f与 f^的计算示例
? 例如，在右图的 NFA中,
f(0,?)={1,2}; f(0,a)={0} ?是输入符号
f^(0,?)= ?-CLOSURE(0)={0,1,2,3};
? 是符号串
0 1
2
3
?
?
?
a b
b
c
f^(0,a)= ?-CLOSURE(f(f^(0,?),a))= ?-CLOSURE(f({0,1,2,3},a))
= ?-CLOSURE(f(0,a)?…?f(3,a))= ?-CLOSURE({0})={0,1,2,3}
f^(0,ac)= ?-CLOSURE(f(f^(0,a),c))= ?-CLOSURE(f({0,1,2,3},c))
= ?-CLOSURE(f(0,c)?…?f(3,c))= ?-CLOSURE({2})={2,3}
61
?-NFA的用途：构造更复杂的 FA
? 有了 ?-NFA，就可把识别各种不同单词的 FA用 ?矢线
（并连）连接起来，组成一个单一的 NFA，经确定化
后可得识别所有单词的 DFA，由此可设计编译程序的
词法分析器。
? 例如，某语言的单词有,
1.BEGIN 2.END 3.IF 4.THEN 5.ELSE
6.标识符 7.无符号整数 8,< 9,<= 10,=
11.<> 12,> 13.>=
可分别构造出识别各类单词的 FA,然后将其合并为一
个大 FA,如书中 P65图 3-11所示。
62
3.3.5具有 ?动作的 NFA的确定化
? 为具有 ?动作的 NFA M=(K,?,f,S0,Z)构造相应的 DFA
M’=(K’,?,f’,q0,Z’)
? 基本思路：从 M的初始状态 S0出发，仅经过任意条
矢线所能到达的状态集合作为 M’的初态 q0 ；然后从
q0出发，将对输入符号 a??进行状态转移所能到达
的状态（包括转移后再经过 ?矢线所能到达的状态）
所组成的集合作为 M’的状态，如此反复，直到无新
状态产生为止。
63
构造 K’,f’和 Z’的递归过程
1,令 K’={[?-CLOSURE(S0)]}; f’=? ;
2,对 K’中尚未被标记的状态 qi=[Si1,Si2,…,Sim],
(1)标记 qi;
(2)对于每个 a??,令 Ta=f({Si1,Si2,…,Sim},a); 对 a转移
令 qj= [?-CLOSURE(Ta)]; 进行 ?矢线转移
(3)若 qj?K’,则令 K’=K’?{qj };
(4)令 f’=f’ ?{f’(qi,a)= qj };
3,重复 2.,直到 K’中无未标记的状态 ;
4,令 Z’={qj | qj ? Z??} (这里把 qj 视为集合 )
64
确定化具有 ?动作的 NFA的例子
例 3.4 考虑右图具有 ?动作的 NFA
1.q0 = [?-CLOSURE(0)]
=[0,1,2,3]==>K’;
2.q0未标记,故
(1)标记 q0;
0 1
2
3
?
?
?
a b
b
c
(2)f’(q0,a)=[?-CLOSURE(f({0,1,2,3},a))]
=[?-CLOSURE({0})] = q0;
f’(q0,b)=[?-CLOSURE(f({0,1,2,3},b))]
=[?-CLOSURE({1,3})] = [1,3]= q1 ==>K’;
f’(q0,c)= [?-CLOSURE(f({0,1,2,3},c))]
=[?-CLOSURE({2})] = [2,3]= q2 ==>K’;
65
确定化具有 ?动作的 NFA的例子 (续 )
3,K’={q0,q1,q2},q1,q2 没有标记,
(1) 标记 q1;
(2) f’(q1,a)=[?-CLOSURE(f({1,3},a))]=?
f’(q1,b)=… =q1; f’(q1,c)=… = ?;
4,q2 没标记,(1) 标记 q2;
(2) f’(q2,a)=[?-CLOSURE(f({2,3},a))]=?；
f’(q2,b)=?; f’(q2,c)=q2;
K’不再增大，且所有的状态都已被标记,Z’={q0,q1,q2}，
最后的 DFA M’ 如下所示,
q1 q0 q2
a
b
b
c
c
0 1
2
3
?
?
?
a b
b
c
66
NFA的确定化示例
? 需要说明的是,上述算法也适合于不含 ?产生式的 NFA
的确定化,
? 例 3.5 对于书中图 3-11所示的 NFA利用上述算法所得
的 DFA如 P67图 3-13所示,
– 其中,圆圈中的数字是原 NFA的状态编号,在图 3-13
中,q0={0,1,7,11,14,19,24,26,28,30,33,35,40},
– 标有, #”的状态为特殊状态,在该状态下,若遇非弧
线上出现的字符,则转到状态 25,
67
3.3.6 DFA状态数的最小化
? 对于一 DFA来说,其状态数可能并不是最小的,原因是
DFA中有些状态是, 等价, 的,为得到高效率的 DFA,需
将这些, 等价, 状态合并,这就是 DFA的最小化,
? DFA M的最小化, 构造等价的 DFA M’其状态数达到最小,
? 可区分状态, 设 s,t?K,s,t由某 w??*所区分 iff
( f(s,w)?Z ? f(t,w)?Z ) ? ( f(s,w)?Z ? f(t,w)?Z )
若 ?w??*,f(s,w)?Z ? f(t,w)?Z,则 s与 t不可区分，称
二者等价。
? 确定了等价状态，就可以对其进行合并。
68
DFA最小化算法
? 基本思想, 将 M的状态集 K逐步地进行划分,以期将 K
划分为满足等价关系的等价类：使得在同一类中的
状态不可区分 ;在不同类中的状态可区分,算法如下,
1,先将状态集 K按终态和非终态划分为两个子集 Z和 K-
Z,显然分属于这两个集合的状态是可 (被 ?)区分的,记
?={Z,K-Z},
2,设当前的划分 ?中已含有 m个子集,?={I1,I2,…,Im},其
中,属于不同子集 Ii和 Ij (i?j)的状态是可区分的,而属于
同一子集 Ii中的状态是待区分的,现对每个子集
Ii={Si1,Si2,…,Sin}中的各状态 Sir(Sir?K,1? r ?n )进行
考查,看其是否可区分,
69
DFA最小化算法 (续 )
对于 Sip,Siq ?Ii,若存在 a??,使得 f(Sip,a)=Su?Ij,f(Siq,a)
=Sv?Ik（ 即经过 a转换后落在不同的等价类中 ），则根
据 Su和 Sv被某个 w所区分可知,Sip 和 Siq 可被 aw 区分,
f(Sip,aw)=f(Su,w)，而 f(Siq,aw)= f(Sv,w),且 Su与 Sv
可区分,将 Ii细分,使其落入不同的更小的子集中,得到新
划分 ?new,（ 细分 Ii的方法见下页）。
3.若 ?new,不等于 ?,则令 ? =?new,转 2,
4.对于最终的 ?，从每个划分块 Ii中任选一状态为代表，
构成 K’。若 Ii中含有初态，则其代表也为初态；若 Ii
?Z??，则 Ii 的代表 ?Z’。 删除非代表状态，将引入非
代表状态的矢线引向代表状态,
70
细分划分块的方法
.
),(,,,,
,
),(),(,,
21
中同一子集落入
使得个更小的子集分为
则将个不同的子集中的状态分别落入若
令对每个子集
?
?
aIfIIIpI
pI
aSfaIfIaI
jp
i
iiiii
a
i
IS
i
a
ii
?
?
?
?????
.),(
,),(,
可区分有意义的状态它任何使
与其则无意义使得若某状态
i
i
Iqaqf
papfIp
?
?
71
DFA最小化的例子
1,?={{0,1,2,3},{4}}
{0,1,2,3}a={1} 未区分 ;
{0,1,2}b={2,3},{3}b={4},所以 3与
0,1,2 可区分 ; ?={{0,1,2},{3},{4}}
2,{0,1,2}a={1},未区分 ;
{0,2}b={2},{1}b={3},1与 0,2可区分 ;
?={{0,2},{1},{3},{4}};
3,{0,2}a={1},{0,2}b={2} 不可区分,
?new=?.结束,
0 1 3 4 a
a
a
b
a b
b
b
定理 3.2 具有 最小状态数的 DFA在同构意义下是唯一的,
0 1 3
2
4
a
a
a
a
a
b
b
b
b
b
接受句子：以 abb为后
缀的 a,b符号串
72
3.4正规表达式与正规集
到目前为止,我们已了解了对于任意三型语言 L(G),存在
FA M使 L(M)=L(G),反之,对于任意的 M,存在正规文法 G,
使 L(G)=L(M).这称为描述语言的等价性,
本节将引入 正规表达式 的概念,它们可用于描述三型语
言的特征,特别是对自动生成词法分析程序而言，它是
非常有用的工具。
所谓 正规表达式 就是用特定的 运算符 （ *,?,| 等）及
运算对象 按某种规则构造的表达式，它可以用于描述
给定三型语言的所有句子。 正规表达式 所描述的句子
集合 (语言 )称为 正规集 。
73
3.4.1正规表达式及正规集的定义
? 定义 设 ?是一字母表,则 ?上的 正规表达式 (正则表达式,
正规式 )及其表示的 正规集 可递归定义如下,
(1) ?是一正规式,相应的正规集为 ?;
(2) ?是一正规式,相应的正规集为 {?};
(3) ?a??,a 是一正规式,相应的正规集为 {a};
(4) 设 r,s是正规式,且它们所表示的正规集为 Lr,Ls,则
1,(r) ?(s)是正规式,相应的正规集为 Lr?Ls;
2,(r)|(s)是正规式,相应的正规集为 Lr? Ls;
3,(r)*是正规式,相应的正规集为 Lr*
有限地使用上面的规则 (4),所得的表达式均是正规式,
74
有关正规式及正规集的说明
定义中的括号主要用于规定运算顺序。一般规定
优先级从高到低依次为 *,?,|，则可以省略某些
括号,例如 (r) ?((s)*)|(r) 可简写为 r ?s*|r。另外,?
常常可省略不写，进一步写成 rs*|r。
75
正规式与正规集的例子
},,,{}{}{
00
* ??? aaaaaa
i
i
i
i ???
?
?
?
?
正规集正规式
aa* {a,aa,aaa,…}
a|b {a,b}
a|ba* {a,b,ba,baa,baaa,…}
(a|b)*abb 任何以 abb结尾的 a,b符号串
(aa|ab|ba|bb)* 空串或者任意长度为偶数的 a,b符号串
(a|b)(a|b)(a|b)* 长度大于等于 2的 a,b符号串
76
? 给定正规式,它唯一确定一正规集 ;反之不真,即一个正
规集可由多个不同的正规式表示,如,(a|b)*和 (a*b*)*，
b(ab)*和 (ba)*b表示相同的正规集。
? 若二正规式描述同一正规集,则称二式 等价 (相等 )
? 正规式间的基本等价关系,
A1,r|s=s|r A2,r|r=r
A3,r|?=r A4,(r|s)|t=r|(s|t)
A5,(rs)t=r(st) A6,r(s|t)=rs|rt
A7,(s|t)r=sr|tr A8,r?=?r=?
A9,r?=?r=r A10,r*=(?|r)*=?|rr*
77
3.4.2 由正规文法构造相应的正规式
? 对于给定的三型文法 G,如何构造正规式 r,使 Lr=L(G)
? 方法, 将正规文法 G看作是非终结符作为变量的联立方
程组,通过解方程组求得相应的正规式,
? 例,正规文法 G,S?aS | bA | b； A?aS。假设 S,A所
产生的正规集分别为 LS,LA，则有,
LS={a} ? LS ? {b} ? LA ? {b}； LA ={a} ? LS
由定义可知,L(G)= LS。用 S,A代表 LS和 LA的正规式，
并用 ‘ +’ 代替 ‘ |’,则上述 关系可以改写为,
S=aS + bA + b （ 1）
A=aS （ 2）
将 (2)代入 (1),得 S=aS + baS + b = (a+ba) S +b (3)
? 上述问题转化为求解形如 X= ?X + ? 的方程,
78
求解形如 X= ?X + ? 的方程
关于这类方程有如下 论断,
论断 3.1 方程 X= ?X + ? 有解 X= ?*? (不唯一 )
证, 将 X= ?*? 代入方程右边,
右边 = ??*?+ ?=(??*+?) ?= ?*?=左边
由论断 3.1可知,方程 S=aS+baS+b=(a+ba)S+b的解为
S=(a+ba)*b=(a|ba)*b,
另外,对 S=aS+baS+b连续使用两次论断 3.1,有
S=a*(baS+b)=a*baS+a*b=(a*ba)*a*b
可得一等式, (a|ba)*b = (a*ba)*a*b
? 文法的状态转换图如右,S A
F
a
a
b
b
79
正规式求解示例
? 例如,S?aA； A?bA | aB | b； B?aA
相应的方程组为,S=aA (1)
A=bA+aB+b (2)
B=aA (3)
(3)代入 (2),A=(b+aa)A+b
得 A=(b+aa)*b
代入 (1),S=a(b+aa)*b=a(b|aa)*b
A
B
F
a
a
b
b S
a
80
左线性文法 正规式的求解
? 对于左线性文法,在解联立方程时最终会得到形如
X=X?+?的方程,类似于论断 3.1,可知其有解 X=??*
? 例, 标识符的文法为, I?Id |Il |l
相应的方程为 I=I(d+l)+l
解为, I= l(d+l)* =l(d|l)*
? 在正规式的实际应用中,人们还引入了许多新的运算符,
如正闭包‘ +‘,限制重复次数的‘ {m,n}‘,可选符‘?‘,字
符类‘ [ ]‘,首符号‘ ^‘,尾符号‘ $‘等,这里不再赘述,
81
3.4.3 正规式构造 FA? Thompson法
? 对于 ?正规式 r,?FA M,使 L(M)=Lr
? 构造方法, 根据正规式运算的递归定义,按 运算符的个
数 n,归纳地构造出 FA M。 M只含一个初态,一个终态,
且终态无矢线射出，可能包含若干条 ?矢线。
? 设 r 为 ?上的正规式,且含 n个运算符,构造 M的方法如下,
1.当 n=0时，则有 r=?或 r=? 或 r=a??，相应的 FA分别
如下,
r=? r=? r=a??
S f f S f
a
82
Thmopson 法 (续 )
2,假设当 n=1,2,…,k -1时,M均可构造。当 n=k时,根据正规
式的定义,r只能是 r1|r2,r1?r2,r1*这三种形式之一。其
中,r1和 r2 中共含 k-1个运算符,且设相应的自动机为
M1=(K1,?1,f1,S01,{Sf1}) L(M1)=Lr1
M2=(K2,?2,f2,S02,{Sf2}) L(M2)=Lr2
并且 K1?K2=?。分情况讨论,
? M
1 S01 Sf1
M2 S02 Sf2
S0 Sf
?
? ?
(1) r= r1|r2,引入新开始状态 S0,终态 Sf,将 M1,M2并联,
M=(K1?K2 ?{S0,Sf},?1??2,f,S0,{Sf})
83
Thmopson 法 (续 )
(3) r=r1*,引入新开始状态 S0,终态 Sf,令原 M1构成循环
M=(K1?{S0,Sf},?1,f,S0,{Sf})
M1 S01 Sf1 M2 S02 Sf2
?
(2) r=r1?r2,将 M1,M2串联,
M=(K1?K2,?1??2,f,S01,{Sf2})
?
? M1 S
01 Sf1 S0 Sf
?
?
84
Thmopson 法 举例
? 由正规式 a(b|aa)*b 构造相应的 FA过程。令 r1=a,
r2=b|aa,r3 = b,则 a(b|aa)*b= r1r2*r3,相应的 FA构造过
程如下,
（ 1）对 r2=b|aa构造 FA，可得,
?
S1
S3
S7 S8
?
? ?
S2
S5 S4
b
S6 ? a a
85
Thmopson 法 举例 (续 )
（ 2）对 r2*构造 FA，可得,
? S
1
S3
S7
?
? ?
S2
S5 S4
b
S6 ? a a
S8 S9
?
S10 ? ?
?
86
Thmopson 法 举例 (续 )
(3)对 r1r2*r3构造 FA，可得,
? S
1
S3
S7
?
? ?
S2
S5 S4
b
S6 ? a a
S8 S9
?
? ?
?
S10 S14 S13 S11 S12 a ?
? b
A
B
F
a
a
b
b S
a
S7
?
S4
b
a a
S8
?
S14 S11
a b
将 S7和 S8合并可以得到最初的状态转换图，如右上所示。
第三章
词法分析及词法分析程序
2
主要内容
3.1 设计扫描器时应考虑的问题
符号的内部表示、识别约定和策略、源程序的输入和预处理
3.2 正规文法和状态转换图
正规文法 —— 状态转换图，状态转换图的实现
3.3 有限自动机（ FA）
DFA,NFA以及二者的等价性；具有 ?动作的 NFA的确定化；
DFA状态数的最小化
3.4 正规表达式与正规集
正规文法 —— 正规式 —— FA
3.5 词法分析程序的实现（自学）
编写、自动生成
3
词法分析的任务
? 词法分析的任务
?扫描输入串中的字符，从中识别出具有独立意义的基本
语法单位：单词，生成单词序列。
?剥去源程序中的注释（块、行）和, 空白, 符
?预处理 —— 宏处理与文件包含
? 词法分析程序亦称为扫描器
? 设计和实现扫描器的相关问题,
?描述语言中各种单词的结构,3型文法及其正规式
?识别源程序中的各个单词：状态转换图或有限自动机
4
扫描器的功能
词法分
析器
语法分
析器
get_next_token
编译器其
它阶段
符号表
高级语言
源程序
字符流
token
单词
（流）
5
程序语言的单词（ 1）
单词 词文 模式
关键字 WHILE while while FOR for for
标识符 ID temp,i,max 字母开头的字母数字串
常数 NUM 3.14 100 数字串 {.数字串 }
单词：同类词文的总称
词文：源程序中能匹配某一记号的字符串
模式：描述用字符串构成单词的规则
6
程序语言的单词（ 2）
单词 词文 模式
运算符
MUL * *
GT > >
界符,,,
串常量 STRING ―hello‖ ?there‘ 双（单）引号中间的字符 串（不包括引号本身）
7
3.1 设计扫描器时应考虑的问题
3.1.1 词法分析的两种处理方式
? 将词法分析纳入到语法分析中进行
? 词法分析与语法分析分开来进行
– 描述单词结构比描述语法结构简单，仅用 3型文法就够了；
– 将单词识别从语法分析中分离出来，可采用更有效的工
具（状态转移图、有限自动机等）实现；
– 有些语言（如 FORTRAN）的单词识别与前后文相关，将词
法分析独立出来，有利于实现统一的语法分析；
– 使编译程序各部分独立出来，有利于设计、调试和维护
? 逻辑上的划分，不是指编译程序的执行流程
8
? 词法分析作为单独的一遍（ 多遍扫描 ）
①大部分编译时间花在扫描字符上，独立出来便于集
中处理,
② 单词的词法规则简单, 可建立特别适用于这种文法
的有效技术, 实现词法分析的自动生成,
③ 整个编译程序结构简单, 清晰, 产生中间文件, 占
内存,
? 词法分析作为一个独立的子程序, 供语法分析程序调
用 （ 单遍扫描 ）
① 语法分析调用时, 返回一个单词符号,
② 无中间文件, 省内存, 编译效率高,
两种具体的实现方式
9
3.1.2 单词符号的内部表示
— 词法分析器的输出形式
(1) 单词符号的种类
① 保留字,如 begin,end,do等用户不能使用
② 标识符,由用户定义
③ 无符号整数,如 124
④ 单字符分界符, +,－, *,/, ；,,,
（, ）,,
⑤ 双字符分界符, //,/*,*/,:=等
10
(2)单词符号的表示形式 —— 二元组
二元组,（ 单词类别, 单词自身值 ）
① 单词类别,说明单词属于哪一类, 常用助记符或
整数编码表示,
例：标识符用 4 表示
′ + ′ 用 8表示
′ * ′ 用 10表示
② 单词自身值
一种类只有一个单词, 不必给出单词自身值,因为
根据类别编码能完全确定,
一种类含有多个单词, 必须给出单词自身值予以
区别 。
11
一般,
① 保留字, 运算符和分界符都是一个符号一
种类别, 不需单词自身值,
如 ′ + ′ 类别 8,
′ + ′ 的二元组 （ 8,-）
② 标识符整体作为一个类别,其单词自身值采
用自身的字符串编码表示,
如标识符类别为 5,‘ AB’的二元组 (5,‘ AB’）
③ 常数按类型分类别：单词自身值采用自身
的 二进制 形式,
如整数类别为 20,整数 4的二元组 (20,100）
12
3.1.3 识别标识符的若干约定和策略
? 约定,
(1)标识符中的字符个数超过最大允许长度, 截去尾部,
(2)不超过最大长度的标识符, 则按, 尽可能长, 的原
则匹配,
如：如果标识符最大长度为 6,则 identifier识别为
identi,而不是 identifier;
而 NO23A可识别出 NO23A标识符,而不是 NO,23和 A
13
? 禁止关键字作为标识符的前缀的语言系统（如
标准 FORTRAN和 PASCAL）
– DO10I会识别为 DO 10 I，而不是将之识别为一个标
识符。
? 若允许关键字作为标识符的前缀（非标准
FORTRAN）
① DO99K=1,10 DO循环语句
② DO99K=1.10 变量赋值
③ IF(5.EQ.M)X=5 IF语句
④ IF(5)=55 函数赋值
14
单词符号的识别 —— 超前扫描技术
? 超前扫描技术：在无法判别和识别当前单词时, 先向
前扫描若干个字符, 直到可以进行判断和识别为止 。
? 嵌套括号的分层
– 由外向内编号：第一层，第二层,……
? 语句内容的分层
– 按包含它的括号层次确定
– 不被括号包含的语句内容称为属于第零层
– 不被括号包含的等号和逗号分别称为零层等号和零
层逗号
? 利用超前扫描到的零层等号和零层逗号来识别
单词符号
15
超前扫描技术示例
① DO99K=1,10 DO循环语句
② DO99K=1.10 变量赋值
③ IF(5.EQ.M)X=5 IF语句
④ IF(5)=55 函数赋值
? 包含零层等号的语句：赋值语句,DO语句、函数定
义语句以及某些逻辑 IF语句
? 既包含零层等号，也包含零层逗号的语句,DO语句
? 如，函数或数组赋值语句 f(a1,a2,…,an)=e
– 函数语句,f不出现在数组说明符中
– 数组赋值语句,f出现在数组说明符中
? 再如，扫描到字符 <,还需继续向前扫描
– <,<<（左移）,<=,<<=（复合赋值）
16
回退字符
? 在超前扫描结束后，还要, 回退, 字符，即将
超前扫描的字符退回输入缓冲区。
? 实现回退的数据结构：堆栈
– 回退：将要回退的字符依次压入堆栈。
– 扫描：检查堆栈是否为空，如果不为空，则从栈顶
读取后续字符，否则从输入字符串读取。
? 书中 P45程序 3-1给出了使用堆栈实现多字符
回退的算法。
17
3.1.4 源程序的输入及预处理
? 缓冲输入：将磁盘上的源程序分批送入缓冲
区，等待扫描器处理。可以提高读盘效率和
方便扫描器工作。
? 输入系统：一组完成源程序输入的函数或者
子程序，支持读盘、超前搜索、多字符回退
等操作
? Lex中的扫描缓冲区实例,P46,图 3-2
? 预处理,消除无用空白、回车、换行、制表、
注释、区分标号区、续行号（ FORTRAN）等,
18
3.2 正规文法和状态转换图
单词的描述：正规文法定义了 3型语言,常见
的单词可由正规文法定义。
单词的识别：状态转换图可用于识别 3型语言,
它是设计和实现扫描器的一种有效工具，是有
限自动机的直观图示。
19
3.2.1 由正规文法构造状态转换图
? 程序设计语言的单词都能用正规文法描述，例如，
标识符可定义为,
<标识符 >?<标识符 >字母
<标识符 >?<标识符 >数字
<标识符 > ?字母
? 若把字母、数字视为终结符，则上述产生式为左
线性文法，是正规文法。
? 若我们用 d表示 0-9间的数字，则 C语言的 <无符
号数 >的文法是右线性文法，也是正规文法（见
P48）
20
状态转换图
? 状态转换图,由一组矢线连接的有限个 结点 所
组成的有向图。
– 每个 结点 代表在识别分析过程中扫描器所处的 状态,
其中含有一个 初始状态 和若干个 终态 。在图中,状
态 用 圆圈 表示,终态 用 双层圆圈 表示。
– 状态 之间可用 有向边 连接，其上标记一字符 a??，
表示从有向边的射出状态出发，识别一字符 a后，
将进入箭头所指状态（结点）
? 凡能用正规文法描述的语言，均可 由某种有限
状态算法 ——状态转换图 进行分析。
21
由右线性文法构造状态转换图
设 G=(VN,VT,P,S)是一右线性文法，并设 |VN|=k,
则所要构造的状态转换图共有 k+1个状态 (结
点 )。用 VN中的每个符号分别标记其中的 k个
结点，且令 G的开始符 S为初态结点；余下
的一个结点作为终态结点，用 F(?VN)标记。
22
A
状态转换图的构造原则
① G的每一个非终结符号代表一结点 (状态 )
② 开始符号 S作为初始状态
设一符号 F不属于 V作为终止状态
③形如 A→aB 的规则 a
④ 形如 A→a 的规则 a
特别,A →ε 未曾在 A的射出弧中
出现过的终结符号
某些情况下也可考虑直接将 A作为终态
B
S
F
B A
A F
A F
A
23
无符号数文法举例
0,<无符号数 > ? d <余留无符号数 > | ? <小数部分 > | d
1,<余留无符号数 > ? d <余留无符号数 > | ? <十进小数 > |
E <指数部分 > | ? | d
2,<十进小数 > ? E <指数部分 > | d <十进小数 > | d
3,<小数部分 > ? d <十进小数 > | d
4,<指数部分 > ? d <余留整指数 > | + <整指数 > |
- <整指数 > | d
5,<整指数 > ? d <余留整指数 > | d
6,<余留整指数 >? d <余留整指数 > | d
d表示 0~9之间的数字
24
无符号数文法对应的状态转换图
? 例如,P48中定义的无符号数的文法对应的状态
转换图为 (化简后 ),
? 可识别的无符号数形式,dmdm-1… d0, d-1… d-n E ? dd… d
0 4 5
3
1 2 6 d,
d
d
d
d
,
E +|-
E d d
25
利用状态转换图识别符号串的方法
对于已给的字符串 w=a1a2… an,ai?VT,利用状态转换图
对 w 识别的步骤如下,
(1)从初始状态 S出发,自左至右逐个扫描 w的各个字符
(当前为 a1),此时在结点 S所射出的诸矢线中,寻找标
记为 a1的矢线 (若不存在,则表明 w有语法错误 ),读入
a1并沿矢线所指方向前进,过渡到下一状态 (设为 A1),
(2)设当前处在 Ai状态,所扫描的字符为 ai+1,在结点 Ai所
射出的诸矢线中,寻找标记为 ai+1的矢线 (若不存在,则
表明 w有语法错误 ),读入 ai+1,并进入状态 Ai+1;
(3)重复 (2),直到 w中所有字符被读完且恰好进入终态 F
时,宣告整个识别结束,w可被接受,
26
状态转换图识别的语言
? 显然,若从 初态 出发,分别沿 一切可能 的 路径 到达 终态
结点,并将路径中 矢线上所标记的字符 依次连接起来,
便得到 状态转换图 所能识别的 全部符号串,这些符号串
组成的集合构成了该 状态转换图 识别的语言。
27
状态转换图与文法推导
? 用状态转换图识别符号串 w的过程，就是为 w建立一个
推导 S?* w的过程。
? 在第一步（在初始状态 S下，扫描到 a1而过渡到下一状
态 A1），由状态转换图的构造规则可知,G中必有产生
式 S?a1A1;
? 对于识别过程的后续步骤，由状态 Ai 识别 ai+1后过渡到
Ai+1恰好对应了使用产生式 Ai ?ai+1Ai+1 。
? 最后在状态 An-1识别 an后到达终态 F，对应了使用产生
式 A ?an。
? 整个推导过程,S ?a1A1 ?a1a2A2 ?……
?a1a2… an-1An-1 ?a1a2… an
28
例,G[Z],状态转换图,
Z→0U ∣ 1V
U →1Z ∣ 1 1
V →0Z ∣ 0 0 1
初态
1 0
0
例, ω=011001
通过状态图可以确定 ω 是文法的句子,
② 此过程是一种推导过程,
Z=>0U=>01Z=>011V=>0110Z=>01100U=>011001
Z
U
V
F
29
右线性文法与状态转换图
设 G是一 右线性文法,M是相应的 状态转换图,则从前面的讨
论可以看出如下事实,
(1)在利用 M对符号串 w进行识别时,M中每次状态的转换都模拟了一
步直接推导,即识别方法 (或称分析方法 ) 是, ?” 的 ;
(2)因 右线性文法 只有形如 A?aB,A ?a的产生式，所以推导的每
一步所得句型只含一个非终结符，且必出现在句型的最右端，所
以推导是 规范推导,每步所得的句型也必为 规范句型 ；
(3)对于 M所识别的任一符号串 x,必存在 G中的一个推导 S ?* x (即有
x?L(G);反之,对于 L(G)中任一句子 y,必存在一条从初态 S到终态 F
的路径,此路径上各矢线的标记依次拼接起来所组成的符号串恰为
y。
30
由左线性文法构造状态转换图
? 设 G=(VN,VT,P,S)是一左线性文法,构造相应的状态转换
图的方法是,
首先用 VN中的非终结符标记 M的结点，其中，开始符 S
对应的结点为终态结点。引入一个新结点 R(?VN)标记初
态。矢线的连接规则为,
(1)对于 G中形如 A?a 的产生式，引矢线 R?A,且标记
为 a；
(2)对于 G中形如 A?Ba 的产生式，引矢 线 B?A，且标
记为 a。
31
由左线性文法构造状态转换图
已给文法 G=({S,U},{0,1},{S?S1 |U1,U?U0 | 0},S)
R U S 0
0
1
1
用左线性文法构造出的状
态转换图识别文法的句子
与前面的过程一样,
就识别的方法而言,属于自
底向上的分析,
以句子 00011为例,给出其
识别的的步骤,见右表,
步骤 当前状态 余留的符号串
1 R 00011
2 U 0011
3 U 011
4 U 11
5 S 1
6 S (识别结束 )
32
例,G[Z],
Z→U0 ∣ V1
U →Z1 ∣ 1
V →Z0 ∣ 0
状态转换图,
0
初态 1 1
0 0
1
R
U
V
Z
(2)状态转换图的使用
① 识别句子 (单词符号 )
例,100110通过状态图可
以确定是文法的句子,
② 识别过程对应着归约
过程
100110
U00110
Z0110
V110
Z10
U0
Z
33
识别符号串与归约过程
? 由构造状态转换图的方法可知,从初态 R
到下一状态 A的转换,对应了形如 A?a
的产生式,即将终结符 a归约成非终结符
A;
? 从状态 B转换到状态 A,对应了形如
A?Ba的产生式,即将 Ba归约为 A;
? 如此下去,直到从某状态 A转换到状态
S(终态 ),对应了形如 S ?Aa的产生式,即
将 Aa归约为开始符 S.此时归约成功,也
恰好进入了终态,即状态转换图识别了
(或接受 )该符号串,
? 前面识别 00011的例子对应的归约过程
见右图
0 0 0 1 1
U
U
U
S
S
R U S 0
0
1
1
34
3.2.2 状态转换图的实现 -状态矩阵法
? 状态转换图 可方便地用于识别单词,但是,如何让计算机
利用状态转换图来进行词法分析呢?
? 一个简单实用的方法就是将图以矩阵的形式保存在内存
中,这就是所谓的 状态矩阵法,
? 状态矩阵 以图中各个状态 S1,S2,…,Sn为行,以各个输入符
号 a1,a2,…,am为列,组成一个 n?m矩阵 B,其元素
Bij=B[Si,aj]指明扫描器此时应完成的语义动作和要转换
到的下一状态 Sk,其含义是,在 Si状态下,扫描到 aj符时,按
序偶 (Si,aj)查矩阵 B,扫描器根据 Bij的指示,先执行相应的
语义动作,再转换到下个状态 Sk,
? 若 Bij为, 出错,,则说明输入符号串有误,拒绝接受,扫描
器将调用出错处理程序进行处理
35
程序 3-2 状态矩阵驱动程序
CurStat=0;
FlagOfFS=NoneSeen; /*将终态标志置为, 未经历, */
if(CurChar==EOF) return 0;
while (CurChar != EOF){
if(Stat=TransMat[CurStat][CurChar]!=NULL) {
/*能进行状态转换 */
CurStat=Stat; advance( );
if( CurStat 是终态 ){
FlagOfFS=HasSeen; /*标记经历过的终态 */
记下输入串中当前位置及该状态相关联的动作 ;
}/*end if CurStat 是终态 */
}
36
else{ /*不能继续进行状态转换 */
if(FlagOfFS==NoneSeen) { /*未经历过 终态 */
报告词法错误 ;
略过当前词文及输入字符 ;
CurStat=0;
}
else { /*经历过 终态 */
回退到最近经历的那个终态的输入字符位置 ;
执行所记录的该终态的相关动作 ; /*执行经历过的终态 */
} /*end if FlagOfFS==NoneSeen */
} /*end if Stat !=NULL*/
}/*end while*/
37
贪心策略
? 目的是获得最长匹配单词
（ 1）若当前状态对输入符号有后继动作，则继续进行状
态转移；
（ 2）若当前状态为终态，记下该状态和当前输入字符的
位置，并继续向前扫描；
（ 3）若当前状态已无后继状态，并且此前经历过终态，
则执行曾经历的最近的终态所对应的语义动作；
（ 4）若当前状态已无后继状态，并且此前没有经历过终
态，则表明输入字符串有词法错误，报错，并略过余
下的部分词文，从状态 0开始继续下一单词的识别。
? 状态矩阵是稀疏的，应该采用紧凑的数据结构
38
识别无符号数 的语义操作
? 功能：把识别出的无符号数转换成整数（ ICON） 和实数
（ FCON）。
? 无符号数的输入形式,dmdm-1… d0, d-1… d-n E ? dd… d
可改写为 dmdm-1… d0 d-1… d-n ?10^(? dd… d -n);
? 用 w,p,n,e分别计录尾数、指数、小数位及指数的符号。
因此数值为,N=w ? 10^(e?p-n)
? 语义加工过程,
– w,p,n初值为 0,e初值为 1；
– 处理整数部分时，对于每个 di,令 w=w?10+di ;
– 处理小数部分时，对于每个 di,令 w=w?10+di ;及 n++;
– 处理指数时,E后若有 ‘ -‘号，令 e=-1；计算指数值
p=p?10+d;
– 在出口处，令 ICON=w或 FCON=w?10^(e?p-n),
39
识别 无符号数 的状态矩阵
当 前 状
态
扫 描 字 符 语 义 处 理 操 作 或 接 受 动 作 后 继 状
态
d { w = 0 ; n = 0 ; p = 0 ; e = 1 ; w = w * 1 0 + d } 1
,{ w = 0 ; n = 0 ; p = 0 ; e = 1 ; } 30
t h e r e r r o r
d { w = w * 1 0 + d ; } 1
,2
E 41
o t h e r { r e t u r n ( I C O N = w ) ; e n d
d { n + + ; w = w * 1 0 + d ; } 2
E 42
o t h e r { r e t u r n ( F C O N = w * p o w ( 1 0,e * p - n ) ) ; } e n d
d { n + + ; w = w * 1 0 + d ; } 2
3 o t h e r e r r o r
d { p = p * 1 0 + d ; } 6
+ 5
- e = - 1 ; 54
o t h e r e r r o r
d { p = p * 1 0 + d ; } 6
5 o t h e r e r r o r
d { p = p * 1 0 + d ; } 6
6 o t h e r { r e t u r n ( F C O N = w * p o w ( 1 0,e * p - n ) ) ; e n d
40
3.3 有限自动机
状态转换图 实际上是 有限自动机 的图形
表示
41
3.3.1 确定的有限自动机 DFA
? 抽象地看,状态转换图 由五个部分组成,
(1)有限个状态之集,记作 K;
(2)有限个输入符号组成的字母表,记作 ?;
(3)从 K??到 K的 转换函数 f,K???K,f(p,a)=q表示若
当前状态为 p,且输入符号为 a,则进入下一个状态为 q;
(4)S0?K,初始 (开始 )状态 ;
(5)若干个终态之集, Z(?K)
由上述五个要素组成的五元式 M=(K,?,f,S0,Z )称为
一个 确定的有限自动机 (DFA,Deterministic Finite
Automata)
由此可见,DFA实际上是状态转换图的形式描述 (数学定
义 ),状态转换图是 DFA的几何 (图形 )表示,
42
DFA的接受集
? DFA M的接受集 我们把一 DFA M所接受的符号串的
全体称为 M的接受集或 M接受的语言，记为 L(M),即
L(M)={ x | f^(S0,x) ?Z,x??* }
? M接受 (或识别 )某符号串 x??*：从初态 S0出发,经一恰
好标有 x 的路径后可达到某终态 S?Z 。 用 f^描述就是,
?S?Z,f^(S0,x)=S
? 将转换函数 f 的定义域拓广到 K??*,可以得到 f^,
(1) f^ (s,?)=s,s?K;
(2) f^ (s,aw)=f^ ( f(s,a),w),s?K,a??,w??*;
? 对于 x??*,f^(s,x)=t 的含义是,当 M从状态 s出发,依次扫
描完 x的各个符号后将进入状态 t,
? 只要 f有定义,f^与 f的效果是一致的，以后不再区分。
43
确定的有限自动机
? 确定的 FA,在状态转换的每一步，根据 FA当前的状态
及扫描的输入字符，便能 唯一地 确定 FA的下一状态。
在转换图上看，若 |?|=n，则任何结点所引出的矢线至
多有 n条，且矢线上的标记均不同。
? 例如,P51图 3-4所对应的 DFA为
M=({R,U,S},{0,1},f,R,{S}) 其中,f的定义如下：
f(R,0)=U f(U,0)=U f(U,1)=S f(S,1)=S
? 由 DFA与状态转换图的关系可知，构造状态转换图的
算法，同样适用于构造 DFA。
? 可以证明,?正规文法 G,? DFA M，使
L(M)=L(G)，反之亦然。
44
3.3.2非确定的有限自动机
? 若 在一右线性文法中同
时含有形如
U?aA U?aB U?aC
? U?aX 的产生式,
? 或 在一左线性文法中含
有多个右部相同的产生
式，如 A?Ua
B?Ua C?Ua ?
X?Ua,
? 在相应的状态转换图中，
就会出现这样的结点 U，
它具有多条标记为同一
输入符号 a的矢线
图 3-8 NFA的状态转换图
在 U状态下，输入符号为 a时，
FA的下一状态不唯一，而是
在状态集 {A,B,C,…,X} 中任选
其一。具有这种性质的 FA称
为非确定的 FA（ NFA,
Nondeterministic FA）
U
A
B
C
X
a
a
a
a
..,
45
非确定有限自动机的定义
? NFA M 也可用五元式定义,M=(K,?,f,S0,Z)，其中,K,
?,S0,Z的含义同 DFA,转换函数 f的定义为 f,K????(K),
即将 (Si,aj)映射到 K的一个子集 {Sk1,…,Skm}
? 类似地，我们可把 f的定义域拓广到 K??*,
(1) f^(S,?)={S};
(2) f^(S,aw)=f^(f(S,a),w) a??,w??*,
? 将定义域进一步扩大到 ?(K) ??*,定义
?
??
m
i
k
m
i
kkkk
wSfwaSffawSf
wSfwSSSf
i
im
1
1
),(^)),,((^),(^
:则有
),(^)},,,,({^
21
?
?
??
?
46
NFA的接受集
? 所有为 NFA M所接受的符号串之集称为 NFA M的接受
集（或识别集），记作 L(M).即
L(M)={x|f（ S0,x） ? Z ? ?,x??* }
? x??* 为 M所接受：集合 f(S0,x)中含有 Z中的元素
（终态），即至少存在一条从初态 S0到某一终态的路
径，此路径上的符号之连接恰为 x。
例 3.1 给定 M=({S,A,B,C},
{a,b},f,S,{C}),其状态转
换图见右。由图可知 M是一
NFA。
S A B
C
a
a,b
a
b
b
a
a
47
识别符号串 ababb的路径
? 注意, NFA识别输入符号串时有一个试探过程，为了能
走到终态，往往要走许多弯路（ 带回溯 ），这影响了
FA的效率。
? 能否提高其工作效率就是下一小节讨论的课题。事实
上，对任一 NFA M,总可构造一个 DFA M’，使
L(M’)=L(M)成立。这就是 NFA与 DFA的等价性 。
S A B
C
a
a|b
a
b
b
a
a
? 符号串 ababb的识别路径
S(a)?A(b)?B(a)?A(b)
?B(b)?C(接受 )。
(参见书中 P60)
48
3.3.3 NFA与 DFA的等价性
? 可将 DFA看作 NFA的特殊情况,即 DFA所接受
的语言类包含在 NFA所接受的语言类中。因
此，要证明 NFA与 DFA的等价性，只需证明
每一个 NFA都可以确定化。
? 确定化：对任意 NFA M，构造一个 DFA M’，
使得 L(M)=L(M’)。
? 思路：令 M’的某个状态与 M的某个状态子集
相对应，并使得在 M’扫描与 M相同的输入符
号时，保持对 M的状态进行跟踪（能根据 M
的状态确定 M’的状态）。
49
证明 NFA与 DFA的等价性
? 定理 3.1 对于字母表 ?上的任一 NFA M，必存
在与 M等价的 DFA M’ 。
? 证明 设 M=(K,?,f,S0,Z) 是 ?上的 NFA，现构造 ?上
DFA M’=（ K’,?,f’,S0’,Z’).方法如下,
1.K’=?(K).为表示方便,如 K某子集为 {S1,S2,…,Si},
记相应的状态为 [S1,S2,…,Si].特别地,令 S0’=[S0],
2.映射 f’的定义,
f’([S1,S2,…,Si],a)=[R1,R2,…,Rj] iff
f({S1,S2,…,Si},a)={R1,R2,…,Rj}
3.M’的终态集 Z’={[Sp,Sq,…,Sr]|[Sp,Sq,…,Sr]?
K’并且 {Sp,Sq,…,Sr}?Z??}
50
现在,证明 M’与 M等价的等价性,为此,对输入符号串 |x|=n
的长度进行 归纳,以证明如下论断,
f(S0,x)= {S1,S2,…,Si} ?
f’(S0’,x)=[S1,S2,…,Si] (S0’=[S0])
当 |x|=0 (即 x=?)时,由于总有 f(S0,?)={S0},f’(S0’,?)=S0’,即
f’([S0],?)=[S0],故论断成立,
设对于长度小于或等于 m的任何输入串 x论断均成立,即
f(S0,x)={S1,S2,…,Si}?f’([S0],x)=[S1,S2,…,Si]
现证明对于输入串 xa,其中,|x|=m,a?? 论断也成立,即
f(S0,xa)={R1,R2,…,Rj} ?
f’([S0],xa)=[R1,R2,…,Rj]
51
f(S0,xa)= f(f(S0,x),a)=f({S1,S2,…,Si},a)
={R1,R2,…,Rj}
f’(S0’,xa)=f’(f’(S0’,x),a)=f’([S1,…,S i],a) (归纳假设 )
=[R1,…,R j] (f’的构造定义 )
? 最后,若 f(S0,x)?Z?? 及由 Z’的定义,f’(S0,x)?Z’.即
x ?L(M) ? x ?L(M’) 得证。由于 NFA与 DFA是等价的,
今后统称 FA,
? 还应指出，确定化时所得的 DFA的状态数是很大的，
往往有许多无用状态（ 即那些从初态 S0不可达的状态
或那些从其出发不能到达终态的状态 ），这些状态可
从 DFA中删除。
52
NFA确定化的例子
例 3.2 M=({S0,S1},{a,b},f,S0,{S1})
S0 S1
a
b
b a|b 构造 M的 DFA M’=(K’,{a,b},f’,[S0],Z’}),
其中 K’={[S0],[S1],[S0,S1],?}
f’([S0],a)=[S0,S1] f’([S0],b)=[S1]
f’([S1],a)= ? f’([S1],b)=[S0,S1]
因为 f({S0,S1},a)= f(S0,a)? f(S1,a)= {S0,S1}
f({S0,S1},b)= f(S0,b)? f(S1,b)= {S0,S1}
所以 f’([S0,S1],a)= f’([S0,S1],b)=[S0,S1]
_f_|_a____ b___
S0 |{S0,S1} {S1}
S1 | ? {S0,S1}
53
NFA确定化的例子（续）
f’(?,a)= f’(?,b)= ?
f’ | a b | new state
? | ? ? |
[S0] | [S0,S1] [S1] | 1
[S1] | ? [S0,S1] | 2
[S0,S1]| [S0,S1] [S0,S1] | 3
Z’= {[S1],[S0,S1]}
M’=(K’,{a,b},f’,[S0],{[S1],[S0,S1]})
1 2
3
a b
b|a
b
54
3.3.4 具有 ? 动作的 FA
? 若在一 FA中,允许对 ?也作状
态转移,则这样的 FA称为具有
?动作的 FA,
? 右图就是一个 具有 ?动作的
FA。 其中,有的矢线上标记
为 ?（ 在此看作一个符号 ）。
标记为 ? 的矢线 对识别符号
串无影响,但却 改变了当前的
状态,
0 1
2
3
?
?
?
a b
b
c
例如,上图的 FA中,从状态 0到状态 3存在路径,
0(a)?0(a)?0(?)?2(c)?2(c)?2(?)?3,
即 M识别了 aa?cc?=aacc,
55
具有 ? 动作的 FA的定义
? 具有 ? 动作的 FA 定义为 M=(K,?,f,S0,Z),其中,f定义
为 f:K?(??{?})??(K),
? 在 具有 ? 动作的 FA中,?视为一个 输入符号,在矩阵表
示中,也有相应的列 。 例如，对于前面 具有 ? 动作 的
FA，相应的状态转换矩阵如 P63表 3-2所示。
? 同理可以定义 f^:K??*??(K),f^(S,x)是由这
样的状态 q组成,存在从 S到 q的路径,该路径上矢线
的标记组成的符号串恰好为 x,标记中可以包含若
干个 ?。
56
状态 S的 ?-闭包,?-CLOSURE(S)
? 状态 S的 ?-闭包,记为 ?-CLOSURE(S),它是从 S出发经过
若干标记为 ?的矢线所能达到的全部状态之集，其归纳定
义如下,
(1)S??-CLOSURE(S);
(2)设 Sj??-CLOSURE(S),且 Sj ?? Sk,则 Sk??-CLOSURE(S);
(3)重复使用规则 （ 2） 所得的集合为 ?-CLOSURE(S),
? ?-CLOSURE还可定义在状态集上，设 Q?K,则
?
QS
SC L O S U R EQC L O S U R E
?
????? )()(
57
?-CLOSURE示例
? 例 如,对于右图的 NFA,
?-CLOSURE(0)={0,1,2,3}；
?-CLOSURE(1)={1}；
?-CLOSURE(2)={2,3}；
?-CLOSURE(3)={3},
0 1
2
3
?
?
?
a b
b
c
58
转换函数 f和 f^ 的拓广
? 利用 ?-CLOSURE(S),可定义 f^如下,
?
?
?
Rq
Rq
wSfq
wqfwRf
aqfaRf
KRKRKKf
KKf
ffaqfawSffP
PC L O S U R EwaSf
SC L O S U R ESf
waKS
?
?
?
?
?
??????
????
??
??
??
??????
),(),(^)4(
),(),(3
)(:^
}{:
^)2(),()),,(^(,
);(),(^)2(
);(),(^)1(
,,
*
),(^
*
）（
有：）（）。对（）（
）和（）（）（定义分别拓广到
的及将。其中
???
???
?
??
59
f与 f^的区别
? 由 f^的定义可知,f^(S,a) 与 f(S,a) 不同,f^(S,a)是从 S
出发经过路径 a所达的状态集（可走若干步）；而
f(S,a)是从 S出发经过矢线 a所达的状态集（只走一步）
? 显然,f(S,a) 只走一步 a矢线
? ?-CLOSURE(f(S,a)) 多步，第一步必须走 a矢线
? f^(S,a) 路径 a, 第一步可以是 ?矢线
? ?-NFA的接受集, L(M)={w|f^(S0,w)?Z??}
60
f与 f^的计算示例
? 例如，在右图的 NFA中,
f(0,?)={1,2}; f(0,a)={0} ?是输入符号
f^(0,?)= ?-CLOSURE(0)={0,1,2,3};
? 是符号串
0 1
2
3
?
?
?
a b
b
c
f^(0,a)= ?-CLOSURE(f(f^(0,?),a))= ?-CLOSURE(f({0,1,2,3},a))
= ?-CLOSURE(f(0,a)?…?f(3,a))= ?-CLOSURE({0})={0,1,2,3}
f^(0,ac)= ?-CLOSURE(f(f^(0,a),c))= ?-CLOSURE(f({0,1,2,3},c))
= ?-CLOSURE(f(0,c)?…?f(3,c))= ?-CLOSURE({2})={2,3}
61
?-NFA的用途：构造更复杂的 FA
? 有了 ?-NFA，就可把识别各种不同单词的 FA用 ?矢线
（并连）连接起来，组成一个单一的 NFA，经确定化
后可得识别所有单词的 DFA，由此可设计编译程序的
词法分析器。
? 例如，某语言的单词有,
1.BEGIN 2.END 3.IF 4.THEN 5.ELSE
6.标识符 7.无符号整数 8,< 9,<= 10,=
11.<> 12,> 13.>=
可分别构造出识别各类单词的 FA,然后将其合并为一
个大 FA,如书中 P65图 3-11所示。
62
3.3.5具有 ?动作的 NFA的确定化
? 为具有 ?动作的 NFA M=(K,?,f,S0,Z)构造相应的 DFA
M’=(K’,?,f’,q0,Z’)
? 基本思路：从 M的初始状态 S0出发，仅经过任意条
矢线所能到达的状态集合作为 M’的初态 q0 ；然后从
q0出发，将对输入符号 a??进行状态转移所能到达
的状态（包括转移后再经过 ?矢线所能到达的状态）
所组成的集合作为 M’的状态，如此反复，直到无新
状态产生为止。
63
构造 K’,f’和 Z’的递归过程
1,令 K’={[?-CLOSURE(S0)]}; f’=? ;
2,对 K’中尚未被标记的状态 qi=[Si1,Si2,…,Sim],
(1)标记 qi;
(2)对于每个 a??,令 Ta=f({Si1,Si2,…,Sim},a); 对 a转移
令 qj= [?-CLOSURE(Ta)]; 进行 ?矢线转移
(3)若 qj?K’,则令 K’=K’?{qj };
(4)令 f’=f’ ?{f’(qi,a)= qj };
3,重复 2.,直到 K’中无未标记的状态 ;
4,令 Z’={qj | qj ? Z??} (这里把 qj 视为集合 )
64
确定化具有 ?动作的 NFA的例子
例 3.4 考虑右图具有 ?动作的 NFA
1.q0 = [?-CLOSURE(0)]
=[0,1,2,3]==>K’;
2.q0未标记,故
(1)标记 q0;
0 1
2
3
?
?
?
a b
b
c
(2)f’(q0,a)=[?-CLOSURE(f({0,1,2,3},a))]
=[?-CLOSURE({0})] = q0;
f’(q0,b)=[?-CLOSURE(f({0,1,2,3},b))]
=[?-CLOSURE({1,3})] = [1,3]= q1 ==>K’;
f’(q0,c)= [?-CLOSURE(f({0,1,2,3},c))]
=[?-CLOSURE({2})] = [2,3]= q2 ==>K’;
65
确定化具有 ?动作的 NFA的例子 (续 )
3,K’={q0,q1,q2},q1,q2 没有标记,
(1) 标记 q1;
(2) f’(q1,a)=[?-CLOSURE(f({1,3},a))]=?
f’(q1,b)=… =q1; f’(q1,c)=… = ?;
4,q2 没标记,(1) 标记 q2;
(2) f’(q2,a)=[?-CLOSURE(f({2,3},a))]=?；
f’(q2,b)=?; f’(q2,c)=q2;
K’不再增大，且所有的状态都已被标记,Z’={q0,q1,q2}，
最后的 DFA M’ 如下所示,
q1 q0 q2
a
b
b
c
c
0 1
2
3
?
?
?
a b
b
c
66
NFA的确定化示例
? 需要说明的是,上述算法也适合于不含 ?产生式的 NFA
的确定化,
? 例 3.5 对于书中图 3-11所示的 NFA利用上述算法所得
的 DFA如 P67图 3-13所示,
– 其中,圆圈中的数字是原 NFA的状态编号,在图 3-13
中,q0={0,1,7,11,14,19,24,26,28,30,33,35,40},
– 标有, #”的状态为特殊状态,在该状态下,若遇非弧
线上出现的字符,则转到状态 25,
67
3.3.6 DFA状态数的最小化
? 对于一 DFA来说,其状态数可能并不是最小的,原因是
DFA中有些状态是, 等价, 的,为得到高效率的 DFA,需
将这些, 等价, 状态合并,这就是 DFA的最小化,
? DFA M的最小化, 构造等价的 DFA M’其状态数达到最小,
? 可区分状态, 设 s,t?K,s,t由某 w??*所区分 iff
( f(s,w)?Z ? f(t,w)?Z ) ? ( f(s,w)?Z ? f(t,w)?Z )
若 ?w??*,f(s,w)?Z ? f(t,w)?Z,则 s与 t不可区分，称
二者等价。
? 确定了等价状态，就可以对其进行合并。
68
DFA最小化算法
? 基本思想, 将 M的状态集 K逐步地进行划分,以期将 K
划分为满足等价关系的等价类：使得在同一类中的
状态不可区分 ;在不同类中的状态可区分,算法如下,
1,先将状态集 K按终态和非终态划分为两个子集 Z和 K-
Z,显然分属于这两个集合的状态是可 (被 ?)区分的,记
?={Z,K-Z},
2,设当前的划分 ?中已含有 m个子集,?={I1,I2,…,Im},其
中,属于不同子集 Ii和 Ij (i?j)的状态是可区分的,而属于
同一子集 Ii中的状态是待区分的,现对每个子集
Ii={Si1,Si2,…,Sin}中的各状态 Sir(Sir?K,1? r ?n )进行
考查,看其是否可区分,
69
DFA最小化算法 (续 )
对于 Sip,Siq ?Ii,若存在 a??,使得 f(Sip,a)=Su?Ij,f(Siq,a)
=Sv?Ik（ 即经过 a转换后落在不同的等价类中 ），则根
据 Su和 Sv被某个 w所区分可知,Sip 和 Siq 可被 aw 区分,
f(Sip,aw)=f(Su,w)，而 f(Siq,aw)= f(Sv,w),且 Su与 Sv
可区分,将 Ii细分,使其落入不同的更小的子集中,得到新
划分 ?new,（ 细分 Ii的方法见下页）。
3.若 ?new,不等于 ?,则令 ? =?new,转 2,
4.对于最终的 ?，从每个划分块 Ii中任选一状态为代表，
构成 K’。若 Ii中含有初态，则其代表也为初态；若 Ii
?Z??，则 Ii 的代表 ?Z’。 删除非代表状态，将引入非
代表状态的矢线引向代表状态,
70
细分划分块的方法
.
),(,,,,
,
),(),(,,
21
中同一子集落入
使得个更小的子集分为
则将个不同的子集中的状态分别落入若
令对每个子集
?
?
aIfIIIpI
pI
aSfaIfIaI
jp
i
iiiii
a
i
IS
i
a
ii
?
?
?
?????
.),(
,),(,
可区分有意义的状态它任何使
与其则无意义使得若某状态
i
i
Iqaqf
papfIp
?
?
71
DFA最小化的例子
1,?={{0,1,2,3},{4}}
{0,1,2,3}a={1} 未区分 ;
{0,1,2}b={2,3},{3}b={4},所以 3与
0,1,2 可区分 ; ?={{0,1,2},{3},{4}}
2,{0,1,2}a={1},未区分 ;
{0,2}b={2},{1}b={3},1与 0,2可区分 ;
?={{0,2},{1},{3},{4}};
3,{0,2}a={1},{0,2}b={2} 不可区分,
?new=?.结束,
0 1 3 4 a
a
a
b
a b
b
b
定理 3.2 具有 最小状态数的 DFA在同构意义下是唯一的,
0 1 3
2
4
a
a
a
a
a
b
b
b
b
b
接受句子：以 abb为后
缀的 a,b符号串
72
3.4正规表达式与正规集
到目前为止,我们已了解了对于任意三型语言 L(G),存在
FA M使 L(M)=L(G),反之,对于任意的 M,存在正规文法 G,
使 L(G)=L(M).这称为描述语言的等价性,
本节将引入 正规表达式 的概念,它们可用于描述三型语
言的特征,特别是对自动生成词法分析程序而言，它是
非常有用的工具。
所谓 正规表达式 就是用特定的 运算符 （ *,?,| 等）及
运算对象 按某种规则构造的表达式，它可以用于描述
给定三型语言的所有句子。 正规表达式 所描述的句子
集合 (语言 )称为 正规集 。
73
3.4.1正规表达式及正规集的定义
? 定义 设 ?是一字母表,则 ?上的 正规表达式 (正则表达式,
正规式 )及其表示的 正规集 可递归定义如下,
(1) ?是一正规式,相应的正规集为 ?;
(2) ?是一正规式,相应的正规集为 {?};
(3) ?a??,a 是一正规式,相应的正规集为 {a};
(4) 设 r,s是正规式,且它们所表示的正规集为 Lr,Ls,则
1,(r) ?(s)是正规式,相应的正规集为 Lr?Ls;
2,(r)|(s)是正规式,相应的正规集为 Lr? Ls;
3,(r)*是正规式,相应的正规集为 Lr*
有限地使用上面的规则 (4),所得的表达式均是正规式,
74
有关正规式及正规集的说明
定义中的括号主要用于规定运算顺序。一般规定
优先级从高到低依次为 *,?,|，则可以省略某些
括号,例如 (r) ?((s)*)|(r) 可简写为 r ?s*|r。另外,?
常常可省略不写，进一步写成 rs*|r。
75
正规式与正规集的例子
},,,{}{}{
00
* ??? aaaaaa
i
i
i
i ???
?
?
?
?
正规集正规式
aa* {a,aa,aaa,…}
a|b {a,b}
a|ba* {a,b,ba,baa,baaa,…}
(a|b)*abb 任何以 abb结尾的 a,b符号串
(aa|ab|ba|bb)* 空串或者任意长度为偶数的 a,b符号串
(a|b)(a|b)(a|b)* 长度大于等于 2的 a,b符号串
76
? 给定正规式,它唯一确定一正规集 ;反之不真,即一个正
规集可由多个不同的正规式表示,如,(a|b)*和 (a*b*)*，
b(ab)*和 (ba)*b表示相同的正规集。
? 若二正规式描述同一正规集,则称二式 等价 (相等 )
? 正规式间的基本等价关系,
A1,r|s=s|r A2,r|r=r
A3,r|?=r A4,(r|s)|t=r|(s|t)
A5,(rs)t=r(st) A6,r(s|t)=rs|rt
A7,(s|t)r=sr|tr A8,r?=?r=?
A9,r?=?r=r A10,r*=(?|r)*=?|rr*
77
3.4.2 由正规文法构造相应的正规式
? 对于给定的三型文法 G,如何构造正规式 r,使 Lr=L(G)
? 方法, 将正规文法 G看作是非终结符作为变量的联立方
程组,通过解方程组求得相应的正规式,
? 例,正规文法 G,S?aS | bA | b； A?aS。假设 S,A所
产生的正规集分别为 LS,LA，则有,
LS={a} ? LS ? {b} ? LA ? {b}； LA ={a} ? LS
由定义可知,L(G)= LS。用 S,A代表 LS和 LA的正规式，
并用 ‘ +’ 代替 ‘ |’,则上述 关系可以改写为,
S=aS + bA + b （ 1）
A=aS （ 2）
将 (2)代入 (1),得 S=aS + baS + b = (a+ba) S +b (3)
? 上述问题转化为求解形如 X= ?X + ? 的方程,
78
求解形如 X= ?X + ? 的方程
关于这类方程有如下 论断,
论断 3.1 方程 X= ?X + ? 有解 X= ?*? (不唯一 )
证, 将 X= ?*? 代入方程右边,
右边 = ??*?+ ?=(??*+?) ?= ?*?=左边
由论断 3.1可知,方程 S=aS+baS+b=(a+ba)S+b的解为
S=(a+ba)*b=(a|ba)*b,
另外,对 S=aS+baS+b连续使用两次论断 3.1,有
S=a*(baS+b)=a*baS+a*b=(a*ba)*a*b
可得一等式, (a|ba)*b = (a*ba)*a*b
? 文法的状态转换图如右,S A
F
a
a
b
b
79
正规式求解示例
? 例如,S?aA； A?bA | aB | b； B?aA
相应的方程组为,S=aA (1)
A=bA+aB+b (2)
B=aA (3)
(3)代入 (2),A=(b+aa)A+b
得 A=(b+aa)*b
代入 (1),S=a(b+aa)*b=a(b|aa)*b
A
B
F
a
a
b
b S
a
80
左线性文法 正规式的求解
? 对于左线性文法,在解联立方程时最终会得到形如
X=X?+?的方程,类似于论断 3.1,可知其有解 X=??*
? 例, 标识符的文法为, I?Id |Il |l
相应的方程为 I=I(d+l)+l
解为, I= l(d+l)* =l(d|l)*
? 在正规式的实际应用中,人们还引入了许多新的运算符,
如正闭包‘ +‘,限制重复次数的‘ {m,n}‘,可选符‘?‘,字
符类‘ [ ]‘,首符号‘ ^‘,尾符号‘ $‘等,这里不再赘述,
81
3.4.3 正规式构造 FA? Thompson法
? 对于 ?正规式 r,?FA M,使 L(M)=Lr
? 构造方法, 根据正规式运算的递归定义,按 运算符的个
数 n,归纳地构造出 FA M。 M只含一个初态,一个终态,
且终态无矢线射出，可能包含若干条 ?矢线。
? 设 r 为 ?上的正规式,且含 n个运算符,构造 M的方法如下,
1.当 n=0时，则有 r=?或 r=? 或 r=a??，相应的 FA分别
如下,
r=? r=? r=a??
S f f S f
a
82
Thmopson 法 (续 )
2,假设当 n=1,2,…,k -1时,M均可构造。当 n=k时,根据正规
式的定义,r只能是 r1|r2,r1?r2,r1*这三种形式之一。其
中,r1和 r2 中共含 k-1个运算符,且设相应的自动机为
M1=(K1,?1,f1,S01,{Sf1}) L(M1)=Lr1
M2=(K2,?2,f2,S02,{Sf2}) L(M2)=Lr2
并且 K1?K2=?。分情况讨论,
? M
1 S01 Sf1
M2 S02 Sf2
S0 Sf
?
? ?
(1) r= r1|r2,引入新开始状态 S0,终态 Sf,将 M1,M2并联,
M=(K1?K2 ?{S0,Sf},?1??2,f,S0,{Sf})
83
Thmopson 法 (续 )
(3) r=r1*,引入新开始状态 S0,终态 Sf,令原 M1构成循环
M=(K1?{S0,Sf},?1,f,S0,{Sf})
M1 S01 Sf1 M2 S02 Sf2
?
(2) r=r1?r2,将 M1,M2串联,
M=(K1?K2,?1??2,f,S01,{Sf2})
?
? M1 S
01 Sf1 S0 Sf
?
?
84
Thmopson 法 举例
? 由正规式 a(b|aa)*b 构造相应的 FA过程。令 r1=a,
r2=b|aa,r3 = b,则 a(b|aa)*b= r1r2*r3,相应的 FA构造过
程如下,
（ 1）对 r2=b|aa构造 FA，可得,
?
S1
S3
S7 S8
?
? ?
S2
S5 S4
b
S6 ? a a
85
Thmopson 法 举例 (续 )
（ 2）对 r2*构造 FA，可得,
? S
1
S3
S7
?
? ?
S2
S5 S4
b
S6 ? a a
S8 S9
?
S10 ? ?
?
86
Thmopson 法 举例 (续 )
(3)对 r1r2*r3构造 FA，可得,
? S
1
S3
S7
?
? ?
S2
S5 S4
b
S6 ? a a
S8 S9
?
? ?
?
S10 S14 S13 S11 S12 a ?
? b
A
B
F
a
a
b
b S
a
S7
?
S4
b
a a
S8
?
S14 S11
a b
将 S7和 S8合并可以得到最初的状态转换图，如右上所示。
