什么是狀態(tài)機(jī)？

關(guān)于狀態(tài)機(jī)的一個(gè)極度確切的描述是它是一個(gè)有向圖形，由一組節(jié)點(diǎn)和一組相應(yīng)的轉(zhuǎn)移函數(shù)組成。狀態(tài)機(jī)通過(guò)響應(yīng)一系列事件而“運(yùn)行”。每個(gè)事件都在屬于“當(dāng)前”節(jié)點(diǎn)的轉(zhuǎn)移函數(shù)的控制范圍內(nèi)，其中函數(shù)的范圍是節(jié)點(diǎn)的一個(gè)子集。函數(shù)返回“下一個(gè)”（也許是同一個(gè)）節(jié)點(diǎn)。這些節(jié)點(diǎn)中至少有一個(gè)必須是終態(tài)。當(dāng)?shù)竭_(dá)終態(tài)，狀態(tài)機(jī)停止。

但一個(gè)抽象的數(shù)學(xué)描述（就像我剛給出的）并不能真正說(shuō)明在什么情況下使用狀態(tài)機(jī)可以解決實(shí)際編程問(wèn)題。另一種策略就是將狀態(tài)機(jī)定義成一種強(qiáng)制性編程語(yǔ)言，其中節(jié)點(diǎn)也是源碼行。從實(shí)用角度看，這個(gè)定義盡管精確，但它和第一種描述一樣，都是紙上談兵、毫不實(shí)用。（對(duì)于說(shuō)明型、函數(shù)型或基于約束的語(yǔ)言，例如，Haskell、Scheme 或 Prolog，不一定會(huì)發(fā)生這種情況。）

讓我們嘗試使用更適合身邊實(shí)際任務(wù)的例子來(lái)進(jìn)行討論。邏輯上，每個(gè)規(guī)則表達(dá)式都等價(jià)于一個(gè)狀態(tài)機(jī)，而每個(gè)規(guī)則表達(dá)式的語(yǔ)法分析器都實(shí)現(xiàn)這個(gè)狀態(tài)機(jī)。實(shí)際上，大多數(shù)程序員編寫狀態(tài)機(jī)時(shí)，并沒(méi)有真正考慮到這一點(diǎn)。

在以下這個(gè)例子中，我們將研究狀態(tài)機(jī)的真正探索性定義。通常，我們有一些不同的方法來(lái)響應(yīng)一組有限數(shù)量的事件。某些情況下，響應(yīng)只取決于事件本身。但在其它情況下，適當(dāng)?shù)牟僮魅Q于以前的事件。

本文中討論的狀態(tài)機(jī)是高級(jí)機(jī)器，其目的是演示一類問(wèn)題的編程解決方案。如果有必要按響應(yīng)事件行為的類別來(lái)討論編程問(wèn)題，那么您的解決方案很可能是顯式狀態(tài)機(jī)。

文本處理狀態(tài)機(jī)

最可能調(diào)用顯式狀態(tài)機(jī)的一個(gè)編程問(wèn)題涉及到處理文本文件。處理文本文件通常包括讀取信息單元（通常叫做字符或行），然后對(duì)剛讀取的單元執(zhí)行適當(dāng)操作。 某些情況下，這個(gè)處理是“無(wú)狀態(tài)的”（即每個(gè)這樣的單元都包含了足夠的信息，可以正確確定要執(zhí)行什么操作）。在其它情況下，即使文本文件不是完全無(wú)狀態(tài)， 數(shù)據(jù)也只有有限的上下文（例如，操作取決于不比行號(hào)更多的信息）。但是，在其它常見(jiàn)文本處理問(wèn)題中，輸入文件是極具“狀態(tài)”的。 每一塊數(shù)據(jù)的含義取決于它前面的字符串（也許是它后面的字符串）。報(bào)告、大型機(jī)數(shù)據(jù)輸入、可讀文本、編程源文件和其它種類的文本文件都是有狀態(tài)的。 一個(gè)簡(jiǎn)單例子是可能出現(xiàn)在 Python 源文件中的一行代碼：

myObject = SomeClass(this, that, other)

