大學裏計算機科學最吸引我的地方就是編譯器。最神奇的是，編譯器是如何讀出我寫的那些爛代碼，並且還能生成那麽復雜的程序。當我終於選了壹門編譯方面的課程時，我發現這個過程比我想的要簡單得多。
在本系列的文章中，我會試著通過為壹種基本命令語言IMP寫壹個解釋器，來展示這種簡易性。因為IMP是壹個簡單廣為人知的語言，所以打算用 Python寫這個解釋器。Python代碼看起來很像偽代碼，所以即使妳不認識 Python，妳也能理解它。解析可以通過壹套從頭開始實現的解析器組合完成（在本系列的下壹篇文章中會有解釋）。除了sys（用於I/O）、re（用於解析正則表達式）以及unittest（用於確保壹切工作正常）庫，沒有使用其他額外的庫。
IMP 語言
在開始寫之前，我們先來討論壹下將要解釋的語言。IMP是擁有下面結構的最小命令語言：
賦值語句（所有變量都是全局的，而且只能存儲整數）：
Python
1
x := 1
條件語句：
Python
1
2
3
4
5
if x = 1 then
y := 2
else
y := 3
end
while循環：
Python
1
2
3
while x < 10 do
x := x + 1
end
復合語句（分號分隔）：
Python
1
2
x := 1;
y := 2
OK，所以它只是壹門工具語言，但妳可以很容易就把它擴展成比Lua或python更有用的語言。我希望能把這份教程能保持盡量簡單。
下面這個例子是計算階乘的程序：
Python
1
2
3
4
5
6
n := 5;
p := 1;
while n > 0 do
p := p * n;
n := n - 1
end
IMP沒有讀取輸入的方式，所以初始狀態必須是在程序最開始寫壹系列的賦值語句。也沒有打印結果的方式，所以解釋器必須在程序的結尾打印所有變量的值。
解釋器的結構
解釋器的核心是「中間表示」（Intermediate representation，IR）。這就是如何在內存中表示IMP程序。因為IMP是壹個很簡單的語言，中間表示將直接對應於語言的語法；每壹種表達和語句都有對應的類。在壹種更復雜的語言中，妳不僅需要壹個「語法表示」，還需要壹個更容易分析或運行的「語義表示」。
解釋器將會執行三個階段：
將源碼中的字符分割成標記符（token）
將標記符組織成壹棵抽象語法樹（AST）。抽象語法樹就是中間表示。
評估這棵抽象語法樹，並在最後打印這棵樹的狀態
將字符串分割成標記符的過程叫做「詞法分析」，通過壹個詞法分析器完成。關鍵字是很短，易於理解的字符串，包含程序中最基本的部分，如數字、標識符、關鍵字和操作符。詞法分析器會除去空格和註釋，因為它們都會被解釋器忽略。
將標記符組織成抽象語法樹（AST）的過程稱為「解析過程」。解析器將程序的結構提取成壹張我們可以評估的表格。
實際執行這個解析過的抽象語法樹的過程稱為評估。這實際上是這個解析器中最簡單的部分了。
本文會把重點放在詞法分析器上。我們將編寫壹個通用的詞匯庫，然後用它來為IMP創建壹個詞法分析器。下壹篇文章將會重點打造壹個語法分析器和評估計算器。
詞匯庫
詞法分析器的操作相當簡單。它是基於正則表達式的，所以如果妳不熟悉它們，妳可能需要讀壹些資料。簡單來說，正則表達式就是壹種能描述其他字符串的特殊的格式化的字符串。妳可以使用它們去匹配電話號碼或是郵箱地址，或者是像我們遇到在這種情況，不同類型的標記符。
詞法分析器的輸入可能只是壹個字符串。簡單起見，我們將整個輸入文件都讀到內存中。輸出是壹個標記符列表。每個標記符包括壹個值（它代表的字符串）和壹個標記（表示它是壹個什麽類型的標記符）。語法分析器會使用這兩個數據來決定如何構建壹棵抽象語法樹。
由於不論何種語言的詞法分析器，其操作都大同小異，我們將創建壹個通用的詞法分析器，包括壹個正則表達式列表和對應的標簽（tag）。對每壹個表達式，它都會檢查是否和當前位置的輸入文本匹配。如果匹配，匹配文本就會作為壹個標記符被提取出來，並且被加上該正則表達式的標簽。如果該正則表達式沒有標簽，那麽這段文本將會被丟棄。這樣免得我們被諸如註釋和空格之類的垃圾字符幹擾。如果沒有匹配的正則表達式，程序就要報錯並終止。這個過程會不斷循環直到沒有字符可匹配。
下面是壹段來自詞匯庫的代碼：
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import sys
import re
def lex(characters, token_exprs):
pos = 0
tokens = []
while pos < len(characters):
match = None
for token_expr in token_exprs:
pattern, tag = token_expr
regex = re.compile(pattern)
match = regex.match(characters, pos)
if match:
text = match.group(0)
if tag:
token = (text, tag)
tokens.append(token)
break
if not match:
sys.stderr.write('Illegal character: %sn' % characters[pos])
sys.exit(1)
else:
pos = match.end(0)
return tokens
註意，我們遍歷正則表達式的順序很重要。lex會遍歷所有的表達式，然後接受第壹個匹配成功的表達式。這也就意味著，當使用詞法分析器時，我們應當首先考慮最具體的表達式（像那些匹配算子（matching operator）和關鍵詞），其次才是比較壹般的表達式（像標識符和數字）。
詞法分析器
給定上面的lex函數，為IMP定義壹個詞法分析器就非常簡單了。首先我們要做的就是為標記符定義壹系列的標簽。IMP只需要三個標簽。RESERVED表示壹個保留字或操作符。INT表示壹個文字整數。ID代表標識符。
Python
1
2
3
4
5
import lexer
RESERVED = 'RESERVED'
INT?= 'INT'
ID? = 'ID'
接下來定義詞法分析器將會用到的標記符表達式。前兩個表達式匹配空格和註釋。它們沒有標簽，所以 lex 會丟棄它們匹配到的所有字符。
Python
1
2
3
token_exprs = [
(r'[ nt]+',?None),
(r'#[^n]*',? None),
然後，只剩下所有的操作符和保留字了。記住，每個正則表達式前面的“r”表示這個字符串是“raw”；Python不會處理任何轉義字符。這使我們可以在字符串中包含進反斜線，正則表達式正是利用這壹點來轉義操作符比如“＋”和“＊”。
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
(r':=',? RESERVED),
(r'(',RESERVED),
(r')',RESERVED),
(r';', RESERVED),
(r'+',RESERVED),
(r'-', RESERVED),
(r'*',RESERVED),
(r'/', RESERVED),
(r'<=',RESERVED),
(r'<', RESERVED),
(r'>=',RESERVED),
(r'>', RESERVED),
(r'=', RESERVED),
(r'!=',RESERVED),
(r'and',? RESERVED),
(r'or',RESERVED),
(r'not',? RESERVED),
(r'if',RESERVED),
(r'then',?RESERVED),
(r'else',?RESERVED),
(r'while', RESERVED),
(r'do',RESERVED),
(r'end',? RESERVED),
最後，輪到整數和標識符的表達式。要註意的是，標識符的正則表達式會匹配上面的所有的保留字，所以它壹定要留到最後。
Python
1
2
3
(r'[0-9]+',INT),
(r'[A-Za-z][A-Za-z0-9_]*', ID),
]
既然正則表達式已經定義好了，我們還需要創建壹個實際的lexer函數。
Python
1
2
def imp_lex(characters):
return lexer.lex(characters, token_exprs)
如果妳對這部分感興趣，這裏有壹些驅動代碼可以測試輸出：
Python
1
2
3
4
5
6
7
8
9
10
11
import sys
from imp_lexer import *
if __name__ == '__main__':
filename = sys.argv[1]
file = open(filename)
characters = file.read()
file.close()
tokens = imp_lex(characters)
for token in tokens:
print token
繼續……
在本系列的下壹篇文章中，我會討論解析器組合，然後描述如何使用他們從lexer中生成的標記符列表建立抽象語法樹。
如果妳對於實現IMP解釋器很感興趣，妳可以從這裏下載全部的源碼。
在源碼包含的示例文件中運行解釋器：
Python
1
python imp.py hello.imp
運行單元測試：
Python
1
python test.py