抽象语法树在属性计算中的应用.doc

 3 安庆师范学院学报 (自然科学版) J o urnal of Anqing Te a cher s Colle ge (Natural Science Edition) No v. 2008 Vol . 14 No . 4 2008 年 11 月 第 14 卷第 4 期 抽象语法树在属性计算中的应用 张玉州 ,王一宾 ,江克勤 ( 安庆师范学院 计算机与信息学院 , 安徽安庆 246133) 摘 要 : 属性是语义分析中非常重要的一个概念 ,因为它使得语法符号和结构有了意义 ,而这种意义最终将被计算 机接收 。属性计算是一个复杂的过程 ,原因在于属性间的依赖关系的紧密性以及存储结构的复杂性 。抽象语法树是语 法树的简化 ,是属性计算中很有效的一种存储结构 。本文首先阐述抽象语法树的意义 、结构及构造 ,然后对属性及相关 问题作了介绍 ,最后根据属性文法的种类 ,给出相应语法结构的属性计算算法 。 关键词 : 属性 ;抽象语法树 ;结点 ;综合属性 ;继承属性 中图分类号 : T P314 文献标识码 : A 文章编号 : 1007 - 4260 ( 2008) 04 - 0084 - 05 0 引言 语义分析是编译过程中很关键的一个阶段 ,因为在这个阶段 ,通过属性的设置 、计算 ,使得相应的文法符号 、语法结 构有了意义 ,翻译从这个阶段真正开始 。属性计算是在语言句子的翻译过程中 ,依据该语言属性文法的语义规则 ,对文 法符号的属性求值的过程 。属性计算通常是一个复杂的过程 ,主要是因为文法的规模大 、属性的数目多 、属性间的依赖 关系复杂等因素 ,从而导致在设计属性计算算法时 ,存储结构以及计算策略的选取就会相当困难 。 本文主要是介绍利用抽象语法树作为存储结构对属性进行计算 ,并给出了具体的属性计算算法 。 1 抽象语法树 1 . 1 抽象语法树的意义 语法树是语法结构的图形表示 ,使用语法树可以判定一个给定的单词符号串是否符合语言的语法规则 。语法树在 语义分析阶段 ,也是一种重要的数据结构 ,因为语义分析通常是语法制导的 ,即先对源程序代码进行语法分析 ,构造语法 树 ,而后依据语义规则 ,通过对语法树的遍历 ,进行属性计算 [ 1 ] 。 而在实际的属性计算过程中 ,为了简便起见 ,需要对语法树进行处理 ,去掉那些对语义分析不必要的信息 ,从而获得 更有效的数据结构 ,这种结构即为抽象语法树 ( A bst ract Syntax Tree) [ 1 ] 。采用抽象语法树作为存储结构 ,不但在存储上 节省了空间 ,而且对于算法的实现 ,也简便了许多 ,例如对于下文例 2 中的产生式 S - (L ) ,由于圆括号没有设置属性 , 故而在实际的存储中 ,没有给它们分配空间 ,这样 S 结点只有一棵子树 ,降低了算法的复杂性 。 1 . 2 抽象语法树的结构 以抽象语法树作为存储结构进行属性计算 ,树的结点中的信息大致由三部分组成 : ①结点所表示的符号名称 ,该名 称又称为结点的标号 ; ②标号的属性 ,一个标号可能有若干个属性值 ,这些属性可以存放在结点中 ,也可以存放在符号表 中 ,而将相应的地址存储在结点中 ; ③若干个指向其子结点的指针 。 显然抽象语法树中的一个结点可以由包含若干个成员的记录或结构体来实现 。 1 . 3 抽象语法树的构造 抽象语法树是在语法分析的过程中建立起来的 ,建立的过程要依赖于产生式所对应的语义规则 ,也就是为了构造抽 象语法树 ,首先要为文法配置属性和语义规则 ,这里的属性实际上是指向结点的指针 ,而语义规则则是在语法分析时 ,调 用产生式而引发的建树动作 ,主要体现为结点的建立 。建立结点通常是通过函数的调用来实现 ,例如 mkno de ( ) 函数可 以建立一个内部结点 ; mkleaf () 函数建立终端结点 ,即叶结点 。函数之间通过指针的传递来实现抽象语法树的构建 。 3收稿日期 : 2008 - 03 - 13 基金项目 : 安徽省教育厅自然科学研究项目 ( 2005 KJ 364zc) 资助 。 作者简介 : 张玉州 ,男 ,安徽无为人 ,安庆师范学院计算机与信息学院讲师 。 属性是在上下文无关文法的基础上 ,为文法的每个符号设置若干个具有一定含义的“值”,它代表相应符号的语 属性可以参与一定的操作 ,如计算和传递 。属性计算时 ,需要依据一定的计算规则 ,即语义规则 。配备了属性及语义 则的文法称为属性文法 。文法符号典型的属性有 : ①变量的数据类型 ; ②表达式的值 ; ③存储器中变量的位置 ; ④程序 目标代码 ; ⑤数的有效位数 [ 2 ] 。 2 . 2 属性的分类 属性通常可