NFA到DFA的转换演示

  • NFA到DFA的转换演示

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

    演示@google code

    1.示例 NFA

    2.转换后DFA:

  • 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 () {   
  •     }   
  • });