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

最簡單的電腦

|

85

然後匹配輸入到那個 NFA 模擬的字串，看看是否接受該字串。我們可以在第 2 章的語

言將此思考成對正規運算式提供指稱語意的排序：大家可能不知道如何直接執行正規

運算式，但我們可以示範如何將它指稱為 NFA，而且也因為我們擁有 NFA 的操作語意

（『讀取字元並遵循規則來改變狀態』），我們可以執行該指稱來達到相同的結果。

語法

我們必須先明確的解釋我們所謂的『正規運算式』；以下是兩種相當簡單的正規運算式：

• 空的正規運算式。這只能匹配空字串，別無其他。

• 包含單一文字字元的正規運算式。例如，

a

和

b

是分別僅匹配字串

'a'

和

'b'

的正

規運算式。

只要我們有這些簡單的範式，就有 3 種方式可以將它們組合成更為複雜的運算式：

• 接合兩種範式。我們可以接合正規運算式

a

和

b

，得到只能匹配字串

'ab'

的正規運

算式

ab

。

• 以 | 運算子連接兩種範式並從中擇一。我們可以連接正規運算式

a

或

b

，而得到正

規運算式

a|b

，這能匹配字串

'a'

和

'b'

。

• 以

*

運算子置於運算式尾端，可重複範式零或數次。我們可以在正規運算式

a

的尾

端加上

*

而得到

a*

，它可匹配

'a'

、

'aa'

、

'aaa'

等字串，以及空字串

''

（也就是

重複零次）。

真實世界的正規運算式引擎（例如 Ruby 內建的正規運算式引擎）支援的

功能比這更多。為了簡化，我們不會試著實作這些額外的功能，就技術而

言，其中許多其實多餘，之所以提供只是因為方便。

舉例來說，省略掉重複運算子

?

和

+

並不會造成重大的差異，因為它們的

效果（分別『重複一次或零次』和『重複一次或數次』 ...