我正在尝试构建一个工具，它使用正则表达式之类的东西来查找字符串(不是文本字符串，但这现在并不重要)中的模式。我熟悉自动机理论，即我知道如何实现基本的正则表达式匹配，并通过以教科书的方式模拟自动机，如果字符串与我的正则表达式匹配，则输出 true 或 false。
假设我对 b 之前的所有 a 感兴趣，并且 b 之前不再有 ，所以，这个正则表达式:a a[^a]*b。但我不仅仅是想知道我的字符串是否包含这样的部分，我想得到 a 作为输出，以便我可以检查它(记住，我实际上并不是在处理文本)。
总结:假设我用括号标记 a，如下所示:(a)[^a]*b 并在输入字符串 上运行它>bcadacb 然后我想要第二个 a 作为输出。
编辑:正确的反向引用，即用括号捕获并用\1 引用等可能不是必需的。我确实知道回溯引用确实引入了回溯(或类似的东西)的需要，并使问题(IIRC)成为 NP 难问题。我的问题本质上是:没有反向引用的捕获部分的计算成本是否比正确的反向引用要低？
最佳答案
大多数文本编辑器通过使用回溯算法来完成此操作，在这种情况下，添加记录匹配位置很简单。
也可以通过使用括号位置信息扩充状态列表来进行直接 NFA 模拟。这可以通过保留线性时间保证的方式来完成。请参阅http://swtch.com/~rsc/regexp/regexp2.html#submatch .
Timos 的答案是正确的，但是您不能标记 DFA 状态，因为 DFA 状态对应于可能的 NFA 状态的集合，因此一个 DFA 状态可能代表通过 paren 的可能性(但也可能是其他状态)也是如此)，如果事实并非如此，那么将其记录为事实就是不正确的。您确实需要进行 NFA 模拟。
关于regex - 能否找出哪些输入字符与正则表达式的哪一部分匹配？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11552654/