什麼是 Python? 請簡要回顧本專欄中的第一篇文章,Python 是由 Guido van Rossum 開發的免費高級解釋型語言。其語法簡單易懂,而其面向對象的語義功能強大(但又靈活)。Python 可以廣泛使用並具有高度的可移植性。
什麼是狀態機? 關於狀態機的一個極度確切的描述是它是一個有向圖形,由一組節點和一組相應的轉移函數組成。狀態機通過響應一系列事件而“運行”。每個事件都在屬於“當前”節點的轉移函數的控制范圍內,其中函數的范圍是節點的一個子集。函數返回“下一個”(也許是同一個)節點。這些節點中至少有一個必須是終態。當到達終態,狀態機停止。 但一個抽象的數學描述(就像我剛給出的)並不能真正說明在什麼情況下使用狀態機可以解決實際編程問題。另一種策略就是將狀態機定義成一種強制性編程語言,其中節點也是源碼行。從實用角度看,這個定義盡管精確,但它和第一種描述一樣,都是紙上談兵、毫不實用。(對於說明型、函數型或基於約束的語言,例如,Haskell、Scheme 或 Prolog,不一定會發生這種情況。) 讓我們嘗試使用更適合身邊實際任務的例子來進行討論。邏輯上,每個規則表達式都等價於一個狀態機,而每個規則表達式的語法分析器都實現這個狀態機。實際上,大多數程序員編寫狀態機時,並沒有真正考慮到這一點。 在以下這個例子中,我們將研究狀態機的真正探索性定義。通常,我們有一些不同的方法來響應一組有限數量的事件。某些情況下,響應只取決於事件本身。但在其它情況下,適當的操作取決於以前的事件。 本文中討論的狀態機是高級機器,其目的是演示一類問題的編程解決方案。如果有必要按響應事件行為的類別來討論編程問題,那麼您的解決方案很可能是顯式狀態機。
文本處理狀態機 最可能調用顯式狀態機的一個編程問題涉及到處理文本文件。處理文本文件通常包括讀取信息單元(通常叫做字符或行),然後對剛讀取的單元執行適當操作。某些情況下,這個處理是“無狀態的”(即每個這樣的單元都包含了足夠的信息,可以正確確定要執行什麼操作)。在其它情況下,即使文本文件不是完全無狀態,數據也只有有限的上下文(例如,操作取決於不比行號更多的信息)。但是,在其它常見文本處理問題中,輸入文件是極具“狀態”的。每一塊數據的含義取決於它前面的字符串(也許是它後面的字符串)。報告、大型機數據輸入、可讀文本、編程源文件和其它種類的文本文件都是有狀態的。一個簡單例子是可能出現在 Python 源文件中的一行代碼: myObject = SomeClass(this, that, other) 這行表示,如果恰好有以下幾行圍繞著這一行,則有部分內容不同: """How to use SomeClass: myObject = SomeClass(this, that, other) """ 我們應知道我們處於“塊引用”狀態以確定這行代碼是一部分注釋而不是 Python 操作。
何時不使用狀態機 當開始為任何有狀態的文本文件編寫處理器的任務時,問一問自己,您希望在文件中找到什麼類型的輸入項。每種類型的輸入項都是一種狀態的候選項。這些類型共有幾種。如果數字很大或者不確定,則狀態機也許不是正確的解決方法。(在這種情況下,某些數據庫解決方案可能更適合。) 還請考慮您是否需要使用狀態機。許多情況下,最好從更簡單的方法入手。也許會發現即使文本文件是有狀態的,也有一種簡單的方法可以分塊讀取它(其中每一塊是一種類型的輸入值)。實際上,在單一狀態塊中,僅當文本類型之間的轉移需要基於內容的計算時,才有必要實現狀態機。 下面這個簡單的例子說明了需要使用狀態機的情況。請考慮用於將一列數字劃分成幾塊的兩個規則。在第一個規則中,列表中的零表示塊之間的間斷。第二個規則中,當一個塊中的元素總和超過 100 時,會發生塊之間的間斷。由於它使用累加器變量來確定是否達到了阈值,您不能“馬上”看到子列表的邊界。因此,第二個規則也許更適合於類似於狀態機的機制。 稍微有些狀態、但由不太適合用狀態機處理的文本文件的例子是 Windows 風格的 .ini 文件。這種文件包括節頭、注釋和許多賦值。例如: ; set the colorscheme and userlevel [colorscheme] background=red foreground=blue title=green [userlevel] login=2 title=1 我們的例子沒有實際含義,但它表明了 .ini 格式一些有趣的特性。 就某種意義而言,每一行的類型由它的第一個字符確定(可能是分號、左花括號或字母)。 從另一種角度看,這種格式是“有狀態的”,因為關鍵字 "title" 大概表示如果它出現在每一節中,那麼就有獨立的內容。 您可以編寫一個有 COLORSCHEME 狀態和 USERLEVEL 狀態的文本處理器程序,這個程序仍處理每個狀態的賦值。但這好象不是處理此問題的 正確方法。例如,可以使用 Python 代碼在這個文本文件中只創建自然塊,如: 處理 .INI 文件的分塊 Python 代碼 import string txt = open('hypothetical.ini').read() sects = string.split(txt, '[') for sect in sects: # do something with sect, like get its name # (the stuff up to ']') and read its assignments 或者,如果願意,可以使用單個 current_section 變量來確定位置: 處理 .INI 文件的計算 Python 代碼 for line in open('hypothetical.ini').readlines(): if line[0] == '[': current_section = line(1:-2) elif line[0] == ';': pass # ignore comments else: apply_value(current_section, line)
何時使用狀態機 現在,我們已經決定了如果文本文件“太簡單”就不使用狀態機,讓我們再研究 需要使用狀態機的情況。本專欄中 最近一篇文章討論了實用程序 Txt2Html,它將“智能 ASCII”(包括本文)轉換成 HTML。讓我們扼要重述。 “智能 ASCII”是一種文本格式,它使用一些間隔約定來區分文本塊的類型,如頭、常規文本、引語和代碼樣本。雖然讀者或作者能容易地通過查看分析這些文本塊類型之間的轉移,但卻沒有簡單的方法可以讓計算機將“智能 ASCII”文件分割成組成它的文本塊。不像 .ini 文件示例,文本塊類型可以任何順序出現。在任何情況下都沒有單一定界符來分隔塊(空行 通常分隔文本塊,但代碼樣本中的空行卻不一定結束代碼樣本,並且文本塊不需要用空行來分隔)。由於需要以不同方式重新格式化每個文本塊以生成正確的 HTML 輸出,狀態機似乎就是自然的解決方案。 Txt2Html 閱讀器的一般功能如下: 在初始狀態中啟動。 讀取一行輸入。 根據輸入和當前狀態,轉移到新狀態或按適合當前狀態的方式處理該行。 這個例子是關於您會遇到的最簡單的情況,但它說明了我們描述過的以下模式: Python 中一個簡單的狀態機輸入循環 global state, blocks, bl_num, newblock #-- Initialize the globals state = "HEADER" blocks = [""] bl_num = 0 newblock = 1 for line in fhin.readlines(): if state == "HEADER": # blank line means new block of header if blankln.match(line): newblock = 1 elif textln.match(line): startText(line) elif codeln.match(line): startCode(line) else: if newblock: startHead(line) else: blocks[bl_num] = blocks[bl_num] + line elif state == "TEXT": # blank line means new block of text if blankln.match(line): newblock = 1 elif headln.match(line): startHead(line) elif codeln.match(line): startCode(line) else: if newblock: startText(line) else: blocks[bl_num] = blocks[bl_num] + line elif state == "CODE": # blank line does not change state if blankln.match(line): blocks[bl_num] = blocks[bl_num] + line elif headln.match(line): startHead(line) elif textln.match(line): startText(line) else: blocks[bl_num] = blocks[bl_num] + line else: raise ValueError, "uneXPected input block state: "+state 可以用 Txt2Html 下載從中取出該代碼的源文件(請參閱參考資料)。請注意:變量 state 聲明為 global,在函數(如 startText())中更改它的值。轉移條件,如 textln.match(),是規則表達式模式,但它們可能也是定制函數。實際上,以後會在程序中執行格式化。狀態機只將文本文件分析成 blocks 列表中帶標簽的塊。
抽象狀態機類 在表單和函數中使用 Python 實現抽象狀態機很容易。這使程序的狀態機模型比前一個例子中的簡單條件塊顯得更突出(初看,其中的條件與其它條件沒有什麼不同)。而且,以下類及其關聯處理程序在隔離狀態中操作方面完成得很好。許多情況下,這改善了封裝和可讀性。 文件:statemachine.py from string import upper class StateMachine: def __init__(self): self.handlers = {} self.startState = None self.endStates = [] def add_state(self, name, handler