regex - 使用基于DFA的(线性时间)正则表达式: possible?捕获组

Question

是否可以使用基于DFA的正则表达式实现捕获组，同时相对于输入长度保持线性时间复杂度？

直觉上我不认为，因为子集构造过程不知道它可能落入了哪个捕获组，但这是我第一次意识到这可能是一个潜在的问题，所以我不知道。

Answer 1

Is it possible to implement capture groups with DFA-based regular expressions while maintaining a linear time complexity with respect to the input length?

是的-至少在捕获组是确定性的情况下。考虑示例正则表达式/a|(a)/；将其与输入的"a"匹配可能会产生捕获的组，也可能不会产生捕获的组。

我认为捕获组可以基于使用finite state transducers的理论基础，就像自动机，但在更改状态时也可以输出字符串。您可以回显输入，但是例如用括号将每个捕获组括起来。

Intuitively I think not, because the subset construction procedure does not know which capture group it may have landed inside, but this is the first time I've realized this may be a potential problem, so I don't know.

确实，这是一个问题。我认为您可以通过用捕获状态标记集合来解决此问题，并类似地区分结果DFA的状态。您可能无法为上述正则表达式生成完全确定性的自动机，就像Wikipedia writes:“某些非确定性的换能器不允许使用等效的确定性的换能器”。

但是，可以修改子集构造过程，请参见Determinization of Transducers。他们的算法似乎围绕以下方面展开:

local ambiguities […] are solved by delaying the outputs as far as needed, until these symbols can be written out deterministically.

例如，正则表达式/ab|(a)c/甚至/(a[bc])|ad/都可以解析为确定性转换器。请注意，与没有捕获组的情况相比，它们的内存表示可能要大得多。