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

88

|

第 3 章

若是真實世界的實作，我們當然使用解析器來建置這些樹狀結構，而非徒手打造；細節

請見第 97 頁的『解析』。

語意

現在我們有一種方式可以將正規運算式的語法表示成 Ruby 物件的樹狀結構，但我們該

如何將那樣的語法轉換成 NFA ？

我們需要決定每個語法類別的實體要怎麼轉換成 NFA。最容易轉換的類別是

Empty

，我

們應該要轉換成只接受空字串的單一狀態 NFA：

同樣的，我們應該將任何文字、單一字元範式都轉換成只接受包含該字元的單一字元字

串的 NFA。以下是該範式

a

的 NFA：

為了

Empty

和

Literal

要產生這些 NFA 而實作

#to_nfa_design

方法的確很容易：

class Empty

def to_nfa_design

start_state = Object.new

accept_states = [start_state]

rulebook = NFARulebook.new([])

NFADesign.new(start_state, accept_states, rulebook)

end

end

class Literal

de f to_nfa_design

start_state = Object.new

accept_state = Object.new

rule = FARule.new(start_state, character, accept_state)

rulebook = NFARulebook.new([rule]) ...