這行表示，如果恰好有以下幾行圍繞著這一行，則有部分內(nèi)容不同：

"""How to use SomeClass:
myObject = SomeClass(this, that, other)
"""

我們應(yīng)知道我們處于“塊引用” 狀態(tài) 以確定這行代碼是一部分注釋而不是 Python 操作。

何時(shí)不使用狀態(tài)機(jī)

當(dāng)開始為任何有狀態(tài)的文本文件編寫處理器的任務(wù)時(shí)，問(wèn)一問(wèn)自己，您希望在文件中找到什么類型的輸入項(xiàng)。每種類型的輸入項(xiàng)都是一種狀態(tài)的候選項(xiàng)。這些類型共有幾種。如果數(shù)字很大或者不確定，則狀態(tài)機(jī)也許不是正確的解決方法。（在這種情況下，某些數(shù)據(jù)庫(kù)解決方案可能更適合。）

還請(qǐng)考慮您是否需要使用狀態(tài)機(jī)。許多情況下，最好從更簡(jiǎn)單的方法入手。也許會(huì)發(fā)現(xiàn)即使文本文件是有狀態(tài)的，也有一種簡(jiǎn)單的方法可以分塊讀取它（其中每一塊是一種類型的輸入值）。實(shí)際上，在單一狀態(tài)塊中，僅當(dāng)文本類型之間的轉(zhuǎn)移需要基于內(nèi)容的計(jì)算時(shí)，才有必要實(shí)現(xiàn)狀態(tài)機(jī)。

下面這個(gè)簡(jiǎn)單的例子說(shuō)明了需要使用狀態(tài)機(jī)的情況。請(qǐng)考慮用于將一列數(shù)字劃分成幾塊的兩個(gè)規(guī)則。在第一個(gè)規(guī)則中，列表中的零表示塊之間的間斷。第二個(gè)規(guī)則中，當(dāng)一個(gè)塊中的元素總和超過(guò) 100 時(shí)，會(huì)發(fā)生塊之間的間斷。由于它使用累加器變量來(lái)確定是否達(dá)到了閾值，您不能“馬上”看到子列表的邊界。因此，第二個(gè)規(guī)則也許更適合于類似于狀態(tài)機(jī)的機(jī)制。

稍微有些狀態(tài)、但由 不 太適合用狀態(tài)機(jī)處理的文本文件的例子是 Windows 風(fēng)格的 .ini 文件。這種文件包括節(jié)頭、注釋和許多賦值。例如：

; set the colorscheme and userlevel
[colorscheme]
background=red
foreground=blue
title=green
[userlevel]
login=2
title=1

我們的例子沒(méi)有實(shí)際含義，但它表明了 .ini 格式一些有趣的特性。

    就某種意義而言，每一行的類型由它的第一個(gè)字符確定（可能是分號(hào)、左花括號(hào)或字母）。
    從另一種角度看，這種格式是“有狀態(tài)的”，因?yàn)殛P(guān)鍵字 "title" 大概表示如果它出現(xiàn)在每一節(jié)中，那么就有獨(dú)立的內(nèi)容。

您可以編寫一個(gè)有 COLORSCHEME 狀態(tài)和 USERLEVEL 狀態(tài)的文本處理器程序，這個(gè)程序仍處理每個(gè)狀態(tài)的賦值。但這好象不是處理此問(wèn)題的 正確 方法。例如，可以使用 Python 代碼在這個(gè)文本文件中只創(chuàng)建自然塊，如：
處理 .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

或者，如果愿意，可以使用單個(gè) current_section 變量來(lái)確定位置：
處理 .INI 文件的計(jì)算 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)

何時(shí)使用狀態(tài)機(jī)

現(xiàn)在，我們已經(jīng)決定了如果文本文件“太簡(jiǎn)單”就不使用狀態(tài)機(jī)，讓我們?cè)傺芯?需要使用狀態(tài)機(jī)的情況。本專欄中最近一篇文章 討論了實(shí)用程序 Txt2Html，它將“智能 ASCII”（包括本文）轉(zhuǎn)換成 HTML。讓我們扼要重述。

