SUIF 抽象语法树

SUIF抽象语法树

1.概述

本次实验中实验三的目标是通过解析语法分析的输出文件来生成中间代码。至于中间代码的形式，我们要求采用抽象语法树。抽象语法树的结构则是借鉴SUIF的中间表示。

2.SUIF编译系统中间表示

总体上来说，SUIF中间表示由三部分组成：抽象语法树(AST)、符号表、和指令表达式。

2.1.SUIF的层级结构

SUIF中间表示组织成4级层次结构，包括：文件级，过程级，高级结构控制级和指令表达式树级。SUIF中间表示的主要部分是一个混合式的抽象语法树(AST)。从层次结构上来看，包括高级结构控制级和指令表达式树级，即除了传统的指令级别的操作，它还包含三个高级的结构：循环，条件声明和数组访问。循环和条件表示类似于抽象语法树，但却是语言无关的。图2-1展示了SUIF中间表示的层级结构：

图2-1：SUIF中间表示的层次结构

2.2.SUIF的符号表示

SUIF的符号表分为global symbal table，file symbal table，proc symbal table和block symbal table这4种。它们也是高到低，逐级的贯穿在了SUIF中间表示前3个层级中。图

2-2则表明了这个层次结构：

图2-2：SUIF的符号表示

2.3.SUIF的面向对象实现

SUIF系统的内核提供了一个面向对象的SUIF中间表示的实现。SUIF库对每个程序表示元素定义了一个C++类，允许我们对隐藏了细节的数据结构提供接口。在这个系统中，各个类之间存在若干相互联系和共享的属性，这由类的继承和动态邦定功能实现。例如：变量、标号和过程都是符号，他们共享相同的符号接口，但过程除了符号还有函数体。除了基本的SUIF数据结构，SUIF的内核中还定义了很多基本的数据结构，包括哈希表，可扩展数组等。对每个类来说，经常需要用到的函数都被定义为成员函数。图2-3给出了主要的SUIF数据

结构的类层次，所有的类都从suif_object基类继承。

图2-3： SUIF结构的类继承

类tree_node及其子类定义了抽象语法树(AST)数据结构。抽象语法树中定义了很多节点，对应于源程序中的控制流和操作。叶子节点全部是指令节点(tree_instr)，每个指令节点可以是一条单独的指令，也可以是一个表达式树。instruction类中定义了SUIF中间表示的指令系统，它作为抽象语法树的叶子节点，和tree_node的子类tree_instr紧密相连。

2.4.SUIF的抽象语法树(AST)

在图2-1 关于SUIF的层次结构表示中，从tree_proc节点以下显示了SUIF的抽象语法树的总体结构。

2.4.1.树节点

不同类型的AST节点用从tree_node类继承的对象表示。最简单的tree节点类型是tree_instr。每个这样的节点都是叶子节点，包含一条简单的指令或者是表达式树；条件结构

用tree_if节点表示；AST包括两种不同类型的循环节点：tree_for节点和tree_loop节点，分别对应不同的循环结构；嵌套的作用域用tree_block节点来表示。tree_block包含一系列的树节点和一个符号表。符号表中的符号和类型只能在这个block内部引用。AST的根节点是一个称作tree_proc的特殊的tree_block节点。tree_proc对象使用一个稍微不同的符号表并且包含几个额外的方法，其余的则是从tree_block继承而来。在每个过程体里面，树节点和指令都被分配了一个单独ID号。在SUIF中间表示内部或者是输出的注释中，这些号码可以用来辨别节点和指令。但是，通常我们要避免给tree_instr节点分配ID号，因为tree_instr

节点并不写入输出文件之中，并且在表达式树和指令序列之间转换的时候，它自动的完成节点顺序的重排，所以分配ID号实际上已经没有什么意义。

1)指令节点

指令节点，是抽象语法树的叶子节点，由类tree_instr实现。每个指令节点包含一条单独的指令或者是表达式树。和其它节点不同的是，指令节点被看作是临时对象。当SUIF在表达式树和指令序列(也就是high-level SUIF和low-level SUIF)之间转换的时候，SUIF库会根据需要对指令节点进行创建和删除。

2)if节点

由类tree_if实现的if节点，表示“if-then-else”结构。tree_if包括三个树节点链表(tree node list)：test part，then part和else part。test part表示计算if条件并且跳转到jumpto标号的代码，如果条件为假，这个标号的隐含值就是else part的开头。否则，就跳转到then part。

3)loop节点

