当字符串与正则表达式匹配时,幕后发生了什么？

Question

我有兴趣知道使用什么样的算法来匹配它,以及它们是如何优化的,因为我想有些正则表达式会产生大量可能的匹配,这些匹配可能会在一个效果不佳的正则表达式解析器上造成严重问题.

另外,我最近发现了一种概念重做操作,为什么正则表达式,如(a|aa)+或(a|a?)+造成问题？

编辑:我在C#和Python中使用过它们,所以这就是我在考虑这个问题时的想法.我假设Python是用C语言编写的,就像解释器的其余部分一样,但我不知道C#

Answer 1

正则表达式引擎有两种：NFA和DFA。我很生疏，所以不敢凭记忆详述。不过，这是一个详细介绍算法的页面。有些解析器对于写得不好的表达式会表现得更好。关于这个主题的一本好书（就在我的书架上）是《掌握正则表达式》。