用Python寫語言的解釋器

花了一下午的時間完成了一個簡單語言的解釋器，我會在最後帖出所有代碼，但是今天不打算詳細解釋程序的每一個步驟，最近考慮找實習、做論文，要花一些時間。有時間了我會解釋每一部分，在這裡只提醒一下讀者，程序的寫作過程和它呈現出來的不一樣，總體來說我的寫作過程是先寫一個只包含一條指令的解釋器，然後逐漸加入其他指令。ps：我是多麼的想看看高手們寫程序的過程，而不只是結果，但是就像graham說的“寫的過程往往顯得冗長”，所以這方面的書籍不多。我覺得比較接近的書包括《clean code》、《paip》、《software tools》。只可惜現在只看完了一本半。

想法的來源

昨天聖誕節，坐在不能上網的實驗室，覺得好無聊。然後想起了學習《可計算性與計算復雜性》的時候，裡面用到了一種含有5條指令的原語言，老師也要求我們用這個語言寫程序，所以我就想寫一個解釋器，來執行用該語言，並把這個解釋器作為自己的聖誕禮物。

原語言描述

書中說它是一個fortran式的簡單語言，所以我就給它起了個簡單的名字Metafor，表示meta fortran。下面來看一下它的具體描述，然後貼上我在代碼裡更詳細的描述，我為每一種指令都起了個名字（注意其中把賦值語句命名為setf是由於我最近在寫common lisp多一些）。

+-------------------------------------------------------------------------------------------+

指令                         描述
x = x + 1                   變量x的值加1
x = x - 1                    變元x的值減1。若x的值為0，則結果仍為0
TO A IF x≠0             若x≠0，則轉標號為A的指令；否則執行下一條指令
TO A                        無條件轉到標號為A的指令
y=x                           把x的值賦給變元y，x值保持不變

+-------------------------------------------------------------------------------------------+

1. 1. Metafor has five instructions:  
2.   
3. name instruction description  
4.   
5. inc: x = x + 1, Increase by 1 the value of the variable x.  
6. dec: x = x - 1, If the value of x is 0, leave it unchanged; otherwise  
7.                 decrease by 1 the value of x.  
8. con_goto: TO A IF x != 0, If the value of x is nonzero, perform the instruction  
9.                           with the label A next; otherwise proceed to the next  
10.                           instruction in the list.  
11. goto: TO A, Perform the instruction with the label A next.  
12. setf: y = x, Change the value variable y to the value of variable x.  
13.   
14. 2. Some specification:  
15.   
16. (1) Input variables are represented as:  
17. x1, x2, x3, ...  
18.   
19. (2) Local variables are represented as:  
20. z1, z2, z3, ...  
21.   
22. (3) Output variable is represented as:  
23. y  
24.   
25. note: the num 1 is often omitted(i.e., x stands for x1 and z stands  
26. for z1).  
27.   
28. 3. Labeled instructions:  
29.   
30. Instructions may or may not have labels. When an instruction is labeled,  
31. the label is written to its left in square brackets. For example,  
32.   
33. [B] Z = Z - l  
34.   
35. 4. A smaple program:  
36.   
37. "Program to compute y = x1+ x2"  
38.   
39.     y = x1  
40. [B] TO A IF x2 != 0  
41.     TO E  
42. [A] x2 = x2 - 1  
43.     y = y + 1  
44.     TO B  
45.   
46. 4. For more information, please refer to 《可計算性與計算復雜性》,  
47. 周長林、李占山著.  

整體思路

由於該語言中含有goto語句，所以我不能一句一句的解釋執行，我需要把整個程序讀進來，轉換成一種方面的內部格式後，作為整體執行。例如，這是計算y = x + x2的語言程序：

1. y = x  
2. TO A IF x2 != 0  
3. TO E  
4. x2 = x2 - 1  
5. y = y + 1  
6. TO B  

它轉換為內部格式後，為：

1. [['setf', 'y', 'x'],  
2.  ['labeled_exp', 'B', ['con_goto', 'A', 'x2']],  
3.  ['goto', 'E'],  
4.  ['labeled_exp', 'A', ['dec', 'x2']],  
5.  ['inc', 'y'],  
6.  ['goto', 'B']]