正则表达式/实现
< 正则表达式
至少有3种不同的算法可以确定给定字符串是否（以及如何）与正则表达式匹配。它们基于正则表达式作为有限自动机的不同表示以及匹配器中存在的功能数量。
- 一个不包含反向引用和前瞻/后顾的基于NFA的匹配器。大小为O(n)的输入可以在O(nm)时间内测试与大小为O(m)的正则表达式匹配，并且通过使用汤普森算法模拟NFA，额外需要O(m)的空间。如果要记录c个子匹配捕获组，则运行时间增加到O(nm log c)，但空间需求仍然为O(m)。
- 一个包含反向引用和前瞻/后顾的基于NFA的匹配器。这样的匹配器需要使用回溯来实现。大小为O(n)的输入可以在O(2mn)时间内使用回溯测试与大小为O(m)的正则表达式匹配。需要一些努力来确保基于回溯的匹配器不会进入无限循环，反复测试相同的路径。
- 一个基于DFA的匹配器。基于DFA的匹配器不支持反向引用、子匹配捕获或前瞻/后顾。这是最古老、最快的匹配器类型，它依赖于形式语言理论中的一项结果，该结果允许将每个非确定性有限状态机 (NFA) 转换为确定性有限状态机 (DFA)。该算法执行或模拟这种转换，然后在输入字符串上运行生成的DFA，每次处理一个符号。后一个过程（DFA匹配）所花费的时间与输入字符串的长度成正比。更准确地说，大小为m的正则表达式在大小为S的输入字母表上可以在O(2mS)时间内转换为DFA，随后可以O(n)时间内测试大小为n的输入字符串与任何大小的DFA是否匹配。
基于DFA的算法在将输入与正则表达式匹配方面很快，但只能用于匹配，不能用于调用分组的子表达式。有一种变体可以调用分组的子表达式，但它的运行时间会降至O(n2m) [需要引用]。
基于回溯算法的运行时间可能是指数级的，当匹配包含交替和无限量化的表达式（例如“(a|aa)*b”）时，简单的实现会表现出这种行为，迫使算法考虑指数级的子情况。更复杂的实现会识别并加速各种常见情况，否则它们会运行缓慢。
即使回溯实现只在最坏情况下提供指数级保证，但它们允许更大的灵活性并提供更强大的表达能力。例如，任何允许使用反向引用或实现 Perl 引入的各种改进的实现都必须使用回溯实现。
一些实现尝试通过首先运行一个快速的 DFA 匹配来查看字符串是否与正则表达式匹配，只有在这种情况下才会执行一个潜在的更慢的回溯匹配，从而提供两种算法的最佳效果。