《程序分析方法》——2.2元程序设计系统

2.2 元程序设计系统

2.2.1 元程序系统的组成　　元程序的处理对象是程序而不是通常的数据，因此其处理过程要相对复杂。通常一个元程序设计系统由下面三个部分构成：

预处理——把目标程序变成一种中间表示（目标语言的内部表示形式）。元级操作——对内部表示直接进行处理的基本操作。后处理——把中间表示转化为目标代码。　　其中，中间表示决定了该系统中目标程序到元级用户的接口特性，对整个系统的可用性起到重要作用；而元级操作是系统的另一重要部分，用户主要使用这些元级操作对目标程序的内部表示进行处理（注意，此时的操作对象已经不是目标程序，而是目标程序的内部表示结构）。

2.2.2 中间表示　　正如之前所说，中间表示是元程序设计系统提供给程序员的到目标语言的接口，其结构设计的好坏对元程序设计系统起着极其重要的作用。在元程序设计中，中间表示有很多种形式，常见的有四元式、逆波兰式、树形结构和抽象语法树结构。　　（1）四元式　　一般结构为：（operator, operand1, operand2, result）　　其中，operator表示操作符；operand1、operand2分别表示运算分量；result表示运算结果。　　对于运算型四元式，如（+,a,1,t1），其含义是将operand1和operand2在operator的作用下得到的结果送入result中，此例中即将变量a和常量1做加操作的结果存入临时变量t1中。　　而对于控制型四元式，其作用是对程序的执行起标志或控制转移的作用，此时operator位置已不再表示操作符，而为标志位，其他部分为空或者为控制转移条件的表达式的结果。例如，（WHILE, , , _ ）表示while循环的入口。　　（2）逆波兰式　　逆波兰式，即后缀式，表示方式为：表达式中各运算分量顺序不变且计算顺序排定；计算方式为：将表达式从左至右依次扫描，扫描到一个计算符后，向前取两个运算分量，计算出结果即可。　　例如，算术表达式a(x+y)d的逆波兰式表示为：axy+d，按照下图中的方块，从内到外为计算顺序：

　　从中缀表达式到后缀表达式的转换，可以通过T形的栈式结构实现，如图2.1所示。

　　（3）树形结构　　树形结构是按分支关系把信息项联系起来的一种数据结构。这种结构中有一个没有前驱的节点，称为根；树中除根以外的节点有且仅有一个前驱节点，并且对于任一非根节点都存在一条从根到该节点的路径。对于上面所举的例子，表达式a(x+y)d的树形结构表示如图2.2和图2.3所示。

　　由于树形结构便于进行元级操作并且比较直观，所以做程序分析和程序变换时比较适合使用这种结构作为目标程序的内部表示结构。　　（4）抽象语法树结构　　抽象语法树是目标程序的抽象语法结构的树状表现形式。当目标语言是面向对象语言时，将抽象语法树作为其内部表示是更为合适的，与之前提到的利用分支关系构造的树形结构不同，这种方法是利用对象及其成员变量之间的关系建立起的树形结构，与普通的树形结构相比，对于目标语言的描述更加清晰、细致，并且易于施加各种操作。　　例如，有如下上下文无关文法G = (N, T, S, P)：

N = {E} //N表示非终极符的有限集合 T = {+, -,×,÷,(, ), id} //T表示终极符的有限集合 S = E //S是文法的开始符号 P = E?E+E|E×E|E÷E|(E)|-E|id //P是产生式的有限集合

　　-(id+id)是由该文法构造的语句，图2.4为该语句对应的具体语法树和抽象语法树。

2.2.3 规则分类和对应的结构　　由于元程序设计是基于给定目标语言文法的，故需要针对每种不同的文法规则来构造不同的内部表示结构。此处，我们使用类似语法树的树形结构来表示规则对应的内部结构。　　下面是常用的五种文法规则：　　（1）结构规则（Constructor Rule）

< A0>→{N0}w1< t1:A1>w2…wn< tn:An>

