第3章 词法分析和词法分析程序

对运算符个数n进行递归 算法：
1、n=0时： r=
s f
r=
f
r=a
s
a
f
2、设当n=1,2,…,k-1时,M均可构造,当n=k时,根据正规式的 定义,r只能是 r1|r2, r1•r2, r1*这三种形式之一.其中, r1,r2 中 最多含k-1个运算符,且设相应的自动机为 M1=(K1, ,f1,S01,{Sf1}) M2=(K2, ,f2,S02,{Sf2}) L(M1)=Lr1 L(M2)=Lr2 K1∩K2=
将单词识别从语法分析识别分离出来，可采用更
有效的工具实现；
有些语言的单词识别与前后文相关，不宜将其与 语法分析合并； 使编译程序各部分独立出来，有利于设计、调试 和维护
3.1.2 单词符号的内部表示 常用的内部表示方法: (class,value)
为便于阅读，常用助记符（或常量标识符、
Thmopson 法(续)
(1) r= r1|r2 ,引入新开始状态S0,终态Sf,将M1,M2并联:

S01
Sf1 Sf2

s

Sf
S02

(2) r=r1r2 , 将M1,M2串联 (3) r=r*,引入新开始状态S0, 终态Sf,令原M1构成循环 在实际的构造中，我们可省 略一些矢线。
习题
对于文法：G=({S,A,B,C,D}, {a,b,c,d},P,S)，
P由如下产生式组成：
SaA|B AabS|bB Bb|cC CD
Dd|bB
（1）构造该文法的状态转换图
（2）构造一等价的左线性文法
3.3.2 非确定的有限自动机 NFA
M=(K, , f , S0, Z )
• 1. (r) •(s)是正则表达式, 相应的正规集为Lr•Ls; • 2. (r)|(s)是正则表达式, 相应的正规集为Lr ∪ Ls; • 3. (r)*是正则表达式, 相应的正规集为Lr*
有限地使用上面的规则(4),所得的表达式均是正规表达式
例子 a*, aa*, a|ba*, (a|b) (a|b) (a|b)*
宏定义等）表示class。 在识别出变量名、函数（过程）名时，还应 进行查填符号表的工作。
3.1.3 识别标识符的若干约定和策略
在允许长度下，应按最长匹配原则进 行识别 有时需要超前扫描来进行单词识别。
百度文库
3.2 正规文法和状态转换图
3.2.1 由正规文法构造状态转换图 例：正规文法如下：
a1 … am
S1
S2 … Sn
B11
B21 Bn1
…
… …
B1m
B2m
Bij:
Si
aj
Bij
若无则置“出错”
Bnm
太浪费！！！
用有效的数据结构 如 表3-1
3.2.2 状态矩阵法（二） 构造状态矩阵，控制程序对单词加以识别
开始
初始化
getchar() 查状态矩阵（state, symbol） end?
b a a|b b
S1
3.3.4 具有 动作的FA 允许对作转移
例：
串aacc可被接受

a 0
b b
1
3
2 c
f也可以拓广到f’: K* (K). f’(S,x)是由这样的状态Q组成,存 在从S到Q的路径,该路径上的连 线标记组成的符号串恰好为x,其 中,允许有有限个标记为
构造状态转换图（三）
由左线性文法构造状态转换图
初态R(VN) 构造规则 Aa
R a A
ABa
B a A
例：文法G=({S,U},{0,1},{SS1 |U1, UU0 | 0},S)
• 识别句子 00011
R 0 1 1 S
0
U
归约——对应的语法树
3.2.2 状态矩阵法（一）
正规集1：n正规式
正规式r =正规式s Lr=Ls
正规式的基本等价关系（公理） A1. r|s=s|r A2. r|r=r
A3. r|=r
A5. (rs)t=r(st) A7. (s|t)r=sr|st A9. r=r=r
A4. (r|s)|t=r|(s|t)
A6. r(s|t)=rs|rt A8. r=r= A10. r*=(|r)*=|rr*
^ ^ ^ ^
f ( q, a )
q f ( S , w )
^
(3)实际上, (2)将f及 f 的定义拓广到R f : 2 K * 2 K , 对R 2 K ( R K ) : ( 4) f ( R, w)
^
f ( R, a )
qR
f ( q, a )
qR
DFA NFA
3.3.1 确定的有限自动机DFA
五要素
状态集合
M=(K, , f , S0, Z )
字母表 状态映射 初态 终态集
状态映射
f： K K K* K
可将f定义域推广为
(1) f^ (s,)=s, sK; (2) f^ (s,aw)=f^ ( f(s,a),w), sK, a, w*; 所以，f与f^不可区分
NFA的接受集
L(M)={x | f(S0, x )∩Z , x }
例：
a,b a b a b
S
a
A
a
B
识别符号串ababb
C
3.3.3 NFA与DFA的等价性 NFA的确定化：构造一DFA，使得它们有
相同的接受集
思路：使DFA的状态与NFA某一状态子集 相同
定理3.1 S0 例：M=({S0,S1}, {a,b}, f, S0, {S1}) 此确定化算法的弱点

状态S的-闭包：-CLOSURE(S) 定义
(1)S-CLOSURE(S);
(2)设Sj-CLOSURE(S),且Sj Sk,
b b
则Sk-CLOSURE(S);
(3)有限地使用规则（2）所得的集 合为-CLOSURE(S).
a 0
1
3
例
2
c

