6.10 构造抽象语法树
最后更新于：2022-04-01 01:10:38
yacc.py没有构造抽像语法树的特殊方法。不过，你可以自己很简单的构造出来。
一个最为简单的构造方法是为每个语法规则创建元组或者字典，并传递它们。有很多中可行的方案，下面是一个例子：
~~~
def p_expression_binop(p):
'''expression : expression PLUS expression
| expression MINUS expression
| expression TIMES expression
| expression DIVIDE expression'''
p[0] = ('binary-expression',p[2],p[1],p[3])
def p_expression_group(p):
'expression : LPAREN expression RPAREN'
p[0] = ('group-expression',p[2])
def p_expression_number(p):
'expression : NUMBER'
p[0] = ('number-expression',p[1])
~~~
另一种方法可以是为不同的抽象树节点创建一系列的数据结构，并赋值给p[0]：
~~~
class Expr: pass
class BinOp(Expr):
def __init__(self,left,op,right):
self.type = "binop"
self.left = left
self.right = right
self.op = op
class Number(Expr):
def __init__(self,value):
self.type = "number"
self.value = value
def p_expression_binop(p):
'''expression : expression PLUS expression
| expression MINUS expression
| expression TIMES expression
| expression DIVIDE expression'''
p[0] = BinOp(p[1],p[2],p[3])
def p_expression_group(p):
'expression : LPAREN expression RPAREN'
p[0] = p[2]
def p_expression_number(p):
'expression : NUMBER'
p[0] = Number(p[1])
~~~
这种方式的好处是在处理复杂语义时比较简单：类型检查、代码生成、以及其他针对树节点的功能。
为了简化树的遍历，可以创建一个通用的树节点结构，例如：
~~~
class Node:
def __init__(self,type,children=None,leaf=None):
self.type = type
if children:
self.children = children
else:
self.children = [ ]
self.leaf = leaf
def p_expression_binop(p):
'''expression : expression PLUS expression
| expression MINUS expression
| expression TIMES expression
| expression DIVIDE expression'''
p[0] = Node("binop", [p[1],p[3]], p[2])
~~~