Download presentation
Presentation is loading. Please wait.
1
第三章 词法分析与有穷自动机 有穷自动机是构造词法分析程序的理 论基础。本章主要介绍词法分析程序的 设计原理和构造方法，重点介绍有穷自
第三章 词法分析与有穷自动机 有穷自动机是构造词法分析程序的理 论基础。本章主要介绍词法分析程序的 设计原理和构造方法，重点介绍有穷自 动机的基本概念以及正规文法、正规表 达式与有穷自动机之间的相互关系。
2
第三章 词法分析与有穷自动机 ◇ 词法分析程序功能 ◇ 单词符号及输出单词的形式 ◇ 语言单词符号的两种定义方式 ◇ 正规式与有穷自动机
第三章 词法分析与有穷自动机 ◇ 词法分析程序功能 ◇ 单词符号及输出单词的形式 ◇ 语言单词符号的两种定义方式 ◇ 正规式与有穷自动机 ◇ 正规文法与有穷自动机 ◇ 词法分析程序的编写方法
3
3.1 词法分析程序的功能 词法分析的任务是对字符串表示的源程 序从左到右地进行扫描和分解，根据语言 的词法规则识别出一个一个具有独立意义
的单词符号。 字符串 表示的 源程序 词 法 分 析 器 语 法 分 析 器 单词符号 字符 取下一个 单词符号
4
3.2 单词符号及输出单词的形式 语言的单词符号是指语言中具有独立 意义的最小语法单位 。 关键字 也称基本字，例如，C语言中
的if，else，while, do等, 这些字在语言中 具有固定的意义，一般不作为标识符使用。 标识符 表示各种名字，如变量名、常 量名、数组名和函数名等。
5
3.2 单词符号及输出单词的形式 常数 各种类型的常数，如整型常数 125、实型常数0.718、布尔型常数TRUE 等 。
常数 各种类型的常数，如整型常数 125、实型常数0.718、布尔型常数TRUE 等 。 运算符 如＋、－、*、/、＜等。 分界符 如 ，、；、（、）、：等 。
6
3.2 单词符号及输出单词的形式 （单词种别，单词自身的值） 词法分析程序输出单词的形式
词法分析程序所输出的单词符号通常表示成如下的二元式： （单词种别，单词自身的值）
7
3.2 单词符号及输出单词的形式 单词种别 单词种别表示单词的种类，它是语法分析需要的信息。 为处理方便通常让每种单词对应一个整数码。
8
3.2 单词符号及输出单词的形式 基本字: 可将其全体视为一种，也可 以一字一种。 标识符: 一般统归为一种。
常数: 可统归为一种，也可按类型 （整型、实型、布尔型等）分种。 运算符和界符: 可采用一符一种的分法， 也可以统归为一种。
9
3.2 单词符号及输出单词的形式 单词自身的值 一个种别只含一个单词符号 一个种别含有多个单词符号 (1) 对于标识符其自身值是标识符自
(1) 对于标识符其自身值是标识符自 身的字符串； (2) 常数自身值是常数本身的二进制 数值。
10
3.2 单词符号及输出单词的形式 (3) 用指向某类表格一个特定项目指 针值来区分同类中不同的单词。
(3) 用指向某类表格一个特定项目指 针值来区分同类中不同的单词。 例如, 对于标识符用它在符号表的入口指针作为它自身值; 常数用它在常数表的入口指针作为它自身的值。
11
3.2 单词符号及输出单词的形式 对例子: if (a＞1) b =100； 假定: 基本字、运算符和界符都是一符一种；
标识符自身的值用自身的字符串表示； 常数自身的值用常数本身的值 (转变成 标准二进制形式) 表示；
12
3.2 单词符号及输出单词的形式 假设: 标识符的种别编码为整数10 ； 常数的种别编码为整数11 ； 基本字if种别编码为2 ；
赋值号的种别编码为17 ； 大于号的种别编码为23 ； 分号的种别编码为26 ； 左括号的种别编码为29 ； 右括号的种别编码为30 ；则程序段 ：
13
3.2 单词符号及输出单词的形式 if (a＞1) b =100；在经词法分析程序扫 描后，它所输出的单词符号串是： （2， ） 基本字if
（30， ） 右括号 ) （29， ） 左括号 ( 10，‘b’）标识符b （10，‘a’）标识符a （17， ） 赋值号 = （23， ） 大于号 ＞ （11，100）常数 100 （11，1） 常数 1 （26, ） 分号 ；
14
3.3 单词符号的两种定义方式 正规文法 正规式 以标识符为例: I→l|Il|Id 或 I→l|lT T→l|d|lT|dT
l ( l | d )*
15
3.3.1 正规式和正规集 设有字母表Σ={a1, a2,…, an} ，在字母表 Σ上的正规式和它所表示的正规集可用如 下规则来定义：
1. Φ是Σ 上的正规式，它所表示的正规 集是 Φ ，即空集{ }。 2. ε是Σ 上的正规式，它所表示的正规 集仅含一空符号串，即{ε}。 3. ai是∑上的一个正规式，它所表示的 正规集是由单个符号ai 所组成，即{ai}。
16
3.3.1 正规式和正规集 4. 如果 e1和 e2 是∑上的正规式，它们所表示的正规集分别为 L(e1)和L(e2) ，则：
(1) e1 | e2是∑上的一个正规式，它所表示的正规集为L(e1 | e2)=L(e1 )∪L(e2) (2) e1e2 也是∑上的一个正规式，它所表示的正规集为L(e1e2)=L(e1)L(e2) (3) (e1)*也是∑上的一个正规式，它所表示的正规集为L((e1)*)=(L(e1))*
17
3.3.1 正规式和正规集 正规式中包含三种运算符：连接“·”，或“|”和闭包“*”。其中闭包运算的优先级最高，连接运算次之，或运算最低。连结符“·”一般可省略不写。这三种运算符均是左结合的。
18
3.3.1 正规式和正规集 例1 设有字母表Σ={a,b} ，根据正规式与 正规集的定义，则有： a 和 b是正规式，相应正规集为
L(a)={a} , L(b)={b} 定义3 2. a | b 是正规式，相应正规集为 L(a | b )=L(a)∪L(b)={a ,b} 定义4.(1) 3. ab 是正规式，相应正规集为 L(ab)=L(a)L(b)={a}{b}={ab} 定义4.(2)
19
3.3.1 正规式和正规集 4. (a | b)* 是正规式，相应正规集为 L((a | b)*)= (L(a | b))* 定义4.(3)
=(L(a)∪L(b))* 定义4.(1) =({a} ∪{b})* 定义3 ={a ,b}* ={ε, a, b, aa, ab, ba, bb, …} 所以 L((a | b)*)= {ε, a, b, aa, ab, ba, bb, …}
20
3.3.1 正规式和正规集 需要指出的是，对 {a,b}*的任一子集不能认为是一个正规集。
例如， {a ,b}* 的子集 {an bn | n≥1} 就不是一个正规集， 不能用正规式来描述，也不能用正规文法来描述，只能用上下文无关法来描述。
21
3.3.1 正规式和正规集 5. ba*是正规式，相应的正规集为 L(ba* )=L(b)L(a*)={b,ba,baa,baaa,…}
={b}{ε,a,aa,aaa, …} ={ba,baa,baaa,…}
22
3.3.1 正规式和正规集 (a | b)*(aa | bb) (a | b)* 是正规式，相应正规集为
L((a | b)*(aa | bb) (a | b)*) =L((a | b)*)L((aa | bb)(a | b)*) =(L(a | b))*L(aa | bb)L((a | b)*) =L((a | b)) *L(aa | bb)(L(a | b))* ＝{a,b}*{aa,bb}{a,b}* 即Σ上所有含两个相继a或两个相继b组成的串。
23
3.3.1 正规式和正规集 例2 设Σ={a,b,c},则 aa*bb*cc* 是∑上的一个正规式 , 它所表示的正规集：
L={ abc, aabc, abbc, abcc, aaabc, …} ={ ambnck | m, n, k≥1}
24
3.3.1 正规式和正规集 例3 设程序语言字母表是键盘字符集合，则程序语言部分单词符号可用如下正规式定义：
例3 设程序语言字母表是键盘字符集合，则程序语言部分单词符号可用如下正规式定义： 关键字 if | else | while | do 标识符 l (l | d)* l代表a~z中任一字母 整常数 dd* d代表0~9中任一数字 关系运算符 <<=>>=<>
25
3.3.1 正规式和正规集 注意: 正规式与正规文法之间的区 别和联系： 标识符 ID = l (l | d)* l代表a~z中任一字母
注意: 正规式与正规文法之间的区 别和联系： 标识符 ID = l (l | d)* l代表a~z中任一字母 d代表0~9中任一数字 I→l | Il | Id
26
3.3.1 正规式和正规集 如果正规式 R1 和 R2 描述的正规集相同, 则我们称正规式R1与R2等价。 记为 R1＝R2。
例如，(a|b)*=(a*b*)* ; b(ab)*=(ba)*b
27
3.3.1 正规式和正规集 (a|b)*表示的正规集为 {a，b}* (a*b*)*表示的正规集为
L((a*b*)*)= (L(a*)L(b*) )* = ({ε,a,aa,aaa,…} {ε ,b,bb,bbb,…})* = {ε ,a,b,aa,bb,ab,ba,aaa,bbb,aab,abb,…}* ={a，b}* {a，b}* 和(a*b*)*表示的正规集相同 所以 (a*b*)*= (a|b)*
28
3.3.1 正规式和正规集 b(ab)*表示的正规集为: L(b(ab)*)= L(b)L((ab)*)= L(b)(L(ab))*
={b}{ε，ab，abab，ababab，…} ={b，bab，babab，bababab，… } (ba)*b表示的正规集为: L((ba)*b)= L((ba)*)L(b) = (L(ba))*L(b)= {ba}* {b}={ε,ba,baba,…}{b} =={b，bab，babab，bababab，… } b(ab)*和(ba)*b表示的正规集相同 所以 b(ab)*和(ba)*b
29
3.3.1 正规式和正规集 例 4 无符号数 设 Σ ＝{d, ., e, +, -}，则Σ上的正规式 dd*(.dd* | ε)( e ( +|-|ε ) dd*|ε) 2 12.59 3.6e2 471.88e-1 213.44e+123
30
3.3.1 正规式和正规集 正规式具有如下性质 : 令A , B 和 C 均为正规式，则 1．A | B = B | A (交换律)
2．A | ( B | C) = (A | B) | C (结合律) 3．A(BC) = (AB)C (结合律) 4．A(B | C) = AB | AC (分配律) 5．(A | B)C = AC | BC (分配律) 6． Aε | εA = A 7． A* = AA* | ε = A | A* = (A | ε )* 8． (A* )* = A*
31
3.3.2 正规文法与正规式 1. 正规文法到正规式的转换 (1) 将正规文法中的每个非终结符表示成关于
(1) 将正规文法中的每个非终结符表示成关于 它的一个正规式方程，获得一个联立方程组。 (2) 依照求解规则： 若 x = αx | β (或 x = αx + β ) 则解为 x = α*β 若 x = xα | β (或 x = xα + β ) 则解为 x = βα * 以及正规式的分配律、交换律和结合律求关于 文法开始符号的正规式方程组的解。
32
3.3.2 正规文法与正规式 例1 设有正规文法G： Z 0A A 0A | 0B B 1A | ε
试给出该文法生成语言的正规式。 分析 首先给出相应的正规式方程组(方程组中用“＋”代替正规式中的“ | ” )如下： Z = 0A (1) A = 0A + 0B (2) B = 1A + ε (3)
33
3.3.2 正规文法与正规式 将(3)代入(2)中的B得 Z = 0A (1) A = 0A + 01A + 0 (4)
A = 0A + 0B (2) B = 1A + ε (3) 对(4)利用分配律得 A = (0 + 01)A (5) 对(5)使用求解规则得 A = (0 + 01)* (6) 将(6)代入(1)式中的A，得 Z = 0 (0 + 01)* 0 即正规文法G[Z]所生成语言的正规式是 R = 0 (0 | 01)* 0
34
3.3.2 正规文法与正规式 例2 设有正规文法G： A aB | bB B aC | a | b C aB
试给出该文法生成语言的正规式。 分析 首先给出相应的正规式方程组(方程组中用“＋”代替正规式中的“ | ” )如下： A = aB + bB (1) B = aC + a + b (2) C = aB (3)
35
3.3.2 正规文法与正规式 A = aB + bB (1) B = aC + a + b (2) C = aB (3)
B = aaB + a + b (4) 对(4)使用求解规则得 B = (aa)*(a + b) (5) (5)代入(1)中的B得 A = (a + b)(aa)*(a + b) 即正规文法G[A]所生成语言的正规式是 R = (a | b)(aa)*(a | b)
36
3.3.2 正规文法与正规式 例3 设有正规文法G： Z U0 | V1 U Z1 | 1 V Z0 | 0
相应的正规式方程组为 Z = U0 + V (1) U = Z (2) V = Z (3)
37
3.3.2 正规文法与正规式 Z = U0 + V1 (1) Z = Z10 + 10 + Z01 + 01 U = Z1 + 1 (2)
(2)和(3)代入(1)得 Z = Z Z (4) 对(4)使用求解规则得 Z = ( ) ( )* 即正规文法G[Z]所生成语言的正规式是 R = (10 | 01)(10 | 01)*
38
3.3.2 正规文法与正规式 例4 已知描述 “标识符” 单词符号的正规 文法为
例4 已知描述 “标识符” 单词符号的正规 文法为 <标识符>l<标识符>l<标识符>d IlIlId I=l+Il+Id =Il+Id+l =I(l+d)+l
39
3.3.2 正规文法与正规式 亦即 I=I(l+d)+l 根据前述求解规则, 可知该文法所描述语言的正规式是 l ( l | d )*
40
3.4 正规式与有穷自动机 有穷自动机是具有离散输入与输出系统的一种抽象数学模型。
3.4 正规式与有穷自动机 有穷自动机是具有离散输入与输出系统的一种抽象数学模型。 有穷自动机有“确定的”和“非确定的”两类，确定的有穷自动机和非确定的有穷自动机都能准确地识别正规集。
41
3.4.1 确定有穷自动机 确定有穷自动机（DFA） M=( Q, Σ, f, S, Z ) 一个确定有穷自动机M是一个五元组
Σ是一个有穷输入字母表，每个元素称为一个输入字符。
42
3.4.1 确定有穷自动机 M=( Q, Σ, f, S, Z ) f 是一个从QΣ 到Q的单值映射：
f ( qi , a) = qj (qi , qj Q, a Σ) 表示当前状态为qi ，输入字符为a时，自动机将转换到下一个状态qj , qj 称为qi 的一个后继状态。
43
3.4.1 确定有穷自动机 单值函数是指 f(q i,, a) 唯一地确定了下一个要转移的状态，即每个状态的所有输出边上标记的输入字符不同，见下图。 S2 a S1 S3 b S4 c
44
3.4.1 确定有穷自动机 M=( Q, Σ, f, S, Z ) SQ ，是唯一的一个初态。 ZQ ，是一个终态集。
45
3.4.1 确定有穷自动机 例 设DFA M=({q0 , q1 , q2},{a, b}, f , q0 ,{q2}) 其中
f ( q0 , a) = q f ( q0 , b) = q2 f ( q1 , a) = q f ( q1 , b) = q1 f ( q2 , a) = q f ( q2 , b) = q1 状态转换矩阵 状态 字符 a q0 b q1 q2
46
3.4.1 确定有穷自动机 q1 q0 q2 一个 DFA也可以表示成一张状态转换图。
例中DFA M=({q0 , q1 , q2},{a, b}, f , q0 ,{q2}) 的状态转换图如下图所示。 f ( q0 , a) = q f ( q0 , b) = q2 f ( q1 , a) = q f ( q1 , b) = q1 f ( q2 , a) = q f ( q2 , b) = q1 a b q1 a b q0 q2 a b
47
3.4.1 确定有穷自动机 对Σ*中的任何符号串β，若存在一条从初态结到终态结的道路, 在这条路上所有弧的标记连结成的符号串等于β , 则称β为DFA M所识别(或接受)。M所识别的符号串的全体记为 L(M) ，称为DFA M所识别的语言。 q0 q1 q2 b a 例中的DFA M所识别的语言为L(M) = ba*。
48
3.4.2 非确定有穷自动机 非确定有穷自动机（NFA） M=( Q, Σ, f, S, Z) 一个非确定有穷自动机M是一个五元组
其中：Q, ∑, Z 意义同DFA ，f 和 S不同 于DFA 。
49
3.4.2 非确定有穷自动机 (1) 状态转换函数f 不是单值函数,它是一 个多值函数：f(qi ,a) ={某些状态的集合} 由图可知
f( S1, a)={S1 , S2 , S3} a S2 a a 非确定的有穷自动机还 允许 f(qi ,ε)={某些状态的集合}。 S1 S3 c S4 (2) S Q ，是非空初态集。
50
3.4.2 非确定有穷自动机 例 设有NFA M=({1,2,3},{a,b},f,{1,3},{2}) 其中
f (1, a) = {3} f (1 , b) = {1,2} f (2, a) = Φ f (2 , b) = {3} f (3, a) = Φ f (3 , b) = {2} 例中 NFA M′ 对应的状态转换矩阵如下表所示。 状态 字符 a 1 b {2} {3} Φ {1,2} 2 3
51
3.4.2 非确定有穷自动机 1 3 2 例 设有NFA M=({1,2,3},{a,b},f,{1,3},{2}) 其中
f (1, a) = {3} f (1 , b) = {1,2} f (2, a) = Φ f (2 , b) = {3} f (3, a) = Φ f (3 , b) = {2} 例中 NFA M′ 对应的状态转换图如下图所示。 1 a b 2 3
52
3.4.2 非确定有穷自动机 例中NFA M' 所识 别的语言为 1 (1) b*b(bb)* 3 2 (2) b*ab(bb)*
L(M') = b*(b|ab)(bb)*
53
3.4.2 非确定有穷自动机 1 3 2 由NFA的定义可知，同一个符号串 β可由多 条路来识别。
例中 NFA M' ,对符号串β =bbb可由3条路来识别。 1 a b 2 3 第一条路：状态1状态2状态3状态2； 第二条路：状态1状态1状态1状态2； 第三条路：状态3状态2状态3状态2；
54
3.4.2 非确定有穷自动机 事实上DFA是NFA 的特例, 即对于每个NFA M 存在 DFA M' ,使 L(M) = L(M')。因此，我们利用有穷自动机构造词法分析程序的方法是从语言单词的描述中构造出非确定的有穷自动机，再将非确定的有穷自动机转化为确定的有穷自动机，并将其化简为状态最少化的DFA , 然后对DFA的每一个状态构造一小段程序将其转化为识别语言单词的词法分析程序
55
3.4.3 由正规式R构造NFA 输入：字母表Σ上的正规式R 输出：识别(接受)语言L(R)的NFA N 方法：
引进初始结点X和终止结点Y，把R 表示成拓广转换图 X Y R 2. 分析R的语法结构，用如下规则对R 中的每个基本符号构造NFA。
56
3.4.3 由正规式R构造NFA (1) R=Φ, 构造NFA如图所示。 X Y (2) R= ε , 构造NFA如图所示。 X Y
(3) R= a (aΣ), 构造NFA如图所示。 X Y a
57
3.4.3 由正规式R构造NFA A B A C B A B A B A B A C B (4) 若R是复合正规式，则按下图的转换规则
只留下一个符号或 ε 为止。 A B r1r2 A C B r1 r2 对于 代换为 A B r1 r2 A B r1| r2 代换为 对于 A B r1* A C B ε r1 对于 代换为
58
3.4.3 由正规式R构造NFA 3. 整个分裂过程中, 所有新结均采用不同 的名字，保留X，Y为全图唯一初态结 和终态结。
59
3.4.3 由正规式R构造NFA 例1 试构造识别语言R = (a | b)*abb 的NFA N, 使 L(N)=L(R)。 首先将R表示成如下拓广转换图 X Y (a | b)*abb 从左到右分裂R X 1 2 Y (a | b)* 3 b a X 1 2 Y ε 3 b a
60
3.4.3 由正规式R构造NFA X Y X 1 2 Y 例2 试构造识别标识符的NFA，描述标识符的正 规式R= l ( l | d )*
ε 1 l d
61
3.4.3 由正规式R构造NFA X Y X 1 2 Y 例3 试构造正规式 R= 0 ( l* )* | 01 的NFA。
( A* )*=A* 首先利用正规式的等价性化简正规式 ∵ ( l* )*=1* ∴ R=01* | 01=0 (1* | 1) =01* 首先将R表示成如下拓广转换图 A | A*=A* X Y 01* 从左到右分裂R X 2 Y ε 1
62
3.4.4 NFA确定化为DFA的方法 基本思想: 对于一个NFA，由于状态转换函数 f 是一个 多值函数 ，因此，对于它们有
f ( q, a)={q1 , q2 , q3…,qn} 即是NFA状态集合的一个子集，为了将NFA 转换为DFA，把状态集合{q1 , q2 , q3…, qn}看作 一个状态A。 也就是说，DFA的每一个状态代表NFA状态 集合的某个子集，这个DFA使用它的状态去记 录在NFA读入输入符号之后可能到达的所有状 态的集合,我们称此构造方法为子集法
63
3.4.4 NFA确定化为DFA的方法 输入：一个NFA N 输出：一个接受（识别）相同语言的DFA M
1. 状态集合 I 的 ε –闭包的概念。 设I是NFA N的一个状态子集, ε – closure(I)定义 如 下： (1) 若s∈I , 则 s∈ε – closure(I) (2) 若s∈I ,那么从s出发经过任意条ε弧而能到达 的任何状态 s'，都属于ε – closure(I)
64
NFA确定化为DFA的方法 由定义可知, ε – closure(I) 表示所有那些从I中的元素出发经过 ε 道路所能到达的NFA的状态所组成的集合, I中任何状态也在其中，因为它们是通过 ε 通路到达自身的。该集合对DFA来说是一个状态
65
3.4.4 NFA确定化为DFA的方法 通过下图理解状态集合 I 的 ε 一闭包。 1 2 3 4 5 6 7 8 9 ε b
1 2 3 4 5 6 7 8 9 ε b ε – closure({0})={0,1,2,3}, 即{ 0,1,2,3} 中的任一状态都是从NFA的初态0出发， 经任意条ε道路可到达的状态。 这个状态集合实际就是要求的DFA的初态
66
3.4.4 NFA确定化为DFA的方法 1 2 3 4 5 6 7 8 9 ε b 若令A={0,1,2,3},则
1 2 3 4 5 6 7 8 9 ε b 若令A={0,1,2,3},则 J=f(A,b)=f(0,b)∪f(1,b)∪f(2,b)∪f(3,b)={4,7} 因为在状态A中只有状态0有b的转移，转移 到的状态为4和7。 那么令B= ε – closure({4,7})={4,5,6,7,8,9} 即是DFA在状态A下遇到输入符号b，转移到 的后继状态
67
3.4.4 NFA确定化为DFA的方法四周第1次 2. 从 NFA N 构造 DFA M 的算法
已知 NFA N=( Q, ∑, f, x, {y}) 求 DFA M=( Q', ∑, f ', 初态, 终态集 ) 开始令Q'={ }
68
3.4.4 NFA确定化为DFA的方法 求DFA M的初态ε–CLOSURE({x}),并置为无标记送入Q';
while ( Q'中存在一个无标记的状态 T={ s1, s2, s3, …, sn} ) { 标记T; for ( 每个输入符号a ) /* 求 f '( T, a )=U */ { J = f ({s1, s2, s3, …, sn},a ) = f ( s1, a )∪f ( s2 , a )∪… ∪f ( sn, a ); U = ε–CLOSURE( J ); if (U不在Q'中 && U不为空) 置U为无标记并送入Q'; if (U不为空) 置M[T, a ]=U; if (U中至少有一个是N的终态) U为M的终态; }
69
状态转换矩阵M 字符 a 状态 T U T={ s1, s2, s3, …, sn}
J = f ({s1, s2, s3, …, sn},a ) = f ( s1, a )∪f ( s2 , a )∪… ∪f ( sn, a ) U = ε–CLOSURE( J ) M[T, a ]=U f '( T, a )=U
70
3.4.4 NFA确定化为DFA的方法 X 1 2 Y 3 (1) Q'={A} 例1 将下图所示的NFA N确定化。 a ε b
Q′ a b (1) 其等价DFA的开始状态为: A=ε–CLOSURE({X}) ={X, 0, 1} A { X, 0, 1 } 作为未标记的状态添加到Q'中(标记的状态如A记为A) Q'={A}
71
求DFA M的初态ε–CLOSURE({x}),并置为无标记送入Q';
while ( Q'中存在一个无标记的状态 T={ s1, s2, s3, …, sn} ) { 标记T; for ( 每个输入符号a ) /* 求 f '( T, a )=U */ { J = f ({s1, s2, s3, …, sn},a ) = f ( s1, a )∪f ( s2 , a )∪… ∪f ( sn, a ); U = ε–CLOSURE( J ); if (U不在Q'中 && U不为空) 置U为无标记并送入Q'; if (U不为空) 置M[T, a ]=U; if (U中至少有一个是N的终态) U为M的终态; }
72
3.4.4 NFA确定化为DFA的方法 X 1 2 Y 3 Q'={A} a ε b f'(A,a)= f'(A,b)=
Q′ a b f'(A,a)= ε–CLOSURE(f({X,0,1},a)) =ε–CLOSURE( {0, 2}) ={0,1,2}=B A { X, 0, 1 } f'(A,b)= ε–CLOSURE(f({X,0,1},b)) =ε–CLOSURE( {0}) ={0,1}=C J = f ({X, 0, 1},a ) = f ( X, a )∪f ( 0 , a )∪f ( 1, a )= {0, 2} Q'={A} U = ε–CLOSURE( J )=｛0，1，2｝;
73
求DFA M的初态ε–CLOSURE({x}),并置为无标记送入Q';
while ( Q'中存在一个无标记的状态 T={ s1, s2, s3, …, sn} ) { 标记T; for ( 每个输入符号a ) /* 求 f '( T, a )=U */ { J = f ({s1, s2, s3, …, sn},a ) = f ( s1, a )∪f ( s2 , a )∪… ∪f ( sn, a ); U = ε–CLOSURE( J ); if (U不在Q'中 && U不为空) 置U为无标记并送入Q'; if (U不为空) 置M[T, a ]=U; if (U中至少有一个是N的终态) U为M的终态; }
74
3.4.4 NFA确定化为DFA的方法 X 1 2 Y 3 Q'={A,B,C} a ε b f'(A,a)= f'(A,b)= Q′ a
Q′ a b f'(A,a)= ε–CLOSURE(f({X,0,1},a)) =ε–CLOSURE( {0, 2}) ={0,1,2}=B A { X, 0, 1 } { 0,1,2 } { 0,1 } B { 0,1,2 } C { 0,1 } f'(A,b)= ε–CLOSURE(f({X,0,1},b)) =ε–CLOSURE( {0}) ={0,1}=C Q'={A,B,C}
75
求DFA M的初态ε–CLOSURE({x}),并置为无标记送入Q';
while ( Q'中存在一个无标记的状态 T={ s1, s2, s3, …, sn} ) { 标记T; for ( 每个输入符号a ) /* 求 f '( T, a )=U */ { J = f ({s1, s2, s3, …, sn},a ) = f ( s1, a )∪f ( s2 , a )∪… ∪f ( sn, a ); U = ε–CLOSURE( J ); if (U不在Q'中 && U不为空) 置U为无标记并送入Q'; if (U不为空) 置M[T, a ]=U; if (U中至少有一个是N的终态) U为M的终态; }
76
3.4.4 NFA确定化为DFA的方法 X 1 2 Y 3 Q'={A,B,C} 对A做标记 a ε b f'(A,a)= f'(A,b)=
Q′ a b f'(A,a)= ε–CLOSURE(f({X,0,1},a)) =ε–CLOSURE( {0, 2}) ={0,1,2}=B A { X, 0, 1 } { 0,1,2 } { 0,1 } B { 0,1,2 } C { 0,1 } f'(A,b)= ε–CLOSURE(f({X,0,1},b)) =ε–CLOSURE( {0}) ={0,1}=C Q'={A,B,C} 对A做标记
77
求DFA M的初态ε–CLOSURE({x}),并置为无标记送入Q';
while ( Q'中存在一个无标记的状态 T={ s1, s2, s3, …, sn} ) { 标记T; for ( 每个输入符号a ) /* 求 f '( B, a )=U */ { J = f ({s1, s2, s3, …, sn},a ) = f ( s1, a )∪f ( s2 , a )∪… ∪f ( sn, a ); U = ε–CLOSURE( J ); if (U不在Q'中 && U不为空) 置U为无标记并送入Q'; if (U不为空) 置M[T, a ]=U; if (U中至少有一个是N的终态) U为M的终态; }
78
3.4.4 NFA确定化为DFA的方法 X 1 2 Y 3 (2)在Q'中取B Q'={A,B,C} a ε b f'(B,a)=
(2)在Q'中取B Q′ a b f'(B,a)= ε–CLOSURE(f({0,1,2},a)) =ε–CLOSURE( {0, 2}) ={0,1,2}=B A { X, 0, 1 } { 0,1,2 } { 0,1 } B { 0,1,2 } C { 0,1 } f'(B,b)= ε–CLOSURE(f({0,1,2},b)) =ε–CLOSURE( {0,3}) ={0,1,3}=D Q'={A,B,C}
79
3.4.4 NFA确定化为DFA的方法 X 1 2 Y 3 (2)在Q'中取B Q'={A,B,C,D} a ε b f'(B,a)=
(2)在Q'中取B Q′ a b f'(B,a)= ε–CLOSURE(f({0,1,2},a)) =ε–CLOSURE( {0, 2}) ={0,1,2}=B A { X, 0, 1 } { 0,1,2 } { 0,1 } B { 0,1,2 } { 0,1,2 } { 0,1,3 } C { 0,1 } D { 0,1,3 } f'(B,b)= ε–CLOSURE(f({0,1,2},b)) =ε–CLOSURE( {0,3}) ={0,1,3}=D Q'={A,B,C,D}
80
3.4.4 NFA确定化为DFA的方法 X 1 2 Y 3 (3)在Q‘中取C Q'={A,B,C,D} a ε b f'(C,a)=
(3)在Q‘中取C Q′ a b f'(C,a)= ε–CLOSURE(f({0,1},a)) =ε–CLOSURE( {0, 2}) ={0,1,2}=B A { X, 0, 1 } { 0,1,2 } { 0,1 } B { 0,1,2 } { 0,1,2 } { 0,1,3 } C { 0,1 } D { 0,1,3 } f'(C,b)= ε–CLOSURE(f({0,1},b)) =ε–CLOSURE( {0}) ={0,1}=C Q'={A,B,C,D}
81
3.4.4 NFA确定化为DFA的方法 X 1 2 Y 3 (3)在Q‘中取C Q'={A,B,C,D} a ε b f'(C,a)=
(3)在Q‘中取C Q′ a b f'(C,a)= ε–CLOSURE(f({0,1},a)) =ε–CLOSURE( {0, 2}) ={0,1,2}=B A { X, 0, 1 } { 0,1,2 } { 0,1 } B { 0,1,2 } { 0,1,2 } { 0,1,3 } C { 0,1 } { 0,1,2 } { 0,1 } D { 0,1,3 } f'(C,b)= ε–CLOSURE(f({0,1},b)) =ε–CLOSURE( {0}) ={0,1}=C Q'={A,B,C,D}
82
3.4.4 NFA确定化为DFA的方法 X 1 2 Y 3 (3)在Q‘中取D Q'={A,B,C,D} a ε b f'(D,a)=
(3)在Q‘中取D Q′ a b f'(D,a)= ε–CLOSURE(f({0,1,3},a)) =ε–CLOSURE( {0, 2}) ={0,1,2}=B A { X, 0, 1 } { 0,1,2 } { 0,1 } B { 0,1,2 } { 0,1,2 } { 0,1,3 } C { 0,1 } { 0,1,2 } { 0,1 } D { 0,1,3 } f'(D,b)= ε–CLOSURE(f({0,1,3},b)) =ε–CLOSURE( {0,Y}) ={0,1,Y}=E Q'={A,B,C,D}
83
3.4.4 NFA确定化为DFA的方法 X 1 2 Y 3 (3)在Q‘中取D Q'={A,B,C,D,E} 标记D,将E加入Q' a ε
(3)在Q‘中取D Q′ a b f'(D,a)= ε–CLOSURE(f({0,1,3},a)) =ε–CLOSURE( {0, 2}) ={0,1,2}=B A { X, 0, 1 } { 0,1,2 } { 0,1 } B { 0,1,2 } { 0,1,2 } { 0,1,3 } C { 0,1 } { 0,1,2 } { 0,1 } { 0,1,2 } { 0,1,Y } D { 0,1,3 } f'(D,b)= ε–CLOSURE(f({0,1,3},b)) =ε–CLOSURE( {0,Y}) ={0,1,Y}=E E { 0,1,Y } Q'={A,B,C,D,E} 标记D,将E加入Q'
84
3.4.4 NFA确定化为DFA的方法 X 1 2 Y 3 (4)在Q‘中取E Q'={A,B,C,D,E}
ε 3 b (4)在Q‘中取E Q′ a b f'(E,a)= ε–CLOSURE(f({0,1,Y},a)) =ε–CLOSURE( {0, 2}) ={0,1,2}=B A { X, 0, 1 } { 0,1,2 } { 0,1 } B { 0,1,2 } { 0,1,2 } { 0,1,3 } C { 0,1 } { 0,1,2 } { 0,1 } { 0,1,2 } { 0,1,Y } D { 0,1,3 } f'(E,b)= ε–CLOSURE(f({0,1,Y},b)) =ε–CLOSURE( {0}) ={0,1}=C E { 0,1,Y } Q'={A,B,C,D,E} 未增加新的状态,且已无其它状态可处理
85
3.4.4 NFA确定化为DFA的方法 X 1 2 Y 3 (4)在Q‘中取E Q'={A,B,C,D,E} Q'已无其它状态可处理 a ε
(4)在Q‘中取E Q′ a b f'(E,a)= ε–CLOSURE(f({0,1,Y},a)) =ε–CLOSURE( {0, 2}) ={0,1,2}=B A { X, 0, 1 } { 0,1,2 } { 0,1 } B { 0,1,2 } { 0,1,2 } { 0,1,3 } C { 0,1 } { 0,1,2 } { 0,1 } { 0,1,2 } { 0,1,Y } D { 0,1,3 } f'(E,b)= ε–CLOSURE(f({0,1,Y},b)) =ε–CLOSURE( {0}) ={0,1}=C { 0,1 } { 0,1,2 } E { 0,1,Y } Q'={A,B,C,D,E} Q'已无其它状态可处理
86
求DFA M的初态ε–CLOSURE({x}),并置为无标记送入Q';
while ( Q'中存在一个无标记的状态 T={ s1, s2, s3, …, sn} ) { 标记T; for ( 每个输入符号a ) /* 求 f '( T, a )=U */ { J = f ({s1, s2, s3, …, sn},a ) = f ( s1, a )∪f ( s2 , a )∪… ∪f ( sn, a ); U = ε–CLOSURE( J ); if (U不在Q'中 && U不为空) 置U为无标记并送入Q'; if (U不为空) 置M[T, a ]=U; if (U中至少有一个是N的终态) U为M的终态; }
87
3.4.4 NFA确定化为DFA的方法 b { X, 0, 1 } { 0, 1, Y } { 0, 1, 3 } { 0, 1 }
{ 0, 1, 2 } a { 0 ,1, 2 } E D C B A Q′ b A E D C B a Q′
88
NFA确定化为DFA的方法 b A E D C B a Q′ A B C D E a b
89
3.4.4 NFA确定化为DFA的方法 X 1 2 Y 1 2 例2 将下面的NFA N确定化。 ε l d 首先确定其初态 ,命名为0状态
0 =ε–CLOSURE({X})={X} 2 l 1 d Q′ l d {X} {1,2,Y} Φ 1 {1,2,Y} {2,Y} {2,Y} {2,Y} {2,Y} {2,Y} 2
90
3.4.4 NFA确定化为DFA的方法 X 1 2 Y 2 例3 将下面的NFA N确定化。 ε 首先确定其初态 ,命名为0状态
首先确定其初态 ,命名为0状态 0 =ε–CLOSURE({X})={X} 1 2 Q′ 1 {X} {1,2,Y} Φ 1 {1,2,Y} Φ {2,Y} {2,Y} Φ {2,Y} 2
Similar presentations
