用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']]  
  • 1
  • 2
  • 下一页

相关内容