regex - 可以找出哪些输入字符与正则表达式的哪一部分匹配吗？

Question

我正在尝试构建一个使用正则表达式之类的工具来查找字符串中的模式(不是文本字符串，但现在这并不重要)。我熟悉自动机理论，即我知道如何实现基本的正则表达式匹配，如果字符串与我的正则表达式匹配则输出 true 或 false，通过以教科书方式模拟自动机。

假设我对 b 之前的所有 a 感兴趣，b 之前没有更多的 a s，所以，这个正则表达式:a[^a]*b。但我不只是想知道我的字符串是否包含这样的部分，我想得到 a 作为输出，以便我可以检查它(记住，我实际上并不是在处理文本)。

总结:假设我用括号标记了 a，如下所示:(a)[^a]*b 并在输入字符串上运行它 bcadacb 然后我想要第二个 a 作为输出。

或者，更一般地说，是否可以找出输入字符串中的哪些字符与正则表达式的哪一部分相匹配？它是如何在文本编辑器中完成的？他们至少知道比赛从哪里开始，因为他们可以突出比赛。我必须使用回溯方法，还是有更智能、计算成本更低的方法？

编辑:可能不需要正确的反向引用，即用括号捕获并用\1 等引用。我确实知道反向引用确实引入了回溯(或类似的东西)的需要，并使问题 (IIRC) 成为 NP-hard。我的问题本质上是:在没有反向引用的情况下，捕获部分的计算成本是否低于适当的反向引用？

Answer 1

大多数文本编辑器通过使用回溯算法来做到这一点，在这种情况下记录匹配位置很容易添加。

通过使用括号位置信息扩充状态列表，也可以使用直接 NFA 模拟。这可以通过保留线性时间保证的方式来完成。参见 http://swtch.com/~rsc/regexp/regexp2.html#submatch .

Timos 的答案是正确的，但是你不能标记 DFA 状态，因为 DFA 状态对应于可能的 NFA 状态的集合，因此一个 DFA 状态可能代表通过了 paren 的可能性(但也可能是其他东西也是)，如果事实并非如此，则将其记录为事实是不正确的。您确实需要改为进行 NFA 模拟。