3.1 引言
3.2 正则表达式与有穷状态自动机
3.3 词法分析程序的实现
本章小结
第三章 词法分析
3.1 引言
3.1.1 词法分析与词法分析程序
3.1.2 实现方式
第三章 词法分析
3.1 引言
3.1.1 词法分析与词法分析程序
词法分析,
词法分析程序,
词法分析程序功能,
词法规则,
第三章 词法分析
3.1 引言
3.1.1 词法分析与词法分析程序
词法分析,识别出源程序中具有独立含义的最小语法单位 ——
符号或单词，如标识符、无正负号常数与界限符等。
词法分析程序,
词法分析程序功能,
词法规则,
第三章 词法分析
3.1 引言
3.1.1 词法分析与词法分析程序
词法分析：识别出源程序中具有独立含义的最小语法单位 ——
符号或单词，如标识符、无正负号常数与界限符等。
词法分析程序,完成词法分析工作的程序，又称为扫描程序。
词法分析程序功能,
词法规则,
第三章 词法分析
3.1 引言
3.1.1 词法分析与词法分析程序
词法分析：识别出源程序中具有独立含义的最小语法单位 ——
符号或单词，如标识符、无正负号常数与界限符等。
词法分析程序：完成词法分析工作的程序，又称为扫描程序。
词法分析程序功能,
（ 1）读入源程序字符串； （ 2）识别单词；
（ 3）变换成了等价的属性字序列； （ 4）其他。
词法规则,
第三章 词法分析
3.1 引言
3.1.1 词法分析与词法分析程序
词法分析：识别出源程序中具有独立含义的最小语法单位 ——
符号或单词，如标识符、无正负号常数与界限符等。
词法分析程序：完成词法分析工作的程序，又称为扫描程序。
词法分析程序功能,
（ 1）读入源程序字符串； （ 2）识别单词；
（ 3）变换成了等价的属性字序列； （ 4）其他。
词法规则,又叫构词规则, 它们刻划了符号的书写规则, 指明
符号是如何书写或如何构造的 。
第三章 词法分析
3.1 引言
3.1.1 词法分析与词法分析程序
3.1.2 实现方式
? 1)完全融合方式 把有关符号的重写规则与有关一般语法成
分的重写规则统一处理 。
? 2)相对独立方式
? 3)完全独立方式
第三章 词法分析
3.1 引言
3.1.1 词法分析与词法分析程序
3.1.2 实现方式
? 1)完全融合方式 把有关符号的重写规则与有关一般语法成
分的重写规则统一处理 。
? 2)相对独立方式 把词法分析程序作为语法分析程序的一个
独立子程序 。 每当语法分析程序需要一个新符号时便调用这
个子程序 。
? 3)完全独立方式
第三章 词法分析
3.1 引言
3.1.1 词法分析与词法分析程序
3.1.2 实现方式
? 1)完全融合方式 把有关符号的重写规则与有关一般语法成
分的重写规则统一处理 。
? 2)相对独立方式 把词法分析程序作为语法分析程序的一个
独立子程序 。 每当语法分析程序需要一个新符号时便调用这
个子程序 。
? 3)完全独立方式 词法分析程序作为单独一趟来实现, 从而
把词法分析与语法分析工作截然分开 。
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.1 状态转换图与转换系统
3.2.2 确定有穷状态自动机 DFA
3.2.3 非确定有穷状态自动机 NFA
3.2.4 确定有穷状态自动机的化简
3.2.5 正则表达式
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.1 状态转换图与转换系统
? 状态转换图的定义
? 状态转换图的构造
? 应用状态转换图来识别句子
? 用状态转换图为正则语言构造正则文法
? 转换系统
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.1 状态转换图与转换系统
? 状态转换图的定义
状态转换图, 为了识别正则文法的句子而专门设计的有向图
1.有穷多个状态 (结点 ):每个状态结点都代表文法的非终结符号；
2.弧,弧上的标记指明在射出弧的结点状态下可能出现的输入字符或字符
类 。
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.1 状态转换图与转换系统
? 状态转换图的构造
步骤 1：以 S为开始状态作结点；
步骤 2：以每一个非终结符号为状态作结点；
步骤 3：对于形如 Q∷=T 的每个规则, 引一条从开始状态 S到状
态 Q的弧, 其标记为 T；而对形如 Q∷=RT 的规则引一条从状态
R到 Q的弧, 其标记为 T。 其中 R为非终结符号, T为终结符号；
步骤 4：识别符号为终止状态 。
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.1 状态转换图与转换系统
? 状态转换图的构造
步骤 1：以 S为开始状态作结点；
步骤 2：以每一个非终结符号为状态作结点；
步骤 3：对于形如 Q∷=T 的每个规则, 引一条从开始状态 S到状
态 Q的弧, 其标记为 T；而对形如 Q∷=RT 的规则引一条从状态
R到 Q的弧, 其标记为 T。 其中 R为非终结符号, T为终结符号；
步骤 4：识别符号为终止状态 。
G[Z],Z::=Za|Aa|Bb
A::=Ba|a
B::=Ab|b
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.1 状态转换图与转换系统
? 应用状态转换图来识别句子
步骤 1：从开始状态开始，以它作为当前状态，并从 x的最左字
符开始，重复步骤 2直到达到 x的右端为止。
步骤 2：扫描 x的下一字符 (当前字符 )，在当前状态射出的各个
弧中找出标记有该字符的弧，并沿此弧前进，以所达到的状
态作为下一当前状态。
定理 3.1 当识别一个字符串 x时，如果能从状态转换图的开始
状态出发行进达到 x的右端,x为句子的充分必要条件是最后
的当前状态为终止状态。
例如,ababaaa和 bababbb
第三章 词法分析
G[Z],Z::=Za|Aa|Bb
A::=Ba|a
B::=Ab|b
步骤 当前状态 输入的其余部分
1 S a b a b a a a
2 A b a b a a a
3 B a b a a a
4 A b a a a
5 B a a a
6 A a a
7 Z a
8 Z
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.1 状态转换图与转换系统
? 用状态转换图为正则语言构造正则文法
（ 1）为正则语言画出状态转换图。基于其句子的一般形式和
状态转换图运行思想。
（ 2）从该状态转换图构造相应的正则文法。
如果一个状态转换图中有从状态 V到状态 U的弧，弧上标
记为 T，显然必存在规则 U∷=VT ；
如果从开始状态 S到状态 U有一弧，弧上标记为 T时，则
存在规则 U∷=T 。
第三章 词法分析
例如, 对于正则语言 ｛ (ab)nb2｜ n≥ 0｝,
相应的正则文法,
G［ Z］, Z∷=Cb C∷=Bb ｜ b B∷=Ab A∷=Ba ｜ a
（ 1）为正则语言画出状态转换图。
（ 2）从该状态转换图构造相应的正则文法。
如果一个状态转换图中有从状态 V到状态 U的弧，弧上标
记为 T，显然必存在规则 U∷=VT ；
如果从开始状态 S到状态 U有一弧，弧上标记为 T时，则
存在规则 U∷=T 。
第三章 词法分析
3.2 正则表达式与有穷状态自动机
? 转换系统
定义 3.1 转换系统是具有下列三个特征的状态转换图, 即,
1)只有唯一的开始状态 S和唯一的终止状态 Z；
2)在其中无弧进入 S,也无弧自 Z射出；
3)可能存在有 ε 弧, 即标记为 ε (空串 )的弧 。
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.2 确定有穷状态自动机 DFA
? 定义
? 运行 DFA
? FA在计算机内的表示
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.2 确定有穷状态自动机 DFA
定义 3.2 一个确定的有穷状态自动机 DFA是五元组 (K,Σ, M，
S,F),其中,K：有穷非空的状态集合；
Σ,有穷非空的输入字母表；
M：从 K×Σ 到 K的映象 。 如果 M(R,T)=Q,则输
入字符为 T时, 当前状态 R将转换到状态 Q,
Q成为下一当前状态；
S：是开始状态, S∈K ；
F：是非空的终止状态集合, F ? K。
第三章 词法分析
3.2 正则表达式与有穷状态自动机
DFA D2=(K,{a,b},M,S,{Z})
其中,K={S,A,B,C,Z}
M,M(S,a)=A M(S,b)=C
M(A,b)=B
M(B,a)=A M(B,b)=C
M(C,b)=Z
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.2 确定有穷状态自动机 DFA
? 运行 DFA
(1) 运行 DFA的定义
当运行一个 DFA时, 该 DFA的输入是输入字母表 Σ上的一
个字符串, 输出是一个逻辑值, 或为, 是, 或为, 否,, 表
示该字符串是否为该 DFA所接受 。
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.2 确定有穷状态自动机 DFA
? 运行 DFA
(1) 运行 DFA的定义
定义 3.3 扩充了的映象 M定义如下,
M(R,ε )=R,其中 R为任意状态；
M(R,Tt)=M(M(R,T),t),其中 t∈ Σ *,T∈ Σ 。
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.2 确定有穷状态自动机 DFA
? 运行 DFA
(1) 运行 DFA的定义
(2) 字符串被 DFA接受
定义 3.4 对于某个 DFA D=(K,Σ, M,S,F),
如果 M(S,t)=P,P∈F,
则称字符串 t可被该 DFA D所接受 。
第三章 词法分析
3.2 正则表达式与有穷状态自动机
定义 3.4 对于某个 DFA D=(K,Σ, M,S,F),
如果 M(S,t)=P,P∈F,
则称字符串 t可被该 DFA D所接受 。
DFA D=({S,Z,A,B},{a,b},M,S,{Z})
其中,M,M(S,a)=A M(S,b)=B
M(A,a)=Z M(A,b)=B
M(B,a)=A M(B,b)=Z
M(Z,a)=Z
第三章 词法分析
3.2 正则表达式与有穷状态自动机
定义 3.4 对于某个 DFA D=(K,Σ, M,S,F),
如果 M(S,t)=P,P∈F,
则称字符串 t可被该 DFA D所接受 。
DFA D=({S,Z,A,B},{a,b},M,S,{Z})
其中,M,M(S,a)=A M(S,b)=B
M(A,a)=Z M(A,b)=B
M(B,a)=A M(B,b)=Z
M(Z,a)=Z
M(S,ababaa) =M(M(S,a),babaa)=M(M(A,b),abaa)=M(M(B,a),baa)
=M(M(A,b),aa)=M(M(B,a),a)=M(A,a)=Z
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.2 确定有穷状态自动机 DFA
? 运行 DFA
(1) 运行 DFA的定义
(2) 字符串被 DFA接受
定义 3.5 由有穷状态自动机接受的字符串集合称正则集,
对于 (D)FA D,记为 L(D)。
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.2 确定有穷状态自动机 DFA
? 运行 DFA
(1) 运行 DFA的定义
(2) 字符串被 DFA接受
(3) 两个定理
定理 3.3 如果句子 x属于正则文法 G,则它能为 G的相应 FA所接
受；反之, 对于任何 FA D存在一个正则文法 G,G的句子正
是该 FA D所能接受的那些字符串 。
定理 3.4 接受正则语言 L的最小状态自动机不计同构 (即状态可
重新命名 )是唯一的 。
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.2 确定有穷状态自动机 DFA
? FA在计算机内的表示
1)矩阵表示
DFA D=({S,Z,A,B},{a,b},M,S,{Z})
其中,M,M(S,a)=A M(S,b)=B
M(A,a)=Z M(A,b)=B
M(B,a)=A M(B,b)=Z
M(Z,a)=Z
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.2 确定有穷状态自动机 DFA
? FA在计算机内的表示
1)矩阵表示
2)表结构表示
DFA D=({S,Z,A,B},{a,b},M,S,{Z})
其中,M,M(S,a)=A M(S,b)=B
M(A,a)=Z M(A,b)=B
M(B,a)=A M(B,b)=Z
M(Z,a)=Z
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.3 非确定有穷状态自动机 NFA
? 定义
? 运行 NFA
? 从 NFA产生 DFA
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.3 非确定有穷状态自动机 NFA
? 定义
定义 3.6 一个非确定的有穷状态自动机 NFA是一个五元组
(K,Σ, M,S,F),
其中,K：有穷非空的状态集合；
Σ,有穷非空的输入字母表；
M：从 K×Σ 到 K的子集所组成集合的映象；
S：非空的开始状态集合, S ? K；
F：非空的终止状态集合, F ? K。
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.3 非确定有穷状态自动机 NFA
? 定义
例如, 正则文法 G[Z],Z ∷=Za ｜ Aa｜ Bb
A ∷=Ba ｜ Za｜ a
B ∷=Ab ｜ Ba｜ b
NFA N=（ {S,A,B,Z},{a,b},M,{S},{Z}）
其中 M,M(S,a)={A} M(S,b)={B}
M(A,a)={Z} M(A,b)={B}
M(B,a)={A,B} M(B,b)={Z}
M(Z,a)={A,Z} M(Z,b)= ?
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.3 非确定有穷状态自动机 NFA
? 运行 NFA
定义 3.7 扩充了的映象 M定义如下,
M(R,ε )={R},其中 R是任意的状态；
M(R,Tt)= M(｛ Q1,Q2,…,Qn｝, t),
其中 T∈ Σ, t∈ Σ *,而
M(R,T)={Q1,Q2,…,Qn}
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.3 非确定有穷状态自动机 NFA
? 运行 NFA
如果对于某个 NFA存在状态 P,P∈ F,有 P∈ M(S′,t),
S′∈ S,则说字符串 t可被该 NFA所接受 。
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.3 非确定有穷状态自动机 NFA
? 运行 NFA
例如, 正则文法 G[Z],Z ∷=Za ｜ Aa｜ Bb
A ∷=Ba ｜ Za｜ a
B ∷=Ab ｜ Ba｜ b
对于输入字符串 t=babbabb
NFA N=（ {S,A,B,Z},{a,b},M,{S},{Z}）
其中 M,M(S,a)={A} M(S,b)={B}
M(A,a)={Z} M(A,b)={B}
M(B,a)={A,B} M(B,b)={Z}
M(Z,a)={A,Z} M(Z,b)= ?
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.3 非确定有穷状态自动机 NFA
? 运行 NFA
定理 3.5 从任一正则文法 G出发, 能够构造出状态转换图
及其 NFA,此 NFA能接受 G的任一句子；反之, 对任一 NFA,
能找到一个正则文法 G,使得 G的句子正是该 NFA所能接受的
那些字符串 。
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.3 非确定有穷状态自动机 NFA
? 从 NFA产生 DFA
定理 3.6 设 N=(K,Σ, M,S,F)是一个 NFA,它所接受的字符
串集合是 L,则可定义一个 DFA N’=(K’,Σ, M’,S’,F’),
其中,K’是有穷非空的状态集合, 它由 K的一切子集所组成 。
M′ 是由下式定义的映象,
M′ (［ R1,R2,…,Ri］, T)=［ Q1,Q2,…,Qj］
这里 M({R1,R2,…,Ri},T)={Q1,Q2,…,Qj}。
S′ =［ S1,S2,…,Sn］, 这里 S={S1,S2,…,Sn}。
定理 3.7 设 L是一个为某 NFA所接受的字符串集合, 则存在一个
接受 L的 DFA。
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.3 非确定有穷状态自动机 NFA
? 从 NFA产生 DFA
从 NFA N 构造 DFA N′ 的一般步骤如下,
步骤 1 把一切开始状态 S1,S2,...,Sm合并成一个新的
开始状态 [S1,S2,...,Sm]；
步骤 2 从新开始状态出发, 列表求出其它一切新状态；
步骤 3 以状态名中包含原有终止状态名的一切新状态作为
新终止状态；
步骤 4 构造 DFA N′。
例,NFA N=（ {S,A,B,Z},{a,b},M,{S},{Z}）
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.3 非确定有穷状态自动机 NFA
? 从 NFA产生 DFA
例,NFA N=（ {S,A,B,Z},{a,b},M,{S},{Z}）
则, DFA N’=(K’,{a,b},M’,[S],F’)
其中,K’={[S],[A],[B],[Z],[AB],[AZ],[BZ],[ABZ]}
M’,M’([S],a)=[A] M’([S],b)=[B]
M’([A],a)=[Z] M’([A],b)=[B]
M’([B],a)=[AB] M’([B],b)=[Z]
M’([Z],a)=[AZ]
M’([AB],a)=[ABZ] M’([AB],b)=[BZ]
M’([AZ],a)=[AZ] M’([AZ],b)=[B]
M’([BZ],a)=[ABZ] M’([BZ],b)=[Z]
M’([ABZ],a)=[ABZ] M’([ABZ],b)=[BZ]
F’=｛［ Z］, ［ AZ］, ［ BZ］, ［ ABZ］｝
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.3 非确定有穷状态自动机 NFA
? 从 NFA产生 DFA
例,NFA N=（ {S,A,B,Z},{a,b},M,{S},{Z}）
则, DFA N’=(K’,{a,b},M’,[S],F’)
定义 3.8 设 A与 A’是两个有穷状态自动机, 如果 L(A)=L(A’),即
接受相同的语言, 则称这两个有穷状态自动机 A与 A′等价 。
定理 3.8 存在有判定两个有穷状态自动机是否等价的算法 。
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.4 确定有穷状态自动机的化简
定义 3.9 当运行 DFA A时如果从某个状态 P开始，以字符串 w作
为输入,DFA A将结束于终止状态，而以 w为输入，从另一状
态 Q开始时却结束于非终止状态，或者反之亦然，则说字符
串 w把状态 P同状态 Q区别开。
定义 3.10 不可区别开的两个状态称为等价的状态 。
第三章 词法分析
3.2.4 确定有穷状态自动机的化简
步骤 1 首先构造状态集的分划, 直到不再能有新的分划产生 。 构造新分划的算
法为,
for(分划的每一组 G)
{把 G分划成子组, 使得 G的两个状态 P和 Q属同一个子组, 当且仅当对任何
的输入字符 a,状态 P和 Q转换成的状态都属于分划的同一个子组；
把这样形成的所有子组放进新分划 }
步骤 2 按步骤 1构成最终分划后, 取每组中的一个状态作代表, 而删去其他一切
等价的状态, 则所有这些状态代表构成化简了的 DFA A′ 的状态集合 。
步骤 3 如果 A′ 中有死状态，即对任何输入字符 a都转换到本身而不可能从它达到
终止状态的那些非终止状态，以及不可能从开始状态达到它的那些无用状态，
则把这些死状态与无用状态一概删去。
3.2 正则表达式与有穷状态自动机
3.2.5 正则表达式
? 正则表达式的定义及其性质
? 正则表达式与有穷状态自动机的等价性
? 由正则文法直接构造正则表达式
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.5 正则表达式
? 正则表达式的定义及其性质
定义 3.11 设有字母表 Σ 。 Σ 上的正则表达式递归地定义如下,
(1) ε 与 ?都是 Σ 上的正则表达式, 这里 ε 是空串, 而 ?是空集；
(2) 对于任何的 a∈ Σ, a是 Σ 上的正则表达式；
(3) 如果 e1与 e2是 Σ上的正则表达式,
则 (e1),e1e2,e1｜ e2与 ｛ e1｝ 都是 Σ上的正则表达式 。
例 3.9 设 Σ1=｛ 0,1｝，则 (0｜ 1)｛ 0｜ 1｝是 Σ1上的正则表达式。
例 3.10 设 Σ 2=｛ A,B,0,1｝，则 (A｜ B)｛ A｜ B｜ 0｜ 1｝ 5是 Σ 2上的正
则表达式。
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.5 正则表达式
? 正则表达式的定义及其性质
定义 3.12 正则表达式 e的值是字母表上的正则集, 记作｜ e｜, 定义如下,
｜ ?｜ =? ｜ ε ｜ =｛ ε ｝
｜ a｜ =｛ a｝ ｜ (e)｜ =｜ e｜
｜ e1e2｜ =｜ e1｜｜ e2｜ =｛ xy｜ x∈ ｜ e1｜且 y∈ ｜ e2｜ ｝
｜ e1｜ e2｜ =｜ e1｜ ∪ ｜ e2｜ =｛ x｜ x∈ ｜ e1｜或 x∈ ｜ e2｜ ｝
｜ ｛ e｝ ｜ =｜ e｜ * 即｜ e｜的闭包
例 3.11 (0｜ 1)｛ 0｜ 1｝ 的值是由一切只包含 0与 1的任意序列组成的正则集,
即二进制数集合 。
例 3.12 (A｜ B)｛ A｜ B｜ 0｜ 1｝ 5的值是这样一个正则集, 其中每个字符串都
是以字母 A或 B打头, 后跟以至多 5个字母 (A或 B)或数字 (0或 1)。
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.5 正则表达式
? 正则表达式的定义及其性质
定义 3.13 如果两个正则表达式 e1与 e2表示的正则集相同, 即值相
等, 则称它们是等价的 。 记为 e1=e2。
例 3.13 正则表达式等价的例子有,
b｛ ab｝ =｛ ba｝ b
｛ a｜ b｝ =｛ {a}{b}｝
由此定义可得, 两个等价的正则表达式定义相同的正则集 。
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.5 正则表达式
? 正则表达式的定义及其性质
设 e,e1,e2与 e3均为某字母表上的正则表达式, 则有,
零正则表达式,e｜ ?=?｜ e=e e?=?e=?
单位正则表达式 ε, ε e=eε =e
交换律,e1｜ e2=e2｜ e1
结合律,e1｜ (e2｜ e3)=(e1｜ e2)｜ e3
e1(e2e3)=(e1e2)e3
分配律,e1(e2｜ e3)=e1e2｜ e1e3
(e1｜ e2)e3=e1e3｜ e2e3
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.5 正则表达式
? 正则表达式的定义及其性质
正则表达式与语法规则的关系,
字母表 Σ={字母, 数字 }上的正则表达式, 字母 {字母｜数字 }
扩充 BNF表示法表示的语法规则, <标识符 >∷= 字母 {字母 |数字 }
无正负号整数的正则表达式, 数字 ｛ 数字 ｝
正则表达式,字母 ｛ 字母｜数字 ｝ 5
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.5 正则表达式
? 正则表达式与有穷状态自动机的等价性
定理 3.10 对于字母表 Σ 上的每个正则表达式 e,存在 Σ 上的一
个 DFA A,使得 L(A)=｜ e｜ 。
因此, 对于一个正则表达式 e能构造一个有穷状态自动机 A使得 L(A)=|e|,
相反, 对于一个有穷状态自动机 A能构造一个正则表达式 e使得 |e| =L(A)。
第三章 词法分析
3.3 词法分析程序的实现
3.3.1 单词与属性字
3.3.2 标识符的处理
3.3.3 词法分析程序的实现
第三章 词法分析
3.3 词法分析程序的实现
3.3.1 单词与属性字
? 属性字的一般结构
? 不处理说明部分时属性字的构造
? 处理说明部分时属性字的构造
第三章 词法分析
符号类 符号值
3.3 词法分析程序的实现
3.3.1 单词与属性字
? 属性字的一般结构
? 不处理说明部分时属性字的构造
(1)特定符号类：一个符号类唯一地对应一个符号值，即符号
本身，称为特定符号类。例如，专用符号。
(2)非特定符号类：由于标识符只是一个终结符号，因此把标
识符统归为一类。
第三章 词法分析
符号类 符号值
第三章 词法分析
·? o? àà ±à ?? ?ú ?? ò? ?? · ? o? àà ± à ?? ? ú ?? ò? ??
?T ?¨ò? 0 $UND ( 17 $LPAR
±ê ê? ·? 1 $ID ) 18 $RPAR
?? êy 2 $NUM [ 19 $LS
+ 3 $PLUS ] 20 $RS
- 4 $MINUS { 21 $LB
* 5 $STAR } 22 $RB
/ 6 $SLASH, 23 $COLON
< 7 $LT ￡? 24 $SEMICOLON
<= 8 $LE,25 $COMMA
== 9 $EQ void 26 $VOID
!= 10 $NEQ int 27 $INT
> 11 $GT f lo a t28 $FLOAT
>= 12 $GE char 29 $CHAR
& 13 $ADDR if 30 $IF
&& 14 $AND else 31 $ELSE
|| 15 $OR while 32 $WHILE
= 16 $ASSIGN do 33 $DO
表中给出不指明是特定符号还是非特定符号类的各类符号编码
·? o? àà ±à ?? ?ú ?? ò? ?? · ? o? àà ± à ?? ? ú ?? ò? ??
?T ?¨ò? 0 $UND ( 17 $LPAR
±ê ê? ·? 1 $ID ) 18 $RPAR
?? êy 2 $NUM [ 19 $LS
+ 3 $PLUS ] 20 $RS
- 4 $MINUS { 21 $LB
* 5 $STAR } 22 $RB
/ 6 $SLASH, 23 $COLON
< 7 $LT ; 24 $SEMICOLON
<= 8 $LE,25 $COMMA
== 9 $EQ void 26 $VOID
!= 10 $NEQ int 27 $INT
> 11 $GT f lo a t28 $FLOAT
>= 12 $GE char 29 $CHAR
& 13 $ADDR if 30 $IF
&& 14 $AND else 31 $ELSE
|| 15 $OR while 32 $WHILE
= 16 $ASSIGN do 33 $DO
void main( )
{ int x,AB,C;
x=(AB+C*C)/8;
}
3.3 词法分析程序的实现
3.3.1 单词与属性字
? 属性字的一般结构
? 不处理说明部分时属性字的构造
(3)符号类的编码,
(a)采用自然数顺序编号
(b)分级编码的方法
第三章 词法分析
符号类 符号值
3.3 词法分析程序的实现
3.3.1 单词与属性字
? 属性字的一般结构
? 不处理说明部分时属性字的构造
(3)符号类的编码,
(a)采用自然数顺序编号 特定符号,
(b)分级编码的方法 非特定符号,
第三章 词法分析
符号类 符号值 1
符号类 符号值 0
3.3 词法分析程序的实现
3.3.1 单词与属性字
? 属性字的一般结构
? 不处理说明部分时属性字的构造
(3)符号类的编码,
(a)采用自然数顺序编号 特定符号,
(b)分级编码的方法 非特定符号,
第三章 词法分析
符号类 符号值 1
符号类 符号值 0
ε 0ε 1ε 2ε 3……ε 15ε 16…ε 31
其中 ε 0=1：特定符号类
1 说明符 1 运算符
ε 1= ε 2=
0 非说明符 0 非运算符
ε 3ε 4ε 5ε 6：运算符优先级信息
ε 7…ε 15,符号类编码
ε 16…ε 31：符号值
3.3 词法分析程序的实现
3.3.1 单词与属性字
? 属性字的一般结构
? 不处理说明部分时属性字的构造
(4)与处理有关的表格,
(a)字符表,字符表中列出在源程序中可能出现的一切字符，词法分析
程序输入源程序字符串扫描字符时查看此表。
(b)特定符号及其机内表示表,给出源程序中可能出现的一切特定
符号及相应的机内表示，即特定符号类编码。
(c)标识符表,用来登录源程序中出现的一切标识符。
(d)无正负号整数表,用来登录源程序中出现的一切 无正负号整数
（常量表） 。
第三章 词法分析
3.3 词法分析程序的实现
3.3.1 单词与属性字
? 属性字的一般结构
? 不处理说明部分时属性字的构造
? 处理说明部分时属性字的构造
种类,常量、简单变量、数组、结构体、共用体、文件、标号、指针、函
数、过程与类型；
特征,整型、实型、字符型、枚举型、形参、参数、系统定义的标识符等。
第三章 词法分析
0 种类 (4位 ) 特征 (11位 ) 符号值 (16位 )
3.3 词法分析程序的实现
3.3.2 标识符的处理
? 定义性出现与使用性出现
? 标识符的作用域
? 标识符属性字之符号值的确定
第三章 词法分析
3.3 词法分析程序的实现
3.3.2 标识符的处理
? 定义性出现与使用性出现
定义性出现,当源程序中某标识符在说明部分中首次被说明而
与类型等属性信息相关联时，此标识符便是定义性出现。 定
义性出现时，为标识符构造属性字，这时把标识符及其属性
字内容登录入标识符表。
使用性出现：不是定义性出现的标识符都是使用性出现。当标
识符出现在语句部分中时总是使用性出现，只需复制所构造
的属性字即可。
第三章 词法分析
3.3 词法分析程序的实现
3.3.2 标识符的处理
? 定义性出现与使用性出现
? 标识符的作用域
标识符的作用域是标识符与某种类型等属性信息相关
联的有效范围。
第三章 词法分析
确定标识符的作用域的算法,
1.设置标识符栈为空栈, 它仅包含作为标记的一个间隔, 这对应于第 0层分
程序 。
2.以最外层 (第 0层 )为当前层 。
3.登录当前层中定义性出现的标识符, 为其构造属性字, 连同标识符一起
下推入栈 。
4.若处理到当前层分程序的复合语句之前又进入新的一层分程序, 则在进
入之前把一间隔下推入栈, 以新的一层为当前层重复步骤 3与步骤 4,直
到进入当前层所对应的复合语句 。
5.对当前层所对应复合语句中使用性出现的标识符自栈顶向下地在当前层
查找该标识符 。 查到, 则相应属性字即为该标识符的属性字, 将其复制
到属性字序列中；否则越过间隔在外一层中继续向下查找, 如此继续,
直到查到, 这时进行属性字的复制 。 如果直到最外层 (第 0层 )也未查到,
这表明该标识符未被定义, 可给出出错信息：该标识符未说明 。
6.重复步骤 5直到处理到结束当前层所相应的分程序之 END,这时把当前层
退去, 直到遇到的第一个间隔为止 。 以此间隔作为新的当前层的顶 。
7.重复步骤 3-6,直到源程序扫描完, 也即扫描到结束程序之句点,,, 。
PROGRAM exp2；
VAR x,y,integer;
PROCEDURE f1(p1:real);
VAR s,char;
BEGIN (1)
… x… s…
… p1… y…
END； (2)
PROCEDURE f2(p2:integer); (3)
VAR x,z,s,real;
PROCEDURE f2l;
VAR t,boolean;
BEGIN (4)
… t… y…
… x… s… z… (5)
END;
BEGIN
…
END; (6)
BEGIN
… x… y… s…
END,
PROGRAM exp2；
VAR x,y,integer;
PROCEDURE f1(p1:real);
VAR s,char;
BEGIN (1)
…x…s…
…p1…y…
END； (2)
PROCEDURE f2(p2:integer); (3)
VAR x,z,s,real;
PROCEDURE f2l;
VAR t,boolean;
BEGIN (4)
…t…y…
…x…s…z… (5)
END;
BEGIN
…
END; (6)
BEGIN
…x…y…s…
END,
PROGRAM exp2；
VAR x,y,integer;
PROCEDURE f1(p1:real);
VAR s,char;
BEGIN (1)
…x…s…
…p1…y…
END； (2)
PROCEDURE f2(p2:integer); (3)
VAR x,z,s,real;
PROCEDURE f2l;
VAR t,boolean;
BEGIN (4)
…t…y…
…x…s…z… (5)
END;
BEGIN
…
END; (6)
BEGIN
…x…y…s…
END,
3.3 词法分析程序的实现
3.3.2 标识符的处理
? 定义性出现与使用性出现
? 标识符的作用域
? 标识符属性字之符号值的确定
(1)不处理说明部分的情况,只需依据作用域法则，对不同标识符，
以它们在标识符表中的序号作为属性字符号值即可。
(2)处理说明部分的情况
（ a）对基本类型的简单变量采用编号或标识符表序号作为属性字符号值；
（ b） 对于常量, 以常量表序号作为属性字符号值；
（ c） 对于其它各类标识符, 以相应信息表序号作为属性字符号值 。
第三章 词法分析
3.3 词法分析程序的实现
3.3.1 单词与属性字
3.3.2 标识符的处理
3.3.3 词法分析程序的实现
一个词法分析程序，其基本部分由子程序（函数）组成，
包括取字符子程序、取符号子程序、查造标识符表子程序、
查造常量表子程序以及查符号机内表示对照表子程序等。
第三章 词法分析
3.3 词法分析程序的实现
3.3.1 单词与属性字
3.3.2 标识符的处理
3.3.3 词法分析程序的实现
(1)取字符子程序,从源程序文件中取一个有效字符。
(2)取符号子程序,读入若干字符，并识别出，也即形成一个符号，生
成相应属性字。
约定 1 进入取符号子程序时已取到当前符号的第一个字符；
约定 2 在离开取符号子程序时已取到当前符号的后继字符 。
(3)查造标识符表子程序,当标识符为定义性出现时登录标识符表，形
成相应的属性字；而使用性出现时查标识符表，取出相应的属性字信息。
(4)查造常量表子程序,当一个特定的常量在第一次被扫描到时将它登
录到常量表中。不论是第一次被扫描到还是以后被扫描到，均回送此常
量在常量表中的序号，以此作为属性字中的符号值。
(5)查符号机内表示对照表子程序,在取到一个特定符号时查看对照
表，以确定是哪一个特定符号，从而回送相应的机内表示 (属性字 )。
3.3 词法分析程序的实现
词法分析控制流程图,
3.3 词法分析程序的实现
取符号子程序控制流程图,
3.3 词法分析程序的实现
编写词法分析程序的步骤,
（ 1） 应确定所要实现的语言 （ 或其子集 ） 。
（ 2） 设计属性字, 并设计各类表格, 如标识符表, 常量表,
符号及其机内表示对照表等 。
（ 3） 画出总控流程图及前述各个子程序的流程图 。
3.2 正则表达式与有穷状态自动机
3.3 词法分析程序的实现
本章小结
第三章 词法分析
3.1 引言
3.1.1 词法分析与词法分析程序
3.1.2 实现方式
第三章 词法分析
3.1 引言
3.1.1 词法分析与词法分析程序
词法分析,
词法分析程序,
词法分析程序功能,
词法规则,
第三章 词法分析
3.1 引言
3.1.1 词法分析与词法分析程序
词法分析,识别出源程序中具有独立含义的最小语法单位 ——
符号或单词，如标识符、无正负号常数与界限符等。
词法分析程序,
词法分析程序功能,
词法规则,
第三章 词法分析
3.1 引言
3.1.1 词法分析与词法分析程序
词法分析：识别出源程序中具有独立含义的最小语法单位 ——
符号或单词，如标识符、无正负号常数与界限符等。
词法分析程序,完成词法分析工作的程序，又称为扫描程序。
词法分析程序功能,
词法规则,
第三章 词法分析
3.1 引言
3.1.1 词法分析与词法分析程序
词法分析：识别出源程序中具有独立含义的最小语法单位 ——
符号或单词，如标识符、无正负号常数与界限符等。
词法分析程序：完成词法分析工作的程序，又称为扫描程序。
词法分析程序功能,
（ 1）读入源程序字符串； （ 2）识别单词；
（ 3）变换成了等价的属性字序列； （ 4）其他。
词法规则,
第三章 词法分析
3.1 引言
3.1.1 词法分析与词法分析程序
词法分析：识别出源程序中具有独立含义的最小语法单位 ——
符号或单词，如标识符、无正负号常数与界限符等。
词法分析程序：完成词法分析工作的程序，又称为扫描程序。
词法分析程序功能,
（ 1）读入源程序字符串； （ 2）识别单词；
（ 3）变换成了等价的属性字序列； （ 4）其他。
词法规则,又叫构词规则, 它们刻划了符号的书写规则, 指明
符号是如何书写或如何构造的 。
第三章 词法分析
3.1 引言
3.1.1 词法分析与词法分析程序
3.1.2 实现方式
? 1)完全融合方式 把有关符号的重写规则与有关一般语法成
分的重写规则统一处理 。
? 2)相对独立方式
? 3)完全独立方式
第三章 词法分析
3.1 引言
3.1.1 词法分析与词法分析程序
3.1.2 实现方式
? 1)完全融合方式 把有关符号的重写规则与有关一般语法成
分的重写规则统一处理 。
? 2)相对独立方式 把词法分析程序作为语法分析程序的一个
独立子程序 。 每当语法分析程序需要一个新符号时便调用这
个子程序 。
? 3)完全独立方式
第三章 词法分析
3.1 引言
3.1.1 词法分析与词法分析程序
3.1.2 实现方式
? 1)完全融合方式 把有关符号的重写规则与有关一般语法成
分的重写规则统一处理 。
? 2)相对独立方式 把词法分析程序作为语法分析程序的一个
独立子程序 。 每当语法分析程序需要一个新符号时便调用这
个子程序 。
? 3)完全独立方式 词法分析程序作为单独一趟来实现, 从而
把词法分析与语法分析工作截然分开 。
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.1 状态转换图与转换系统
3.2.2 确定有穷状态自动机 DFA
3.2.3 非确定有穷状态自动机 NFA
3.2.4 确定有穷状态自动机的化简
3.2.5 正则表达式
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.1 状态转换图与转换系统
? 状态转换图的定义
? 状态转换图的构造
? 应用状态转换图来识别句子
? 用状态转换图为正则语言构造正则文法
? 转换系统
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.1 状态转换图与转换系统
? 状态转换图的定义
状态转换图, 为了识别正则文法的句子而专门设计的有向图
1.有穷多个状态 (结点 ):每个状态结点都代表文法的非终结符号；
2.弧,弧上的标记指明在射出弧的结点状态下可能出现的输入字符或字符
类 。
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.1 状态转换图与转换系统
? 状态转换图的构造
步骤 1：以 S为开始状态作结点；
步骤 2：以每一个非终结符号为状态作结点；
步骤 3：对于形如 Q∷=T 的每个规则, 引一条从开始状态 S到状
态 Q的弧, 其标记为 T；而对形如 Q∷=RT 的规则引一条从状态
R到 Q的弧, 其标记为 T。 其中 R为非终结符号, T为终结符号；
步骤 4：识别符号为终止状态 。
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.1 状态转换图与转换系统
? 状态转换图的构造
步骤 1：以 S为开始状态作结点；
步骤 2：以每一个非终结符号为状态作结点；
步骤 3：对于形如 Q∷=T 的每个规则, 引一条从开始状态 S到状
态 Q的弧, 其标记为 T；而对形如 Q∷=RT 的规则引一条从状态
R到 Q的弧, 其标记为 T。 其中 R为非终结符号, T为终结符号；
步骤 4：识别符号为终止状态 。
G[Z],Z::=Za|Aa|Bb
A::=Ba|a
B::=Ab|b
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.1 状态转换图与转换系统
? 应用状态转换图来识别句子
步骤 1：从开始状态开始，以它作为当前状态，并从 x的最左字
符开始，重复步骤 2直到达到 x的右端为止。
步骤 2：扫描 x的下一字符 (当前字符 )，在当前状态射出的各个
弧中找出标记有该字符的弧，并沿此弧前进，以所达到的状
态作为下一当前状态。
定理 3.1 当识别一个字符串 x时，如果能从状态转换图的开始
状态出发行进达到 x的右端,x为句子的充分必要条件是最后
的当前状态为终止状态。
例如,ababaaa和 bababbb
第三章 词法分析
G[Z],Z::=Za|Aa|Bb
A::=Ba|a
B::=Ab|b
步骤 当前状态 输入的其余部分
1 S a b a b a a a
2 A b a b a a a
3 B a b a a a
4 A b a a a
5 B a a a
6 A a a
7 Z a
8 Z
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.1 状态转换图与转换系统
? 用状态转换图为正则语言构造正则文法
（ 1）为正则语言画出状态转换图。基于其句子的一般形式和
状态转换图运行思想。
（ 2）从该状态转换图构造相应的正则文法。
如果一个状态转换图中有从状态 V到状态 U的弧，弧上标
记为 T，显然必存在规则 U∷=VT ；
如果从开始状态 S到状态 U有一弧，弧上标记为 T时，则
存在规则 U∷=T 。
第三章 词法分析
例如, 对于正则语言 ｛ (ab)nb2｜ n≥ 0｝,
相应的正则文法,
G［ Z］, Z∷=Cb C∷=Bb ｜ b B∷=Ab A∷=Ba ｜ a
（ 1）为正则语言画出状态转换图。
（ 2）从该状态转换图构造相应的正则文法。
如果一个状态转换图中有从状态 V到状态 U的弧，弧上标
记为 T，显然必存在规则 U∷=VT ；
如果从开始状态 S到状态 U有一弧，弧上标记为 T时，则
存在规则 U∷=T 。
第三章 词法分析
3.2 正则表达式与有穷状态自动机
? 转换系统
定义 3.1 转换系统是具有下列三个特征的状态转换图, 即,
1)只有唯一的开始状态 S和唯一的终止状态 Z；
2)在其中无弧进入 S,也无弧自 Z射出；
3)可能存在有 ε 弧, 即标记为 ε (空串 )的弧 。
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.2 确定有穷状态自动机 DFA
? 定义
? 运行 DFA
? FA在计算机内的表示
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.2 确定有穷状态自动机 DFA
定义 3.2 一个确定的有穷状态自动机 DFA是五元组 (K,Σ, M，
S,F),其中,K：有穷非空的状态集合；
Σ,有穷非空的输入字母表；
M：从 K×Σ 到 K的映象 。 如果 M(R,T)=Q,则输
入字符为 T时, 当前状态 R将转换到状态 Q,
Q成为下一当前状态；
S：是开始状态, S∈K ；
F：是非空的终止状态集合, F ? K。
第三章 词法分析
3.2 正则表达式与有穷状态自动机
DFA D2=(K,{a,b},M,S,{Z})
其中,K={S,A,B,C,Z}
M,M(S,a)=A M(S,b)=C
M(A,b)=B
M(B,a)=A M(B,b)=C
M(C,b)=Z
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.2 确定有穷状态自动机 DFA
? 运行 DFA
(1) 运行 DFA的定义
当运行一个 DFA时, 该 DFA的输入是输入字母表 Σ上的一
个字符串, 输出是一个逻辑值, 或为, 是, 或为, 否,, 表
示该字符串是否为该 DFA所接受 。
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.2 确定有穷状态自动机 DFA
? 运行 DFA
(1) 运行 DFA的定义
定义 3.3 扩充了的映象 M定义如下,
M(R,ε )=R,其中 R为任意状态；
M(R,Tt)=M(M(R,T),t),其中 t∈ Σ *,T∈ Σ 。
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.2 确定有穷状态自动机 DFA
? 运行 DFA
(1) 运行 DFA的定义
(2) 字符串被 DFA接受
定义 3.4 对于某个 DFA D=(K,Σ, M,S,F),
如果 M(S,t)=P,P∈F,
则称字符串 t可被该 DFA D所接受 。
第三章 词法分析
3.2 正则表达式与有穷状态自动机
定义 3.4 对于某个 DFA D=(K,Σ, M,S,F),
如果 M(S,t)=P,P∈F,
则称字符串 t可被该 DFA D所接受 。
DFA D=({S,Z,A,B},{a,b},M,S,{Z})
其中,M,M(S,a)=A M(S,b)=B
M(A,a)=Z M(A,b)=B
M(B,a)=A M(B,b)=Z
M(Z,a)=Z
第三章 词法分析
3.2 正则表达式与有穷状态自动机
定义 3.4 对于某个 DFA D=(K,Σ, M,S,F),
如果 M(S,t)=P,P∈F,
则称字符串 t可被该 DFA D所接受 。
DFA D=({S,Z,A,B},{a,b},M,S,{Z})
其中,M,M(S,a)=A M(S,b)=B
M(A,a)=Z M(A,b)=B
M(B,a)=A M(B,b)=Z
M(Z,a)=Z
M(S,ababaa) =M(M(S,a),babaa)=M(M(A,b),abaa)=M(M(B,a),baa)
=M(M(A,b),aa)=M(M(B,a),a)=M(A,a)=Z
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.2 确定有穷状态自动机 DFA
? 运行 DFA
(1) 运行 DFA的定义
(2) 字符串被 DFA接受
定义 3.5 由有穷状态自动机接受的字符串集合称正则集,
对于 (D)FA D,记为 L(D)。
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.2 确定有穷状态自动机 DFA
? 运行 DFA
(1) 运行 DFA的定义
(2) 字符串被 DFA接受
(3) 两个定理
定理 3.3 如果句子 x属于正则文法 G,则它能为 G的相应 FA所接
受；反之, 对于任何 FA D存在一个正则文法 G,G的句子正
是该 FA D所能接受的那些字符串 。
定理 3.4 接受正则语言 L的最小状态自动机不计同构 (即状态可
重新命名 )是唯一的 。
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.2 确定有穷状态自动机 DFA
? FA在计算机内的表示
1)矩阵表示
DFA D=({S,Z,A,B},{a,b},M,S,{Z})
其中,M,M(S,a)=A M(S,b)=B
M(A,a)=Z M(A,b)=B
M(B,a)=A M(B,b)=Z
M(Z,a)=Z
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.2 确定有穷状态自动机 DFA
? FA在计算机内的表示
1)矩阵表示
2)表结构表示
DFA D=({S,Z,A,B},{a,b},M,S,{Z})
其中,M,M(S,a)=A M(S,b)=B
M(A,a)=Z M(A,b)=B
M(B,a)=A M(B,b)=Z
M(Z,a)=Z
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.3 非确定有穷状态自动机 NFA
? 定义
? 运行 NFA
? 从 NFA产生 DFA
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.3 非确定有穷状态自动机 NFA
? 定义
定义 3.6 一个非确定的有穷状态自动机 NFA是一个五元组
(K,Σ, M,S,F),
其中,K：有穷非空的状态集合；
Σ,有穷非空的输入字母表；
M：从 K×Σ 到 K的子集所组成集合的映象；
S：非空的开始状态集合, S ? K；
F：非空的终止状态集合, F ? K。
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.3 非确定有穷状态自动机 NFA
? 定义
例如, 正则文法 G[Z],Z ∷=Za ｜ Aa｜ Bb
A ∷=Ba ｜ Za｜ a
B ∷=Ab ｜ Ba｜ b
NFA N=（ {S,A,B,Z},{a,b},M,{S},{Z}）
其中 M,M(S,a)={A} M(S,b)={B}
M(A,a)={Z} M(A,b)={B}
M(B,a)={A,B} M(B,b)={Z}
M(Z,a)={A,Z} M(Z,b)= ?
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.3 非确定有穷状态自动机 NFA
? 运行 NFA
定义 3.7 扩充了的映象 M定义如下,
M(R,ε )={R},其中 R是任意的状态；
M(R,Tt)= M(｛ Q1,Q2,…,Qn｝, t),
其中 T∈ Σ, t∈ Σ *,而
M(R,T)={Q1,Q2,…,Qn}
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.3 非确定有穷状态自动机 NFA
? 运行 NFA
如果对于某个 NFA存在状态 P,P∈ F,有 P∈ M(S′,t),
S′∈ S,则说字符串 t可被该 NFA所接受 。
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.3 非确定有穷状态自动机 NFA
? 运行 NFA
例如, 正则文法 G[Z],Z ∷=Za ｜ Aa｜ Bb
A ∷=Ba ｜ Za｜ a
B ∷=Ab ｜ Ba｜ b
对于输入字符串 t=babbabb
NFA N=（ {S,A,B,Z},{a,b},M,{S},{Z}）
其中 M,M(S,a)={A} M(S,b)={B}
M(A,a)={Z} M(A,b)={B}
M(B,a)={A,B} M(B,b)={Z}
M(Z,a)={A,Z} M(Z,b)= ?
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.3 非确定有穷状态自动机 NFA
? 运行 NFA
定理 3.5 从任一正则文法 G出发, 能够构造出状态转换图
及其 NFA,此 NFA能接受 G的任一句子；反之, 对任一 NFA,
能找到一个正则文法 G,使得 G的句子正是该 NFA所能接受的
那些字符串 。
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.3 非确定有穷状态自动机 NFA
? 从 NFA产生 DFA
定理 3.6 设 N=(K,Σ, M,S,F)是一个 NFA,它所接受的字符
串集合是 L,则可定义一个 DFA N’=(K’,Σ, M’,S’,F’),
其中,K’是有穷非空的状态集合, 它由 K的一切子集所组成 。
M′ 是由下式定义的映象,
M′ (［ R1,R2,…,Ri］, T)=［ Q1,Q2,…,Qj］
这里 M({R1,R2,…,Ri},T)={Q1,Q2,…,Qj}。
S′ =［ S1,S2,…,Sn］, 这里 S={S1,S2,…,Sn}。
定理 3.7 设 L是一个为某 NFA所接受的字符串集合, 则存在一个
接受 L的 DFA。
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.3 非确定有穷状态自动机 NFA
? 从 NFA产生 DFA
从 NFA N 构造 DFA N′ 的一般步骤如下,
步骤 1 把一切开始状态 S1,S2,...,Sm合并成一个新的
开始状态 [S1,S2,...,Sm]；
步骤 2 从新开始状态出发, 列表求出其它一切新状态；
步骤 3 以状态名中包含原有终止状态名的一切新状态作为
新终止状态；
步骤 4 构造 DFA N′。
例,NFA N=（ {S,A,B,Z},{a,b},M,{S},{Z}）
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.3 非确定有穷状态自动机 NFA
? 从 NFA产生 DFA
例,NFA N=（ {S,A,B,Z},{a,b},M,{S},{Z}）
则, DFA N’=(K’,{a,b},M’,[S],F’)
其中,K’={[S],[A],[B],[Z],[AB],[AZ],[BZ],[ABZ]}
M’,M’([S],a)=[A] M’([S],b)=[B]
M’([A],a)=[Z] M’([A],b)=[B]
M’([B],a)=[AB] M’([B],b)=[Z]
M’([Z],a)=[AZ]
M’([AB],a)=[ABZ] M’([AB],b)=[BZ]
M’([AZ],a)=[AZ] M’([AZ],b)=[B]
M’([BZ],a)=[ABZ] M’([BZ],b)=[Z]
M’([ABZ],a)=[ABZ] M’([ABZ],b)=[BZ]
F’=｛［ Z］, ［ AZ］, ［ BZ］, ［ ABZ］｝
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.3 非确定有穷状态自动机 NFA
? 从 NFA产生 DFA
例,NFA N=（ {S,A,B,Z},{a,b},M,{S},{Z}）
则, DFA N’=(K’,{a,b},M’,[S],F’)
定义 3.8 设 A与 A’是两个有穷状态自动机, 如果 L(A)=L(A’),即
接受相同的语言, 则称这两个有穷状态自动机 A与 A′等价 。
定理 3.8 存在有判定两个有穷状态自动机是否等价的算法 。
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.4 确定有穷状态自动机的化简
定义 3.9 当运行 DFA A时如果从某个状态 P开始，以字符串 w作
为输入,DFA A将结束于终止状态，而以 w为输入，从另一状
态 Q开始时却结束于非终止状态，或者反之亦然，则说字符
串 w把状态 P同状态 Q区别开。
定义 3.10 不可区别开的两个状态称为等价的状态 。
第三章 词法分析
3.2.4 确定有穷状态自动机的化简
步骤 1 首先构造状态集的分划, 直到不再能有新的分划产生 。 构造新分划的算
法为,
for(分划的每一组 G)
{把 G分划成子组, 使得 G的两个状态 P和 Q属同一个子组, 当且仅当对任何
的输入字符 a,状态 P和 Q转换成的状态都属于分划的同一个子组；
把这样形成的所有子组放进新分划 }
步骤 2 按步骤 1构成最终分划后, 取每组中的一个状态作代表, 而删去其他一切
等价的状态, 则所有这些状态代表构成化简了的 DFA A′ 的状态集合 。
步骤 3 如果 A′ 中有死状态，即对任何输入字符 a都转换到本身而不可能从它达到
终止状态的那些非终止状态，以及不可能从开始状态达到它的那些无用状态，
则把这些死状态与无用状态一概删去。
3.2 正则表达式与有穷状态自动机
3.2.5 正则表达式
? 正则表达式的定义及其性质
? 正则表达式与有穷状态自动机的等价性
? 由正则文法直接构造正则表达式
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.5 正则表达式
? 正则表达式的定义及其性质
定义 3.11 设有字母表 Σ 。 Σ 上的正则表达式递归地定义如下,
(1) ε 与 ?都是 Σ 上的正则表达式, 这里 ε 是空串, 而 ?是空集；
(2) 对于任何的 a∈ Σ, a是 Σ 上的正则表达式；
(3) 如果 e1与 e2是 Σ上的正则表达式,
则 (e1),e1e2,e1｜ e2与 ｛ e1｝ 都是 Σ上的正则表达式 。
例 3.9 设 Σ1=｛ 0,1｝，则 (0｜ 1)｛ 0｜ 1｝是 Σ1上的正则表达式。
例 3.10 设 Σ 2=｛ A,B,0,1｝，则 (A｜ B)｛ A｜ B｜ 0｜ 1｝ 5是 Σ 2上的正
则表达式。
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.5 正则表达式
? 正则表达式的定义及其性质
定义 3.12 正则表达式 e的值是字母表上的正则集, 记作｜ e｜, 定义如下,
｜ ?｜ =? ｜ ε ｜ =｛ ε ｝
｜ a｜ =｛ a｝ ｜ (e)｜ =｜ e｜
｜ e1e2｜ =｜ e1｜｜ e2｜ =｛ xy｜ x∈ ｜ e1｜且 y∈ ｜ e2｜ ｝
｜ e1｜ e2｜ =｜ e1｜ ∪ ｜ e2｜ =｛ x｜ x∈ ｜ e1｜或 x∈ ｜ e2｜ ｝
｜ ｛ e｝ ｜ =｜ e｜ * 即｜ e｜的闭包
例 3.11 (0｜ 1)｛ 0｜ 1｝ 的值是由一切只包含 0与 1的任意序列组成的正则集,
即二进制数集合 。
例 3.12 (A｜ B)｛ A｜ B｜ 0｜ 1｝ 5的值是这样一个正则集, 其中每个字符串都
是以字母 A或 B打头, 后跟以至多 5个字母 (A或 B)或数字 (0或 1)。
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.5 正则表达式
? 正则表达式的定义及其性质
定义 3.13 如果两个正则表达式 e1与 e2表示的正则集相同, 即值相
等, 则称它们是等价的 。 记为 e1=e2。
例 3.13 正则表达式等价的例子有,
b｛ ab｝ =｛ ba｝ b
｛ a｜ b｝ =｛ {a}{b}｝
由此定义可得, 两个等价的正则表达式定义相同的正则集 。
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.5 正则表达式
? 正则表达式的定义及其性质
设 e,e1,e2与 e3均为某字母表上的正则表达式, 则有,
零正则表达式,e｜ ?=?｜ e=e e?=?e=?
单位正则表达式 ε, ε e=eε =e
交换律,e1｜ e2=e2｜ e1
结合律,e1｜ (e2｜ e3)=(e1｜ e2)｜ e3
e1(e2e3)=(e1e2)e3
分配律,e1(e2｜ e3)=e1e2｜ e1e3
(e1｜ e2)e3=e1e3｜ e2e3
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.5 正则表达式
? 正则表达式的定义及其性质
正则表达式与语法规则的关系,
字母表 Σ={字母, 数字 }上的正则表达式, 字母 {字母｜数字 }
扩充 BNF表示法表示的语法规则, <标识符 >∷= 字母 {字母 |数字 }
无正负号整数的正则表达式, 数字 ｛ 数字 ｝
正则表达式,字母 ｛ 字母｜数字 ｝ 5
第三章 词法分析
3.2 正则表达式与有穷状态自动机
3.2.5 正则表达式
? 正则表达式与有穷状态自动机的等价性
定理 3.10 对于字母表 Σ 上的每个正则表达式 e,存在 Σ 上的一
个 DFA A,使得 L(A)=｜ e｜ 。
因此, 对于一个正则表达式 e能构造一个有穷状态自动机 A使得 L(A)=|e|,
相反, 对于一个有穷状态自动机 A能构造一个正则表达式 e使得 |e| =L(A)。
第三章 词法分析
3.3 词法分析程序的实现
3.3.1 单词与属性字
3.3.2 标识符的处理
3.3.3 词法分析程序的实现
第三章 词法分析
3.3 词法分析程序的实现
3.3.1 单词与属性字
? 属性字的一般结构
? 不处理说明部分时属性字的构造
? 处理说明部分时属性字的构造
第三章 词法分析
符号类 符号值
3.3 词法分析程序的实现
3.3.1 单词与属性字
? 属性字的一般结构
? 不处理说明部分时属性字的构造
(1)特定符号类：一个符号类唯一地对应一个符号值，即符号
本身，称为特定符号类。例如，专用符号。
(2)非特定符号类：由于标识符只是一个终结符号，因此把标
识符统归为一类。
第三章 词法分析
符号类 符号值
第三章 词法分析
·? o? àà ±à ?? ?ú ?? ò? ?? · ? o? àà ± à ?? ? ú ?? ò? ??
?T ?¨ò? 0 $UND ( 17 $LPAR
±ê ê? ·? 1 $ID ) 18 $RPAR
?? êy 2 $NUM [ 19 $LS
+ 3 $PLUS ] 20 $RS
- 4 $MINUS { 21 $LB
* 5 $STAR } 22 $RB
/ 6 $SLASH, 23 $COLON
< 7 $LT ￡? 24 $SEMICOLON
<= 8 $LE,25 $COMMA
== 9 $EQ void 26 $VOID
!= 10 $NEQ int 27 $INT
> 11 $GT f lo a t28 $FLOAT
>= 12 $GE char 29 $CHAR
& 13 $ADDR if 30 $IF
&& 14 $AND else 31 $ELSE
|| 15 $OR while 32 $WHILE
= 16 $ASSIGN do 33 $DO
表中给出不指明是特定符号还是非特定符号类的各类符号编码
·? o? àà ±à ?? ?ú ?? ò? ?? · ? o? àà ± à ?? ? ú ?? ò? ??
?T ?¨ò? 0 $UND ( 17 $LPAR
±ê ê? ·? 1 $ID ) 18 $RPAR
?? êy 2 $NUM [ 19 $LS
+ 3 $PLUS ] 20 $RS
- 4 $MINUS { 21 $LB
* 5 $STAR } 22 $RB
/ 6 $SLASH, 23 $COLON
< 7 $LT ; 24 $SEMICOLON
<= 8 $LE,25 $COMMA
== 9 $EQ void 26 $VOID
!= 10 $NEQ int 27 $INT
> 11 $GT f lo a t28 $FLOAT
>= 12 $GE char 29 $CHAR
& 13 $ADDR if 30 $IF
&& 14 $AND else 31 $ELSE
|| 15 $OR while 32 $WHILE
= 16 $ASSIGN do 33 $DO
void main( )
{ int x,AB,C;
x=(AB+C*C)/8;
}
3.3 词法分析程序的实现
3.3.1 单词与属性字
? 属性字的一般结构
? 不处理说明部分时属性字的构造
(3)符号类的编码,
(a)采用自然数顺序编号
(b)分级编码的方法
第三章 词法分析
符号类 符号值
3.3 词法分析程序的实现
3.3.1 单词与属性字
? 属性字的一般结构
? 不处理说明部分时属性字的构造
(3)符号类的编码,
(a)采用自然数顺序编号 特定符号,
(b)分级编码的方法 非特定符号,
第三章 词法分析
符号类 符号值 1
符号类 符号值 0
3.3 词法分析程序的实现
3.3.1 单词与属性字
? 属性字的一般结构
? 不处理说明部分时属性字的构造
(3)符号类的编码,
(a)采用自然数顺序编号 特定符号,
(b)分级编码的方法 非特定符号,
第三章 词法分析
符号类 符号值 1
符号类 符号值 0
ε 0ε 1ε 2ε 3……ε 15ε 16…ε 31
其中 ε 0=1：特定符号类
1 说明符 1 运算符
ε 1= ε 2=
0 非说明符 0 非运算符
ε 3ε 4ε 5ε 6：运算符优先级信息
ε 7…ε 15,符号类编码
ε 16…ε 31：符号值
3.3 词法分析程序的实现
3.3.1 单词与属性字
? 属性字的一般结构
? 不处理说明部分时属性字的构造
(4)与处理有关的表格,
(a)字符表,字符表中列出在源程序中可能出现的一切字符，词法分析
程序输入源程序字符串扫描字符时查看此表。
(b)特定符号及其机内表示表,给出源程序中可能出现的一切特定
符号及相应的机内表示，即特定符号类编码。
(c)标识符表,用来登录源程序中出现的一切标识符。
(d)无正负号整数表,用来登录源程序中出现的一切 无正负号整数
（常量表） 。
第三章 词法分析
3.3 词法分析程序的实现
3.3.1 单词与属性字
? 属性字的一般结构
? 不处理说明部分时属性字的构造
? 处理说明部分时属性字的构造
种类,常量、简单变量、数组、结构体、共用体、文件、标号、指针、函
数、过程与类型；
特征,整型、实型、字符型、枚举型、形参、参数、系统定义的标识符等。
第三章 词法分析
0 种类 (4位 ) 特征 (11位 ) 符号值 (16位 )
3.3 词法分析程序的实现
3.3.2 标识符的处理
? 定义性出现与使用性出现
? 标识符的作用域
? 标识符属性字之符号值的确定
第三章 词法分析
3.3 词法分析程序的实现
3.3.2 标识符的处理
? 定义性出现与使用性出现
定义性出现,当源程序中某标识符在说明部分中首次被说明而
与类型等属性信息相关联时，此标识符便是定义性出现。 定
义性出现时，为标识符构造属性字，这时把标识符及其属性
字内容登录入标识符表。
使用性出现：不是定义性出现的标识符都是使用性出现。当标
识符出现在语句部分中时总是使用性出现，只需复制所构造
的属性字即可。
第三章 词法分析
3.3 词法分析程序的实现
3.3.2 标识符的处理
? 定义性出现与使用性出现
? 标识符的作用域
标识符的作用域是标识符与某种类型等属性信息相关
联的有效范围。
第三章 词法分析
确定标识符的作用域的算法,
1.设置标识符栈为空栈, 它仅包含作为标记的一个间隔, 这对应于第 0层分
程序 。
2.以最外层 (第 0层 )为当前层 。
3.登录当前层中定义性出现的标识符, 为其构造属性字, 连同标识符一起
下推入栈 。
4.若处理到当前层分程序的复合语句之前又进入新的一层分程序, 则在进
入之前把一间隔下推入栈, 以新的一层为当前层重复步骤 3与步骤 4,直
到进入当前层所对应的复合语句 。
5.对当前层所对应复合语句中使用性出现的标识符自栈顶向下地在当前层
查找该标识符 。 查到, 则相应属性字即为该标识符的属性字, 将其复制
到属性字序列中；否则越过间隔在外一层中继续向下查找, 如此继续,
直到查到, 这时进行属性字的复制 。 如果直到最外层 (第 0层 )也未查到,
这表明该标识符未被定义, 可给出出错信息：该标识符未说明 。
6.重复步骤 5直到处理到结束当前层所相应的分程序之 END,这时把当前层
退去, 直到遇到的第一个间隔为止 。 以此间隔作为新的当前层的顶 。
7.重复步骤 3-6,直到源程序扫描完, 也即扫描到结束程序之句点,,, 。
PROGRAM exp2；
VAR x,y,integer;
PROCEDURE f1(p1:real);
VAR s,char;
BEGIN (1)
… x… s…
… p1… y…
END； (2)
PROCEDURE f2(p2:integer); (3)
VAR x,z,s,real;
PROCEDURE f2l;
VAR t,boolean;
BEGIN (4)
… t… y…
… x… s… z… (5)
END;
BEGIN
…
END; (6)
BEGIN
… x… y… s…
END,
PROGRAM exp2；
VAR x,y,integer;
PROCEDURE f1(p1:real);
VAR s,char;
BEGIN (1)
…x…s…
…p1…y…
END； (2)
PROCEDURE f2(p2:integer); (3)
VAR x,z,s,real;
PROCEDURE f2l;
VAR t,boolean;
BEGIN (4)
…t…y…
…x…s…z… (5)
END;
BEGIN
…
END; (6)
BEGIN
…x…y…s…
END,
PROGRAM exp2；
VAR x,y,integer;
PROCEDURE f1(p1:real);
VAR s,char;
BEGIN (1)
…x…s…
…p1…y…
END； (2)
PROCEDURE f2(p2:integer); (3)
VAR x,z,s,real;
PROCEDURE f2l;
VAR t,boolean;
BEGIN (4)
…t…y…
…x…s…z… (5)
END;
BEGIN
…
END; (6)
BEGIN
…x…y…s…
END,
3.3 词法分析程序的实现
3.3.2 标识符的处理
? 定义性出现与使用性出现
? 标识符的作用域
? 标识符属性字之符号值的确定
(1)不处理说明部分的情况,只需依据作用域法则，对不同标识符，
以它们在标识符表中的序号作为属性字符号值即可。
(2)处理说明部分的情况
（ a）对基本类型的简单变量采用编号或标识符表序号作为属性字符号值；
（ b） 对于常量, 以常量表序号作为属性字符号值；
（ c） 对于其它各类标识符, 以相应信息表序号作为属性字符号值 。
第三章 词法分析
3.3 词法分析程序的实现
3.3.1 单词与属性字
3.3.2 标识符的处理
3.3.3 词法分析程序的实现
一个词法分析程序，其基本部分由子程序（函数）组成，
包括取字符子程序、取符号子程序、查造标识符表子程序、
查造常量表子程序以及查符号机内表示对照表子程序等。
第三章 词法分析
3.3 词法分析程序的实现
3.3.1 单词与属性字
3.3.2 标识符的处理
3.3.3 词法分析程序的实现
(1)取字符子程序,从源程序文件中取一个有效字符。
(2)取符号子程序,读入若干字符，并识别出，也即形成一个符号，生
成相应属性字。
约定 1 进入取符号子程序时已取到当前符号的第一个字符；
约定 2 在离开取符号子程序时已取到当前符号的后继字符 。
(3)查造标识符表子程序,当标识符为定义性出现时登录标识符表，形
成相应的属性字；而使用性出现时查标识符表，取出相应的属性字信息。
(4)查造常量表子程序,当一个特定的常量在第一次被扫描到时将它登
录到常量表中。不论是第一次被扫描到还是以后被扫描到，均回送此常
量在常量表中的序号，以此作为属性字中的符号值。
(5)查符号机内表示对照表子程序,在取到一个特定符号时查看对照
表，以确定是哪一个特定符号，从而回送相应的机内表示 (属性字 )。
3.3 词法分析程序的实现
词法分析控制流程图,
3.3 词法分析程序的实现
取符号子程序控制流程图,
3.3 词法分析程序的实现
编写词法分析程序的步骤,
（ 1） 应确定所要实现的语言 （ 或其子集 ） 。
（ 2） 设计属性字, 并设计各类表格, 如标识符表, 常量表,
符号及其机内表示对照表等 。
（ 3） 画出总控流程图及前述各个子程序的流程图 。
