深入理解運算原理｜從簡單的機器到無所不能的程式

最簡單的電腦

|

97

大多數真實世界的正規運算式實作物（例如 Ruby 使用的 Onigmo 程式

庫），如果將範式逐字編譯進有限自動機並模擬其執行，並無法正常運

作。雖然這是以正規運算式匹配字串的快速且效率的方式，但這種作法會

更難以支援更高階的功能，像是擷取群組和前看 / 後看判定。因此，大部

分程式庫使用某種更直接處理正規運算式的

回溯演算法

（

backtracking

algorithm

），而不是將它們轉換成有限自動機。

Russ Cox 的 RE2 程式庫（

http://code.google.com/p/re2/

）是個商

業水準的 C++ 正規運算式實作物，它會將範式編譯進自動機

6

，而 Pat

Shaughnessy 所寫的部落格文章（

http://patshaughnessy.net/2012/4/3/

exploring-rubys-regular-ex pression-algorithm

），則探討了 Ruby 正規運

算式演算法的運作細節。

解析

我們幾乎建置了完整（儘管基本）的正規運算式實作物，唯一缺少的是範式語法的解析

器：如果我們可以只寫

(a(|b))*

，而不用手動以

Repeat.new(Concatenate.new(Literal.

new('a')

,

Choose.new(Empty.new, Literal.new ('b'))))

建置抽象語法樹，那就更加方便

了。我們在第 61 頁的『實作解析器』看到的是，使用 Treetop 產生能自動將原始語法

轉換成 AST 的解析器並不難，所以就讓我們於此完成這個實作物。 ...