有个同学近来一直在做一个魔兽世界战况分析（名字好像叫DeusCraft），说是很火。只是用C#觉得不是很爽，想移植到C++上面来。但是那个东西在分析的时候用了好多正则表达式，于是只好找了些正则表达式引擎来测。

    测试的文件一共有27万多行，首先通过一个检查时间的正则表达式。如果成功，则在接下来的20几条正则表达式中验证字符串命中哪一条，然后开始做剩余的工作。原先在C#上花了12秒分析，后来换了boost的正则表达式花费40秒，然后从MSR上找了一个号称比boost快4倍的正则表达式引擎，结果还是40秒（都是微软的，咋差距这么大……）。于是同学用他自己做的正则表达式引擎花了23秒（此数据不太记得），我用我以前那个东西花费108秒（-_-|||）。

    于是我们这几天就在优化正则表达式引擎，到了今天同学那个花费13秒，我那个12秒。Visual Studio 2008 Team System上有一个Performance Wizard，用于在程序执行的过程中统计各个函数所占用的时间，可以方便定位，看出效率瓶颈，非常好用。

    我之前的正则表达式为了保持很多语法上的一致性（譬如选择操作符“|”需要遵守交换律等等），使用了一种花费很大的办法来对字符串进行分析。这种分析方法找出所有符合正则表达式要求的所有匹配的路径然后进行筛选。筛选的过程中浪费了很多new和delete的操作，而且做了很多计算，维护了一个非常复杂的数据结构。后来想到有些事情是可以让人来操心的，于是在原来的接口上加了一个option，添加了一种叫做“贪婪式”的分析方法。现在就同时有两种分析方法用了。第二种分析方法的优点是快，缺点是丧失了一些语法上的优美（不过这个对于大部分人来说应该是没什么关系的了。要是正则表达式的执行过程不复杂的话，《精通正则表达式》也就卖不出去了，反正别人的正则表达式大多都是贪婪的）。贪婪式的分析方法不同时扫描所有路径，而是使用回溯的方法。不过这种方法最大的优点在于数据结构可以大幅度简化为三个堆栈（NFA状态、已捕获子串、捕获状态），从而大量减少包括申请和释放等的指针操作。

    上文中的测试是在同学他自己进行的。我在我自己的电脑上使用了一条表达式（而不是20几条）来跑相同的文件，非贪婪式用了23秒，贪婪式用了3.5秒。

    虽然这个正则表达式引擎的接口跟现在C#或Java流行的那些差不多，只是这东西属于Syngram的一部分，所以不是很想单独分隔成一个dll发布。至于代码就要等Vczh Free Script 3.0或者Vczh Lazy Script 1.0发布的时候再一起开放了，因为使用Syngram做编译器是很爽的。到时候再考虑如何将正则表达式和上下文无关文法两个强大的字符串分析库封装成dll用吧。嘿嘿。