用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:
3. name instruction description
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.
14. 2. Some specification:
16. (1) Input variables are represented as:
17. x1, x2, x3, ...
19. (2) Local variables are represented as:
20. z1, z2, z3, ...
22. (3) Output variable is represented as:
23. y
25. note: the num 1 is often omitted(i.e., x stands for x1 and z stands
26. for z1).
28. 3. Labeled instructions:
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,
33. [B] Z = Z - l
35. 4. A smaple program:
37. "Program to compute y = x1+ x2"
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
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']]