如何为给定 DFA 的匹配项解析输入字符串
How to parse an input string for matches given a DFA
我通过从正则表达式生成 NFA，然后从 NFA 生成 DFA，从头开始实现正则表达式解析器。问题是 DFA 只能说什么时候计算正在接受。如果正则表达式是 "n*" 并且要匹配的字符串是 "cannot" DFA 在看到 c 后将进入失败状态，所以我从前面删除第一个字符 "annot"然后 "nnot"。此时它看到 n 并进入最终状态并且只会 return 单个 n 所以我告诉它继续尝试直到下一个字符将其从最终状态中移除。然而，当它完成时，它会再次删除第一个字符，所以它将是 "not" 并且它会匹配 "n" 但我不想要后续匹配，我只想要 "nn"。我不知道这怎么可能。
这是一个简单但可能不是最优的算法。我们通过 运行 从该点开始的 DFA 尝试在字符串中的每个连续点进行锚定匹配。当 DFA 处于 运行 时，我们记录字符串中 DFA 处于接受状态的最后一个点。当我们最终到达字符串的末尾或 DFA 无法继续前进的点时，如果我们通过接受状态，我们可以 return 进行匹配；换句话说，如果我们保存了一个接受位置，这将是比赛的结束。否则，我们返回到下一个起始位置并继续。
(注意：在下面的两个伪代码算法中，假设一个保存字符串索引的变量可以有一个未定义的值。在实际实现中，这个值可能是，例如，-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 组成的字符串会发生这种情况。
另一种方法是 运行 多个 DFA 并行。每个 DFA 对应于模式中的不同起点。我们线性扫描字符串；在每个位置，我们可以生成一个对应于该位置的新 DFA，其状态为初始状态。
重要的是要注意并不是每个起点都有一个DFA，因为没有必要让两个DFA保持相同的状态。由于搜索是针对字符串中的第一个匹配项，如果两个 DFA 共享相同的状态，则只有起点较早的那个才是合理的匹配项。此外，一旦某个 DFA 达到接受状态，就不再需要保留任何起点较晚的 DFA，这意味着一旦任何 DFA 达到接受状态，我们就不再在扫描中添加新的 DFA。
由于活动DFA的数量最多为DFA中的状态数，因此该算法在O(NM)中运行s，其中N是字符串的长度，M是状态数在 DFA 中。在实践中，活动 DFA 的数量通常远少于状态的数量（除非状态非常少）。
尽管如此，病态的最坏情况仍然存在，因为NFA⇒DFA变换可以使状态数量呈指数增长。可以通过使用一组 NFA 而不是 DFA 来避免指数爆炸。使用 ε-free NFA 可以方便地简化 NFA 转换，方法是在 Thompson 自动机上执行 ε-闭包或构建 Glushkov 自动机。使用 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>}.
我通过从正则表达式生成 NFA，然后从 NFA 生成 DFA，从头开始实现正则表达式解析器。问题是 DFA 只能说什么时候计算正在接受。如果正则表达式是 "n*" 并且要匹配的字符串是 "cannot" DFA 在看到 c 后将进入失败状态，所以我从前面删除第一个字符 "annot"然后 "nnot"。此时它看到 n 并进入最终状态并且只会 return 单个 n 所以我告诉它继续尝试直到下一个字符将其从最终状态中移除。然而，当它完成时，它会再次删除第一个字符，所以它将是 "not" 并且它会匹配 "n" 但我不想要后续匹配，我只想要 "nn"。我不知道这怎么可能。
这是一个简单但可能不是最优的算法。我们通过 运行 从该点开始的 DFA 尝试在字符串中的每个连续点进行锚定匹配。当 DFA 处于 运行 时，我们记录字符串中 DFA 处于接受状态的最后一个点。当我们最终到达字符串的末尾或 DFA 无法继续前进的点时，如果我们通过接受状态，我们可以 return 进行匹配；换句话说，如果我们保存了一个接受位置，这将是比赛的结束。否则，我们返回到下一个起始位置并继续。
(注意：在下面的两个伪代码算法中，假设一个保存字符串索引的变量可以有一个未定义的值。在实际实现中，这个值可能是，例如，-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 组成的字符串会发生这种情况。
另一种方法是 运行 多个 DFA 并行。每个 DFA 对应于模式中的不同起点。我们线性扫描字符串；在每个位置，我们可以生成一个对应于该位置的新 DFA，其状态为初始状态。
重要的是要注意并不是每个起点都有一个DFA，因为没有必要让两个DFA保持相同的状态。由于搜索是针对字符串中的第一个匹配项，如果两个 DFA 共享相同的状态，则只有起点较早的那个才是合理的匹配项。此外，一旦某个 DFA 达到接受状态，就不再需要保留任何起点较晚的 DFA，这意味着一旦任何 DFA 达到接受状态，我们就不再在扫描中添加新的 DFA。
由于活动DFA的数量最多为DFA中的状态数，因此该算法在O(NM)中运行s，其中N是字符串的长度，M是状态数在 DFA 中。在实践中，活动 DFA 的数量通常远少于状态的数量（除非状态非常少）。
尽管如此，病态的最坏情况仍然存在，因为NFA⇒DFA变换可以使状态数量呈指数增长。可以通过使用一组 NFA 而不是 DFA 来避免指数爆炸。使用 ε-free NFA 可以方便地简化 NFA 转换，方法是在 Thompson 自动机上执行 ε-闭包或构建 Glushkov 自动机。使用 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>}.