《自己动手写 Python 虚拟机》_更理解虚拟机的意义_2.4.1 构建AST

【摘要】 本书摘自《自己动手写 Python 虚拟机》一书中第2章，第4节，海纳编著。

2.4.1 构建AST

在文法分析的过程中，如果不采取直接计算的方式，而是将每一个分析结果转化 成一个 AST 的内部节点，就可以在文法分析过程中构建 AST 了。

先来定义 AST 结点，代码如下：

class AddNode(object):

def __init_(self,left,right):

self.left =left

self.right =right

def visit(self):

lvalue =self.left.visit()

rvalue =self.right.visit()

self.value =lvalue +rvalue

return self.value

class MulNode(object):

def __init__(self,left,right):

self.left =left

self.right =right

def visit(self):

lvalue =self.left.visit()

rvalue =self.right.visit()

self.value =lvalue *rvalue

return self.value

class ConstNode(object):

def__init__(self,value):

在上面的例子中，只展示了加法结点 AddNode、代表乘法的结点 MulNode 和代 表整数的结点 ConstNode 。减法和除法结点与加法和乘法是相同的，就不再展示了， 请读者自行补充，

定义了这些结点以后，就可以在文法分析阶段，只生成 AST, 而不计算。计算的 过程可以保留到对树根结点调用visit 方法时才执行。

生成 AST 的代码如下：

1 def expr(tk):

2 s1 =term(tk)

3 toknum =current().toknum

4 tokvalue =current().tokvalue

5

6 value =s1

7

8 while tokvalue =="+"or tokvalue =="-"

9 next(tk)

10

11 s2 =term(tk)

12 if tokvalue =="+":

13 value =AddNode(value,s2)

14 elif tokvalue =="-":

15 value =SubNode(value,s2)

16 toknum =current().toknum

17 tokvalue =current().tokvalue

18

19 return value

20

21

22

23 def factor(tk):

24 if current().toknum ==tokenize.NUMBER:

25 value =current().tokvalue

26 next(tk)

27 return ConstNode(int(value))

28 elif current().tokvalue =="(":

29 next(tk)

30 f =expr(tk)

这里只展示了expr 函数和 factor 函数的修改，其他修改的地方略去了。考察 factor 函数，如果词法扫描时，遇到一个数字，就产生一个 ConstNode, 并且作为返回 值返回调用者，也就是返回到 term 函数中去。这意味着，term 调用 factor 的时候得 到的就是一个 AST 结点，而不像原来是一个具体的值。

在 expr 方法里，第一次调用 term 所得到的也是一个结点，或者说是一棵子树。 当遇到加号时，再次调用 term, 就可以得到另一棵子树，这两棵子树就可以形成一个 AddNode 结点。这样一来，调用 expr 方法对输入进行处理时，得到的结果就不再是 表达式具体的求值了，而是一棵抽象语法树。

抽象语法树求值

求值的过程是后序遍历这棵树。如果遇到运算符结点，就把它的两个子结点的 值取出来进行计算，并把运算结果存在这个运算符结点上。

只需要在抽象语法树上调用 visit 方法即可，代码如下：

此处采用典型的后序遍历来遍历这棵语法树。后序遍历，对于树中的任何一个 结点，在遍历完它的所有子树以后才会处理自身结点。显然，这是因为任何一个结点 的求值都依赖于它的子树的值，所以只能使用后序遍历来进行计算。执行这个程序， 就可以得到预期的值：635。

2.4.2 递归程序的本质

在发生程序调用的情况下，操作系统会为被调用的子程序开辟一块空间，用于存 储与这个程序执行相关的数据，例如函数的参数值、函数的局部变量、函数的返回地 址等。在一定意义上，这一块空间中的数据也遵循了“后进先出”的原则，因此，在计 算机系统中，也把这一块与被调用程序相应的数据存储区称为栈。

在常见的操作系统中，栈都是向下增长的。压栈的操作会使栈顶地址减小，出栈 的操作会使栈顶地址增大。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们 [email protected] 处理，核实后本网站将在24小时内删除侵权内容。