如何确定正则表达式实现使用DFA还是NFA？

Question

我面临一个问题，即某个正则表达式实现是否基于DFA还是NFA。

有哪些起点可以帮助我解决这个问题。也可以问：我在找什么？有哪些基本模式和/或特征？一个好的解释性链接或一些比较（即使不直接针对正则表达式）也完全可以。

- Jan

---

考虑在http://cstheory.stackexchange.com/上发布此内容。 - Codie CodeMonkey

我认为你的术语有点反了。非确定性有限状态自动机（NFAs）具有多个执行路径的可能性，因此它们需要回溯。回溯对确定性有限状态自动机（DFA）没有任何好处，因为它只能按一种方式进行。 - phs

http://lambda.uta.edu/cse5317/notes/node9.html 也可能与您的兴趣相关。评估正则NFA需要算法保持状态集（回溯），而DFA评估器始终仅保持一个自动机状态。 - phs

所以如果我理解正确，应该是 NFA + 回溯 或 DFA？ - Jan

是的，我相信如此。已经有一段时间了。 - phs

@DeepYellow：不，cstheory是用于研究级理论问题的。 - sdcvvc

Answer 1

如果它是一个黑盒子，那么请给它一些输入，并使用病态案例测量其时间特性，参考这篇关于NFS与回溯正则表达式实现的讨论中的图表。（注意，NFS图表的单位是微秒而不是秒）。

另外，如果它是一个纯NFA，则不会有一些非正则特征，这些特征在一些“正则表达式”解析器中被发现，需要回溯。

或者，查看RxParser类的文档；文档似乎在网络上无法获取，需要运行Squeak才能浏览。

- Pete Kirkham

Answer 2

我认为你的意思是“正则表达式实现”，而不是算法（通常意义上的算法）。

你可以使用已知会在一种方法或另一种方法中出现问题的已知表达式进行测试。同样，寻找在一种或另一种方法中更容易实现的功能（这不是一种可靠的方法 - 正则表达式引擎的开发人员会找到以前难以实现的新方法）。

通常的答案是阅读文档或查看已知参考资料（《精通正则表达式》 "Mastering Regular Expressions" 记录了许多流行的情况）。最后，为什么不问作者呢？

- Richard

---

我会接受这个答案，因为明显的建议是询问作者。我甚至没有想到那个 :) Pete Kirkham的答案也非常有价值。 - Jan