网站验证码 出不来,ueditor上传wordpress,国外哪个网站可以做外贸比较好,_count-views_all wordpress书接上文#xff0c;上回说道NFA已经可以完全描述正则语言的全部内容。那么#xff0c;我们在这一章探索一下一个比较复杂的正则表达式在用NFA做匹配的时候会有什么“不足“。NFA匹配的不足为了言之有物#xff0c;不妨设要讨论的模式为d?(c(a|b)*)*(b|c)图1-1…书接上文上回说道NFA已经可以完全描述正则语言的全部内容。那么我们在这一章探索一下一个比较复杂的正则表达式在用NFA做匹配的时候会有什么“不足“。NFA匹配的不足为了言之有物不妨设要讨论的模式为d?(c(a|b)*)*(b|c)图1-1效率从上图可以明确的看到存在大量的ℇ转换。这些ℇ转换在程序实现的时候就对应了大量的回溯入口即决策点。那么很显然这个时候一定存在大量的递归回溯调用自然也就必然会需要大量时间来执行。ℇ转换冗余究其原因无非就是冗余状态太多了冗余 ≠ 无用这些看似冗余的转换实际上对分组捕获非常有用,因为在分组捕获时这些回溯可以记录当前匹配的状态还有剩余输入信息等。但是如果我们不用分组捕获只是要求模式全称匹配则这些转换就是冗余的我们需要通过状态压缩来实现确定化以避免任何回溯。状态压缩从上可知若要完成状态压缩则必须消除这些ℇ转换。但是如何完成这一算法呢完成后的确定化的结果仍然自动机么当然是并且它有个与NFA对应的名字叫做DFA。DFA登场DFA与NFA的区别从图1-1与图1-2中可以明显的发现NFA和DFA在转换边上的差异,归纳为下表。NFADFAℇ转换存在不存在相同输入不同转换存在不存在ℇ转换 closure---克林闭包消除ℇ转换function cleenClosure(){// BFSlet espilonSet [state];let queue [state];while(queue.length 0){let q queue.shift();for(const st of q.epsilonTransitions){if(espilonSet.findIndex(val st.label val.label) -1){queue.push(st);espilonSet.push(st)if(st.isEnd) state.isEnd st.isEnd}}}return espilonSet;
}
Subset-Construction(子集构造借助上文的消除ℇ转换函数我们可以将能够通过ℇ转换到达的相连节点划分为新DFA的等价状态。function toDFA(exp) {// 输入字符集let aplhabets new Set();// 原始正则表达式for(const ch of exp){if(ch ! ( ch ! . ch ! ? ch ! ) ch ! * ch ! |) {aplhabets.add(ch)}}const transExp insertExplicitConcatOperator(exp);// 经过后缀改写的正则表达式后缀改写目的在于解决运算符的优先级确定const postfixExp toPostfix(transExp);let nfa toNFA(postfixExp);//1. 从初始状态开始进行下一状态等价集合的构造let q0 createDFAState(false);q0.nfaStateSet epsilonCleen(nfa.start);q0.isEnd nfa.start.isEnd;//2. 存储新发现等价状态的工作集let workLst new Array();//3. 存储已经生成等价状态的集合let dfaStates [q0];workLst.push(q0);//4. 不停增加和删除等价状态知道workLst变为空集while(workLst.length 0){let q workLst.shift();for(const ch of aplhabets) {// 4.1 计算delta并合并进入新状态t epsilonCleenDelta(q,ch);if(t ! null) {if(!dfaStatesHas(dfaStates,t)){dfaStates.push(t);workLst.push(t);q.transitions[ch] t} else {let node dfaStatesFind(dfaStates,t);node.isEnd t.isEnd;q.transitions[ch] node;}}}}return q0;
}
图1-2
