原文地址: http://blog.chinaunix.net/uid-26750235-id-3142172.html
描象语法树的数据结构
(Abstract Syntax Tree(AST) Data Structure)
(一)语法树实例
在介绍描象语法树数据结构这前先来看一小段代码，这段代码的功能是求1～100的和：
代码1.1
sum=0 i=0 while i<100 sum+=i i+=1 end
代码1.1只有6行，两条赋值语句与一条while循环语句，根据代码1.1来绘制其相应语法树，可以得到下面一张图片
这张图片完整的展现了代码1.1的语法结构，最顶端是语法树的根结点，从根结点到下面，有3个分支，也是意为着源文件有三条语句，前两条为赋值语句，第三条为while循环语句，在第三条语句下面，有两条分支，展现出while语句的结构，左边为执行while中语句所需要的条件，右边为while语句体。如果想要根据整个语法树来运行源代码，只需要这么做：
1.找到整个语法树的根结点，上图中，根结点为L1，L1是一个语句集合，在L1中总共包含三条语句。要执L1， 首先从第一条语句开始执行，完成以后，执行第二条语句，依次下去。子过程如下：
1.1 执行第一条语句S1，S1是一条赋值语句：把0赋值给sum，第一条语句执行完成 1.2 执行第二条语句S2，同样也为赋值语句，把0赋值给i，第二符语句执行完成 1.3 执行第三条语句S3，S3为while循环语句，while语句是一条复合语句，由条件和语句体两部分组成，条件对应图中的结点C1，语句体对应图中结点L2，执行的子过程如下： 1.3.1 第一步判断条件C1是否成立：变量i是否小于100 1.3.2 如果结果为假，退出while循环。 1.3.3 如果结果为真，则执行while体中的语句L2，结点L2有两条语句，执行子过程如下 1.3.3.1 第一条语句(W1)为加并且赋值语句，把sum与i的和赋值给sum 1.3.3.2 第二条语句(W2)为加并且赋值语句，把i与1的和赋值给i 1.3.4 跳转到步骤1.3.1 2.整个语法树执行完成。
解析器解析源代码，并构造与之等价的语法树。在得到语法树后，可以通过执行语法树，来完成源代码所需要完成的功能。在上面的实例中，构造了代码1.1相对应的语法树，并且描述了执行该语法树的步骤。这些步骤可以看做是递归执行的过程，例如用代码来描述为：
代码1.2
.... tree_root=parser(soure_file) /*解析源代码，并构造与之等价的语法树*/ tree_root.execute() /*执行语法树*/ ....
代码1.1相对应语法树的根结点为L1（上图），结点L1是一个集合类型，用于把其它的子语句顺序的组合在一起。要执行L1，只需要依次下面每一个子语句即可，代码为：
代码1.3
L1.execute() S1.execute() /*赋值语句sum=0*/ S2.execute() /*赋值语句i=0*/ S3.execute() /*while语句*/ end
L1结点的类型为stmts_list，下面用更通用的代码来描述stmts_list执行过程：
代码1.4
stmts_list.execute() for node in stmts_list.substmts /*遍历每一个子语句*/ node.execute() /*执行子语句*/ endfor end
按照这种递归执行的方法依次为每一个不同类型的结点编写代码，代码描述该结点的执行方式。
(二)语法树分析
在上面的实例，为代码1.1构造相应语法树，该语法树总共由18个结点构成，这些结点总共分为7种不同类型，仔细观察，会发现：
不同类型的结点有不同执行方式。例如，
stmts_list依次执行其包含的每一个子语句，
stmt_assign则是把其右边结点执行后得到的结果，赋值给左边的变量。
每一个结点不用去知道其子结点的类型。例如在，stmts_list中他不知道，也不用去知道它所包含的每一个子结点类型，stmts_list可以包含赋值语句，while语句，也可以包含for语句，以及其它的一些语句。如果要运行子结点，它只需要调用其子结点的execute方法即可。
上面分析这么多，主要是为了说明，要构造语法树的数据结构，第一：需要抽出一个父类来描述所有不同类型结点的公有特征，方法，以及属性。并且该父类有一个虚方法，用于表示该结点的执行方式。每一个继承父类的结点都必须实现该方法。
(三)语法树的数据结构
在redy源码中，每一个语法树结点都继承了结构体ast_object，结构体的代码可以在src/syntax/ ast_object.h 中找到。
(1)结构体ast_object的定义：
代码1.5
struct ast_object { int a_type; /*结点类型*/ char* a_name; /*结点名称*/ struct list_head a_pending; struct ast_object_ops* a_ops; /*虚方法，每一个子类都必须实现*/ }; typedef struct ast_object AstObject;
成员说明：
a_type，表于该结点类型
a_name，表示该结点类型的名称，属性a_name在结构体ast_object不是必需的，它存在的原因主要是因为从源码中构造语法树出错时，或都是执行语法树出错时，能更好的输出一些有用，更友好的一些错误信息，使程序更容易调试。
a_pending，是一个链表(struct list_head采用linux内核中的代码)，当解析器从源码中构造语法树的过程中，临时性的把所有结点连接在一起。这样做是因为，redy采用yacc对其文法构造LALR(1)分析表，而LALR(1)是一种自底向上的方法。如果在语法分析过程发现源程序存在语法错误，分析动作就会停止。但是在发生错误前，已经构造出了相应的语法结点，但是还未形成一根完成的语法树，而如果遍历树中的每一个结点，必须是通过树根才能做到。这样就造成多个结点无法直接或都是间接的到达。造成永久性的内存遗漏。属性a_pending用于防止这种情况的发生，当构造语法构失败时，同样可以通过链表遍历到每一个结点。
a_ops，虚方法，每一个子类都必须实现，具体如下
(2)结构体ast_object_ops的定义：
代码1.6
struct ast_object_ops { void (*ao_free_self(struct ast_object*); void (*ao_free)(struct ast_object*); int (*ao_execute)(struct ast_object*); };
成员说明：
ao_free_self，用于在构造语法树失败时调用，该函数只释放结点自身，不能释放其子结点 ao_free，用于销毁语法树时调用，该函数不仅需要释放结点自身，也同时要释放其子结点 ao_execute，结点的执行方法。
返回文档首页
附: 代码下载: git clone git://git.code.sf.net/p/redy/code redy-code
