Crafting an Efficient Expression

Perl、Java、.NET、Python和PHP（这里没有列全，其他语言请参考第145页的表格）使用的都是表达式主导的NFA引擎，细微的改变就可能对匹配的结果及方式产生重大的影响。DFA中不存在的问题，对NFA来说却很重要。因为NFA引擎容许用户进行精确控制，所以我们可以用心打造（译注1）正则表达式，但对不熟悉的人来说，这样可能会带来麻烦。本章讲解的就是调校正则表达式的诀窍。

调校表达式时需要考虑的两个因素是准确性和效率：精确匹配我们需要的文本，不包含多余的内容，而且速度要快。第4章和第5章探讨了准确性，现在我们来考察NFA引擎的效率，以及如何有效地利用这些知识（我们会在合适的时候提到DFA的问题，不过本章主要关注的还是基于 NFA 的引擎）。总的来说，关键在于彻底理解回溯背后的过程，学习些技巧来避免可能的回溯。在深入了解了处理机制的细节之后，读者不但能够把匹配的速度提到最高，写更复杂的正则表达式时也会更有信心。

本章内容

为了让读者彻底掌握这些知识，本章首先说明了效率的重要性，然后回顾前几章讲解过的回溯，重点强调效率和回溯对整个匹配的影响，为掌握高级的技巧做准备。然后我们会考察一些常见的内部优化措施，它们可能对效率有相当程度的实质性影响；还要讲解，针对具体实现方式，如何构建最合适的正则表达式。最后，我会做个总结，传授一些终极技巧，来构建快如雷霆的NFA表达式。

测试与回溯

我们将看到的例子代表了使用正则表达式时经常遇到的情况。在分析某个的正则表达式的效率时，我有时会列出正则引擎在匹配过程中进行的独立测试（inpidual test）的次数。如果用正则表达式「marty」匹配smarty，一共会进行6次独立测试，首先是「m」对s（匹配失败），然后是「m」对m，「a」对a，依次继续。我通常会给出回溯的次数（本例中回溯次数为0，不过，正则引擎的传动装置必然会在第二个字符处重试正则表达式，这或许可以算作一次回溯）

之所以要列出这些数字，并不是为表明精确性，而是因为它们比“许多”、“少量”、“多次”、“更好”、“不太多”之类更为准确。我的意思不是说，在NFA上使用正则表达式需要精确地考察测试和回溯的次数，我只是希望让读者知道这些例子的相对优劣。

另一个重要的问题是，你必须意识到这些“精确”的数字可能根据工具的不同而有所不同。我期望读者能够知道，它只是针对具体例子的、相对的粗略表现。不同工具之间的一个重要区别就是，它们可能使用的优化措施不同。如果能够预先判断目标字符串基本无法匹配（例如目标字符串缺少一个引擎能够预知的，匹配成功必须的字符），足够聪明的实现方式可以完全不应用正则表达式。我在本章讨论了这些重要的优化措施，不过普遍原理比具体问题更为重要。

传统型NFA还是POSIX NFA

在分析效率时，一定不要忘记所使用工具的引擎类型：传统型NFA还是POSIX NFA。下一节中我们会看到，有些问题只对某种引擎存在。有的改变可能对其中之一没有影响，对另一个却有极大的影响。还是那句话，理解基本原理，就能应付各种情况。