“智能 ASCII”是一種文本格式，它使用一些間隔約定來(lái)區(qū)分文本塊的類型，如頭、常規(guī)文本、引語(yǔ)和代碼樣本。雖然讀者或作者能容易地通過(guò)查看分析這些文本塊類型之間的轉(zhuǎn)移，但卻沒(méi)有簡(jiǎn)單的方法可以讓計(jì)算機(jī)將“智能 ASCII”文件分割成組成它的文本塊。不像 .ini 文件示例，文本塊類型可以任何順序出現(xiàn)。在任何情況下都沒(méi)有單一定界符來(lái)分隔塊（空行 通常 分隔文本塊，但代碼樣本中的空行卻不一定結(jié)束代碼樣本，并且文本塊不需要用空行來(lái)分隔）。由于需要以不同方式重新格式化每個(gè)文本塊以生成正確的 HTML 輸出，狀態(tài)機(jī)似乎就是自然的解決方案。

Txt2Html 閱讀器的一般功能如下：

•     在初始狀態(tài)中啟動(dòng)。
•     讀取一行輸入。
•     根據(jù)輸入和當(dāng)前狀態(tài)，轉(zhuǎn)移到新狀態(tài)或按適合當(dāng)前狀態(tài)的方式處理該行。

這個(gè)例子是關(guān)于您會(huì)遇到的最簡(jiǎn)單的情況，但它說(shuō)明了我們描述過(guò)的以下模式：
Python 中一個(gè)簡(jiǎn)單的狀態(tài)機(jī)輸入循環(huán)

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 下載從中取出該代碼的源文件（請(qǐng)參閱 參考資料 ）。請(qǐng)注意：變量 state 聲明為 global ，在函數(shù)（如 startText() ）中更改它的值。轉(zhuǎn)移條件，如 textln.match() ，是規(guī)則表達(dá)式模式，但它們可能也是定制函數(shù)。實(shí)際上，以后會(huì)在程序中執(zhí)行格式化。狀態(tài)機(jī)只將文本文件分析成 blocks 列表中帶標(biāo)簽的塊。

抽象狀態(tài)機(jī)類

在表單和函數(shù)中使用 Python 實(shí)現(xiàn)抽象狀態(tài)機(jī)很容易。這使程序的狀態(tài)機(jī)模型比前一個(gè)例子中的簡(jiǎn)單條件塊顯得更突出（初看，其中的條件與其它條件沒(méi)有什么不同）。而且，以下類及其關(guān)聯(lián)處理程序在隔離狀態(tài)中操作方面完成得很好。許多情況下，這改善了封裝和可讀性。
文件：statemachine.py

from
 
   string 
  import
 
   upper
  class 
   StateMachine
 
  :
 
  def 
   __init__
 
  (self):
 self.handlers = {}
 self.startState = None
 self.endStates = []
 
  def 
   add_state
 
  (self, name, handler, end_state=0):
 name = upper(name)
 self.handlers[name] = handler
 
  if
 
   end_state:
 self.endStates.append(name)
 
  def 
   set_start
 
  (self, name):
 self.startState = upper(name)
 
  def 
   run
 
  (self, cargo):
 
  try
 
  :
 handler = self.handlers[self.startState]
 
  except
 
  :
 
  raise
 
  "InitializationError", 
  "must call .set_start() before .run()"


 
   if 
 
  not
 
   self.endStates:
 
  raise
 
  "InitializationError", 
  "at least one state must be an end_state"

 
   while
 
   1:
 (newState, cargo) = handler(cargo)
 
  if
 
   upper(newState) 
  in
 
   self.endStates:
 
  break

 
   else
 
  :
 handler = self.handlers[upper(newState)]

要真正 使用StateMachine 類，需要為每個(gè)要使用的狀態(tài)創(chuàng)建一些處理程序。處理程序必須符合模式。它循環(huán)處理事件，直到要轉(zhuǎn)移到另一個(gè)狀態(tài)，此時(shí)處理程序應(yīng)該將一個(gè)字節(jié)組（它包括新狀態(tài)名稱以及新的狀態(tài)處理程序需要的任何 cargo）傳遞回去。