tree_loop节点表示“do-while”循环。它包含两个节点链表，一个是body，一个是test part。body链表在前，表示循环体。test part链表表示计算”while”表达式和有条件的回转到循环体开始处的代码。

4)for 节点

tree_for节点的index变量用来保存索引值，index变量必须是一个定义在tree_for节点范围内的变量，它不能在循环体内的任何地方被修改。如果循环体包含一个调用其它函数的语句，而且这个被调用的函数修改了index变量，那么这个循环就不能用tree_for节点来表示。index变量的取值范围由三个操作数域指定：lower bounds、upper bounds和step。index 变量首先被初始化为lower bounds的值，然后以step的值递增，直到它达到upper bound的值得大小。tree_for节点还必须指定用于决定index变量何时到达upper bound的比较操作符。可能出现的比较操作符在枚举类型的变量tree_for_test里面指定。for结构的循环体保存在

body中，body是一个树节点链表。

5)block节点

tree_block节点引入了一个新的作用域。嵌套的作用域对于保留源程序中某作用域内特有的信息以及用作调试目的都很有用处。它们也可以避免代码移植过程中的名字冲突问题。

2.4.2.抽象语法树的一个实例

以上介绍了抽象语法树的节点类型和结构，下面给出一个C源程序，并图示这个C程序生成的抽象语法树。下面用方框框起来的是C源程序：

生成的抽象语法树如图2-3所示。可以看到，这个抽象语法树主要由两部分组成：一个指令节点和一个if节点，指令节点采用表达式树的方式表示。

图2-3：SUIF抽象语法树的一个实例

2.5.S UIF的指令系统

在用类tree_instr表示的抽象语法树的叶子节点中，含有SUIF指令。每条指令完成一个单独的操作。除了个别情况以外，操作码都是非常简单直接的，类似于RISC处理器的指令集。指令系统包括算术，数据移动和控制流等操作。

1)表达式树(expression trees)

SUIF指令中的大部分的高级遍历使用表达式树(expression trees)，几条指令被分成一组，对应于源程序中的一个表达式，这几条指令共有一个tree_instr作为父节点。我们针对几条C 语句，给出它的表达式树。C语句：

1:x=0;

2:y=*ptr;

3:if(y

4:*ptr=x;

5:}

对应的表达式树：

1:ldc (i.32) x=0

2:lod (i.32) y=ptr

3:bfalse e1，L：L1

4:e1:sl (i.32) y， e2

5:e2:add (i.32) x， z

6:str ptr=x

7:lab L:L1

一行一行解释：第一行ldc是常数加载指令，将0加载到x变量，i.32表示加载的是32位的整型数。下来lod是加载ptr所指内存地址中的内容到变量y。下来bfalse这一句，e1是指针，指向另外的表达式，L：L1表示标号，整体的意思就是当e1表达式的值为假的时候，就跳到标号名为L1的标号处。再下来e1：后面的内容则是表达式e1的定义，sl是<小于指令，如果y比e2小，那么e1结果为真。下来的e2：后面则是e2的内容，add不用多说，是加法指令，x和z相加，结果返回给e2。然后是str，将x的内容存储到ptr所指的内存地址中。然后是标号设置指令lab，将此处设置为标号L1所指的地方。

2)指令格式和操作码

每一个操作码都和特定的指令格式相对应。操作码的内部名字都用io开头。

A.指令格式

SUIF指令系统包含8种指令格式，大部分的SUIF指令属于3操作数指令。SUIF中，通过枚举变量inst_format来表示指令格式：

enum inst_format {

inf_none,

inf_rrr,

inf_bj,

inf_ldc,

inf_cal,

inf_array,

inf_mbr,

inf_lab,

inf_gen

};

表2-2-1显示了各种指令格式的特点和属性：

表2-2-1： SUIF指令格式

指令格式类表示格式描述

inf_rrr in_rrr 三操作数指令。有两个源操作数域，但并不是所有的操作数都必须使

用。例如：nop指令没有任何操作数。

inf_bj in_bj 分支和跳转指令。此类指令包含一个标号符号，指向跳转的目标；有

一个可选的源操作数，用来表示分支和跳转的条件。标号必须定义在

分支或跳转可见的作用域内，而且必须在同一个过程体中。

inf_ldc in_ldc 常数载入指令。SUIF使用单独的ldc指令来载入常量，而不允许常量

值直接作为操作数来实现。

inf_cal in_cal 调用指令。SUIF使用一个特别的cal指令来表示过程调用。这个高级

表示隐含了各种各样的链接细节。一个调用指令包含一个源操作数，

是一个指向被调用过程的指针。

inf_array in_array 数组指令。

