Chinaunix首页 | 论坛 | 博客
  • 博客访问: 236118
  • 博文数量: 32
  • 博客积分: 424
  • 博客等级: 准尉
  • 技术积分: 465
  • 用 户 组: 普通用户
  • 注册时间: 2012-03-02 10:23
文章分类

全部博文(32)

文章存档

2012年(32)

分类: Python/Ruby

2012-03-21 13:47:22

返回文档首页 

描象语法树的数据结构

(Abstract Syntax Tree(AST) Data Structure)


()语法树实例

在介绍描象语法树数据结构这前先来看一小段代码,这段代码的功能是求1100的和:

代码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.找到整个语法树的根结点,上图中,根结点为L1L1是一个语句集合,在L1中总共包含三条语句。要执L1, 首先从第一条语句开始执行,完成以后,执行第二条语句,依次下去。子过程如下:

1.1  执行第一条语句S1S1是一条赋值语句:把0赋值给sum,第一条语句执行完成
1.2  执行第二条语句S2,同样也为赋值语句,把0赋值给i,第二符语句执行完成
1.3  执行第三条语句S3S3while循环语句,while语句是一条复合语句,由条件和语句体两部分组成,条件对应图中的结点C1,语句体对应图中结点L2,执行的子过程如下:
1.3.1  第一步判断条件C1是否成立:变量i是否小于100
1.3.2 如果结果为假,退出while循环。
1.3.3 如果结果为真,则执行while体中的语句L2,结点L2有两条语句,执行子过程如下
1.3.3.1  第一条语句(W1)为加并且赋值语句,sumi的和赋值给sum
1.3.3.2 第二条语句(W2)为加并且赋值语句,把i1的和赋值给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


阅读(4630) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~