正则表达式引擎

首先看一下Regex引擎是如何工作的

了解正则表达式引擎的工作原理使我们可以更轻松地写出更好的正则表达式。它可以帮助我们快速理解为什么特定的正则表达式不能达到我们最初的期望。当我们需要编写更复杂的正则表达式时，它可以帮我们节省大量的猜测时间和减少很多不必要的麻烦。

引入新的regex token后，本教程将逐步解释regex引擎如何实际处理该token。在某些时候，这种引擎内部的解释看起来似乎有些冗长。但是，了解正则表达式引擎的工作方式将使我们能够发挥其全部功能并帮助我们避免常见的错误。

虽然有许多正则表达式的实现有时在语法和行为上有时会稍有不同，而且有时也是大不相同，但基本上只有两种正则表达式引擎：文本导向（text-directed）引擎和正则表达式导向（regex-directed）引擎。几乎所有现代正则表达式都是基于正则表达式引擎的。这是因为某些非常有用的功能（例如延迟量词和反向引用）只能在正则表达式导向的引擎中实现。   

正则表达式导向的引擎遍历regex，尝试将regex中的下一个标记与下一个字符进行匹配。如果找到匹配项，引擎将通过正则表达式和目标字符串前进。如果不匹配，则引擎将回溯到正则表达式和目标字符串中的先前位置，在该位置它尝试正则表达式的其他路径。本教程稍后将详细讨论回溯。使用正则表达式定向引擎的现代正则表达式样式具有许多功能，例如原子分组和量词，可让我们控制此回溯。

文本导向的引擎遍历目标字符串，尝试进行正则表达式的所有排列，然后前进到字符串中的下一个字符。文本导向的引擎永远不会回退。因此，关于文本导向引擎的匹配过程没有太多要讨论的内容。在大多数情况下，文本导向引擎会找到与正则表达式导向引擎相同的匹配项。

当本教程讨论正则表达式引擎内核时，该讨论假定使用的是正则表达式导向的引擎。我们仅在找到不同匹配项的情况下才会去提及文本导向引擎。  

正则表达式引擎始终返回最左边的匹配项

这是一个非常重要的知识点：即使以后可以找到“更好”的匹配，正则表达式引擎也总是返回最左边的匹配项。将正则表达式应用于字符串时，引擎将从字符串的第一个字符开始。它尝试在第一个字符处对正则表达式进行所有可能的排列。仅在尝试了所有可能性并发现失败后，引擎才会继续使用文本中的第二个字符。再次以完全相同的顺序尝试正则表达式的所有可能排列。最终的结果是正则表达式引擎返回最左边的匹配项。  

当使用正则cat匹配目标字符串‘He captured a catfish for his cat.’中的’cat’时，引擎会尝试将正则表达式cat中的第一个标记c与字符串中的第一个字符H进行匹配。失败了，此正则表达式没有其他可能的排列，因为它仅由一系列字符组成。因此，正则表达式引擎尝试将c与e匹配。这也失败了，将c与空格匹配也是如此。当到达字符串中的第4个字符，c匹配c 。然后，引擎尝试将第二个token a与第5个字符a匹配。这也成功。但是，token t不能匹配字符p 。在这一点上，引擎知道正则表达式不能从字符串的第4个字符开始进行匹配。因此，它继续第5次匹配：a 。同样，c此处不匹配，引擎继续运行。在字符串的第15个字符处，c再次与c匹配。然后，引擎继续尝试在字符15处匹配正则表达式的其余部分，并发现a匹配a和t匹配t 。

整个正则表达式可以从字符15开始匹配。引擎“急于”报告匹配。因此，它将报告 fish 的前三个字母报告为有效匹配项。引擎将永远也不会再超越这一点，去查看是否有任何“更好”的匹配。这次的匹配已经被认为足够可以了。这就是最左匹配原则。

在引擎内部的第一个示例中，我们的regex引擎看起来就像是常规文本搜索例程一样工作。但是，重要的是我们必须遵循引擎所考虑的步骤。在以下示例中，引擎的工作方式对其找到的匹配项具有深远的影响。一些结果可能令人惊讶。但是，一旦我们了解了引擎的工作原理，它们始终是合乎逻辑且是可以预先确定的。