inf_mbr in_mbr 多路分支指令

inf_lab in_lab 标号指令

inf_gen in_gen 通用指令

B.操作码

下面是SUIF中定义的所有的操作码：

表2-2-2：SUIF指令的操作码集合

指令名称操作数个数指令格式指令描述

nop 0 inf_rrr 空操作。

lod 2 inf_rrr 单指针载入操作。dst=*src1，src1必须是一个指针。str 2 inf_rrr 单指针逆载入操作。*src1=src2，src1操作数必须是

一个指针。

memcpy 2 inf_rrr 内存到内存的拷贝。*src1=*src2。

cpy 2 inf_rrr 拷贝操作。dst=src1，src1和dst类型必须一致。

cvt 2 inf_rrr 类型转化操作。dst=(dst)src1，struct, union,array或

者是void数据类型不能被转换。

neg 2 inf_rrr 取负操作。dst= -src1。

add 3 inf_rrr 加操作。dst=src1+src2。

sub 3 inf_rrr 减操作。dst=src1-src2。

mul div 3 inf_rrr

乘/除操作。dst=src1*src2，dst=src1/src2。

rem mod 3 inf_rrr

求余和取整操作。

not 2 inf_rrr 按位取反操作。dst= ~src1。

and ior ror 3 inf_rrr

按位与(或、异或)操作。dst=src1&src2，dst=src1|src2，

dst=src1^src2。

asr lsr lsl 3 inf_rrr

移位操作。dst=src1<>src2。src2

操作数变量必须是无符号整型。

asr：符号扩展移位，src1：有符号的整型。

lsr：符号无扩展移位，src1：无符号整型。

lsl：左移操作。

divfloor divceil 3 inf_rrr

除法和取下界及取上界运算的结合。

divfloor：取除法商的下界(整数)。

divceil：取除法商的上界(整数)。

min max 3 inf_rrr

最大值和最小值操作。dst=a>b?a:b，dst=a>b?b:a

abs 2 inf_rrr 绝对值操作

rot 3 inf_rrr 循环移位操作。

左移或右移src1操作数中的值，由src2指定左移或

者右移的位数。src2操作数中的变量必须是一个有

符号的整型。如果src2是个正值，则循环左移；如

果是负值，则循环右移。

seq sne sl sle 3 inf_rrr

比较指令。dst=(src1=src2)?1:0，dst=(src1!=src2)?1:0，

dst=(src1

ret 1 inf_rrr 返回指令。

mrk 0 inf_rrr 伪指令。指出源程序中语句或者符号的位置，用来

说明例如行号等的多种注释信息。它在功能上等价

于nop指令。

jmp 0 inf_bj 无条件跳转。

btrue 2 inf_bj 条件跳转指令。src1：条件，src2：标号

若条件为真，控制流跳转到目的标号。

bfalse 2 inf_bj 条件跳转指令。src1：条件，src2：标号

若条件为假，控制流跳转到目的标号。

ldc 1 inf_ldc 常量载入指令。ldc指令支持3种常量值：

符号地址(指针)；整数；浮点值。

cal 1 inf_cal 过程调用指令。

array 1 inf_array 数组指令。专门针对Fortran语言

mbr 1 inf_mbr 多路分支指令。表示Fortran语言中的goto语句和

C语言中的switch语句。

lab 1 inf_lab 标号指令。指定标号的位置。

gen 1、2 inf_gen 通用指令。用于SUIF指令的扩展。

注：src1和src2表示源操作数，dst表示目的操作数。这些指令中，本文算法中所用到的指

令主要有in_ldc类的ldc，in_rrr类的mul, div, neg, asr, lsl。

3)操作数

SUIF指令的操作数用操作数类(operand class)的对象来表示。一个操作数会有三种不同

类型的值：

A.空操作数：当指令中的操作数域没有用到或者是没有用的时候，此操作数就是空操

作数。

B.直接对变量符号的引用：源操作数中的变量表明需要使用本变量的内容。在目的操

作数中，操作数的内容是指令的结果。

C. 操作数也可以指向另外一条指令： 这经常用来实现表达式树或者是在指令序列中的对其它指令的结果的引用。在源操作数中的指令指针意味着所指的那条指令的结果被用作本条指令的操作数。相反的，在目的操作数中的指令指针表明本条指令的结果会被所指的那条指令使用。

图2-4显示了指令表达式树的可能出现的情况：

图2-4：指令表达式树的层次关系

3. 实验中对SUIF 中间表示的实现

3.1. SUIF 的抽象语法树(AST)相关的类结构

