Redy语法分析－－抽象语法树的数据结构

6592阅读　0评论2012-03-21　NosicLin
分类：Python/Ruby

返回文档首页 

描象语法树的数据结构

(Abstract Syntax Tree(AST) Data Structure)


(一)语法树实例

在介绍描象语法树数据结构这前先来看一小段代码，这段代码的功能是求1～100的和：

代码1.1

  1. sum=0
  2. i=0
  3. while i<100
  4.     sum+=i
  5.     i+=1
  6. 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

  1. ....
  2. tree_root=parser(soure_file) /*解析源代码，并构造与之等价的语法树*/
  3. tree_root.execute() /*执行语法树*/
  4.     ....

代码1.1相对应语法树的根结点为L1（上图），结点L1是一个集合类型，用于把其它的子语句顺序的组合在一起。要执行L1，只需要依次下面每一个子语句即可，代码为：

代码1.3

  1. L1.execute()
  2.     S1.execute() /*赋值语句sum=0*/
  3.     S2.execute() /*赋值语句i=0*/
  4.     S3.execute() /*while语句*/
  5. end

L1结点的类型为stmts_list，下面用更通用的代码来描述stmts_list执行过程：

代码1.4

  1. stmts_list.execute()
  2.     for node in stmts_list.substmts /*遍历每一个子语句*/
  3.         node.execute() /*执行子语句*/
  4.     endfor
  5. end

按照这种递归执行的方法依次为每一个不同类型的结点编写代码，代码描述该结点的执行方式。


(二)语法树分析

在上面的实例，为代码1.1构造相应语法树，该语法树总共由18个结点构成，这些结点总共分为7种不同类型，仔细观察，会发现：

  1. 不同类型的结点有不同执行方式。例如，

    1. stmts_list依次执行其包含的每一个子语句，

    2. stmt_assign则是把其右边结点执行后得到的结果，赋值给左边的变量。

  2. 每一个结点不用去知道其子结点的类型。例如在，stmts_list中他不知道，也不用去知道它所包含的每一个子结点类型，stmts_list可以包含赋值语句，while语句，也可以包含for语句，以及其它的一些语句。如果要运行子结点，它只需要调用其子结点的execute方法即可。


上面分析这么多，主要是为了说明，要构造语法树的数据结构，第一：需要抽出一个父类来描述所有不同类型结点的公有特征，方法，以及属性。并且该父类有一个虚方法，用于表示该结点的执行方式。每一个继承父类的结点都必须实现该方法。


(三)语法树的数据结构

在redy源码中，每一个语法树结点都继承了结构体ast_object，结构体的代码可以在src/syntax/ ast_object.h 中找到。


(1)结构体ast_object的定义：

代码1.5

  1. struct ast_object
  2. {
  3.         int a_type; /*结点类型*/
  4.         char* a_name; /*结点名称*/
  5.         struct list_head a_pending;
  6.         struct ast_object_ops* a_ops; /*虚方法，每一个子类都必须实现*/
  7. };
  8. typedef struct ast_object AstObject;

成员说明：

  1. a_type，表于该结点类型

  2. a_name，表示该结点类型的名称，属性a_name在结构体ast_object不是必需的，它存在的原因主要是因为从源码中构造语法树出错时，或都是执行语法树出错时，能更好的输出一些有用，更友好的一些错误信息，使程序更容易调试。

  3. a_pending，是一个链表(struct list_head采用linux内核中的代码)，当解析器从源码中构造语法树的过程中，临时性的把所有结点连接在一起。这样做是因为，redy采用yacc对其文法构造LALR(1)分析表，而LALR(1)是一种自底向上的方法。如果在语法分析过程发现源程序存在语法错误，分析动作就会停止。但是在发生错误前，已经构造出了相应的语法结点，但是还未形成一根完成的语法树，而如果遍历树中的每一个结点，必须是通过树根才能做到。这样就造成多个结点无法直接或都是间接的到达。造成永久性的内存遗漏。属性a_pending用于防止这种情况的发生，当构造语法构失败时，同样可以通过链表遍历到每一个结点。

  4. a_ops，虚方法，每一个子类都必须实现，具体如下


(2)结构体ast_object_ops的定义：

代码1.6

  1. struct ast_object_ops
  2. {
  3.         void (*ao_free_self(struct ast_object*);
  4.         void (*ao_free)(struct ast_object*);
  5.         int (*ao_execute)(struct ast_object*);
  6. };

成员说明：

  1. ao_free_self，用于在构造语法树失败时调用，该函数只释放结点自身，不能释放其子结点
  2. ao_free，用于销毁语法树时调用，该函数不仅需要释放结点自身，也同时要释放其子结点
  3. ao_execute，结点的执行方法。

 

返回文档首页 

附:  代码下载: git clone git://git.code.sf.net/p/redy/code redy-code


上一篇：Redy语法分析－－抽象语法树简介
下一篇：Redy语法分析－－文字常量结点