The consistent implementation procedure for trees is a special case of the ``Composite'' design pattern. ``Composite'' is applicable to situations where complex structures are built from components, and these structures may themselves be components of other structures. It describes how to use recursive composition to avoid forcing clients to treat each component object specially.
A class that represents all components is the key to this design pattern. That class is provided by the ``tree node'' class created by step (1) of the consistent implementation procedure:
This macro is invoked in definition 24.
class Node {
public:
virtual SPMtilde;Node() {}
Empty Accept method[9];
};
The purpose and implementation of the Accept method are discussed in Section 2.2.1.
Step (2) of the consistent implementation procedure requires one class for each nonterminal symbol of the grammar. Each nonterminal symbol class is a subclass of the tree node class, and all of them have exactly the same structure. The only thing that varies among the classes is the name:
:
This macro is invoked in definition 3.
class: public Node {
public:
virtual SPMtilde;
Empty Accept method[9];
};
Here the parameter is the nonterminal symbol. Symbol classes must also accept the visitors that do the interpretation, as discussed in Section 2.2.1.
This macro is invoked in definition 24.
Class definition for nonterminal[2](`Stm')
Class definition for nonterminal[2](`Exp')
Class definition for nonterminal[2](`ExpList')
Class definition for nonterminal[2](`Binop')
The last two steps of the consistent implementation procedure are concerned with rule classes. Each rule class is a subclass of the class for its left-hand side symbol, and must have fields reflecting the rule's right-hand side symbols.
One of the inconsistencies in Appel's Grammar 1.3 lay in the specification of the right-hand side symbols. The following class definitions assume that print, +, -, * and / are all literal terminal symbols, while id and num are literal terminal symbols.
The Binop rule classes are the simplest because those rules have no right-hand-side symbols. All of them have identical structure, differing only in the rule name:
:
This macro is invoked in definition 6.
class
public:
virtual SPMtilde;
Prototype for the Accept method[8];
};
(The Accept method is explained in Section 2.2.1.)
The class definition for the assignment statement rule is more interesting, illustrating the way in which right-hand-side symbols of different types are represented:
This macro is invoked in definition 6.
class AssignStm : public Stm {
public:
AssignStm (string arg1, Exp* arg2) { child1 = arg1; child2 = arg2; }
virtual SPMtilde;AssignStm () {}
string Child1() { return child1; }
Exp* Child2() { return child2; }
Prototype for the Accept method[8];
private:
string child1; Exp* child2;
};
The fields implementing the right-hand-side symbols are private, and each is assigned a value by the class constructor. An access function is provided for each field so that routines outside the class can traverse the tree. There is little incentive to choose mnemonic names for the fields, since the primary documentation of the program is the grammar. The convention used here is positional, with the field names and access function names identical except for the case of the first letter.
Here is the complete set of rule classes:
This macro is invoked in definition 24.
class CompoundStm : public Stm {
public:
CompoundStm (Stm* arg1, Stm* arg2) { child1 = arg1; child2 = arg2; }
virtual SPMtilde;CompoundStm () {}
Stm* Child1() { return child1; }
Stm* Child2() { return child2; }
Prototype for the Accept method[8];
private:
Stm* child1, *child2;
};
Class definition for rule AssignStm[5]
class PrintStm : public Stm {
public:
PrintStm (ExpList* arg1) { child1 = arg1; }
virtual SPMtilde;PrintStm () {}
ExpList* Child1() { return child1; }
Prototype for the Accept method[8];
private:
ExpList* child1;
};
class IdExp : public Exp {
public:
IdExp (string arg1) { child1 = arg1; }
virtual SPMtilde;IdExp () {}
string Child1() { return child1; }
Prototype for the Accept method[8];
private:
string child1;
};
class NumExp : public Exp {
public:
NumExp (int arg1) { child1 = arg1; }
virtual SPMtilde;NumExp () {}
int Child1() { return child1; }
Prototype for the Accept method[8];
private:
int child1;
};
class OpExp : public Exp {
public:
OpExp (Exp* arg1, Binop *arg2, Exp* arg3)
{ child1 = arg1; child2 = arg2; child3 = arg3; }
virtual SPMtilde;OpExp () {}
Exp* Child1() { return child1; }
Binop* Child2() { return child2; }
Exp* Child3() { return child3; }
Prototype for the Accept method[8];
private:
Exp* child1, *child3; Binop *child2;
};
class EseqExp : public Exp {
public:
EseqExp (Stm* arg1, Exp* arg2) { child1 = arg1; child2 = arg2; }
virtual SPMtilde;EseqExp () {}
Stm* Child1() { return child1; }
Exp* Child2() { return child2; }
Prototype for the Accept method[8];
private:
Stm* child1; Exp* child2;
};
class PairExpList : public ExpList {
public:
PairExpList (Exp* arg1, ExpList* arg2) { child1 = arg1; child2 = arg2; }
virtual SPMtilde;PairExpList () {}
Exp* Child1() { return child1; }
ExpList* Child2() { return child2; }
Prototype for the Accept method[8];
private:
Exp* child1; ExpList* child2;
};
class LastExpList : public ExpList {
public:
LastExpList (Exp* arg1) { child1 = arg1; }
virtual SPMtilde;LastExpList () {}
Exp* Child1() { return child1; }
Prototype for the Accept method[8];
private:
Exp* child1;
};
Class definition for Binop rule[4](`Plus')
Class definition for Binop rule[4](`Minus')
Class definition for Binop rule[4](`Times')
Class definition for Binop rule[4](`Div')