3.1.1. 文件级(fileset_entry.h)

为了简单起见，文件级只考虑单文件的情况，多文件暂不考虑。所以去掉fileset ，只留下fileset_entry 即可。

class file_set_entry {

char* fn; /* file name */

proc_iter* iter /* iteritor for tree_proc */

};

至少需要2个变量，一个记录读入的文件名，一个则是用来在文件中定义的所有过程中进行切换的迭代子。其中proc_iter 这个类型由学生自行定义。

3.1.2. 过程级和高级结构控制级(trees.h)

enum tree_kinds {

TREE_INSTR,

TREE_LOOP,

TREE_FOR,

简单指令

指令表达式树

TREE_IF,

TREE_BLOCK

};

这个枚举变量用来表示树节点的类型。

class tree_node {

name

*/

node

nname;

/*

char*

k; /* tree node kind */

tree_kinds

tree_node_list *par; /* parent list */

};

所有的tree_proc, tree_for等树节点都是从tree_node这个抽象类派生而来的。nname表示树节点名tree_proc, tree_for等等。k表示树节点类型。par则是指向父树节点链表的指针。树节点链表在下面介绍。

class tree_node_list {

unsigned num /* number of child node */

tree_node** list /* tree_node pointer list */ tree_node *par; /* parent tree node */

};

这里树节点链表(tree_node_list)是用来将并列的树节点链起来。num表示链表上所挂的子树节点的数目。list则是所有指向子树节点指针的列表的头指针。

class tree_block : public tree_node {

tree_node_list *bod; /* body list */

};

代码块节点从tree_node派生而来，代码块至少需要有代码体，而代码体本身则又是一个树节点链表。

class tree_proc : public tree_block {

*/

symbol

psym; /*

proc_sym*

proc

};

函数体节点从代码块节点派生而来，除了和代码一样都需要代码体，还需要表示函数调用参数，函数入口标号等各种符号信息。这个用proc_sym类型的psym来表示。proc_sym

由学生自行定义。

class tree_loop : public tree_node {

tree_node_list *bod, *tst; /* body list, test list */

label_sym *clab, *blab, *tol;/* continue label, break label, top-of-loop label */

};

从tree_node派生而来，这个节点类型主要是用来表示while这种循环体。首先需要有测试部分，用树节点链表类型的tst表示。然后还需要主体部分，用树节点链表类型的bod 表示。下来就是需要有各种label_sym类型的跳转标号，像continue label，break label等。label_sym由学生自行定义。

enum tree_for_test {

FOR_EQ, FOR_NEQ,

FOR_SGELE, FOR_SGT, FOR_SGTE, FOR_SLT, FOR_SLTE, /* signed */ FOR_UGELE, FOR_UGT, FOR_UGTE, FOR_ULT, FOR_ULTE /* unsigned */ };

列举了各种可能出现的测试语句的类型，如判断相等，不等，小于。

class tree_for : public tree_node {

var_sym *ind; /* index */ tree_for_test tst; /* test type */

label_sym *clab, *blab; /* continue label, break label */

tree_node_list *bod, *lower, *upper, *step; /*

landing_pad */

};

从tree_node派生而来，这个节点类型主要是用来表示for这种循环体。首先需要索引变量，用var_sym类型的ind表示。var_sym由学生自行定义。然后需要测试语句类型，用tree_for_test枚举类型的tst表示。然后是跳转标号continue label, break label。最后的4个树节点链表类型的变量分别是：bod表示for循环的主体部分，lower 表示循环下界，upper表示循环上届，step则是步长。

class tree_if : public tree_node {

label_sym *jmp; /* label maybe jump to */

tree_node_list *hdr; /* header_part */

tree_node_list *then; /* then_part */

tree_node_list *els; /* else_part */

};

从tree_node派生而来，这个节点类型主要是用来表示if这种结构。首先需要跳转标号，即最终判断的需要跳转到的下一语句的标号。跳转标号用label_sym类型的jmp表示。label_sym由学生自行实现。下来还需要有if的测试部分，用树节点链表类型的hdr表示。然后是then部分，即测试为真时的语句部分，用树节点链表类型的then表示。else 部分类似，不再多说。

class tree_instr : public tree_node {

instruction *ins;

};

从tree_node派生而来，这个节点类型主要是作为更低级的指令级的接口。所以至少需要有一个instruction类型的ins变量。

3.1.3.指令级(instruction.h)

class instruction {

if_ops op; /* opcode */

unsigned inum; /* number of operand */

tree_instr *par; /* parent tree_instr */

unsigned nd; /* number of dest */

operand *dsts; /* dest operand */

};

