您当前的位置:首页 > 计算机 > 编程开发 > 编译原理

编译程序第一个工作阶段-词法分析(NFA和DFA转换)

时间:04-28来源:作者:点击数:

上篇讲述确定有穷自动机和不确定有穷自动机,本篇讲述不确定有穷自动机和确定有穷自动机之间的转换。从百度文库中找到一个示例感觉很合适。

如图所示:

1.具有ε动作的NFA状态转换表

                                              

                         a                        

                        b                        

                               ε                            

0

Φ

Φ

1, 7

1

Φ

Φ

2, 4

2

3

Φ

Φ

3

Φ

Φ

6

4

Φ

5

Φ

5

Φ

Φ

6

6

Φ

Φ

1, 7

7

8

Φ

Φ

8

Φ

9

Φ

9

Φ

Φ

Φ

2.分别求ε-closure

ε-closure(I)就是状态集I中,任意状态S经过任意的 ε能到达的状态集合。

ε-closure(0) = {0,1,2,4,7}
ε-closure(1) = {1,2,4}
ε-closure(2) = {2}
ε-closure(3) = {1,2,3,4,6,7}
ε-closure(4) = {4}
ε-closure(5) = {1,2,4,5,6,7}
ε-closure(6) ={1,2,4,6,7}
ε-closure(7) = {7}
ε-closure(8) = {8}
ε-closure(9) = {9}

3.转换算法:

move(I,a)是从I中的某一状态经过一条a弧而到达的状态全体。

ε-closure(0) ={0,1,2,4,7} = A
ε-closure(move(A,a))=ε-closure({3,8})={1,2,3,4,6,7,8} = B
ε-closure(move(A,b))=ε-closure({5})={1,2,4,5,6,7} = C
ε-closure(move(B,a))=ε-closure({3,8}) = B
ε-closure(move(B,b))=ε-closure({5,9})={1,2,4,5,6,7,9} = D
ε-closure(move(C,a))=ε-closure({3,8}) = B
ε-closure(move(C,b))=ε-closure({5}) = C
ε-closure(move(D,a))=ε-closure({3,8}) = B
ε-closure(move(D,b))=ε-closure({5}) = C

4.DFA的转换表

                                          状态                                                 

      输入符号       

a

b

A

B

C

B

B

D

C

B

C

D

B

C

5.状态转换图

本篇到这里,编译原理入门教程就到这里了。

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门