Meh*_*dad 6 regex finite-automata dfa
是否可以使用基于DFA的正则表达式实现捕获组,同时保持相对于输入长度的线性时间复杂度？
直觉上我想不是,因为子集构造过程不知道它可能落入哪个捕获组,但这是我第一次意识到这可能是一个潜在的问题,所以我不知道.
\n\n\n是否可以使用基于 DFA 的正则表达式实现捕获组，同时保持相对于输入长度的线性时间复杂度？
\n
是的 - 至少当捕获组是确定性的时。考虑示例正则表达式/a|(a)/；将其与输入进行匹配"a"可能会产生捕获组，也可能不会产生捕获组。
我认为捕获组可以基于使用有限状态传感器的理论基础，它就像自动机，但也可以在改变状态时输出字符串。例如，您可以回显输入，但用括号将每个捕获组括起来。
\n\n\n\n\n直觉上我认为不是，因为子集构造过程不知道它可能落在哪个捕获组内，但这是我第一次意识到这可能是一个潜在的问题，所以我不知道。
\n
确实，这是一个问题。我认为你可以通过用捕获状态标记你的集合来解决这个问题，并类似地区分结果 DFA 的状态。您可能无法为上面的正则表达式生成完全确定性自动机，正如维基百科所写：“一些非确定性传感器不承认等效的确定性传感器”。
\n\n然而，子集构建过程的修改是可能的，请参阅换能器的确定。他们的算法似乎围绕以下内容：
\n\n\n\n\n局部歧义 [\xe2\x80\xa6] 通过根据需要延迟输出来解决，直到这些符号可以确定地写出。
\n
例如，正则表达式/ab|(a)c/甚至/(a[bc])|ad/可以解析为确定性转换器。请注意，它们的内存表示可能比没有捕获组时大得多。