正则表达式实现细节

Question

我回答的问题让我感到奇怪：

如何在Python中实现正则表达式？有什么样的效率保证？实施是“标准”还是会更改？

我认为正则表达式将实现为DFA，因此非常有效（最多需要扫描输入字符串一次）。Laurence
Gonsalves提出了一个有趣的观点，即并非所有的Python正则表达式都是正则表达式。（他的示例是r“（a +）b \1”，它与一定数量的a，ab匹配，然后与之前相同的a数量匹配）。显然，这不能通过DFA实施。

因此，重申一下：Python正则表达式的实现细节和保证是什么？

如果有人可以（根据实现方式）对正则表达式“ cat | catdog”和“ catdog | cat”为何导致字符串“
catdog”中的搜索结果不同做出某种解释，这也很好。在我之前提到的问题中提到过。

Answer 1

Python的re模块基于PCRE，但已经转向他们自己的实现。

这是C代码的链接。

当采用了错误的路径时，似乎库是基于递归回溯的。

正则表达式和文字大小n
吗？Ñ一个Ñ匹配Ñ

请记住，此图不代表正常的正则表达式搜索。

http://swtch.com/~rsc/regexp/regexp1.html