NFA到DFA的转换演示

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

 

演示@google code

 

1.示例 NFA

 

2.转换后DFA：

 

3.代码结构：

 

Ext.ns("Ext.ux.compiler");
/*
状态机基类
*/
Ext.ux.compiler.Fa = function () {
}
Ext.override(Ext.ux.compiler.Fa, {
		/*
			用于简化dfa状态标记，得到s的状态index
		*/
    getStateIndex: function (s) {
    },
    /*
    	加入终结状态
    */
    addEndState: function (s) {
    },
    /*
    	加入转移字符，排除x空字符
    */
    addInput: function (c) {
    },
    /*
    	加入状态
    */
    addState: function (s, end) {
    },
    /*
    	是否为终结状态
    */
    containEndState: function (array) {
    },
    /*
    	是否已经包含该状态
    */
    containState: function (array, end) {
    }
});

/*
DFA类
*/
Ext.ux.compiler.Dfa = function () {
}
Ext.extend(Ext.ux.compiler.Dfa, Ext.ux.compiler.Fa, {
		/*
			配置dfa状态图
			从from状态经input字符转移到to状态
		*/
    transState: function (from, to, input) {
    },
    
    /*
    	得到标记简化的新dfa
    */
    genCompress: function () {
    }
});


/*
Nfa类
*/
Ext.ux.compiler.Nfa = function (nfaConfig, nfaStart, nfaEnd) {
}
Ext.extend(Ext.ux.compiler.Nfa, Ext.ux.compiler.Fa, {
	
		/*
			states中是否包含nfa的终结状态
		*/
    isCrossEndState: function (states) {
    },
    /*
    	初始化，状态图，开始状态，结束状态
    */
    init: function (nfa, nfaStart, nfaEnd) {
    },
    
    /*
    	配置状态图，同DFA类
    */
    transState: function (from, to, input) {
    },
    
    /*
    	递归得到由state从空字符可以转到的状态，注意不要重复就行了
    */
    x_closure: function (state, currentStates) {
    },
    
    /*
    	从state状态经由a字符可以转换到的状态，注意a不要为x(空字符)
    */
    move: function (state, a) {
    },
    
    /*
    	得到该NFA对应的DFA
    */
    genDfa: function () {
    }
});