在 StateMachine 類中將 cargo 用作變量的做法將封裝狀態(tài)處理程序所需的數(shù)據(jù)（該狀態(tài)處理程序不必調(diào)用它的 cargo 變量）。狀態(tài)處理程序使用 cargo 來(lái)傳遞下一個(gè)處理程序所需的內(nèi)容，于是新的處理程序可以接管前一個(gè)處理程序的遺留工作。 cargo 通常包括文件句柄，它允許下一個(gè)處理程序可以在前一個(gè)處理程序停止后讀取更多數(shù)據(jù)。 cargo 還可能是數(shù)據(jù)庫(kù)連接、復(fù)雜的類實(shí)例或帶有幾個(gè)項(xiàng)的列表。

現(xiàn)在，讓我們研究測(cè)試樣本。在本例中（在以下代碼示例中概述），cargo 只是不斷將反饋傳送給迭代函數(shù)的一個(gè)數(shù)字。只要 val 處于某個(gè)范圍內(nèi)，則 val 的下一個(gè)值永遠(yuǎn)只是 math_func(val) 。一旦函數(shù)返回了超出范圍的值，那么該值將傳送到另一個(gè)處理程序，或者狀態(tài)機(jī)在調(diào)用了一個(gè)什么也不做的終態(tài)處理程序后就退出。示例說(shuō)明了一件事： 事件不必是輸入事件。它也可以是計(jì)算事件（這種情況很少）。狀態(tài)處理程序相互之間的區(qū)別只是在輸出它們處理的事件時(shí)使用不同的標(biāo)記。該函數(shù)比較簡(jiǎn)單，沒(méi)必要使用狀態(tài)機(jī)。但它很好地說(shuō)明了概念。代碼也許比解釋更易于理解！
文件：statemachine_test.py

from
 
   statemachine 
  import
 
   StateMachine
  def
   ones_counter
 
  (val):
 
  print
 
  "ONES State: ",
 
  while
 
   1:
 
  if
 
   val <= 0 
  or
 
   val >= 30:
 newState = 
  "Out_of_Range" ; 
  break
 elif
 
   20 <= val < 30:
 newState = 
  "TWENTIES"; 
  break
 elif
 
   10 <= val < 20:
 newState = 
  "TENS"; 
  break
 else
 
  :
 
  print
 
  " @ %2.1f+" % val,
 val = math_func(val)
 
  print
 
  " >>"

 
   return
 
   (newState, val)
  def 
   tens_counter
 
  (val):
 
  print
 
  "TENS State: ",
 
  while
 
   1:
 
  if
 
   val <= 0 
  or
 
   val >= 30:
 newState = 
  "Out_of_Range"; 
  break
 elif
 
   1 <= val < 10:
 newState = 
  "ONES"; 
  break
 elif
 
   20 <= val < 30:
 newState = 
  "TWENTIES"; 
  break
 else
 
  :
 
  print
 
  " #%2.1f+" % val,
 val = math_func(val)
 
  print
 
  " >>"

 
   return
 
   (newState, val)
  def 
   twenties_counter
 
  (val):
 
  print
 
  "TWENTIES State:",
 
  while
 
   1:
 
  if
 
   val <= 0 
  or
 
   val >= 30:
 newState = 
  "Out_of_Range"; 
  break
 elif
 
   1 <= val < 10:
 newState = 
  "ONES"; 
  break
 elif
 
   10 <= val < 20:
 newState = 
  "TENS"; 
  break
 else
 
  :
 
  print
 
  " *%2.1f+" % val,
 val = math_func(val)
 
  print
 
  " >>"

 
   return
 
   (newState, val)
  def 
   math_func
 
  (n):
 
  from
 
   math 
  import
 
   sin
 
  return
 
   abs(sin(n))*31
  if
 
   __name__== 
  "__main__":
 m = StateMachine()
 m.add_state(
  "ONES", ones_counter)
 m.add_state(
  "TENS", tens_counter)
 m.add_state(
  "TWENTIES", twenties_counter)
 m.add_state(
  "OUT_OF_RANGE", None, end_state=1)
 m.set_start(
  "ONES")
 m.run(1)

最新評(píng)論