- Semantic Stack
- Can be a separate stack synchronized with the parse stack
- Can be a descendent of parse stack that contains both syntax and semantics.
// This is the parent stack node for a syntax stack in
// an LR parser. Children of this node will store
// semantic information.
class StackNode
{
public :
StackNode(int s){state = s;}
void setState(int s){state = s;}
int seeState(){return state;} // See the state at the top of the stack
private:
int state;
};
// The parse stack is augmented to make it possible to store semantic
// information. There are three types of node. A node for variables, types and
// temporary storage (StoreNode). A node for Jump locations (JumpNode).
// A node for operators (OperatorNode).
class StoreNode :public StackNode
{
public :
StoreNode(int st, const String &n, const String &t)
:StackNode(st),name(n),type(t){}
String seeName(){return name;}
String seeType(){return type;}
void setName(const String &s){name = s;}
void setType(const String &t){type = t;}
private :
String name;// actual name of an identifier or temperary, if known
String type; //type of the data storage, if known
};
// JumpNodes are used to store jump locations for both backfills and
// forward locations. Since the locations must be integers when used
// as subscripts we need GetAddress to return an integer value. Code
// is stored as strings, so SeeAddress returns a string version of
// the value.
class JumpNode:public StackNode
{
public :
JumpNode(int s,int ja):StackNode(s){jumpAddress = ja;}
String addressAsText(){char num[10]; itoa(jumpAddress,num,10);return String(num);}
int seeAddress(){return jumpAddress;}
private :
int jumpAddress; // Location of a jump or where jump to
};
class StateStack
{
public :
StateStack(int size=0,int resize=1):data(size,resize){top = -1;}
int insert(StackNode* t){data[++top]= t;return top;}
int seeTop(){return data[top]->seeState();}
StackNode* getTop(){return data[top];}
StackNode* remove(){return data[top--];}
int empty(){return top ==-1;}
private :
Array<StackNode*> data;
int top;
};
- The only action that generates code is the reduce action. So the action function for the Reduce action is suplemented by the code necessary to generate code. This is mainly a call to the generator function. This is a virtual function that each descendent of a base class Generator implements.
int ReduceAction::action(StateStack &s,const ActionArray &a,
Lexical &lex,IdTable &ids,ThreeAddressCode &code)const
{
Array<StackNode*> temps(5,1); // grab the stuff coming out to generate code
if (popNum >0)
for (int i = 0;i<popNum;i++)
temps[i] = s.remove(); //deleted as needed in generate
else
temps[0] = s.getTop();// must know conditional goto storage
if (actionNumber == 14)
{
StackNode *temp = new StoreNode(temps[1]->seeState(),"+","");
delete temps[1];
temps[1] = temp;
}
else if (actionNumber == 16)
{
StackNode *temp = new StoreNode(temps[1]->seeState(),"*" ,"" );
delete temps[1];
temps[1] = temp;
}
//add next line when generating code
generators[actionNumber]->generate(ids,code,temps,popNum);
// temps[0] always comes back with an appropriate type of StackNode *
int top = s.seeTop();
int newState = a.act(top,pushSym)->action(s,a,lex,ids,code);
temps[0]->setState(newState);// now we have the state - set it
s.insert(temps[0]);// push the new node
return newState;
}
- The Generator Class Hierarchy
//Used to update the parse stack and generate code
//Different children of Generator will represent
//various actions on reduce
class Generator
{
public :
Generator(){}
virtual void generate(IdTable &idents,ThreeAddressCode &codeGen,
Array<StackNode*> &s,int &num);
};
//Add variables to table in declaration section
class NewVars : public Generator
{
public :
NewVars(){} //needed to bind the virtual functions
virtual void generate(IdTable &idents,ThreeAddressCode &codeGen,
Array<StackNode*> &s,int &num);
};
//Transfer temporary address from nonterminal in stack to new nonterminal
class ChangeNonTerm : public Generator
{
public :
ChangeNonTerm(){} //needed to bind the virtual functions
virtual void generate(IdTable &idents,ThreeAddressCode &codeGen,
Array<StackNode*> &s,int &num);
};
//Test to see if variable in table in F->ident
class OldVars :public ChangeNonTerm
{
public :
OldVars(){} //needed to bind the virtual functions
virtual void generate(IdTable &idents,ThreeAddressCode &codeGen,
Array<StackNode*> &s,int &num);
};
//Generates the code for S->ident := E. Must do type checking
//and see if ident is defined to ensure the assignment is possible
class AssignGen : public Generator
{
public :
AssignGen(){} //needed to bind the virtual functions
virtual void generate(IdTable &idents,ThreeAddressCode &codeGen,
Array<StackNode*> &s,int &num);
};
//Operator with two operands
class StandardOp : public Generator
{
public :
StandardOp(){} //needed to bind the virtual functions
virtual void generate(IdTable &idents,ThreeAddressCode &codeGen,
Array<StackNode*> &s,int &num);
};
//Other Generator Classes
//******************* More of the same here followed by this list class.
class Generators
{
public :
Generators();
~Generators();
Generator* operator [](int i){return gen[i];}
private :
Array<Generator*> gen;
int size;
};
- Initializing the array of generators for your grammar.
//The array of generators has a generator that corresponds to each production.
//The production number is used as subscript
Generators::Generators():gen(24,10)
{
size = 24;
for (int i = 0;i<4;i++)
gen[i] = new Generator;
// Generators for adding variables to table
gen[4] = new NewVars;//V1-> ident : type
gen[5] = new NewVars;//V1 -> ident : type;V1
for (int i = 6;i<8;i++)
gen[i] = new Generator;
// Generator for ident = E
gen[8] = new AssignGen;
// Treat if thenelse and if then
gen[9] = new IfElseGen;
gen[10] = new IfGen;
//Treat while loop
gen[11] = new WhileGen;
for (int i = 12;i<14;i++) // S1->"begin" S "end" and S1-> epsilon
gen[i] = new Generator;
// Treat the standard three address cases
gen[14] = new StandardOp; // E -> E+T
gen[16] = new StandardOp; // T -> T*F
gen[20] = new StandardOp; // C -> E relop E
// Treat the simple Transfers
gen[15] = new ChangeNonTerm;// E -> T
gen[17] = new ChangeNonTerm;// T -> F
gen[18] = new ChangeNonTerm;// F -> (E)
//Treat the use of a variable on the right-hand side
gen[19] = new OldVars;// F -> ident
// Treat the marker nonterminals
gen[21] = new CondGotoGen;//CondGoToMark -> epsilon
gen[22] = new UnCondGoToGen; // GoToMark -> epsilon
gen[23] = new BackFillGen;// Mark -> epsilon
}
- The easiest generator to understand, simply destroys the nodes that have been popped and creates a new StackNode. Remember the reduce action will fill in the appropriate new state number.
// disposes of unused nodes in case when they are not needed
void Generator::generate(IdTable &,ThreeAddressCode &,
Array<StackNode*> &s,int &num)
{
for (int i = 0;i<num;i++)
delete s[i];
num = 1;
s[0] = new StackNode(0);
}
- The production E -> E + E uses the StandardOp generate to create its code
void StandardOp::generate(IdTable &idents,ThreeAddressCode &codeGen,
Array &s,int &num)
{
// There are two operands and an operator, so pop three times
StoreNode *op2 = (StoreNode*)(s[0]);//first operand
StoreNode *op1 = (StoreNode*)(s[2]); //second operand
//Get the names of the operands and operator
String op1Name = op1->seeName();
String type1 = idents.getType(op1Name);
String op2Name = op2->seeName();
String type2 = idents.getType(op2Name);
String opName;//holds operator depends on the actionNumber
StoreNode *op = (StoreNode*)(s[1]);
opName = op->seeName();
// Dispose of stack nodes since we wont need them again
for (int i = 0;i<num;i++)
delete s[i];
// if the operands are different types, convert the integer to real
if (type1 != type2)
coerce(op1Name,op2Name,type1,type2,codeGen,idents);
//Generate the code for this operation
String leftSide = codeGen.genName();//Get a temperary storage location
idents.insert(leftSide,type1);
//Insert the code
codeGen.gen(leftSide + String(" := ")+op1Name + opName + op2Name);
//Update the parse stack with the new information
s[0] = new StoreNode(0,leftSide,type1);//state is inserted in reduce
num = 1;
}