一条指令需要操作码op。源操作数的个数inum。父指令节点的指针par。目标操作数的个数nd。目标操作数的列表的指针。

class in_rrr : public instruction {

operand src1, src2; /* two source operand */

};

三操作数指令。有一个目的操作数，2个源操作数。

class in_bj : public instruction {

label_sym *targ; /* target label */

operand src; /* used for condition test */

};

跳转指令。一个跳转标号targ，一个条件测试操作数src。

class in_ldc : public instruction {

value

*/

number

val; /*

immediate

immed

};

常数加载指令。需要一个immed类型val。immed类型由学生自行实现。

class in_cal : public instruction {

operand addr; /* address of this function call */ unsigned nargs; /* number of args */

operand *args; /* args operand */

};

函数调用指令。函数调用的入口地址addr。参数的个数nargs。参数列表的指针。

class in_array : public instruction {

operand base; /* base */

unsigned elemsz; /* size of element */

operand *indxs, *uppers; /* index, upbound */

};

数组指令。数组基地址base，比如数组a[100]，那么base的内容就可能是变量a在符号表中的基地址。数组中元素的大小elemsz。数组的上界uppers。数组的索引indxs。

3.1.

4.操作数(operand.h)

enum operand_kinds {

OPER_SYM, /* variable symbol */

OPER_INSTR, /* instruction */

OPER_REG /* register operand */

};

操作数的类型。分别为变量型，指令型(操作数可能是另外一条指令)，寄存器型(直接在内存中存储)。

class operand {

operand_kinds k;

union { /* union of operands */

var_sym *sym; /* symbol */

instruction *i; /* instruction pointer */

int r;

} u;

};

operand_kinds类型的k表示了本操作数的类型。联合体中的3种变量分别对应上面3种类型的操作数。

3.1.5.操作码(opcode)

enum if_ops {

io_eos, /* end-of-stream; internal use only */ io_mrk, /* mark */

io_data, /* -- no longer used -- */

io_cpy, /* copy */

io_nop, /* no op */

io_add, /* add */

io_sub, /* subtract */

io_neg, /* negate */

io_mul, /* multiply */

io_div, /* divide */

io_rem, /* remainder */

io_mod, /* modulus */

io_min, /* minimum */

io_max, /* maximum */

io_not, /* bitwise not */

io_and, /* bitwise and */

io_ior, /* bitwise inclusive or */

io_xor, /* bitwise exclusive or */

io_abs, /* absolute value */

io_asr, /* arithmetic shift right */ io_lsl, /* logical shift left */

io_lsr, /* logical shift right */

io_rot, /* rotate */

io_cvt, /* convert */

io_ldc, /* load constant */

io_lod, /* load */

io_str, /* store */

io_seq, /* set equal */

io_sne, /* set not equal */

io_sl, /* set less than */

io_sle, /* set less than or equal */ io_btrue, /* branch if true */

io_bfalse, /* branch if false */

io_jmp, /* unconditional jump */

io_cal, /* call */

io_ret, /* return */

io_lab, /* label */

io_array, /* array reference */

io_mbr, /* multi-way branch */

io_divfloor, /* divide with floor */

io_divceil, /* divide with ceiling */

io_memcpy, /* memory-to-memory copy */ io_gen, /* generic instruction */

io_last

};

各种指令操作码。io_表示intermediate form opcode。

enum inst_format {

inf_none,

inf_rrr,

inf_bj,

inf_ldc,

inf_cal,

inf_array,

inf_mbr,

inf_lab,

inf_gen

};

指令操作码的类型。

static char *if_op_names[] = {

"eos",

"mrk",

"unused", /* -- no longer used -- */

"cpy",

"nop",

"add",

"sub",

"neg",

"mul",

"div",

"rem",

"mod",

"min",

"max",

"not",

"and",

"ior",

"xor",

"abs",

"asr",

"lsl",

"lsr",

"rot",

"cvt",

"ldc",

"lod",

"str",

"seq",

"sne",

"sl",

"sle",

"btrue",

"bfalse",

"jmp",

"cal",

"ret",

"lab",

"array",

"mbr",

"divfloor", "divceil", "memcpy",

"gen"

};

对应的操作码名称。

安全检查符号表抽象语法树Java字节码字节码分析工具论文

