我面临的问题是，某个正则表达式实现是基于 DFA 还是 NFA。
我要解决这个问题的出发点是什么。也可以问：我在找什么？基本模式和/或特征是什么？一个好的和解释性的链接或一些比较（即使不直接专用于正则表达式）是非常好的。
问问题
763 次
2 回答
4
如果它是一个黑盒子，那么给它一些输入并用一个病态的情况来测量它的时间特征，参考这个 NFS 与回溯正则表达式实现的讨论中的图表。（注意 NFS 图是微秒而不是秒）。
此外，如果它是纯 NFA，那么它不会有一些非常规特征，这些特征是一些需要回溯的“正则表达式”解析器。
或者，查看 RxParser 类的文档；文档似乎在 Web 上不可用，并且需要 squeak 运行时才能浏览。
于 2011-11-25T13:12:29.570 回答
2
我认为您的意思是“正则表达式实现”而不是算法（通常意义上的）。
您可以使用已知会导致一种方法或另一种方法出现问题的已知表达式进行测试。还寻找更容易在其中一个或另一个中实现的功能（这不是一种可靠的方法——正则表达式引擎的开发人员会找到新的方法来实现以前很难的事情）。
通常答案是阅读文档，或查看已知参考资料（“掌握正则表达式”记录了许多流行案例）。最后为什么不问问作者？
于 2011-11-25T11:03:55.857 回答