本章将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。
3.1 词法分析程序
3.2 正规表达式与正规集（正规语言）
3.3 有穷自动机
3.4 词法分析程序 的 自动 构造第三章 词法分析本章重点
单词的描述工具
单词的识别系统
设计和实现词法分析程序
– 首先需要描述和刻画程序设计语言中的原子单位 ——单词，其次需要识别单词和执行某些相关的动作。
– 描述程序设计语言的词法的机制是正则表达式，识别机制是有穷状态自动机。
回顾 什麽是词法分析程序
实现词法分析（ lexical analysis） 的程序
– 逐个读入源程序字符并按照构词规则切分成一系列单词。 单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符号和常量等。
词法分析是编译过程中的一个阶段，在语法分析前进行 。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。
词法分析程序和语法分析程序的关系源程序 词法分析程序 语法分析程序
Token
get token
….
词法分析程序的 主要任务：
– 读源程序，产生单词符号词法分析程序的 其他任务：
– 滤掉空格，跳过注释、换行符
– 追踪换行标志，复制出错源程序，
– 宏展开,……
常常遇到的术语
Token 单词,词标，符号
lexeme 词素，词位
pattern 模式，式样帮助理解术语
In general,there is a set of strings in the
input for which the same token is produced
as output,This set of strings is described
by a rule called a pattern associated with the
token,The pattern is said to match each
string in the set,A lexeme is a sequence of
characters in the source program that is
matched by the pattern for a token,
e.g.
– Const pi=3.14159； 中的 pi是 token ―identifier‖
的 lexeme,其 pattern为 letter followed by letters
and/or digit.
词法分析工作从语法分析工作独立出来的原因：
– 简化设计
– 改进编译效率
– 增加编译系统的可移植性正规表达式与正规集（正规语言）
程序设计语言中的单词是基本语法成分,单词符号的语法可以用有效的工具加以描述，并且基于这类描述工具，实现词法分析程序的自动构造,
首先表述一些基本 术语和概念,
符号 一个抽象实体,我们不再形式地定义它 (就象几何中的,
点,一样 ).例如字母是符号,数字也是符号。
字母表 字母表是元素的非空有穷集合，我们把字母表中的元素称为符号，因此字母表也称为符号集。
不同的语言可以有不同的字母表，例如汉语的字母表中包括汉字、数字及标点符号等。 PASCAL语言的字母表是由字母、数字、若干专用符号及 BEGIN,IF之类的保留字组成。
– 符号串 由字母表中的符号组成的任何有穷序列称为符号串，例如 00 11 10 是字母表? =｛ 0,1｝ 上的符号串,
字母表 A=｛ a,b,c｝ 上的一些符号串有,a,b,c,ab,aaca。
在符号串中，符号的顺序是很重要的，符号串 ab就不同于 ba,abca和 aabc也不同。
可以使用字母表示符号串，如 x=STR表示,x是由符号
S,T和 R,并按此顺序组成的符号串,。
符号串的长度 如果某符号串 x中有 m个符号，则称其长度为 m,表示为｜ x｜ =m,如 001110的长度是 6。
空符号串,即不包含任何符号的符号串，用 ε表示，其长度为 0，即｜ ε｜ =0。
介绍有关符号串的一些运算 。
符号串的头,尾，固有头和固有尾,如果 z=xy是一符号串，那么 x是 z的头,y是 z的尾，如果 x是非空的，那么 y是固有尾；同样如果 y非空，那么 x是固有头。
举个例子,设 z=abc,那么 z的头是 ε,a,ab,abc,除 abc外，
其它都是固有头； z的尾是 ε,c,bc,abc,z的固有尾是
ε,c,bc。
当对符号串 z=xy的头感兴趣而对其余部分不感兴趣时，采用省略写法,z=x… ；
如果只是为了强调 x在符号串 z中的某处出现，则可表示为,z=… x… ； 符号 t是符号串 z的第一个符号，
则表示为 z=t… 。
符号串的连接,设 x和 y是符号串，它们的连接 xy
是把 y的符号写在 x的符号之后得到的符号串,由于 ε 的含义，显然有 ε x=x ε =x。
例如 x=ST,y=abu,则它们的连接 xy=STabu,看出｜ x｜ =2，｜ y｜ =3，｜ xy｜ =5
符号串的 方幂,符号串自身连接 n次得到的符号串
an 定义为 aa… aa n个 a a1=a,a2=aa且 a0=ε
例；若 x=AB 则,
x0 = ε
x1 =AB
x2 = ABAB
x3 = ABABAB
xn = xxn-1 = xn-1 x (n>0)
符号串集合,若集合 A中所有元素都是某字母表
上的符号串，则称 A为字母表?上的符号串集合。
两个符号串集合 A和 B的乘积定义为 AB =?xy|x?A且 y?B?
若 集合 A=?ab,cde? 集合 B =?0,1?
则 AB =?ab1,ab0,cde0,cde1?
使用?* 表示?上的一切符号串（包括 ε ） 组成的集合。 Σ *称为 Σ 的闭包 。
上的 除 ε 外 的所有符号串组成的集合记为?+ 。
Σ +称为 Σ 的正闭包 。
例,Σ ={a,b}
Σ *={ε,a,b,aa,ab,ba,bb,aaa,aab,… }
Σ +={a,b,aa,ab,ba,bb,aaa,aab,… }
.....,} {2 *
.,,,,,}{ 32**
正规式正规式也称正则表达式,正规表达式
（ regular expression） 是说明单词的模式
(pattern)的一种重要的表示法（记号），
是定义正规集的数学工具。我们用以描述单词符号。下面是正规式和它所表示的正规集的递归定义。
定义（正规式和它所表示的正规集）：
设字母表为?，辅助字母表?`={?,?,?,?，
,?,?}。
1。和?都是?上的正规式，它们所表示的正规集分别为 {?}和 { }；
2。任何 a,a是?上的一个正规式，它所表示的正规集为 {a}；
3。 假定 e1和 e2都是?上的正规式，它们所表示的正规集分别为 L(e1)和 L(e2),那么,(e1),
e1? e2,e1?e2,e1?也都是正规式,它们所表示的正规集分别为 L(e1),L(e1)?L(e2),L(e1)L(e2)
和 (L(e1))?。
4。仅由有限次使用上述三步骤而定义的表达式才是?上的正规式，仅由这些正规式所表示的集合才是?上的正规集。
正规式中的符号其中的,?”读为“或”（也有使用,+”代替,?” 的）；,?”读为“连接”；,?”
读为“闭包”（即，任意有限次的自重复连接）。在不致混淆时，括号可省去，但规定算符的优先顺序为,?”、,?,、,?” 。
连接符,?,一般可省略不写。,?”、,?,
和,?” 都是左结合的。
例子令?={a,b},?上的正规式和相应的正规集的例子有：
正规式 正规集
a {a}
a?b {a,b}
ab {ab}
(a?b)(a?b) {aa,ab,ba,bb}
a? {?,a,a,…… 任意个 a的串 }
正规式 正规集
(a?b)? {?,a,b,aa,ab …… 所有由 a
和 b组成的串 }
(a?b)?(aa?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的数字。
程序设计语言的单词都能用正规式 来定义,
若两个正规式 e1和 e2所表示的正规集相同,
则说 e1和 e2等价,写作 e1=e2。
– 例如,e1= (a?b),e2 = b?a
– 又如,e1= b(ab)?,e2 =(ba)?b
e1= (a?b)?,e2 =(ab?)?
设 r,s,t为正规式，正规式服从的代数规律有：
– 1。 r?s=s?r ―或”服从交换律
– 2。 r?(s?t)=(r?s)?t ―或”的可结合律
– 3。 (rs)t=r(st) ―连接”的可结合律
– 4。 r(s?t)=rs?rt
(s?t)r=sr?tr 分配律
5。r=r,r?=r?是“连接”的恒等元素零一律
6。 r?r=r
r?=r?rr?…,或”的抽取律有穷自动机有穷自动机 (也称有限自动机 )作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。
有穷自动机分为两类：确定的有穷自动机
(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可以表示成一个状态图 (或称状态转换图 )。假定 DFA M含有 m个状态,n个输入字符，
那么这个状态图含有 m个结点，每个结点最多有 n个弧射出，整个图含有唯一一个初态结点和若干个终态结点，初态结点冠以双箭头,=>”
或标以,-”,终态结点用双圈表示或标以
,+”,若 f(ki,a)=kj,则从状态结点 ki到状态结点 kj画标记为 a的弧；
DFA 的状态图表示
b
S
U
V
Q
a a
a
b
a,b
一个 DFA还可以用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示相应状态行和输入字符列下的新状态，即 k行 a列为 f(k,a)的值。用双箭头,=>” 标明初态；否则第一行即是初态，相应终态行在表的右端标以 1，非终态标以 0。
DFA 的矩阵表示
a b
S U V
U Q V
V U Q
Q Q Q
字符状态
0
0
0
1
为了说明 DFA如何作为一种识别机制,我们还要理解下面的定义
∑* 上的符号串 t在 DFA M上运行一个输入符 号 串 t，（ 将它表示成 Tt1的形式，
其中 T∈ ∑,t1∈ ∑*）在 DFA M=（ K,Σ,f，
S,Z） 上 运行 的定义为：
f（ Q,Tt1） =f（ f（ Q,T）,t1） 其中 Q∈ K
扩充转换函数 f为 K× Σ*→ K上的映射，且：
f（ ki,?） = ki
∑* 上的符号串 t被 DFA M接受
M=（ K,Σ,f,S,Z）
若 t?∑*,f(S,t)=P,其中 S为 M的开始状态，
P? Z,Z为终态集。
则称 t为 DFA M所 接受 （ 识别 ）,
例,证明 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).
对于任何两个有穷自动机 M和 M′，
L(M)=L(M′),则称 M与 M′是等价的,
结论：
上一个符 号 串集 V是正规的，当且仅当存在一个?上的确定有穷自动机 M,使得
V=L(M)。
DFA的确定性表现在转换函数 f:K× Σ→K 是一个单值函数，也就是说，对任何状态
k∈ K,和输入符号 a∈ Σ,f(k,a)唯一地确定了下一个状态。从状态转换图来看，
若字母表 Σ含有 n个输入字符，那末任何一个状态结点最多有 n条弧射出，而且每条弧以一个不同的输入字符标记。
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‘)
review
Regular expressions on the alphabet? are defined by the
following recursive rules:
1) Every symbol ofis a regular expression
2) ε and f?is a regular expression
3) if r1 and r2 are regular expressions,so are
(r1 ) r1 r2 r1 | r2 r1 *
4) Nothing else is a regular expression.
= {0,1,2,3,4,5,6,7,8,9}
(1|2|3|4|5|6|7|8|9|0) * is a regular expression
(1|2|3|4|...8|9|0) (1|2|3...|8|9|0) * is a regular expression
(1|2|3...|8|9|0)+
review
DFA M=（ K,Σ,f,S,Z）
1) A finite set of states,one of which is designated
the initial state or start state,and some of which
are designated as final states.
2) An alphabet of possible input symbols.
3) A finite set of transitions that specifies for each
state and for each symbol of the input alphabet,
which state to go to next.
DFA
DFA= {digit,not digit}
DFA M所能接受的符 号 串的全体记为 L(M).
对于任何两个有穷自动机 M和 M′，
L(M)=L(M′),则称 M与 M′是等价的,
结论：
上一个符 号 串集 V是正规的，当且仅当存在一个?上的确定有穷自动机 M,使得
V=L(M)。
FA 等价不确定的有穷自动机 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（ Z,0） ={P}
f（ P,1） ={Z}
f（ Z,1） ={P}
f（ S,1） ={S,Z}
状态图表示
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被 NFA M接受也可以这样理解对于 Σ﹡ 中的任何一个串 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的矩阵表示中可以看出，表项通常是一状态的集合，而在 DFA的矩阵表示中，
表项是一个状态,NFA到相应的 DFA的构造的基本思路是,DFA的每一个状态对应 NFA的一组状态,DFA使用它的状态去记录在 NFA读入一个输入符号后可能达到的所有状态,
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
3.4词法分析程序 的 自动 构造对有穷自动机和正规表达式进行了上述讨论之后,我们介绍 词法分析程序 的 自动 构造方法,这个方法基于有穷自动机和正规表达式的等价性,即,
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},
,
再用状态图说明可用方法对于正规式 x,x?∑ 构造的 NFA（ 两种）
X
对于正规式?,构造的 NFA（ 三种）
F
S?
F
对于正规式 R=?,构造的 NFA
F
S
对于正规式 r,r= R1|R2构造的 NFA
对于正规式 r,r=R1 R2构造的 NFA
对于正规式 r,r=R1*构造的 NFA
R=(a|ab)* b b*
正规式用于说明 (描述 )单词的结构十分简洁方便。而把一个正规式编译 (或称转换 )为一个 NFA进而转换为相应的 DFA,这个
NFA或 DFA正是识别该正规式所表示的语言的句子的识别器。基于这种方法来构造词法分析程序词法分析程序的设计技术可应用于其它领域，比如查询语言以及信息检索系统等，这种应用领域的程序设计特点是，通过字符串模式的匹配来引发动作，回想
LEX,说明词法分析程序的语言，可以看成是一个模式动作语言。
词法分析程序的自动构造工具也广泛应用于许多方面，
如用以生成一个程序，可识别印刷电路板中的缺陷，
又如开关线路设计和文本编辑的自动生成等。
习题
4.7 练习
1 （ 1）
3
4 (b)
5
本章小结词法分析程序是编译第一阶段的工作，它读入字符流的源程序，按照词法规则识别单词，
交由语法分析程序接下去。
本章讲述了词法分析程序设计原则，并介绍了分别作为正规集的描述机制和识别机制的正规式和有穷动机。在此基础上给出了词法分析程序自动构造工具如 LEX的原理。
识别 Pl0单词的 FA
NFA的确定化 More example
DFA的最小化算法 —英 文描述
1,Construct an initial partition∏ of
the set of states with two
groups:the accepting states F and
the nonaccepting states S-F.
2,Apply the procedure PP.(Construction of
∏ new) to ∏ to construct a new partition
∏ new.
3,If ∏ new =∏,let ∏ final=∏ and continue
with step (4),Otherwise,repeat step(2)
with ∏:= ∏ new.
4,Choose one state in each group of the
partition ∏ final as the representative for
the group.The representatives will be the
states of the reduced DFA M‘.let s be a
representative state,and suppose on input a
there is a transition from s to t,Let r be
the representative of t‘s group(r may be
t).Then M‘ has a transition from s to r on
a.Let the start state of M‘ be the
representative of the group containing the
start state s0 of M.and let the accepting
states of M‘ be the representative that are
in F.Note that each group of ∏ final either
consists only of states in F or has no
states in F.
5,If M‘ has a dead state,that is,a
states d that is not accepting and
that has transitions to itself on all
input symbols,then remove d from
M‘,Also remove any states not
reachable from the start state,Any
transitions to d from other states
become undefined.
3.1 词法分析程序
3.2 正规表达式与正规集（正规语言）
3.3 有穷自动机
3.4 词法分析程序 的 自动 构造第三章 词法分析本章重点
单词的描述工具
单词的识别系统
设计和实现词法分析程序
– 首先需要描述和刻画程序设计语言中的原子单位 ——单词，其次需要识别单词和执行某些相关的动作。
– 描述程序设计语言的词法的机制是正则表达式，识别机制是有穷状态自动机。
回顾 什麽是词法分析程序
实现词法分析（ lexical analysis） 的程序
– 逐个读入源程序字符并按照构词规则切分成一系列单词。 单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符号和常量等。
词法分析是编译过程中的一个阶段，在语法分析前进行 。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。
词法分析程序和语法分析程序的关系源程序 词法分析程序 语法分析程序
Token
get token
….
词法分析程序的 主要任务：
– 读源程序，产生单词符号词法分析程序的 其他任务：
– 滤掉空格，跳过注释、换行符
– 追踪换行标志，复制出错源程序，
– 宏展开,……
常常遇到的术语
Token 单词,词标，符号
lexeme 词素，词位
pattern 模式，式样帮助理解术语
In general,there is a set of strings in the
input for which the same token is produced
as output,This set of strings is described
by a rule called a pattern associated with the
token,The pattern is said to match each
string in the set,A lexeme is a sequence of
characters in the source program that is
matched by the pattern for a token,
e.g.
– Const pi=3.14159； 中的 pi是 token ―identifier‖
的 lexeme,其 pattern为 letter followed by letters
and/or digit.
词法分析工作从语法分析工作独立出来的原因：
– 简化设计
– 改进编译效率
– 增加编译系统的可移植性正规表达式与正规集（正规语言）
程序设计语言中的单词是基本语法成分,单词符号的语法可以用有效的工具加以描述，并且基于这类描述工具，实现词法分析程序的自动构造,
首先表述一些基本 术语和概念,
符号 一个抽象实体,我们不再形式地定义它 (就象几何中的,
点,一样 ).例如字母是符号,数字也是符号。
字母表 字母表是元素的非空有穷集合，我们把字母表中的元素称为符号，因此字母表也称为符号集。
不同的语言可以有不同的字母表，例如汉语的字母表中包括汉字、数字及标点符号等。 PASCAL语言的字母表是由字母、数字、若干专用符号及 BEGIN,IF之类的保留字组成。
– 符号串 由字母表中的符号组成的任何有穷序列称为符号串，例如 00 11 10 是字母表? =｛ 0,1｝ 上的符号串,
字母表 A=｛ a,b,c｝ 上的一些符号串有,a,b,c,ab,aaca。
在符号串中，符号的顺序是很重要的，符号串 ab就不同于 ba,abca和 aabc也不同。
可以使用字母表示符号串，如 x=STR表示,x是由符号
S,T和 R,并按此顺序组成的符号串,。
符号串的长度 如果某符号串 x中有 m个符号，则称其长度为 m,表示为｜ x｜ =m,如 001110的长度是 6。
空符号串,即不包含任何符号的符号串，用 ε表示，其长度为 0，即｜ ε｜ =0。
介绍有关符号串的一些运算 。
符号串的头,尾，固有头和固有尾,如果 z=xy是一符号串，那么 x是 z的头,y是 z的尾，如果 x是非空的，那么 y是固有尾；同样如果 y非空，那么 x是固有头。
举个例子,设 z=abc,那么 z的头是 ε,a,ab,abc,除 abc外，
其它都是固有头； z的尾是 ε,c,bc,abc,z的固有尾是
ε,c,bc。
当对符号串 z=xy的头感兴趣而对其余部分不感兴趣时，采用省略写法,z=x… ；
如果只是为了强调 x在符号串 z中的某处出现，则可表示为,z=… x… ； 符号 t是符号串 z的第一个符号，
则表示为 z=t… 。
符号串的连接,设 x和 y是符号串，它们的连接 xy
是把 y的符号写在 x的符号之后得到的符号串,由于 ε 的含义，显然有 ε x=x ε =x。
例如 x=ST,y=abu,则它们的连接 xy=STabu,看出｜ x｜ =2，｜ y｜ =3，｜ xy｜ =5
符号串的 方幂,符号串自身连接 n次得到的符号串
an 定义为 aa… aa n个 a a1=a,a2=aa且 a0=ε
例；若 x=AB 则,
x0 = ε
x1 =AB
x2 = ABAB
x3 = ABABAB
xn = xxn-1 = xn-1 x (n>0)
符号串集合,若集合 A中所有元素都是某字母表
上的符号串，则称 A为字母表?上的符号串集合。
两个符号串集合 A和 B的乘积定义为 AB =?xy|x?A且 y?B?
若 集合 A=?ab,cde? 集合 B =?0,1?
则 AB =?ab1,ab0,cde0,cde1?
使用?* 表示?上的一切符号串（包括 ε ） 组成的集合。 Σ *称为 Σ 的闭包 。
上的 除 ε 外 的所有符号串组成的集合记为?+ 。
Σ +称为 Σ 的正闭包 。
例,Σ ={a,b}
Σ *={ε,a,b,aa,ab,ba,bb,aaa,aab,… }
Σ +={a,b,aa,ab,ba,bb,aaa,aab,… }
.....,} {2 *
.,,,,,}{ 32**
正规式正规式也称正则表达式,正规表达式
（ regular expression） 是说明单词的模式
(pattern)的一种重要的表示法（记号），
是定义正规集的数学工具。我们用以描述单词符号。下面是正规式和它所表示的正规集的递归定义。
定义（正规式和它所表示的正规集）：
设字母表为?，辅助字母表?`={?,?,?,?，
,?,?}。
1。和?都是?上的正规式，它们所表示的正规集分别为 {?}和 { }；
2。任何 a,a是?上的一个正规式，它所表示的正规集为 {a}；
3。 假定 e1和 e2都是?上的正规式，它们所表示的正规集分别为 L(e1)和 L(e2),那么,(e1),
e1? e2,e1?e2,e1?也都是正规式,它们所表示的正规集分别为 L(e1),L(e1)?L(e2),L(e1)L(e2)
和 (L(e1))?。
4。仅由有限次使用上述三步骤而定义的表达式才是?上的正规式，仅由这些正规式所表示的集合才是?上的正规集。
正规式中的符号其中的,?”读为“或”（也有使用,+”代替,?” 的）；,?”读为“连接”；,?”
读为“闭包”（即，任意有限次的自重复连接）。在不致混淆时，括号可省去，但规定算符的优先顺序为,?”、,?,、,?” 。
连接符,?,一般可省略不写。,?”、,?,
和,?” 都是左结合的。
例子令?={a,b},?上的正规式和相应的正规集的例子有：
正规式 正规集
a {a}
a?b {a,b}
ab {ab}
(a?b)(a?b) {aa,ab,ba,bb}
a? {?,a,a,…… 任意个 a的串 }
正规式 正规集
(a?b)? {?,a,b,aa,ab …… 所有由 a
和 b组成的串 }
(a?b)?(aa?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的数字。
程序设计语言的单词都能用正规式 来定义,
若两个正规式 e1和 e2所表示的正规集相同,
则说 e1和 e2等价,写作 e1=e2。
– 例如,e1= (a?b),e2 = b?a
– 又如,e1= b(ab)?,e2 =(ba)?b
e1= (a?b)?,e2 =(ab?)?
设 r,s,t为正规式，正规式服从的代数规律有：
– 1。 r?s=s?r ―或”服从交换律
– 2。 r?(s?t)=(r?s)?t ―或”的可结合律
– 3。 (rs)t=r(st) ―连接”的可结合律
– 4。 r(s?t)=rs?rt
(s?t)r=sr?tr 分配律
5。r=r,r?=r?是“连接”的恒等元素零一律
6。 r?r=r
r?=r?rr?…,或”的抽取律有穷自动机有穷自动机 (也称有限自动机 )作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。
有穷自动机分为两类：确定的有穷自动机
(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可以表示成一个状态图 (或称状态转换图 )。假定 DFA M含有 m个状态,n个输入字符，
那么这个状态图含有 m个结点，每个结点最多有 n个弧射出，整个图含有唯一一个初态结点和若干个终态结点，初态结点冠以双箭头,=>”
或标以,-”,终态结点用双圈表示或标以
,+”,若 f(ki,a)=kj,则从状态结点 ki到状态结点 kj画标记为 a的弧；
DFA 的状态图表示
b
S
U
V
Q
a a
a
b
a,b
一个 DFA还可以用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示相应状态行和输入字符列下的新状态，即 k行 a列为 f(k,a)的值。用双箭头,=>” 标明初态；否则第一行即是初态，相应终态行在表的右端标以 1，非终态标以 0。
DFA 的矩阵表示
a b
S U V
U Q V
V U Q
Q Q Q
字符状态
0
0
0
1
为了说明 DFA如何作为一种识别机制,我们还要理解下面的定义
∑* 上的符号串 t在 DFA M上运行一个输入符 号 串 t，（ 将它表示成 Tt1的形式，
其中 T∈ ∑,t1∈ ∑*）在 DFA M=（ K,Σ,f，
S,Z） 上 运行 的定义为：
f（ Q,Tt1） =f（ f（ Q,T）,t1） 其中 Q∈ K
扩充转换函数 f为 K× Σ*→ K上的映射，且：
f（ ki,?） = ki
∑* 上的符号串 t被 DFA M接受
M=（ K,Σ,f,S,Z）
若 t?∑*,f(S,t)=P,其中 S为 M的开始状态，
P? Z,Z为终态集。
则称 t为 DFA M所 接受 （ 识别 ）,
例,证明 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).
对于任何两个有穷自动机 M和 M′，
L(M)=L(M′),则称 M与 M′是等价的,
结论：
上一个符 号 串集 V是正规的，当且仅当存在一个?上的确定有穷自动机 M,使得
V=L(M)。
DFA的确定性表现在转换函数 f:K× Σ→K 是一个单值函数，也就是说，对任何状态
k∈ K,和输入符号 a∈ Σ,f(k,a)唯一地确定了下一个状态。从状态转换图来看，
若字母表 Σ含有 n个输入字符，那末任何一个状态结点最多有 n条弧射出，而且每条弧以一个不同的输入字符标记。
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‘)
review
Regular expressions on the alphabet? are defined by the
following recursive rules:
1) Every symbol ofis a regular expression
2) ε and f?is a regular expression
3) if r1 and r2 are regular expressions,so are
(r1 ) r1 r2 r1 | r2 r1 *
4) Nothing else is a regular expression.
= {0,1,2,3,4,5,6,7,8,9}
(1|2|3|4|5|6|7|8|9|0) * is a regular expression
(1|2|3|4|...8|9|0) (1|2|3...|8|9|0) * is a regular expression
(1|2|3...|8|9|0)+
review
DFA M=（ K,Σ,f,S,Z）
1) A finite set of states,one of which is designated
the initial state or start state,and some of which
are designated as final states.
2) An alphabet of possible input symbols.
3) A finite set of transitions that specifies for each
state and for each symbol of the input alphabet,
which state to go to next.
DFA
DFA= {digit,not digit}
DFA M所能接受的符 号 串的全体记为 L(M).
对于任何两个有穷自动机 M和 M′，
L(M)=L(M′),则称 M与 M′是等价的,
结论：
上一个符 号 串集 V是正规的，当且仅当存在一个?上的确定有穷自动机 M,使得
V=L(M)。
FA 等价不确定的有穷自动机 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（ Z,0） ={P}
f（ P,1） ={Z}
f（ Z,1） ={P}
f（ S,1） ={S,Z}
状态图表示
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被 NFA M接受也可以这样理解对于 Σ﹡ 中的任何一个串 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的矩阵表示中可以看出，表项通常是一状态的集合，而在 DFA的矩阵表示中，
表项是一个状态,NFA到相应的 DFA的构造的基本思路是,DFA的每一个状态对应 NFA的一组状态,DFA使用它的状态去记录在 NFA读入一个输入符号后可能达到的所有状态,
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
3.4词法分析程序 的 自动 构造对有穷自动机和正规表达式进行了上述讨论之后,我们介绍 词法分析程序 的 自动 构造方法,这个方法基于有穷自动机和正规表达式的等价性,即,
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},
,
再用状态图说明可用方法对于正规式 x,x?∑ 构造的 NFA（ 两种）
X
对于正规式?,构造的 NFA（ 三种）
F
S?
F
对于正规式 R=?,构造的 NFA
F
S
对于正规式 r,r= R1|R2构造的 NFA
对于正规式 r,r=R1 R2构造的 NFA
对于正规式 r,r=R1*构造的 NFA
R=(a|ab)* b b*
正规式用于说明 (描述 )单词的结构十分简洁方便。而把一个正规式编译 (或称转换 )为一个 NFA进而转换为相应的 DFA,这个
NFA或 DFA正是识别该正规式所表示的语言的句子的识别器。基于这种方法来构造词法分析程序词法分析程序的设计技术可应用于其它领域，比如查询语言以及信息检索系统等，这种应用领域的程序设计特点是，通过字符串模式的匹配来引发动作，回想
LEX,说明词法分析程序的语言，可以看成是一个模式动作语言。
词法分析程序的自动构造工具也广泛应用于许多方面，
如用以生成一个程序，可识别印刷电路板中的缺陷，
又如开关线路设计和文本编辑的自动生成等。
习题
4.7 练习
1 （ 1）
3
4 (b)
5
本章小结词法分析程序是编译第一阶段的工作，它读入字符流的源程序，按照词法规则识别单词，
交由语法分析程序接下去。
本章讲述了词法分析程序设计原则，并介绍了分别作为正规集的描述机制和识别机制的正规式和有穷动机。在此基础上给出了词法分析程序自动构造工具如 LEX的原理。
识别 Pl0单词的 FA
NFA的确定化 More example
DFA的最小化算法 —英 文描述
1,Construct an initial partition∏ of
the set of states with two
groups:the accepting states F and
the nonaccepting states S-F.
2,Apply the procedure PP.(Construction of
∏ new) to ∏ to construct a new partition
∏ new.
3,If ∏ new =∏,let ∏ final=∏ and continue
with step (4),Otherwise,repeat step(2)
with ∏:= ∏ new.
4,Choose one state in each group of the
partition ∏ final as the representative for
the group.The representatives will be the
states of the reduced DFA M‘.let s be a
representative state,and suppose on input a
there is a transition from s to t,Let r be
the representative of t‘s group(r may be
t).Then M‘ has a transition from s to r on
a.Let the start state of M‘ be the
representative of the group containing the
start state s0 of M.and let the accepting
states of M‘ be the representative that are
in F.Note that each group of ∏ final either
consists only of states in F or has no
states in F.
5,If M‘ has a dead state,that is,a
states d that is not accepting and
that has transitions to itself on all
input symbols,then remove d from
M‘,Also remove any states not
reachable from the start state,Any
transitions to d from other states
become undefined.
