NFA到DFA的转换演示

NFA到DFA的转换演示

博客分类：
• algorithm

EXT正则表达式算法Google 

  复习一下编译，在龙书中提到的NFA（不确定有穷自动机）到DFA（确定有穷自动机）的转换，master regular expression中提到的不依赖于正则表示式的识别问题，不用精心构造正则表达式，只需将正则表达式转化为NFA，进而转化为DFA，则任何长度为n的字符串都可以在O(n)时间内判断出来是否符合该正则表达式。关于正则表示式如何转化为NFA暂略，这里演示一下使用子集构造算法将NFA转化为DFA，转换为后对于词法分析能显著提高效率。

 

演示@google code

 

1.示例 NFA

 

2.转换后DFA：

 

3.代码结构：

 

Js代码  

1. Ext.ns("Ext.ux.compiler");  
2. /* 
3. 状态机基类 
4. */  
5. Ext.ux.compiler.Fa = function () {  
6. }  
7. Ext.override(Ext.ux.compiler.Fa, {  
8.         /* 
9.             用于简化dfa状态标记，得到s的状态index 
10.         */  
11.     getStateIndex: function (s) {  
12.     },  
13.     /* 
14.         加入终结状态 
15.     */  
16.     addEndState: function (s) {  
17.     },  
18.     /* 
19.         加入转移字符，排除x空字符 
20.     */  
21.     addInput: function (c) {  
22.     },  
23.     /* 
24.         加入状态 
25.     */  
26.     addState: function (s, end) {  
27.     },  
28.     /* 
29.         是否为终结状态 
30.     */  
31.     containEndState: function (array) {  
32.     },  
33.     /* 
34.         是否已经包含该状态 
35.     */  
36.     containState: function (array, end) {  
37.     }  
38. });  
39.   
40. /* 
41. DFA类 
42. */  
43. Ext.ux.compiler.Dfa = function () {  
44. }  
45. Ext.extend(Ext.ux.compiler.Dfa, Ext.ux.compiler.Fa, {  
46.         /* 
47.             配置dfa状态图 
48.             从from状态经input字符转移到to状态 
49.         */  
50.     transState: function (from, to, input) {  
51.     },  
52.       
53.     /* 
54.         得到标记简化的新dfa 
55.     */  
56.     genCompress: function () {  
57.     }  
58. });  
59.   
60.   
61. /* 
62. Nfa类 
63. */  
64. Ext.ux.compiler.Nfa = function (nfaConfig, nfaStart, nfaEnd) {  
65. }  
66. Ext.extend(Ext.ux.compiler.Nfa, Ext.ux.compiler.Fa, {  
67.       
68.         /* 
69.             states中是否包含nfa的终结状态 
70.         */  
71.     isCrossEndState: function (states) {  
72.     },  
73.     /* 
74.         初始化，状态图，开始状态，结束状态 
75.     */  
76.     init: function (nfa, nfaStart, nfaEnd) {  
77.     },  
78.       
79.     /* 
80.         配置状态图，同DFA类 
81.     */  
82.     transState: function (from, to, input) {  
83.     },  
84.       
85.     /* 
86.         递归得到由state从空字符可以转到的状态，注意不要重复就行了 
87.     */  
88.     x_closure: function (state, currentStates) {  
89.     },  
90.       
91.     /* 
92.         从state状态经由a字符可以转换到的状态，注意a不要为x(空字符) 
93.     */  
94.     move: function (state, a) {  
95.     },  
96.       
97.     /* 
98.         得到该NFA对应的DFA 
99.     */  
100.     genDfa: function () {  
101.     }  
102. });