我正在从头开始实现一个正则表达式解析器,方法是从正则表达式生成NFA,然后从NFA生成DFA。问题是DFA只能说计算正在接受。如果正则表达式是“n *”并且匹配的字符串是“不能”,则DFA在看到c之后将进入失败状态,因此我从前面删除第一个字符,“annot”然后“nnot”。此时它会看到n并进入最终状态,并且只返回单个n,所以我告诉它继续尝试,直到下一个角色将其从最终状态中取出。但是当它完成时它再次移除第一个字符,因此它将“不”并且它将匹配“n”但我不想要后续的匹配,我只想要“nn”。我不知道这怎么可能。
这是一个简单但可能不是最优的算法。我们通过从该点开始运行DFA来尝试字符串中每个连续点的锚定匹配。在运行DFA时,我们会记录DFA处于接受状态的字符串中的最后一个点。当我们最终到达字符串的末尾或DFA无法再前进的点时,如果我们通过接受状态,我们可以返回匹配;换句话说,如果我们保存了一个接受位置,这将是比赛的结束。否则,我们回溯到下一个起始位置并继续。
(注意:在下面的两种伪代码算法中,假设一个包含字符串索引的变量可以具有未定义的值。在实际实现中,该值可以是,例如,-1。)
在伪代码中:
Set <start> to 0
Repeat A:
Initialise the DFA state the starting state.
Set <scan> to <start>
Set <accepted> to Undefined
Repeat B:
If there is a character at <scan> and
the DFA has a transition on that character:
Advance the DFA to the indicated next state
Increment <scan>
If the DFA is now in an accepting state, set <accepted> to <scan>
Continue Loop B
Otherwise, the DFA cannot advance:
If <accepted> is still Undefined:
Increment <start> and continue Loop A
Otherwise, <accepted> has a value:
Return a match from <scan> to <accepted> (semi-inclusive)
上述算法的问题在于循环B可能在失败并回溯到下一个起始位置之前执行任意次数。因此,在最坏的情况下,搜索时间将是字符串长度的二次方。例如,使用模式a*b
和由大量a
s组成的字符串就会发生这种情况。
另一种方法是并行运行多个DFA。每个DFA对应于模式中的不同起点。我们线性扫描弦;在每个位置,我们可以产生一个对应于该位置的新DFA,其状态是初始状态。
重要的是要注意并非每个起点都有DFA,因为没有必要保持两个具有相同状态的DFA。由于搜索是字符串中的第一个匹配,如果两个DFA共享相同的状态,则只有具有较早起始点的那个是合理的匹配。此外,一旦某个DFA达到接受状态,就不再需要保留任何起点稍晚的DFA,这意味着只要任何DFA达到接受状态,我们就不再在扫描中添加新的DFA。
由于活动DFA的数量最多是DFA中的状态数,因此该算法在O(NM)中运行,其中N是字符串的长度,M是DFA中的状态数。实际上,活动DFA的数量通常远小于状态数(除非状态非常少)。
尽管如此,病态最坏的情况仍然存在,因为NFA⇒DFA转换可以指数地增加状态的数量。通过使用一组NFA而不是DFA,可以避免指数爆炸。通过在Thompson自动机上执行ε-闭合或通过构建Glushkov自动机,使用无ε的NFA简化NFA过渡很方便。使用Glushkov自动机可确保状态数不大于模式的长度。
在伪代码中:
Initialise a vector <v> of <index, state> pairs. Initially the vector
is empty, and its maximum size is the number of states. This vector is
always kept in increasing order by index.
Initialise another vector <active> of string indices, one for each state.
Initially all the elements in <active> are Undefined. This vector records
the most recent index at which some Automaton was in each state.
Initialise <match> to a pair of index positions, both undefined. This
will record the best match found so far.
For each position <scan> in the string:
If <match> has not yet been set:
Append {<scan>, <start_state>} to <v>.
If <v> is empty:
Return <match> if it has been set, or otherwise
return a failure indication.
Copy <v> to <v'> and empty <v>. (It's possible to recycle <v>,
but it's easier to write the pseudocode with a copy.)
For each pair {<i>, <q>} in <v'>:
If <i> is greater than the starting index in <match>:
Terminate this loop and continue with the outer loop.
If there is no transition from state <q> on the symbol at <scan>:
Continue with the next pair.
Otherwise, there is a transition to <q'> (if using NFAs, do this for each transition):
If the index in <active> corresponding to <q'> has already
been set to <scan>:
Continue with the next pair.
Otherwise, <q'> is not yet in <v>:
Append the pair {<i>, <q'>} at the end of <v>.
Set the the index in <active> at <q'> to <scan>.
If <q'> is an accepting state:
Set <match> to {<i>, <scan>}.