來自詞法分析的啟發——使用狀態機改寫控制結構

我發現了一個秘密想要告訴大家：「在程序的世界裡，存在一類控制結構可以被巧妙的數據結構和計算替代！」

用map改寫條件語句的技巧你一定很熟悉，map中的鍵值對分別存儲條件和動作，當某個條件被匹配的時候就取出與此對應的動作執行之。比如下面這個分離奇數偶數的函數里的條件語句完全可以被map替換掉。

def partition(numbers): """a group of numbers -> evens, odds""" evens = [] odds = [] for n in numbers: if n & 1 == 0: evens.append(n) else: odds.append(n) return evens, odds

替換後

def partition(numbers): """a group of numbers -> evens, odds""" map = {0: [], 1: []} for n in numbers: map[n & 1].append(n) return map[0], map[1]

用map改寫後的函數行數變短而且變數數目減少（非英語母語的程序員遇到的最大的編程困難是難以找出地道的單詞作為貼切的變數名）。

這是一個使用數據結構改寫分支語句的例子，下面再展示一個使用計算改寫循環的例子——在一個循環里對二維數組賦值。

int m = 6;int n = 8;int array[m][n];for (int i = 0; i < m * n; ++i) { array[i / n][i % n] = i;}

計算二維數組的下標使用了除法和取模，如果在意效率，當n = 2^k時，可用位運算array[i >> k][i & (n-1)]加速計算過程。

以上兩個例子中，控制語句的結構和邏輯都是最簡單的，改寫後的代碼僅僅減少了行數，下面看一個複雜的例子——檢查C語言的注釋。

方法一

def is_comment_v1(comment): length = len(comment) i = 0 try: if comment[i] == /: i += 1 if comment[i] == *: i += 1 done = False while not done: while comment[i] != *: i += 1 i += 1 while comment[i] == *: i += 1 if comment[i] == /: i += 1 done = True else: i += 1 if i == length: return True else: return False else: return False else: return False except IndexError: return False

如果沒有狀態機那副圖作為參照，這段代碼相當難以理解。但是仔細對照圖和代碼，我們可以得到一些啟發：循環和條件語句似乎和圖裡的環和分支存在某種聯繫。代碼中的三個while對應圖裡的三個環。如果把循環體看作條件語句的if部分，把緊隨著循環結束的語句看作條件語句的else部分（或elif部分），那麼這些分支和圖裡的分支是對應的。這更加啟發我們當面對複雜的控制邏輯時，可以藉助有限狀態機進行分析。

方法二和方法三

這兩個方法的思路是一樣的，使用一個變數維護當前的狀態，使用一個兩層的分支語句表示狀態更迭，區別在於哪一層在外哪一層在內。

方法二中外層switch(state)，內層switch(input)

def is_comment_v2(comment): state = i = 0 while i < len(comment) and state in (0, 1, 2, 3): if state == 0: if comment[i] == /: state = 1 else: state = error elif state == 1: if comment[i] == *: state = 2 else: state = error elif state == 2: if comment[i] == *: state = 3 else: state = 2 elif state == 3: if comment[i] == /: state = accept elif comment[i] == *: state = 3 else: state = 2 i += 1 if state == accept and i == len(comment): return True else: return False

方法三中外層switch(input)內層switch(state)

def is_comment_v3(comment): state = i = 0 while i < len(comment) and state in (0, 1, 2, 3): if comment[i] == /: if state == 0: state = 1 elif state == 3: state = accept else: state = error elif comment[i] == *: if state == 1: state = 2 elif state in (2, 3): state = 3 else: state = error else: if state in (2, 3): state = 2 else: state = error i += 1 if state == accept and i == len(comment): return True else: return False

方法二和方法三的代碼已經非常清晰了,只要完全停不下來就進行狀態的更迭，新狀態由當前狀態和輸入（激勵）確定，即newstat = T(state, c)，這暗示了「查表」。

方法四

在前三種方法中，如果需要調整有限狀態機，則不止一處代碼需要改動，於是人們想到了把控制邏輯編碼到數據結構里，需要改動的時候只需改動狀態機的定義，也叫做表驅動法。

def is_comment_v4(comment): states = [ {/: 1, *: error, other: error}, {/: error, *: 2, other: error}, {/: error, *: 3, other: 2}, {/: accept, *: 3, other: 2} ] state = i = 0 while i < len(comment) and state in (0, 1, 2, 3): c = comment[i] if c not in (/, *): c = other state = states[state][c] i += 1 if state == accept and i == len(comment): return True else: return False

在上面的代碼中，states的索引作為當前狀態，字典中的鍵作為輸入（激勵），字典的值作為新狀態，state = states[i][c]相當於上面提過的狀態轉移函數newstate = T(state, c)。方法四並非絕對比方法二和方法三好，因為方法四的狀態轉移表的維數是狀態數目×字符集種類數目，它是一個稀疏矩陣，而且這個稀疏矩陣難以使用臨接表表示，因為states[i][c]的狀態空間是狀態和輸入（激勵）的笛卡爾積。

詞法分析僅僅是「用狀態機改寫控制結構」的一個應用，這種思想當然可以用到別處，比如化簡多個邏輯判斷流程到最簡形式，這道題目中有人從德摩根定律、卡諾圖的角度（數電里學的，還記得嗎?）給出了方案，其實也可以藉助狀態機的思想進行分析。

if a > m: if b != n: x = 1 else: x = 0else: x = 1

條件作為激勵，變數賦值作為狀態，畫出圖來就是

if a > m and b == n: x = 0else: x = 1

?
推薦閱讀：