安全检查论文：Java程序安全检查工具前端的设计与实现 【中文摘要】本文在分析程序安全检查工具框架的基础上,根据安全检查的特殊需求,给出了一种基于ASM(一种字节码分析工具)构造Java安全检查器前端的方法,并将此方法应用于实际开发过程中。使用此方法构造的前端通过分析Java字节码文件为后端安全检查提供符号表、抽象语法树。文中重点讨论了符号表和抽象语法树的设计与实现。首先,本文针对字节码文件中符号和作用域的特点,设计了适用于Java字节码文件的符号表。其次,针对如何从字节码文件中恢复出表达式和控制流语句结构的问题,设计了模拟字节码指令执行的方法。该方法通过模拟字节码指令的实际执行过程,提取出建立抽象语法树所需的信息,生成抽象语法树。 【英文摘要】According to the specific requirements for the safety check, a method based on a Java bytecode file analyzer ASM, for constructing the front-end of a Java program safety checker is proposed and implemented in this thesis. The front-end provides symbol table and abstract syntax tree for the back-end of the safety checker by analyzing Java bytecode files of the project.The design and implementation of the symbol table and abstract syntax tree are detailedly discussed in the thesis. Firstly, according to t... 【关键词】安全检查符号表抽象语法树 Java字节码字节码

抽象语法树文献综述_V1

抽象语法树 姓名：刘乐 学号：2101470 日期：2011/10/16

抽象语法树(AST) 1.AST的基本概念 在计算机科学中，抽象语法树（abstract syntax tree或者缩写为AST），或者语法树（syntax tree），是源代码的抽象语法结构的树状表现形式[1]，这里特指编程语言的源代码。树上的每个节点都表示源代码中的一种结构，图一是一段源代码的语法书结构，代码见附录一。所以说语法是“抽象”的，是因为这里的语法并不会表示出真实语法中出现的每个细节。比如，嵌套括号被隐含在树的结构中，并没有以节点的形式呈现；而类似于if-condition-then这样的条件跳转语句，可以使用带有两个分支的节点来表示。. 图一源代码语法树 和抽象语法树相对的是具体语法树（concrete syntax tree），通常称作分析树（parse tree）。一般的，在源代码的翻译和编译过程中，语法分析器创建出分析树。一旦AST被创建出来，在后续的处理过程中，比如语义分析阶段，会添加一些信息。

2.语法分析和语法树 语法分析指的是将代码扫描到一个容器中，然后对该容器中的字符在词法分析的基础上将字段组合成各类语法短语，在结构上分析判断源程序。使用语法分析可以解决词法分析中较难解决的字段的多重意义的问题。[4] 图二词法分析[5] 语法树是在语法分析的基础上，将代码的结构转化成树的形式，可以解决字段的上下文相关的问题。而语法树可以通过许多词法语法解析器自动生成，也解决了手工识别的效率问题。 3.AST的作用 在现代编译器的构造过程中，前端主要实现从源程序到中间形式（Intermediate Representation）的转换，而编译器的后端用来完成从中间形式到具体目标机代码的转换，这是一种广泛采用的编译器构造模型。虽然源程序到目标程序的直接转换是可行的，但是使用独立于具体目标平台的中间形式有以下优点： （1）使用中间形式可以比较容易地构造面向不同目标平台和不同语言的编译器。在不改动已有编译器前端的情况下，为新的目标平台构造一个生成该平台目标程序的后端，就可以构造出新平台的编译器。同样对于一个新的语言，在不改动已有编译器后端的情况下，为新语言构造一个识别该语言的前端，就可以构造出新语言的编译器。 （2）针对中间形式，可以进行独立于目标平台的代码优化。这样可以生成较高质量的目标代码，在此基础上可以对目标代码进行平台相关的优化，进而生成更高质量的目标代码。 使用中间形式的主要缺点是，产生中间代码的编译过程与不产生中间代码的编译过程相比在效率上会显得有些低。这是因为中间代码还要进行再一次的翻译

抽象语法树(AST)

抽象语法树（AST） 抽象语法树（AST） 最近在做一个类JA V A语言的编译器，整个开发过程，用抽象语法树（Abstract SyntaxTree,AST）作为程序的一种中间表示，所以首先就要学会建立相对应源代码的AST和访问AST。Eclipse AST是Eclipse JDT的一个重要组成部分，定义在包org.eclipse.jdt.core.dom中，用来表示JA V A语言中的所有语法结构。 Eclipse AST的总体结构 1、org.eclipse.jdt.core.dom.AST（AST节点类） Eclipse AST的工厂类，用于创建表示各种语法结构的节点。 2、org.eclipse.jdt.core.dom.ASTNode及其派生类（AST类）用于表示JA V A语言中的所有语法结构，在实际使用中常作为AST上的节点出现。 3、org.eclipse.jdt.core.dom.ASTVisitor（ASTVisitor类）Eclipse AST的访问者类，定义了统一的访问AST中各个节点的方法。 详细介绍： 一、AST节点类

