词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。
第三章 词法分析及其自动构造
单词的描述工具
单词的识别系统
设计词法分析程序,实现词法分析程序的自动构造回顾 什麽是词法分析程序
实现词法分析（ lexical analysis） 的程序
– 逐个读入源程序字符并按照构词规则切分成一系列单词。 单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符号和常量等。
词法分析是编译过程中的一个阶段，在语法分析前进行 。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。
词法分析程序和语法分析程序的关系源程序 词法分析程序 语法分析程序
Token
get token
….源程序 词法分析程序 语法分析程序源程序词法分析程序 语法分析程序源程序词法分析程序的 主要任务：
– 读源程序，产生单词符号词法分析程序的 其他任务：
– 滤掉空格，跳过注释、换行符
– 追踪换行标志，复制出错源程序，
– 宏展开,……
词法分析工作从语法分析工作独立出来的原因：
– 简化设计
– 改进编译效率
– 增加编译系统的可移植性
单词的描述工具 -正规表达式
单词的识别系统 -有穷自动机
设计词法分析程序,实现词法分析程序的自动构造令?={a,b},?上的正规式和相应的正规集的例子
a
a?b
ab
(a?b)(a?b)
a?
(a?b)?
(a?b)?(aa?bb)(a?b)?
正规式正规式也称正则表达式,是定义正规集的数学工具。正规表达式（ regular expression）
是说明单词的模式 (pattern)的一种重要的表示法（记号），我们用以描述单词符号。
令?={a,b},?上的正规式和相应的正规集的例子
a
a?b
ab
(a?b)(a?b)
a?
(a?b)?
(a?b)?(aa?bb)(a?b)?
{a}
{a,b}
{ab}
{aa,ab,ba,bb}
{?,a,aa,…… 任意个 a
的串 }
{?,a,b,aa,ab,bb …… 所有由 a和 b组成的串 }
{上所有含有两个相继的 a或两个相继的 b组成的串 }
讨论两个例子例 3.1
令?={l,d},则?上的正规式 r=l(l?d)?定义的正规集为,
{l,ll,ld,ldd,……},其中 l代表字母,d代表数字,正规式 即是字母 (字母 |数字 )?,它表示的正规集中的每个元素的模式是“字母打头的字母数字串”,就是 Pascal和 多数程序设计语言允许的的标识符的词法规则,
例 3.2
={d,?,e,+,-},
则?上的正规式 d?(?dd )(e(+?-)dd)表示的是无符号数的集合。其中 d为 0~9的数字。
程序设计语言的单词都能用正规式 来定义,
有穷自动机有穷自动机 (也称有限自动机 )作为一种识别装置，它能准确地识别正规集，即识别正规式所表示的集合,应用有穷自动机这个理论，为词法分析程序的自动构造寻找有效的方法和工具。
有穷自动机分为两类：确定的有穷自动机
(Deterministic Finite Automata)和不确定的有穷自动机 (Nondeterministic Finite Automata) 。
关于 有穷自动机 我们将讨论如下题目确定的有穷自动机 DFA
不确定的有穷自动机 NFA
NFA的确定化
DFA的最小化确定的有穷自动机 DFA
DFA定义：
一个确定的有穷自动机（ DFA） M是一个五元组,M=（ K,Σ,f,S,Z） 其中
1.K是一个有穷集，它的每个元素称为一个状态；
2.Σ 是一个有穷字母表，它的每个元素称为一个输入符号，所以也称 Σ 为输入符号表；
DFA定义
3.f是转换函数，是在 K× Σ→ K上的映射，即，
如 f（ ki,a） =kj，（ ki∈ K,kj∈ K） 就意味着，当前状态为 ki,输入符为 a时，将转换为下一个状态 kj,我们把 kj称作 ki的一个后继状态；
4.S∈ K是唯一的一个初态；
5.Z? K是一个终态集，终态也称可接受状态或结束状态。
一个 DFA 的例子：
DFA M=（ {S,U,V,Q},{a,b},f,S，
{Q}） 其中 f定义为：
f（ S,a） =U f（ V,a） =U
f（ S,b） =V f（ V,b） =Q
f（ U,a） =Q f（ Q,a） =Q
f（ U,b） =V f（ Q,b） =Q
DFA 的状态图表示
b
S
U
V
Q
a a
a
b
a,b
b
DFA 的矩阵表示
a b
S U V
U Q V
V U Q
Q Q Q
字符状态
0
0
0
1
∑* 上的符号串 t被 DFAM接受例,证明 t=baab被下图的 DFA所接受 。
f（ S,baab） =f（ f（ S,b）,aab）
= f（ V,aab） = f（ f（ V,a）,ab）
=f（ U,ab） =f（ f（ U,a）,b）
=f（ Q,b） =Q
Q属于终态。
得证。
b
S
U
V
Qa
b
b
a,ba a
DFA M所能接受的符 号 串的全体记为 L(M).
结论：
上一个符 号 串集 V是正规的，当且仅当存在一个?上的确定有穷自动机 M,使得
V=L(M)。
DFA的行为很容易用程序来模拟,
DFA M=（ K,Σ,f,S,Z） 的行为的模拟程序
– K:=S；
– c:=getchar;
– while c<>eof do
– {K:=f(K,c);
– c:=getchar;
– };
– if K is in Z then return (‘yes’)
– else return (‘no’)
DFA= {digit,not digit}
不确定的有穷自动机 NFA
定义
NFA M=?K,?,f,S,Z?,其中 K为状态的有穷非空集,? 为有穷输入字母表,f为 K?
* 到 K的子集（ 2 K） 的一种映射,S?K是初始状态集,Z?K为终止状态集,
例子
NFA M=（ {S,P,Z},{0,1},f,{S,P},{Z}）
其中
f（ S,0） ={P}
f（ S,1） ={S,Z}
f（ P,1） ={Z}
f（ Z,0） ={P}
f（ Z,1） ={P}
状态图表示
S
P
Z
0
0,1
1
1
1
矩阵表示矩阵表示
0 1
S { P } { S,Z } 0
P {} { Z } 0
Z { P } { P } 1
简化为
0 1
S P S,Z 0
P,Z 0
Z P P 1
具有?转移的不确定的有穷自动机
f为 K* 到 K的子集（ 2 K） 的一种映射
–
1 2 3
a b c
有如下定理,
对任何一个具有?转移的不确定的有穷自动机
NFA N,一定存在一个不具有?转移的不确定的有穷自动机 NFA Ｍ,使得 L(M)=L(N)。
与上例等价的一个 NFA.
2a
c
b
b
3
1
ac
a
c
b
b
类似 DFA,对 NFA M=?K,?,f,S,Z?也有如下定义
∑*上的符 号 串 t在 NFA M上运行,.
一个输入符 号 串 t，（ 我们将它表示成 Tt1的形式，其中 T∈ ∑,t1∈ ∑*）在 NFA M上 运行 的定义为：
f（ Q,Tt1） =f（ f（ Q,T）,t1） 其中 Q∈ K.
∑*上的符 号 串 t被 NFA M接受若 t? ∑*,f(S0,t)=P,其中 S0 ∈ S,P? Z，
则称 t为 NFA M所 接受 （ 识别 ）
∑* 上的符号串 t被 NFAM接受也可以这样理解对于 Σ﹡ 中的任何一个串 t,若存在一条从某一初态结到某一终态结的道路，且这条道路上所有弧的标记字依序连接成的串 (不理采那些标记为 ε的弧 )等于 t,则称 t可为 NFA M所识别 (读出或接受 )。若
M的某些结既是初态结又是终态结，或者存在一条从某个初态结到某个终态结的道路,其上所有弧的标记均为 ε，那么空字可为 M所接受。
000
111
1010001
110000001
00
01100
NFA M所能接受的符 号 串的全体记为
L(M)
结论：
上一个符 号 串集 V是正规的，当且仅当存在一个?上的不确定的有穷自动机 M,使得 V=L(M)。
(0|1)*(000|111)(0|1)*
确定有限自动机和不确定有限自动机
DFA是 NFA的特例,对每个 NFA N一定存在一个 DFA Ｍ,使得 L(M)=L(N)。 对每个
NFA N存在着与之等价的 DFA M。
有一种算法，将 NFA转换成接受同样语言的
DFA.这种算法称为 子集法,
与某一 NFA等价的 DFA不唯一,
NFA确定化算法,
假设 NFA N=(K,?,f,K0,Kt)按如下办法构造一个 DFA M=(S,?,d,S0,St),使得
L(M)=L(N)：
1,M的状态集 S由 K的一些子集 组成。用 [S1
S2..,Sj]表示 S的元素，其中 S1,S2,,..,Sj是 K的状态。并且约定，状态 S1,S2,,..,Sj是按某种规则排列的，即对于子集 {S1,S2}={ S2,S1,}
来说,S的状态就是 [S1 S2]；
2 M和 N的输入字母表是相同的，即是?；
3 转换函数是这样定义的：
d([S1 S2,..,Sj],a)= [R1R2..,Rt] 其中
{R1,R2,...,Rt} =?-closure(move({S1,S2,,..,Sj},a))
4 S0=?-closure(K0)为 M的开始状态；
5 St={[Si Sk..,Se]，其中 [Si Sk..,Se]?S且 {Si,Sk,,...
Se}?Kt}
定义对状态集合 I的几个有关运算：
1,状态集合 I的 ε -闭包,表示为 ε-closure(I),定义为一状态集，是状态集 I中的任何状态 S经任意条 ε弧而能到达的状态的集合。
状态集合 I的任何状态 S都属于 ε-closure(I)。
2,状态集合 I的 a弧转换,表示为 move(I,a)定义为状态集合 J，
其中 J是所有那些可从 I中的某一状态经过一条 a弧而到达的状态的全体。
状态集合 I的有关运算的例子
I={1},?-closure(I)={1,2}；
I={5},?-closure(I)={5,6,2}；
move({1,2},a)={5,3,4}
-closure({5,3,4})={2,3,4,5,6,7,8}；
1 2
5
3
4
6
8
7
a
a
a
构造 NFA N的 状态 K的子集 的算法：
假定所构造的子集族为 C,即 C= (T1,T2,,..,TI),
其中 T1,T2,,..,TI为状态 K的子集。
1 开始，令?-closure(K0)为 C中唯一成员，并且它是未被标记的。
2 while （ C中存在尚未被标记的子集 T） do
{
标记 T；
for 每个输入字母 a do
{
U:=?-closure(move(T,a))；
if U不在 C中 then
将 U作为未标记的子集加在 C中
} }
NFA的确定化例子
4
f
3
5 621i
a a aa
b b b b
Ia Ib
{i,1,2} {1,2,3} {1,2,4}
{1,2,3} {1,2,3,5,6,f} {1,2,4}
{1,2,4} {1,2,3} {1,2,4,5,6,f}
{1,2,3,5,6,f} {1,2,3,5,6,f} {1,2,4,6,f }
{1,2,4,5,6,f} {1,2,3,6,f } {1,2,4,5,6,f}
{1,2,4,6,f } {1,2,3,6,f } {1,2,4,5,6,f}
{1,2,3,6,f } {1,2,3,5,6,f} {1,2,4,6,f }
S A B
A C B
B A D
C C E
D F D
E F D
F C E
4
f
3
5 621i
a a aa
b b b b
等价的 DFA
a
C
DB
A E
F
S b
a
a
a
a
ab
b
b
b
b
a
b
确定有穷自动机的化简说一个有穷自动机是化简了的，即是说，它没有多余状态并且它的状态中没有两个是互相等价的。一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。
所谓有穷自动机的多余状态，是指这样的状态：
从自动机的开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。
DFA的最小化就是寻求最小状态 DFA
最小状态 DFA的含义,
没有多余状态 (死状态 )
没有两个状态是互相等价（不可区别）
两个状态 s和 t可区别：不满足兼容性 ——同是终态或同是非终态传播性 ——从 s出发读入某个 a?a和从
t出发 读入某个 a到达的状态等价。
C和 D同是终态,读入 a到达 C和 F,C和 F同是终态,
C和 F读入 a都到达 C,读入 b都到达 E,C和 D等价
a
C
DB
A E
F
S b
a
a
a
a
ab
b
b
b
b
a
b
最小状态 DFA
对于一个 DFA M =（ K,∑,f,k0,,kt),存在一个 最小状态 DFA M’ =（ K’,∑,f ’,
k0’,,kt’)，,使 L(M’)=L(M),
结论
– 接受 L的最小状态有穷自动机不计同构是唯一的。
,分割法,
DFA的最小化算法的核心把一个 DFA的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的,
算法假定每个状态射出的弧都是完全的,否则,引入一个新状态,叫死状态,该状态是非终态，将不完全的输入弧都射向该状态，对所有输入，
该状态射出的弧还回到自己,
DFA的最小化算法
DFA M =（ K,∑,f,k 0,,kt),最小状态 DFA
M’
1.构造状态的一初始划分?：
终态 kt 和非终态 K- kt两组 (group)
2.对 ∏ 施 用 过程 PP 构造新划分 ∏ new
3,如 ∏ new =∏,则令 ∏ final=∏ 并继续步骤 4,否则 ∏,=∏ new重复 2,
4.为 ∏ final中的每一组选一代表，这些代表构成 M’的状态。若 k是 一代表且
f(k,a)=t,令 r是 t组的 代表，则 M’中有一转换 f’(k,a)=r
M’ 的开始状态是含有 S0的那组的代表 M’
的终态是含有 F的那组的代表
5.去掉 M’中的死状态,
过程 PP,Construction of ∏ new
– For each group G of ∏ do
– begin
– 1.Partiton G into subgroups such that
two states s and t of G are in the
same subgroups if and only if for all
input symbols a,states s and t have
transitions on a to states in the
same group of ∏;/*at worst,a state
will be in a subgroup by itself*/
– 2.replace G in ∏new by the set of all
subgroups formed
– end
DFA的最小化 —例 子
∏0:{ S,A,B}
{C,D,E,F}
∏1:{S,A,B}
{C,D,E,F}
∏2,
C
DB
A E
F
S b
a
a
a
a
a
ab
b
b
b
b
ba
}{}{A S,B
b
B{{ S }} DB
A
S
a
a
a
b
b
b
ba
a
词法分析程序 的 自动 构造对有穷自动机和正规表达式进行了上述讨论之后,我们介绍 词法分析程序 的 自动 构造方法,这个方法基于有穷自动机和正规表达式的等价性,即,
1.对于 ∑ 上的一个 NFA M，可以构造一个 ∑ 上的正规式 R,使得 L(R)=L(M)。
2.对于 ∑ 上的一个正规式 R，可以构造一个 ∑ 上的 NFA M,使 的 L(M)=L(R)。
从 Σ上的一个正规式 R构造 Σ上的一个 NFA
M,使得 L(M)=L(R)的方法。
,语法制导,的方法，即按正规式的语法结构指引构造过程，构造规则具体描述如下：
.,对于 ∑ 上的 一个正规式 R,可以构造一个 ∑ 上的 NFA
M，,使得 L(M)=L(R).” 说明一种构造方法：
(1)R=?,构造 任一具有空终态集的 NFA M
(2） R=?,构造 的 NFA M=({k0},∑,f,k 0.{k0}),
f（ k0,a)对于 所有 a?∑ 都没定义。
(3） R=a,构造 的 NFA M=({k0,,k1},∑,f,k 0.{k1}),
f(k0,a) = k1
(4) R =R1 | R2,将步骤（ 1）（ 2）（ 3）分别应用到 R1,R2 产生 M1= =(K1,∑,f1,k1,F1),
M2=(K2,∑,f2,k2,F2),其中 K1,K2不相交,构造 的
NFA M= (K1?K2?{k},∑,f,k,F),
k是新增加的状态符号，
f包含 f1和 f2,且 f(k,a)=f1(k1,a)?f2(k2,a),
若 k1?F1且 k2?F2则 F=F1? F2,否则 F=F1? F2
{k}
(5)R=R1.R2
将步骤（ 1）（ 2）（ 3）分别应用到 R1,R2 产生
M1==(K1,∑,f1,k1,F1),M2=(K2,∑,f2,k2,F2),其中 K1,K2不相交,
构造 的 NFA M= (K1?K2,∑,f,k 1,F2),f包含 f1和 f2,
且
f(k,a)=f1(k,a),当 k?F1时 ;
f(k,a)=f2(k,a),当 k∈ K2时 ;
f(k1,?)=k2,
(6)R=R1*
将步骤（ 1）（ 2）（ 3）分别应用到 R1,产生 M1==(K1,∑,f1,k1,F1),
构造 的 NFA M= (K1? {k0,F0},∑,f,k 0,F0)其中 k0,F0 是新增加的两个状态,
f(k,a)=f1(k,a),当 k?F1时 ;
f(k0,?)=f(F1,?)= {k1,,F0},
,
对于正规式 R=?,构造的 NFA
F
S
对于正规式 R=?,构造的 NFA
F
对于正规式 R=a,构造的 NFA
F
S
a
对于正规式 r,r= R1|R2构造的 NFA
对于正规式 r,r=R1 R2构造的 NFA
对于正规式 r,r=R1*构造的 NFA
正规表达式 1*0(0+1)*
举例,从 正规表达式 构造等价的? - NFA
1
0
0+1
11*
从 正规表达式 构造等价的? - NFA
(0+1)* 1
0
1
1
0
0
1*0(0+1)*
R=(a|ab)* b b*
正规式用于说明 (描述 )单词的结构十分简洁方便。而把一个正规式编译 (或称转换 )为一个 NFA进而转换为相应的 DFA,这个
NFA或 DFA正是识别该正规式所表示的语言的句子的识别器。基于这种方法来构造词法分析程序词法分析程序的设计技术可应用于其它领域，比如查询语言以及信息检索系统等，这种应用领域的程序设计特点是，通过字符串模式的匹配来引发动作又如 LEX,说明词法分析程序的语言，可以看成是一个模式动作语言。
词法分析程序的自动构造工具也广泛应用于许多方面，
如用以生成一个程序，可识别印刷电路板中的缺陷，
又如开关线路设计和文本编辑的自动生成等。
习题
4.7 练习
1 （ 1）
3
4 (b)
5
本章小结词法分析程序是编译第一阶段的工作，它读入字符流的源程序，按照词法规则识别单词，
交由语法分析程序接下去。
本章讲述了词法分析程序设计原则，并介绍了分别作为正规集描述和识别机制的正规式和有穷动机。在此基础上给出了词法分析程序自动构造工具如 LEX的原理。
第三章 词法分析及其自动构造
单词的描述工具
单词的识别系统
设计词法分析程序,实现词法分析程序的自动构造回顾 什麽是词法分析程序
实现词法分析（ lexical analysis） 的程序
– 逐个读入源程序字符并按照构词规则切分成一系列单词。 单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符号和常量等。
词法分析是编译过程中的一个阶段，在语法分析前进行 。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。
词法分析程序和语法分析程序的关系源程序 词法分析程序 语法分析程序
Token
get token
….源程序 词法分析程序 语法分析程序源程序词法分析程序 语法分析程序源程序词法分析程序的 主要任务：
– 读源程序，产生单词符号词法分析程序的 其他任务：
– 滤掉空格，跳过注释、换行符
– 追踪换行标志，复制出错源程序，
– 宏展开,……
词法分析工作从语法分析工作独立出来的原因：
– 简化设计
– 改进编译效率
– 增加编译系统的可移植性
单词的描述工具 -正规表达式
单词的识别系统 -有穷自动机
设计词法分析程序,实现词法分析程序的自动构造令?={a,b},?上的正规式和相应的正规集的例子
a
a?b
ab
(a?b)(a?b)
a?
(a?b)?
(a?b)?(aa?bb)(a?b)?
正规式正规式也称正则表达式,是定义正规集的数学工具。正规表达式（ regular expression）
是说明单词的模式 (pattern)的一种重要的表示法（记号），我们用以描述单词符号。
令?={a,b},?上的正规式和相应的正规集的例子
a
a?b
ab
(a?b)(a?b)
a?
(a?b)?
(a?b)?(aa?bb)(a?b)?
{a}
{a,b}
{ab}
{aa,ab,ba,bb}
{?,a,aa,…… 任意个 a
的串 }
{?,a,b,aa,ab,bb …… 所有由 a和 b组成的串 }
{上所有含有两个相继的 a或两个相继的 b组成的串 }
讨论两个例子例 3.1
令?={l,d},则?上的正规式 r=l(l?d)?定义的正规集为,
{l,ll,ld,ldd,……},其中 l代表字母,d代表数字,正规式 即是字母 (字母 |数字 )?,它表示的正规集中的每个元素的模式是“字母打头的字母数字串”,就是 Pascal和 多数程序设计语言允许的的标识符的词法规则,
例 3.2
={d,?,e,+,-},
则?上的正规式 d?(?dd )(e(+?-)dd)表示的是无符号数的集合。其中 d为 0~9的数字。
程序设计语言的单词都能用正规式 来定义,
有穷自动机有穷自动机 (也称有限自动机 )作为一种识别装置，它能准确地识别正规集，即识别正规式所表示的集合,应用有穷自动机这个理论，为词法分析程序的自动构造寻找有效的方法和工具。
有穷自动机分为两类：确定的有穷自动机
(Deterministic Finite Automata)和不确定的有穷自动机 (Nondeterministic Finite Automata) 。
关于 有穷自动机 我们将讨论如下题目确定的有穷自动机 DFA
不确定的有穷自动机 NFA
NFA的确定化
DFA的最小化确定的有穷自动机 DFA
DFA定义：
一个确定的有穷自动机（ DFA） M是一个五元组,M=（ K,Σ,f,S,Z） 其中
1.K是一个有穷集，它的每个元素称为一个状态；
2.Σ 是一个有穷字母表，它的每个元素称为一个输入符号，所以也称 Σ 为输入符号表；
DFA定义
3.f是转换函数，是在 K× Σ→ K上的映射，即，
如 f（ ki,a） =kj，（ ki∈ K,kj∈ K） 就意味着，当前状态为 ki,输入符为 a时，将转换为下一个状态 kj,我们把 kj称作 ki的一个后继状态；
4.S∈ K是唯一的一个初态；
5.Z? K是一个终态集，终态也称可接受状态或结束状态。
一个 DFA 的例子：
DFA M=（ {S,U,V,Q},{a,b},f,S，
{Q}） 其中 f定义为：
f（ S,a） =U f（ V,a） =U
f（ S,b） =V f（ V,b） =Q
f（ U,a） =Q f（ Q,a） =Q
f（ U,b） =V f（ Q,b） =Q
DFA 的状态图表示
b
S
U
V
Q
a a
a
b
a,b
b
DFA 的矩阵表示
a b
S U V
U Q V
V U Q
Q Q Q
字符状态
0
0
0
1
∑* 上的符号串 t被 DFAM接受例,证明 t=baab被下图的 DFA所接受 。
f（ S,baab） =f（ f（ S,b）,aab）
= f（ V,aab） = f（ f（ V,a）,ab）
=f（ U,ab） =f（ f（ U,a）,b）
=f（ Q,b） =Q
Q属于终态。
得证。
b
S
U
V
Qa
b
b
a,ba a
DFA M所能接受的符 号 串的全体记为 L(M).
结论：
上一个符 号 串集 V是正规的，当且仅当存在一个?上的确定有穷自动机 M,使得
V=L(M)。
DFA的行为很容易用程序来模拟,
DFA M=（ K,Σ,f,S,Z） 的行为的模拟程序
– K:=S；
– c:=getchar;
– while c<>eof do
– {K:=f(K,c);
– c:=getchar;
– };
– if K is in Z then return (‘yes’)
– else return (‘no’)
DFA= {digit,not digit}
不确定的有穷自动机 NFA
定义
NFA M=?K,?,f,S,Z?,其中 K为状态的有穷非空集,? 为有穷输入字母表,f为 K?
* 到 K的子集（ 2 K） 的一种映射,S?K是初始状态集,Z?K为终止状态集,
例子
NFA M=（ {S,P,Z},{0,1},f,{S,P},{Z}）
其中
f（ S,0） ={P}
f（ S,1） ={S,Z}
f（ P,1） ={Z}
f（ Z,0） ={P}
f（ Z,1） ={P}
状态图表示
S
P
Z
0
0,1
1
1
1
矩阵表示矩阵表示
0 1
S { P } { S,Z } 0
P {} { Z } 0
Z { P } { P } 1
简化为
0 1
S P S,Z 0
P,Z 0
Z P P 1
具有?转移的不确定的有穷自动机
f为 K* 到 K的子集（ 2 K） 的一种映射
–
1 2 3
a b c
有如下定理,
对任何一个具有?转移的不确定的有穷自动机
NFA N,一定存在一个不具有?转移的不确定的有穷自动机 NFA Ｍ,使得 L(M)=L(N)。
与上例等价的一个 NFA.
2a
c
b
b
3
1
ac
a
c
b
b
类似 DFA,对 NFA M=?K,?,f,S,Z?也有如下定义
∑*上的符 号 串 t在 NFA M上运行,.
一个输入符 号 串 t，（ 我们将它表示成 Tt1的形式，其中 T∈ ∑,t1∈ ∑*）在 NFA M上 运行 的定义为：
f（ Q,Tt1） =f（ f（ Q,T）,t1） 其中 Q∈ K.
∑*上的符 号 串 t被 NFA M接受若 t? ∑*,f(S0,t)=P,其中 S0 ∈ S,P? Z，
则称 t为 NFA M所 接受 （ 识别 ）
∑* 上的符号串 t被 NFAM接受也可以这样理解对于 Σ﹡ 中的任何一个串 t,若存在一条从某一初态结到某一终态结的道路，且这条道路上所有弧的标记字依序连接成的串 (不理采那些标记为 ε的弧 )等于 t,则称 t可为 NFA M所识别 (读出或接受 )。若
M的某些结既是初态结又是终态结，或者存在一条从某个初态结到某个终态结的道路,其上所有弧的标记均为 ε，那么空字可为 M所接受。
000
111
1010001
110000001
00
01100
NFA M所能接受的符 号 串的全体记为
L(M)
结论：
上一个符 号 串集 V是正规的，当且仅当存在一个?上的不确定的有穷自动机 M,使得 V=L(M)。
(0|1)*(000|111)(0|1)*
确定有限自动机和不确定有限自动机
DFA是 NFA的特例,对每个 NFA N一定存在一个 DFA Ｍ,使得 L(M)=L(N)。 对每个
NFA N存在着与之等价的 DFA M。
有一种算法，将 NFA转换成接受同样语言的
DFA.这种算法称为 子集法,
与某一 NFA等价的 DFA不唯一,
NFA确定化算法,
假设 NFA N=(K,?,f,K0,Kt)按如下办法构造一个 DFA M=(S,?,d,S0,St),使得
L(M)=L(N)：
1,M的状态集 S由 K的一些子集 组成。用 [S1
S2..,Sj]表示 S的元素，其中 S1,S2,,..,Sj是 K的状态。并且约定，状态 S1,S2,,..,Sj是按某种规则排列的，即对于子集 {S1,S2}={ S2,S1,}
来说,S的状态就是 [S1 S2]；
2 M和 N的输入字母表是相同的，即是?；
3 转换函数是这样定义的：
d([S1 S2,..,Sj],a)= [R1R2..,Rt] 其中
{R1,R2,...,Rt} =?-closure(move({S1,S2,,..,Sj},a))
4 S0=?-closure(K0)为 M的开始状态；
5 St={[Si Sk..,Se]，其中 [Si Sk..,Se]?S且 {Si,Sk,,...
Se}?Kt}
定义对状态集合 I的几个有关运算：
1,状态集合 I的 ε -闭包,表示为 ε-closure(I),定义为一状态集，是状态集 I中的任何状态 S经任意条 ε弧而能到达的状态的集合。
状态集合 I的任何状态 S都属于 ε-closure(I)。
2,状态集合 I的 a弧转换,表示为 move(I,a)定义为状态集合 J，
其中 J是所有那些可从 I中的某一状态经过一条 a弧而到达的状态的全体。
状态集合 I的有关运算的例子
I={1},?-closure(I)={1,2}；
I={5},?-closure(I)={5,6,2}；
move({1,2},a)={5,3,4}
-closure({5,3,4})={2,3,4,5,6,7,8}；
1 2
5
3
4
6
8
7
a
a
a
构造 NFA N的 状态 K的子集 的算法：
假定所构造的子集族为 C,即 C= (T1,T2,,..,TI),
其中 T1,T2,,..,TI为状态 K的子集。
1 开始，令?-closure(K0)为 C中唯一成员，并且它是未被标记的。
2 while （ C中存在尚未被标记的子集 T） do
{
标记 T；
for 每个输入字母 a do
{
U:=?-closure(move(T,a))；
if U不在 C中 then
将 U作为未标记的子集加在 C中
} }
NFA的确定化例子
4
f
3
5 621i
a a aa
b b b b
Ia Ib
{i,1,2} {1,2,3} {1,2,4}
{1,2,3} {1,2,3,5,6,f} {1,2,4}
{1,2,4} {1,2,3} {1,2,4,5,6,f}
{1,2,3,5,6,f} {1,2,3,5,6,f} {1,2,4,6,f }
{1,2,4,5,6,f} {1,2,3,6,f } {1,2,4,5,6,f}
{1,2,4,6,f } {1,2,3,6,f } {1,2,4,5,6,f}
{1,2,3,6,f } {1,2,3,5,6,f} {1,2,4,6,f }
S A B
A C B
B A D
C C E
D F D
E F D
F C E
4
f
3
5 621i
a a aa
b b b b
等价的 DFA
a
C
DB
A E
F
S b
a
a
a
a
ab
b
b
b
b
a
b
确定有穷自动机的化简说一个有穷自动机是化简了的，即是说，它没有多余状态并且它的状态中没有两个是互相等价的。一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。
所谓有穷自动机的多余状态，是指这样的状态：
从自动机的开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。
DFA的最小化就是寻求最小状态 DFA
最小状态 DFA的含义,
没有多余状态 (死状态 )
没有两个状态是互相等价（不可区别）
两个状态 s和 t可区别：不满足兼容性 ——同是终态或同是非终态传播性 ——从 s出发读入某个 a?a和从
t出发 读入某个 a到达的状态等价。
C和 D同是终态,读入 a到达 C和 F,C和 F同是终态,
C和 F读入 a都到达 C,读入 b都到达 E,C和 D等价
a
C
DB
A E
F
S b
a
a
a
a
ab
b
b
b
b
a
b
最小状态 DFA
对于一个 DFA M =（ K,∑,f,k0,,kt),存在一个 最小状态 DFA M’ =（ K’,∑,f ’,
k0’,,kt’)，,使 L(M’)=L(M),
结论
– 接受 L的最小状态有穷自动机不计同构是唯一的。
,分割法,
DFA的最小化算法的核心把一个 DFA的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的,
算法假定每个状态射出的弧都是完全的,否则,引入一个新状态,叫死状态,该状态是非终态，将不完全的输入弧都射向该状态，对所有输入，
该状态射出的弧还回到自己,
DFA的最小化算法
DFA M =（ K,∑,f,k 0,,kt),最小状态 DFA
M’
1.构造状态的一初始划分?：
终态 kt 和非终态 K- kt两组 (group)
2.对 ∏ 施 用 过程 PP 构造新划分 ∏ new
3,如 ∏ new =∏,则令 ∏ final=∏ 并继续步骤 4,否则 ∏,=∏ new重复 2,
4.为 ∏ final中的每一组选一代表，这些代表构成 M’的状态。若 k是 一代表且
f(k,a)=t,令 r是 t组的 代表，则 M’中有一转换 f’(k,a)=r
M’ 的开始状态是含有 S0的那组的代表 M’
的终态是含有 F的那组的代表
5.去掉 M’中的死状态,
过程 PP,Construction of ∏ new
– For each group G of ∏ do
– begin
– 1.Partiton G into subgroups such that
two states s and t of G are in the
same subgroups if and only if for all
input symbols a,states s and t have
transitions on a to states in the
same group of ∏;/*at worst,a state
will be in a subgroup by itself*/
– 2.replace G in ∏new by the set of all
subgroups formed
– end
DFA的最小化 —例 子
∏0:{ S,A,B}
{C,D,E,F}
∏1:{S,A,B}
{C,D,E,F}
∏2,
C
DB
A E
F
S b
a
a
a
a
a
ab
b
b
b
b
ba
}{}{A S,B
b
B{{ S }} DB
A
S
a
a
a
b
b
b
ba
a
词法分析程序 的 自动 构造对有穷自动机和正规表达式进行了上述讨论之后,我们介绍 词法分析程序 的 自动 构造方法,这个方法基于有穷自动机和正规表达式的等价性,即,
1.对于 ∑ 上的一个 NFA M，可以构造一个 ∑ 上的正规式 R,使得 L(R)=L(M)。
2.对于 ∑ 上的一个正规式 R，可以构造一个 ∑ 上的 NFA M,使 的 L(M)=L(R)。
从 Σ上的一个正规式 R构造 Σ上的一个 NFA
M,使得 L(M)=L(R)的方法。
,语法制导,的方法，即按正规式的语法结构指引构造过程，构造规则具体描述如下：
.,对于 ∑ 上的 一个正规式 R,可以构造一个 ∑ 上的 NFA
M，,使得 L(M)=L(R).” 说明一种构造方法：
(1)R=?,构造 任一具有空终态集的 NFA M
(2） R=?,构造 的 NFA M=({k0},∑,f,k 0.{k0}),
f（ k0,a)对于 所有 a?∑ 都没定义。
(3） R=a,构造 的 NFA M=({k0,,k1},∑,f,k 0.{k1}),
f(k0,a) = k1
(4) R =R1 | R2,将步骤（ 1）（ 2）（ 3）分别应用到 R1,R2 产生 M1= =(K1,∑,f1,k1,F1),
M2=(K2,∑,f2,k2,F2),其中 K1,K2不相交,构造 的
NFA M= (K1?K2?{k},∑,f,k,F),
k是新增加的状态符号，
f包含 f1和 f2,且 f(k,a)=f1(k1,a)?f2(k2,a),
若 k1?F1且 k2?F2则 F=F1? F2,否则 F=F1? F2
{k}
(5)R=R1.R2
将步骤（ 1）（ 2）（ 3）分别应用到 R1,R2 产生
M1==(K1,∑,f1,k1,F1),M2=(K2,∑,f2,k2,F2),其中 K1,K2不相交,
构造 的 NFA M= (K1?K2,∑,f,k 1,F2),f包含 f1和 f2,
且
f(k,a)=f1(k,a),当 k?F1时 ;
f(k,a)=f2(k,a),当 k∈ K2时 ;
f(k1,?)=k2,
(6)R=R1*
将步骤（ 1）（ 2）（ 3）分别应用到 R1,产生 M1==(K1,∑,f1,k1,F1),
构造 的 NFA M= (K1? {k0,F0},∑,f,k 0,F0)其中 k0,F0 是新增加的两个状态,
f(k,a)=f1(k,a),当 k?F1时 ;
f(k0,?)=f(F1,?)= {k1,,F0},
,
对于正规式 R=?,构造的 NFA
F
S
对于正规式 R=?,构造的 NFA
F
对于正规式 R=a,构造的 NFA
F
S
a
对于正规式 r,r= R1|R2构造的 NFA
对于正规式 r,r=R1 R2构造的 NFA
对于正规式 r,r=R1*构造的 NFA
正规表达式 1*0(0+1)*
举例,从 正规表达式 构造等价的? - NFA
1
0
0+1
11*
从 正规表达式 构造等价的? - NFA
(0+1)* 1
0
1
1
0
0
1*0(0+1)*
R=(a|ab)* b b*
正规式用于说明 (描述 )单词的结构十分简洁方便。而把一个正规式编译 (或称转换 )为一个 NFA进而转换为相应的 DFA,这个
NFA或 DFA正是识别该正规式所表示的语言的句子的识别器。基于这种方法来构造词法分析程序词法分析程序的设计技术可应用于其它领域，比如查询语言以及信息检索系统等，这种应用领域的程序设计特点是，通过字符串模式的匹配来引发动作又如 LEX,说明词法分析程序的语言，可以看成是一个模式动作语言。
词法分析程序的自动构造工具也广泛应用于许多方面，
如用以生成一个程序，可识别印刷电路板中的缺陷，
又如开关线路设计和文本编辑的自动生成等。
习题
4.7 练习
1 （ 1）
3
4 (b)
5
本章小结词法分析程序是编译第一阶段的工作，它读入字符流的源程序，按照词法规则识别单词，
交由语法分析程序接下去。
本章讲述了词法分析程序设计原则，并介绍了分别作为正规集描述和识别机制的正规式和有穷动机。在此基础上给出了词法分析程序自动构造工具如 LEX的原理。
