2

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

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

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

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

编辑：正确的反向引用，即用括号捕获和用 \1 引用等可能不是必需的。我确实知道反向引用确实需要回溯（或类似的东西）并使问题（IIRC）NP-hard。从本质上讲，我的问题是：在没有反向引用的情况下，捕获部分的计算成本是否比正确的反向引用低？

4

2 回答 2

4

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

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

Timos 的答案在正确的轨道上，但是您不能标记 DFA 状态，因为 DFA 状态对应于可能的 NFA 状态的集合，因此一个 DFA 状态可能代表通过了一个括号的可能性（但也可能是其他东西）和如果事实并非如此，那么将其记录为事实是不正确的。您确实需要进行 NFA 模拟。

于 2012-07-19T11:39:01.367 回答
1

在为匹配构建 DFA 后，在正则表达式中的左括号后标记与第一个状态相对应的所有状态。当你访问这样一个状态时，保存当前输入字符的索引，当你访问一个右括号对应的状态时，也保存索引。当您达到接受状态时，输出两个索引。我不确定这是否是文本编辑器中使用的算法，但我就是这样做的。

于 2012-07-19T01:20:42.027 回答