f^的定义
S K , a , w * (1) ( 2) f ( S , ) CLOSURE( S ); f ( S , wa) CLOSURE( P ); 其中, P f ( f ( S , w), a )
<指数部分> → d<余留整指数>
<指数部分> → +<整指数> <指数部分> → -<整指数>
<余留无符号数> →
<十进小数> → d<余留十进小数>
<整指数> → d<余留整指数>
<余留整指数> → d<余留整指数> <余留整指数> →
由正规文法构造状态转换图 所对应的状态转换图
E d
识别
DFA M识别*中的x ：从初态S0出发，经一恰好标
有x 的路径后可达到某终态SZ
即： f(S0,x)=S，SZ
M的接受集 L(M)={ x | f(S0,x) Z, x* }
DFA：给一状态，一字符，则唯一确定下一状态
任一正规文法G，都存在一个DFA M，使得：
L(G)=L(M)
最小化算法 算法主要思想：将K划分为r个互不相交的
子集，子集内任何两个状态是等价的，而
不同子集任两个状态可区分。
例：
S0 a
a S1 a S2 b
a
b
a
S3
b
S4
b
b
3.4 正规表达式及正规集 L（G）≡L（M），即：正规文法与FA等价
所以，现在来为一个正规表达式构造一等价
的FA
S01
Sf1

S02
Sf2

S
S01

Sf1

Sf
习题 构造识别正规式a(b|aa)*b的DFA 构造识别正规式(b|aa*bb)*的最小DFA
它与-FA等价。
例
a 0
b b
1
3
2 c

习题 试将下面的-FA确定化为DFA:
a S 1 b 2
3 a
a 5
a

6 b

F
b
b
4
3.3.6 DFA状态数的最小化 对一个DFA M，构造另一个DFA M’，使得： L(M) = L(M’)，后者有最小的状态数 可区分状态：s,t K，若w∑*，f(s, w) = q Z，而f(t, w) = p Z，则s,t为一串w所 区分 s和t等价： w，f(s,w) Z，f(t,w) Z 所以，可以将等价的状态合并
3.4.1正规表达式及正规集的定义
举例
定义 设是一字母表,则上的正规表达式(正则表达式,正规
式)及其表示的正规集可递归定义如下:
(1) 是一正则表达式, 相应的正规集为;
(2) 是一正则表达式, 相应的正规集为{};
(3) a, a 是一正则表达式, 相应的正规集为{a}; (4) 设r, s是正则表达式, 且它们所表示的正规集为Lr, Ls,则
d 0 d 1 •
d
2 E 4 +|5 d
d 6
•
3
d
无符号数的状态转换图
3.2 正规文法和状态转换图
3.2.1 由正规文法构造状态转换图 程序设计语言的单词都能用正规文法描述 一般说来，凡能用正规文法描述的语言，均 可由某种有限状态算法——状态转换图进行 分析 状态转换图：
有向图（一个初态 +N个终态 射出结点，进入结点 ）
3.4.2 由正规文法构造相应的正规式
例： SaS | bA | b，AaS 则所产生的
正规集为
论断3.1 方程x= rx + t 有解 x= r*t 例 SbS|aA AaA|bB
BaA|bC|b CbS|aA 左线性文法：x=xr+t的方程，有解x=tr*
3.4.3 正规式构造FAThompson法
编 译 原 理
第三章 词法分析和词法分析程序
winniewan@dhu.edu.cn
3.1 设计扫描器时应考虑的问题 词法分析程序亦称为扫描器
任务：扫描程序，识别单词
扫描器的输出是语法分析程序的输入
3.1.1 词法分析的必要性
描述单词的结构比其它语法结构简单，仅用3型文
法就够了；
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*
m ^ i 1
f ( S , aw) f ( f ( S , a ), w) f ({S k1 , S k 2 , , S k m }, w) f ( S ki , w)
<无符号数> → d.<余留无符号数>
<无符号数> → .<十进小数> <无符号数> → E<指数部分>
<余留十进小数> → d<余留十进小数>
<余留十进小数> → E<指数部分> <余留十进小数> →
<余留无符号数> → d<余留无符号数>
<余留无符号数> → .<十进小数> <余留无符号数> → E<指数部分>
控制程序大都相同， 状态矩阵不同
实数类码 二进制浮点
回退一个字符
返回（R, N）
词法分析程序构造过程
正规表达式
构造识别该正规表 达式的带的自动机 将-自动机转化为 DFA，并且最小化 根据最小化的DFA 构造状态矩阵 编写控制程序，对 词法进行识别
3.3 有限自动机
状态转换图实际上是有限自动机的图形表示
f (q, w)
^
f与f^不相等
f(S,a) -CLOSURE(f(S,a)) f^(S,a)
只走一步a矢线 | 多步，第一步必须走a矢线 | 路径a ：第一步可以是矢线
-NFA的接受集：
L(M)={w|f^(S0,w)∩Z}
-NFA的用途：构造更复杂的FA
3.3.5 -FA的确定化 构造一DFA，使得
构造状态转换图（一）
由右线性文法构造状态转换图
1. |VN|=K,则所要构造的状态转换图共有K+1个状态(结点)
• 构造规则： AaB， Aa， A
A
a
B
A a
F
构造状态转换图（二）
2. 识别串：字符串w=a1a2…an, aiVT
• 实际：建立推导 S* w
3. (1) 自顶向下 (2) 从S出发：a1a2…akAk (3) 对任一句子y，必存在一条路从S至F，各标记相连即y 显然,若我们从初态出发,分别沿一切可能的路径到达终态结点, 并将中径中矢线上所标记的字符依次连接起来,便得到状态 转换图所能识别的全部符号串,这些符号串组成的集合构成 了该文法识别的语言——句子必有一条从初态S到终态F的 路径，此路径上各矢线的标记依次拼接起来所组成的符号 串恰为该句子