如何为给定DFA的匹配解析输入字符串

问题描述 投票:0回答:1

我正在从头开始实现一个正则表达式解析器,方法是从正则表达式生成NFA,然后从NFA生成DFA。问题是DFA只能说计算正在接受。如果正则表达式是“n *”并且匹配的字符串是“不能”,则DFA在看到c之后将进入失败状态,因此我从前面删除第一个字符,“annot”然后“nnot”。此时它会看到n并进入最终状态,并且只返回单个n,所以我告诉它继续尝试,直到下一个角色将其从最终状态中取出。但是当它完成时它再次移除第一个字符,因此它将“不”并且它将匹配“n”但我不想要后续的匹配,我只想要“nn”。我不知道这怎么可能。

regex parsing dfa
1个回答
0
投票

这是一个简单但可能不是最优的算法。我们通过从该点开始运行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和由大量as组成的字符串就会发生这种情况。

另一种方法是并行运行多个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>}.
© www.soinside.com 2019 - 2024. All rights reserved.