6.10 构造抽象语法树

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])