整体结构包括CompilationUnit类(编译单元）、TypeDeclaration类（类型声明）、MethodDeclaration类（方法声明）； 语句包括Block类（语句块）、ExpressionStatement类（表达式）、IfStatement(if语句）、WhileStatement类（while语句）、EmptyStatement类（空语句）、BreakStatement类和ContinueStatement类； 表达式包括MethodInvocation类（方法调用）、Assignment 类（赋值表达式）（“=”、“+=”、“-=”、“*=”、“/=”）、InfixExpression类（中缀表达式）（“+”、“-”、“*”、“/”、“%”、“==”、“！=”、“<"、“<=”、“>=”、“&&”、“||”。）、PrefixExpression类（前缀表达式）（“+”PLUS “-”MINUS “！”NOT）、ParenthesizedExpression类（带括号的表达式）、NumberLiteral类（整数）、Name类（simple）、MethodInvocation类（方法调用）。 二、AST类 关键是创建编译单元节点，创建类AST的实例。 AST ast = AST.newAST(JLS3); 三、ASTVisitor类 它提供与节点类有关的visit()方法和endVisit()法，与节点类无关的preVisit()方法和postVisit()方法。 boolean visit( T node):这类方法如果返回true，则接着访问

SUIF 抽象语法树

SUIF抽象语法树 1.概述 本次实验中实验三的目标是通过解析语法分析的输出文件来生成中间代码。至于中间代码的形式，我们要求采用抽象语法树。抽象语法树的结构则是借鉴SUIF的中间表示。 2.SUIF编译系统中间表示 总体上来说，SUIF中间表示由三部分组成：抽象语法树(AST)、符号表、和指令表达式。 2.1.SUIF的层级结构 SUIF中间表示组织成4级层次结构，包括：文件级，过程级，高级结构控制级和指令表达式树级。SUIF中间表示的主要部分是一个混合式的抽象语法树(AST)。从层次结构上来看，包括高级结构控制级和指令表达式树级，即除了传统的指令级别的操作，它还包含三个高级的结构：循环，条件声明和数组访问。循环和条件表示类似于抽象语法树，但却是语言无关的。图2-1展示了SUIF中间表示的层级结构：

图2-1：SUIF中间表示的层次结构 2.2.SUIF的符号表示 SUIF的符号表分为global symbal table，file symbal table，proc symbal table和block symbal table这4种。它们也是高到低，逐级的贯穿在了SUIF中间表示前3个层级中。图 2-2则表明了这个层次结构：

图2-2：SUIF的符号表示 2.3.SUIF的面向对象实现 SUIF系统的内核提供了一个面向对象的SUIF中间表示的实现。SUIF库对每个程序表示元素定义了一个C++类，允许我们对隐藏了细节的数据结构提供接口。在这个系统中，各个类之间存在若干相互联系和共享的属性，这由类的继承和动态邦定功能实现。例如：变量、标号和过程都是符号，他们共享相同的符号接口，但过程除了符号还有函数体。除了基本的SUIF数据结构，SUIF的内核中还定义了很多基本的数据结构，包括哈希表，可扩展数组等。对每个类来说，经常需要用到的函数都被定义为成员函数。图2-3给出了主要的SUIF数据

基于抽象语法树的代码静态自动测试方法研究

第34卷增刊Ⅰ 2007年北京化工大学学报 JOURNAL OF BEI J IN G UN IV ERSIT Y OF CHEMICAL TECHNOLO GY Vol.34,Sup.Ⅰ 2007 基于抽象语法树的代码静态自动测试方法研究 高传平1　谈利群1　宫云战2 (11北京图形研究所,北京　100029;21北京邮电大学网络与交换技术国家重点实验室,北京　100876) 摘　要:软件测试是排除软件故障,提高软件质量和可靠性的重要手段。从是否需要执行被测程序角度考虑,软件测试分为静态测试和动态测试。动态测试通过输入测试数据,动态执行程序来发现软件中存在的错误。尽管动态测试能发现部分软件错误,但对于一些特殊类型错误的检测无效。鉴于此,本文采取了一种特殊的静态分析技术来实现对代码的测试。本文首先讨论了传统软件测试方法的缺点和局限性,给出了软件的故障模型,进而提出了基于抽象语法树的静态分析技术,并给出了故障自动检测算法。依据该算法开发了自动化测试工具,给出了实验结果和对比分析,并指出了下一步的研究方向。关键词:软件测试;静态分析;故障;故障模型;语法树中图分类号:TP30218 收稿日期:2007204205 第一作者:男,1977年生,博士生E 2mail :cpgzgy @https://www.wendangku.net/doc/7115841301.html, 引　言 软件测试是排除软件故障,提高软件质量和可靠性的重要手段。按是否需要动态执行被测程序考虑,软件测试分为两类,即静态测试和动态测试[1]。静态测试是指不运行实际被测的源程序,而是通过采用其他手段对程序结构进行静态分析,获得程序结构的相关信息,并完成对软件故障的检测;动态测试通过输入测试数据,动态执行程序来发现软件中存在的错误。动态测试只存在于软件生存期的编码阶段之后。动态测试包括两个基本要素:一是被测程序,二是测试数据,程序一次运行所需要的测试数据称为测试用例,所以测试数据是测试用例的集合。尽管动态测试能发现程序中存在的某些方面的错误,但是对于软件本身存在的一些深层次逻辑结构方面的错误或者一些比较特殊的错误的检测是无能为力的。与静态测试相比,动态测试虽然能在软件运行时发现一些软件故障,但又明显具有一定的局限性。 (1)动态测试的结果依赖于测试数据的选择。好的测试数据往往能发现软件中存在的更多的故障,而不好的测试数据很难发现软件中存在的故障,因此测试数据的选择至关重要。 (2)动态测试在很大程度上受测试人员自身素 质和经验的影响。测试人员的经验和素质将会直接影响测试数据的设计,从而间接对测试结果产生影响。 (3)动态测试的结果有时难以复现。某些故障 的发生具有偶然性,这不仅与测试数据的选择有关系,而且与程序的操作逻辑及执行次数有关。 (4)动态测试对于一些特殊类型故障的检测无效。动态测试对于软件本身存在的一些深层次逻辑结构方面的错误或者一些比较特殊错误的检测是无能为力的。如动态测试对于不可达代码的测试无效。 为了能有效地解决上述问题,本文采取了一种特殊的静态分析方法来实现对程序代码的静态检测,尤其是对于那些用动态方法无法检测的软件问题。 1　故障模型 在传统的软件测试方法中,一个故障能否被检测到,是取决于该故障检测概率的大小,对软件中存在的所有故障的检测而言,只能以故障检测的百分比来衡量。如果一种故障的故障检测率比较高,则此种故障比较容易检测,否则故障就不容易被检测。 目前所存在的软件测试方法,其测试理论的基础并不是基于故障模型,而是基于软件中所有可能的故障。这种测试方法的优点是: (1)能够检测软件中的大部分故障;

第三章 抽象语法树

第三章抽象语法树 在现代编译器的构造过程中，前端主要实现从源程序到中间形式（Intermediate Representation）的转换，而编译器的后端用来完成从中间形式到具体目标机代码的转换，这是一种广泛采用的编译器构造模型。虽然源程序到目标程序的直接转换是可行的，但是使用独立于具体目标平台的中间形式有以下优点： （1）使用中间形式可以比较容易地构造面向不同目标平台和不同语言的编译器。在不改动已有编译器前端的情况下，为新的目标平台构造一个生成该平台目标程序的后端，就可以构造出新平台的编译器。同样对于一个新的语言，在不改动已有编译器后端的情况下，为新语言构造一个识别该语言的前端，就可以构造出新语言的编译器。 （2）针对中间形式，可以进行独立于目标平台的代码优化。这样可以生成较高质量的目标代码，在此基础上可以对目标代码进行平台相关的优化，进而生成更高质量的目标代码。 使用中间形式的主要缺点是，产生中间代码的编译过程与不产生中间代码的编译过程相比在效率上会显得有些低。这是因为中间代码还要进行再一次的翻译才能生成目标代码。但是，增加一层中间形式可以使编译器更好地模块化，并且可以在中间形式上做很多优化，这些足以抵消两次翻译所带来的低效率。所以，很多现代的编译器都使用了中间形式，比较常见的中间形式有逆波兰表示，N元表示和树形表示三种。由于，在本系统中，我们使用抽象语法树作为中间形式，所以不再对前两种中间形式做以介绍，感兴趣的读者可以参考《编译原理》（Alfred V.Aho编著）。 3.1 树形表示 树形表示是一种非常流行的中间形式，它与三元式表示有着密切的关系，三元式表示可以看成是树形表示的直接形式。例如，表达式W*X+(Y+Z)的树形表示如图3.1所示： 图3.1 表达式W*X+(Y+Z)的树形表示