　　该规则描述了从非终极符< A0>可以导出串w1 w2…< An>。其中，< A0>,< t1:A1>,…, < tn:An>是非终极符，< ti:Ai>中ti是标签名，Ai是语法范畴；w1,w2,…,wn是可能为空串的终极符；N0是由大括号包围着的该规则的名字，可以省略。标签名用于区别属于同一个语法范畴的非终极符，因此一条规则中的所有标签名都必须是不同的。如果没有提供标签名，那么语法范畴的名字就会被当做标签名使用。　　此类规则对应的树形结构的节点结构为：

type——节点的种类（由此可以判定右侧的语法成分）。par——父节点的指针。ti——指向子节点的指针（1≤i≤n）。　　抽象语法树的节点类为： class A0{}; //结构规则左侧的非终极符对应的抽象类 class N0A0 : A0{ //以结构规则右侧所有成分为成员变量组成 W1 w1;… //的类，是抽象类A0的子类 Wn wn; A1 t1;… //其中Wi和Ai分别为右侧终极符wi和非终极 An tn; }; //符<ti:Ai>对应的各自的类 　　假设有while语句的产生式如下： 　　<while_stmt> →{all} while (<predicate:exp>) do <repetition:stmt>

　　对应该规则的树形结构的节点结构为：

　　对应的抽象语法树类结构为：

class WHILE_STMT{}; class allwhile_stmt:WHILE_STMT{ TOKEN while; TOKEN leftbracket; EXP predicate; TOKEN rightbracket; TOKEN do; STMT repetition;}

　　（2）分支规则（Alternation Rule）

<A0>→{N1}<t1:A1> | {N2}<t2:A2> |…| {Nn}<tn:An>

　　该规则描述了从非终极符可以推导出,,…,中的任意一个，其中每一个分支仍是一个结构类型的规则。其中、ti的定义同上。Ni表示每一个分支的一个名字。

对于树形结构，此规则不定义新的语法结构，因而不存在相应的节点结构定义。对于抽象语法树结构，对应每个分支，分别声明类N1A0,…,NnA0作为A0的子类，其中NiA0的声明如下： class A0{}; class NiA0 : A0{…};

　　一个分支内的构造同结构规则的构造。　　（3）表规则（List Rule）

<A>→{N0}<B>(w<B>)*

　　该规则描述了非终极符将产生由w分隔开的< B>的表序列：< B> w < B> w…w < B>，星号*表示括号中的部分可以重复生成0～n次。其中，< A>、< B>均为非终极符，w是可以为空的终极符。　　例如：

<var_list>→<variable> {,<variable>}

　　对于此种规则，由于括号内的部分可以重复，且结构相同，因而可以使用链表来表示树形结构中的节点结构。每个节点的结构与结构规则的节点类似，特别之处是需要定义一个表头，并且还要为每个节点添加前驱和后继两种指针，这样就构造成了一个双向链表，如图2.5所示。

　　其中，elements为指向第一个表元素的指针，previous为前驱指针；next为后继指针；others为其他信息域，其个数和类型依赖于具体表元素。符号^表示空。　　与树形结构的节点结构类似，在抽象语法树节点中引入了一般面向对象语言中的标准链表类。声明类AA的成员函数为一链表类，其基类型由用户自己定义，此处我们定义为AwB类：

class AwB:{ W w; B b; } 　　链表类ListwB为： TypeDef CTypedPtrList<CPtrList,AwB> ListwB; 　　则类AA的声明为： class N0A:A{ ListwB listwb; }

　　（4）选择规则（Optional Rule）

<A>→(<B>)?

　　非终极符< A>或者导出与非终极符< B>生成的完全相同的串，或者导出空串。其中，< A>、< B>均为非终极符，后面带有“?”的括号（）表示括号中的成分可以出现也可以不出现。

此规则对应的树形结构的节点结构为：

　　其中指针B表示：如果选择< B>，则指向B的节点；否则，指针为空。

对于抽象语法树结构，此规则等价为： <A>→<B> | ε

故按照分支规则定义类结构即可。　　（5）词法规则（Lexical Rule）

<A>→{N} lexeme

　　该规则描述了由非终极符能够导出词汇lexeme。其中是非终极符，用于描述词汇，lexeme是终极符，即预定义的TOKEN。

对应词法规则的树形结构的节点结构为：

　　其中value存放字符串指针（标识符、字符串、关键字）或数值（字符常量、数值）。

