正则表达式 – 使用基于DFA(线性时间)正则表达式捕获组：可能吗

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

是的 – 至少在捕获组是确定性的时候.考虑示例regex / 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 /可以被分解为确定性换能器.请注意,他们的内存表示可能比没有捕获组时大得多.