有個同學近來一直在做一個魔獸世界戰(zhàn)況分析（名字好像叫DeusCraft），說是很火。只是用C#覺得不是很爽，想移植到C++上面來。但是那個東西在分析的時候用了好多正則表達式，于是只好找了些正則表達式引擎來測。

    測試的文件一共有27萬多行，首先通過一個檢查時間的正則表達式。如果成功，則在接下來的20幾條正則表達式中驗證字符串命中哪一條，然后開始做剩余的工作。原先在C#上花了12秒分析，后來換了boost的正則表達式花費40秒，然后從MSR上找了一個號稱比boost快4倍的正則表達式引擎，結果還是40秒（都是微軟的，咋差距這么大……）。于是同學用他自己做的正則表達式引擎花了23秒（此數(shù)據(jù)不太記得），我用我以前那個東西花費108秒（-_-|||）。

    于是我們這幾天就在優(yōu)化正則表達式引擎，到了今天同學那個花費13秒，我那個12秒。Visual Studio 2008 Team System上有一個Performance Wizard，用于在程序執(zhí)行的過程中統(tǒng)計各個函數(shù)所占用的時間，可以方便定位，看出效率瓶頸，非常好用。

    我之前的正則表達式為了保持很多語法上的一致性（譬如選擇操作符“|”需要遵守交換律等等），使用了一種花費很大的辦法來對字符串進行分析。這種分析方法找出所有符合正則表達式要求的所有匹配的路徑然后進行篩選。篩選的過程中浪費了很多new和delete的操作，而且做了很多計算，維護了一個非常復雜的數(shù)據(jù)結構。后來想到有些事情是可以讓人來操心的，于是在原來的接口上加了一個option，添加了一種叫做“貪婪式”的分析方法。現(xiàn)在就同時有兩種分析方法用了。第二種分析方法的優(yōu)點是快，缺點是喪失了一些語法上的優(yōu)美（不過這個對于大部分人來說應該是沒什么關系的了。要是正則表達式的執(zhí)行過程不復雜的話，《精通正則表達式》也就賣不出去了，反正別人的正則表達式大多都是貪婪的）。貪婪式的分析方法不同時掃描所有路徑，而是使用回溯的方法。不過這種方法最大的優(yōu)點在于數(shù)據(jù)結構可以大幅度簡化為三個堆棧（NFA狀態(tài)、已捕獲子串、捕獲狀態(tài)），從而大量減少包括申請和釋放等的指針操作。

    上文中的測試是在同學他自己進行的。我在我自己的電腦上使用了一條表達式（而不是20幾條）來跑相同的文件，非貪婪式用了23秒，貪婪式用了3.5秒。

    雖然這個正則表達式引擎的接口跟現(xiàn)在C#或Java流行的那些差不多，只是這東西屬于Syngram的一部分，所以不是很想單獨分隔成一個dll發(fā)布。至于代碼就要等Vczh Free Script 3.0或者Vczh Lazy Script 1.0發(fā)布的時候再一起開放了，因為使用Syngram做編譯器是很爽的。到時候再考慮如何將正則表達式和上下文無關文法兩個強大的字符串分析庫封裝成dll用吧。嘿嘿。