第三章 词法分析
知识结构：
功能 词法分析器的要求 单词符号分类
词法分析 单词内部形式
器的设计 设计方发
词法分析器的设计 状态图
词法分析器组成
正规表达式
单词描述工具 正规集
词法分析器 正规文法
确定有限自动机（DFA ）
单词识别工具 非确定有限自动机（NFA ）
DFA 的最小化
正规式与FA 的等价转换
等价转换
正规文法与FA 的等价转换
第一节 对词法分析器的要求
一、词法分析器的功能
输入源程序，输出单词符号（二元式表示）。
关键字：是由程序语言定义的具有固定意义的标识符。
标识符：用来表示各种名字，如变量等。
常数：常数的类型有整型，实型等。
运算符：算术运算符，关系运算符，逻辑运算符。
界限符：逗号，分号等。
三、单词符号内部的表示形式
内部的单词符号TOKEN字（二元式），TOKEN字占用机器字的长度，依据信息量的多少而定。
1、TOKEN字结构
CLASS：用整数表示。
VALUE：表示单词符号的属性（符号表指针）。
2、TOKEN的作用
CLASS：用于语法分析器对源程序结构的分析。
VALUE：用于语义分析器对源程序具体操作的分析。
3、单词种别码划分原则
CLASS：关键字，运算符，界限符（编译程序定义的符号）
使用一字一种编码。VALUE值省略。
VALUE：标识符，常数（用户定义的符号），存放符号表
常数表的指针。标识符，常数每一类为一种编码。
例：BEGIN A：= B END；
词法分析结果：符号表
（BEGIN，---- ）Array（A ，K1 ） K1
（：= ，--- ）
（B ，K3 ） K3
（END ，--- ）
（；，--- ）
四、词法分析器的结构
1、一遍扫描（交互式结构）。
2、多遍扫描（独立式结构）。
第二节词法分析器的设计
一、设计步骤
1、确定词法分析器的接口关系；
2、确定单词分类和TOKEN字的结构；
3、对每一类单词构造状态转换图；
4、根据状态转换图设计算法。
二、功能描述
1、组织源程序输入；
2、按词法规则拼读单词符号，并转换成二元式；
3、删除注解行，空格和无用符号；
4、检查词法错误。
三、设计方法
1、输入(读取原文件)
原文件存储方式：
一种方式将原文件一次读入内存，另一种方式利用缓冲区技
术将原文件分批读入内存。
缓冲区的设置：
输入（扫描）缓冲区，存放输入的原文件（双缓冲区）。
2、预处理
功能描述：
删除无用符号，出错信息的列表打印。
单词符号的识别：
⑴语句格式
①标识符不能被无效字符隔开。
②标识符与关键字，关键字与关键字之间用空格符隔开。
②标识符的个数不能超过限定的个数。
⑵单词符号的格式
①标识符，关键字的首字符必须是字母。
②常数的首字符必须是数字。
3、识别算法(P39)
标识符的识别；常数的识别；算符的识别；界符的识别。
四、状态转换图
1、状态转换图的表示形式
是一张有向图,结点代表状态（用○表示），结点间用箭弧线连接（ ），箭弧线上的符号，表示射出结点到达射入结点可能识
别的输入符号，终态结点代表分析结束。
初态?
⑴ ?⊙初始状态,表示识别符号串的开始。
⑵双圈◎终态，表示识别符号串的结束。
⑶◎*
表示多读入一个字符。
例1：标识符的状态转换图
状态转换矩阵
字母，数字
例2：标识符“
AB1”的识别 例4 状态转换矩阵 数字
2、识别过程
从初态开始，逐步读入字符，转到下一个状态（或出错），直
至终态（或不能到达终态出错）。
例3：字符串“AB+12”的识别
识别出单词AB,
多读入一个字符 +。由另一张状态转换图识
别单词符号 +。继续识别剩余字符12(数字)：
上述识别过程把AB ＋12字符串分解为三个单词符号“AB ”、
“ + ” 、“12”。
3、状态转换图的实现
状态转换图非常容易用程序实现，每一个状态对应一段程序。
⑴不含回路的分叉状态结点的程序设计
利用多分支语句CASE 或选择语句IF...THEN...ELSE...。
⑵含回路状态结点的程序设计
利用循环语句WHILE...DO。
⑶词法分析程序的组成
状态转换图是一种特殊的流程，它可直观清晰地描述单词符号的识别过程，只要把每一个结点加入语义动作，就构成了词法分析程序。
4、词法分析程序的组成（八个模块）
主控模块；初始化模块；判定源程序文件是否存在模块；从源程序文件中读一个字模快；拼读一个单词模块；查关键字模块；输出单词模块；错误处理模块。
第三节正规式、正规集、正规文法
一、正规式的定义
∑中的符号为正规式的基本符号，单个符号或由符号与运算符组成的表达式称正规式。
运算符优先级：
重复用“ * ”表示；
连接用“?”表示或省略；
选择用“∣”表示。
例：a，ab *
，a∣b ，（a∣b）c都是正规式。
二、正规集
由正规表达式所表示的字符串的集合称为正规集。如正规式用V表示，正规集L（V）表示。
三、正规文法
正规文法是上下文无关文法的一种特殊情况，所有产生式的
右部至多含有一个非终结符号，左线性文法，右线性文法都属于
正规文法。
左线性文法：
A →
B α
A → α
右线性文法：
A → αB
A → α 其中：A ，
B ∈V N ，α∈V * T * T
四、正规式与正规集的递归定义
1、正规式与正规集的递归定义P46
⑴ε和Ф都是Σ上的正规式，正规集为{ε}和Ф。
⑵任何a ∈Σ，a 是∑上的正规式，正规集为{a}。
⑶假定U 和V 是∑上的正规式，正规集为L(U)，L(V)
U ∪V 是正规式，正规集为L(U)∪L(V)。
UV 是正规式，正规集为L(U)L(V)。
(U)*是正规式，正规集为 (L(U))*
。
例1：令Σ= {a, b}，则
⑴正规式a | b 的正规集是{ a, b }。
⑵正规式（a | b ）（a | b ）的正规集是{aa, ab, ba, bb}。
⑶正规式a * 的正规集是{ε，a, aa, aaa ……}。
⑷正规式（a | b ）* 的正规集是{ε,a, b, aa, ab, ba, bb,
aaa……}。（a | b）*
＝（a
*
b
*
）
*
，即所有a和b的符号串集合。
⑸（a | b）*
(aa| bb)（a | b）
*
的正规集是所有含有两个
相继a或两个相继b的字符串集合。
例2：∑ ={a, b, c……z，0, 1,……9}
正规式（a | b…|z）（a | b|…z|0|1|…|9）*
代表标识符。
2、正规式与正规集的等价性
若两个正规式代表的正规集相同，则认为正规式等价。
U=V，表示L（U）=L（V）
例3：U=10*
*
， L(U)={1}{0}
*
V=10*
， L(V)={1}{0}
*
则10*
*
=10
*
例4：b(ab)*
= (ba)
*
b （ab）
*
≠a
*
b
*
(a|b)*
= (a
*
b
*
)
*
(a|b)
*
≠(a
*
|b
*
)
3、正规式的代数定律
（1）U∣V=V∣U 交换律
（2）U∣V∣W=（U∣V）∣W 结合律
（3）U（VW）=（UV）W 结合律
（4）U（V∣W）=UV∣UW 分配律（5）εU = Uε= U
（6）U *
=U
+
∣ε
（7）U **
=U
*
（8）U +
=U
*
U=UU
*
例1：选择规则U∣V，则描述的正规集L(U∣V)=L(U)∪L(V)。
令 U=a,V=b：
则 L(U∣V)= L(U)∪L(V)=L(a)∪L(b)
={a}∪{b}={a，b}
例2：连接规则UV，则描述的正规集L(UV)=L(U)L(V)。
令 U=a∣b，V=c：
则 L(UV)= L(U)L(V)=L(a∣b )L(c)
= {a，b}{c}={ac,bc}
例3：重复规则U *
，则描述的正规集L(U
*
)=(L(U))
*
。
U *
={ε}∪U
1
∪U
2
∪...∪U
n
U=（a∣ab）
L(U *
)=(L(U))
*
=(L(a∣ab))
*
=(L(a)∪L(ab))
* ={a,ab}
*
={a,ab}0
∪{a,ab}
1
∪{a,ab}
2
∪?
={ε}∪{a,ab}∪{a,ab}{a，ab}∪?
={ε，a，ab，aa，aab，aba，abab，? }
五、正规式与正规文法的转换
正规式与正规文法都有相同的表达能力，用以描述语言（单词符号）的结构，使得所描述的语言是等价的（即L（V）=L（G））。
1、正规式与正规文法的特点
正规式描述的语言结构清晰，简洁；而正规文法描述的语言于识别。
2、正规定义式
d1→ r1
d2→ r2
...
其中:d i 为定义式的名字；r i是∑∪{d1，d2，...，d i-1}构成的正规式；r i中不含有d i，d i+1，...。
3、正规式与正规文法的转换算法
例：高级语言标识符的正规式
字母（字母∣数字）
*
⑴根据正规定义式规则，给正规式分量、正规式定义名称
字母→ A ∣ B ∣ C
数字→ 0 ∣ 1 ∣ 2
id →字母（字母∣数字）
*
⑵对定义式的子表达式定义名称
rid →（字母∣数字）
*
⑶对定义式的子表达式展开
（字母∣数字）
*
= ε∣（字母∣数字）
+
= ε∣（字母∣数字）（字母∣数字）
*
= ε∣字母（字母∣数字）*
∣数字（字母∣数字）*
⑷把展开式代入定义式
rid →ε∣字母（字母∣数字）*
∣数字（字母∣数字）*
⑸把rdi →（字母∣数字）*
代入定义式id、rid，将得到正
规文法：
id →字母rid
rid →ε∣字母rid∣数字rid
其中:id，rid ∈ V N；字母，数字∈V T。
六、正规文法与正规式的转换
建立正规文法的联立方程组，求描述同一语言的正规式。
1、右线性文法到正规式，使得L（G）=L（V）。
产生式 X → rX ∣ t，其中 r，t∈ V T X∈V N。
论断1：
方程 X=rX + t ，有形如 X=r *
t的解。
例：文法G
S →aS ∣bA ∣b
A →aS
⑴立联立方程组
S = aS + bA + b ①
A = aS ②
⑵②式，代入①式
S = aS + baS + b
S =（a + ab）S + b ⑶由论断得方程解
S =（a + ab）*
b
= （a∣ab）*
b
对于同一方程式采用不同的结合方式，可以得到不同形式的正规式，但是所描述的语言（正规集）是等价的。
S = aS + baS + b
= aS +（baS + b）
= a *
（baS + b）
= a *
baS + a
*
b
= （a *
ba）
*
a
*
b
所以（a *
ba）
*
a
*
b = （a∣ab）
*
b。
2、左线性文法与正规式的转换算法
产生式 X → Xr ∣ t，其中 r，t∈ V T X∈V N。论断2：
方程 X=Xr + t ，有形如 X=tr *
的解。
例：文法G
id → id 字母∣ id 数字∣字母
其中:id ∈ V N；字母，数字∈V T。
建立方程
id = id 字母 + id 数字 + 字母
= id（字母 + 数字）+ 字母
= 字母（字母∣数字）
*
3、正规文法与正规式的转换规则
⑴产生式 A→xB，B→y 对应的正规式 A=xy；
⑵产生式 A→xA∣y 对应的正规式 A=x * y；
⑶产生式 A→x ，A→y 对应的正规式 A=x∣y
例：文法G
S→aA，S→a
A→aA，A→dA，A→a，A→d
⑴根据规则⑶先有正规式
S = aA∣a
A = （aA∣dA）∣（a∣d）
⑵再将A的正规式变换为
A = （a∣d）A∣（a∣d）
⑶根据规则⑵将A的正规式变换为
A = （a∣d）*
（a∣d）
⑷再将A式的结果代入S的正规式
S = a（a∣d）*
（a∣d）∣a
⑸再利用正规式的代数性质得到的正规表达式为
S = a（（a∣d）*
（a∣d）∣ε）
因为（a∣d）*
（a∣d）=（a∣d）
+
,
所以S = a（a∣d）+
∣a= a（（a∣d）+∣ε）。
又因为（a∣d）+
∣ε =（a∣d）*，
所以S = a（a∣d）*。
第四节有限自动机（FA）
有限自动机是具有离散输入和输出系统的一种数学模型，它
能准确地识别正规文法所定义的语言和正规式表示的正规集，引入有限自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法。
有限自动机的分类：
⑴确定有限自动机（DFA）。
⑵非确定有限自动机（NFA）。
一、有限自动机的表示形式
⑴状态图
一个有限自动机可以用一个状态图（状态转换图）表示，即含有m个状态，n个输入符号，若f（k i，a）=k j，则从状态结点k i到状态结点k j画标记为a的弧。弧上标记的符号表示当前识别的符号。
⑵状态表
一个有限自动机可以用一个矩阵表示，该矩阵的第一列表示状态，第一行表示输入字符，矩阵元素表示相应状态和输入字符到达的下一状态，即k行a列为f（k，a）的值。
二、有限自动机的应用
⑴翻译器
有限自动机（FA M）作为转换器将输入串变换为输出串。
M = ( S，∑，R，δ，S0，F )
⑵串产生器
有限自动机（FA M）如果只有输出没有输入。
M = ( S，R，δ，S0，F )
⑶串识别器
有限自动机（FA M）如果只有输入没有输出。
M = ( S，∑，δ，S0，F )
其中：S 状态集；∑输入字母表；R 输出字母表；δ状态转换函数；S0 初态；F 终态
三、有限自动机的工作原理
例：有限自动机识别无符号实常数的过程
⑴接受
从初始状态出发所识别的字符串结束时能够到达终态结点。
例：35.67 为有效字符串。
⑵阻塞（出错）
从初始状态出发所识别的字符串结束时没能到达终态结点。
例：356. 为无效字符串。
四、确定有限自动机DFA
确定有限自动机（DFA M）是一个五元组：
DFA（M）=（S，Σ, δ, s0, F）,
其中：
⑴S是一个状态的有穷集—自动机所有状态的集合。
⑵∑是有穷字符集合，它的每一个元素为一个输入字符。
⑶δ状态转换函数δ（S, a ）=S ′，当现行状态为S ，输入
字符为a 时，将转换到下一个状态S ′。S ?∑→S 单值映照函数。
⑷S 0 ∈ S 唯一的初始状态。
⑸F ? S 终态集。
若DFA M 上有m 个状态，n 个输入符号（∑中的元素有n 个），
则状态转换图上有m 个状态结，每个状态结最多有n 个射出弧线
与后续的状态连接。
状态矩阵表
，b
该DFA M 有4个状态{0，1，2，3}。
Σ＝ {a, b }。
S 0 = 0 为初始状态。
F = 3为终态。
δ为状态转换函数： δ (0, a)=1, δ (0, b)=2
δ (1, a)=3, δ (1, b)=2
δ (2, a)=1, δ (2, b)=3
δ (3, a)=3, δ (3, b)=3 1、DFA M所识别的符号串
DFA M所识别的符号串ω：
对ω∈Σ*
，若存在一条从初始状态结点到终态结点的道路，
在这条路上所有弧线标记符号连接成的符号串恰好是ω，则称ω为DFA M所识别。
上例DFA M所识别的符号串为Σ＝ {a, b }上的含有二个相继a或二个相继b的符号串的集合。
例1：“aab”是DFA M所能识别的符号串。
不能被DFA M识别的符号串ω'：
被识别的符号串不能从初始状态结点到终态结点，有下列两种情况：
⑴不能到达终态（ω'已识别完）
例2：“abab”不是该
DFA M所能识别的符号串（上例）。
其中：2状态不是终态结点。
⑵某一状态射出弧线上标记与所识别的符号不同（多态性）。
例3：给定DFA M
“abb ”不能被DFA M 识别。
2、DFA M 所识别的语言L （M ）
DFA M 所能识别的符号串的集合，称DFA M 所识别的语言：
L （M ）={ ω ∣δ（S0，ω ）∈ F ，ω ∈ ∑*
}
例4：L （M ）={a 开头的，a, b 符号串}
DFA M=（{1，2}；{a,b}，δ，1，{2}）
3
如果DFA M 的初始状态又是终态，则空串ε可被DFA M 识别。
例5：
L （M ）={ε，a, aa, aaa,…….. }
例6：，b L （M ）={ ε，任意的a,b 符号串}
五、非确定有限自动机NFA M
1、非确定有限自动机的特性
⑴某一结点射出多条标记相同字符的弧线到达不同的结点。
δ(0,a)=0 δ(0,a)=1 两个状态 δ(0,a)＝{0,1}
δ(0,b) =1
δ(1,b) =0 δ(1,b)=1 两个状态 δ(1,b)＝{0,1}
⑵某一结点射出标记有ε字符的弧线。
2、非确定有限自动机NFA M 定义
NFA （M ）=（S ，Σ，δ，S 0, F ）
⑴S 同上；
⑵Σ同上；
⑶δ是一个从S ?∑*到S 的子集的映照，即δ：S ?∑*→2s
；
⑷S 0 ? S 为一个非空初态集；
⑸F ? S ，为一个终态集（可空）。
3、NFA M 与DFA M 的区别
⑴NFA M 状态转换函数具有多值性；
即δ（S, a ）= {S 1, S 2, ………S n }
⑵NFA M 可以存在有ε弧；
⑶NFA M 可以有多个初态（初态集）
六、非确定有限自动机（NFA M ）的识别
例 M=({1，2。3，4}，{a ，b ，c}?{ε}，δ，1，{4})
1、映射函数值
δ（1，ε）={4}， δ（2，ε）= φ，
δ（3，ε）= φ， δ（4，ε）= φ，
δ（1，a ）={2，3}， δ（2，a ）={2}，
δ（3，a ）= φ， δ（4，a ）= φ，