对于抽象语法树结构，针对此规则的每一个终极符，都建立相应的类Tlexeme。 class Tlexeme { CString value; }

　　类A和NA的声明同结构规则。　　以上是一般文法中涉及的五种文法规则结构及其对应的树形结构和抽象语法树结构中一般节点的结构。在具体的实现中，如果元语言是面向过程式的语言，则可选择树形结构，并使用结构体和指针实现以上结构；如果元语言采用的是面向对象的语言，则可利用抽象语法树通过定义类来实现上述各结构。2.2.4 元级操作　　一个好的元程序设计系统是否好用的关键在于它所提供的元级操作是否足够丰富以满足各种元级用户的需求。一般的元级系统应该提供如下元级操作。　　（1）类型识别

类型识别函数node_type：　　node_type (n) = 节点n的类型，如WHILE_STMT、PLUS_EXP等。

　　如有一if语句节点stmt，则node_type(stmt)=IF_STMT。

判定谓词：　　设有规则left→right

则对应的判定谓词为leftQ(n) = 　　例如，若节点stmt为if语句，则if_stmtQ(stmt)=true，否则为false。

空成分判定谓词：　　

　　（2）成分选择

与结构规则相对应，定义n个成分选择子程序ti_of (1≤i≤n)，例如，对于前面所提到的while语句的规则，定义两个子程序predicate_of和repetition_of。 设 while_statement = ROOT(while (e) do s) 　　则 predicate_of(while_statement) = ROOT(e) repetition_of(while_statement) = ROOT(s)

　　其中，ROOT(β)表示β的内部树TREE(β)的根节点。　　由于采用C++中标准的链表类，故这些针对表的操作比较容易实现。

表的成分选择　

　　（3）构造操作

结构规则的构造：　　对应每个结构规则，都定义一个构造子程序make_A，例如，对应while语句规则如下： make_while_stmt(ROOT(e), ROOT(s1)) = ROOT(while(e) do s1) 表的构造：　　对应每一表规则都定义一子程序make_A构造单元素表；由concat、tack或append扩充给定的表来构造任意长度的表。

　　（4）关系操作　　用于确定节点之间的关系，设E为表的第i个元素Ei，则主要的关系操作可描述如下：

　　

　　（5）编辑操作

　　（6）单词处理　　词汇构造和词汇强制：　　在内部结构中，目标语言的基本值（如标识符、数值）不能直接作为节点对象的成员变量使用。同样，在元程序中，表示词汇的节点也不能直接作为目标语言的基本值使用，因而对每一个词法规则都必须定义一个词汇构造子程序make_A和一个词汇强制子程序coerceA来实现二者之间的相互转换，词汇构造和词汇强制互为逆操作。如词法分析后得到的是数字串“12”，而单词节点需要的是正整数12，make_integer(“12”)=12恰好完成了此任务，CoerceInteger(12)作用相反。　　在面向对象的元程序设计系统中，可使用面向对象的方法将上述提到的几种操作封装到类中，这样可以使整个系统更易于扩充和维护。具体实现这里不再细述。　　当然，以上列举的几种操作仅仅是比较常见的基本操作，在进行元程序系统设计时，可根据不同的系统及其实际要求定义一些新的元级操作，如数据流分析操作、控制流分析操作、程序转换操作等，这使得元程序的设计更加便捷。2.2.5 系统的生成　　通常，在元级系统的设计中，经常要用到如YACC、ACCENT或JAVACC等语法分析器的生成器。以YACC为例，在设计元程序系统时，需要提供YACC specification文件，简称YSP文件。该文件的主要有以下三部分内容。　　1）说明部分：主要给出节点结构的定义。　　2）规则部分：给出目标语言的文法规则集和构造内部树的语义动作。　　3）程序部分：给出目标语言的词法分析程序和语义动作子程序。　　在进行编译时，应该根据所选用的工具对于文法的限制对文法进行相应的转换。例如，YACC只能够处理的文法是LALR（1）文法，如果目标语言的文法规则不是LALR（1）文法，在使用前应将其转换成LALR（1）文法。而ACCENT能够处理所有文法，即使有二义性，也可以通过做优先级标记进行处理，可以不用对文法进行改动。