class StateEntry
{
public:
StateEntry(int pn=0,int p = 0){_productNumber = pn; _position = p;}
int productNumber()const {return _productNumber;}
int position()const {return _position;}
ostream& print(ostream &s,const CodeArray &code,const LookUpTable &lookUp)const ;
int operator != (const StateEntry &se)
{return (se._productNumber != _productNumber) || (se._position != _position);}
int operator == (const StateEntry &se)
{return (se._productNumber == _productNumber) && (se._position == _position);}
private:
int _productNumber;
int _position;
};
class ProductState
{
public:
ProductState(){_size = 0;}
int insert(const StateEntry &se){entries[_size++] = se;return _size -1;}
int size()const {return _size;}
StateEntry& operator [](int i){return entries[i];}
StateEntry operator [](int i)const {return entries[i];}
void insert(int pNum,int pos){entries[_size++] = StateEntry(pNum,pos);}
int operator != (const ProductState &s)const
{return (s._size != _size)|| (s.entries != entries);}
int operator == (const ProductState &s) const
{return (s._size == _size)&& (s.entries == entries);}
int getNextStateCores(const CodeArray &code, Array<ProductState> &cores);
void closure(const CodeArray &code,int numProds, const LookUpTable &lookUp);
void print(ostream &s,const CodeArray &code, const LookUpTable &lookUp)const ;
int getTransSym(const CodeArray &code)const ;
//retrieves grammar item that caused shift to this state
private:
Entries entries;
int _size;
};
int ProductState::getNextStateCores(const CodeArray &code, StateArray &cores)
{
MySet entriesUsed(_size);
entriesUsed +=0;
int coreSize = 0; // nothing in the core
int currentEntry = 0;// subscript of entry under consideration
while (currentEntry < _size)
{
int pNum = entries[currentEntry].productNumber();
int pos = entries[currentEntry].position();
if (pos < code[pNum].length())
{
ProductState testState;
testState.insert(pNum,pos+1);
int sym = code[pNum].getSymI(pos);
currentEntry++;
for(int count = currentEntry;count<_size;count++)
{
pNum = entries[count].productNumber();
pos = entries[count].position();
if (!entriesUsed[count])
if(code[pNum].length() > pos &&
sym == code[pNum].getSymI(pos))
{
entriesUsed += count;
testState.insert(pNum,pos+1);
}
}
cores[coreSize++]=testState;
}
else
currentEntry++;
while (entriesUsed[currentEntry]&¤tEntry<_size)
currentEntry++;
}
return coreSize;//How many cores did this state generate
}
void ProductState::closure(const CodeArray &code,int numProds, const LookUpTable &lookUp)
{
MySet newEntries(numProds);
int currentEntry = 0; // location of first entry in the initialized state
do
{
int prodNum = entries[currentEntry].productNumber();
int place = entries[currentEntry].position();
if (place < code[prodNum].length())
{
int localSym = code[prodNum].getSymI(place);
//localSym is the symbol after marker
if (lookUp[localSym]->kind()== NonTerminalToken)
{
int first;
int last;
lookUp[localSym]->getFirstLast(first,last);
for (int nextEntry = first;nextEntry <=last;nextEntry++)
{
if (! newEntries[nextEntry])
{
newEntries += nextEntry;
//not this new entry so not repeated
insert(nextEntry,0);
// increases _size by one each time
//add a new entry to state
}
}
}
}
currentEntry++; // get the next item in the state
}while (currentEntry < _size); //this continues until no more new entries
}
typedef Array<ProductState> StateArray;
void TAGCompiler::computeGoTos(ostream &out)//compute all of the states and fill in parse table
{
int currentState = 0;
do
{
StateArray cores;
int coreSize = states[currentState].getNextStateCores(code,cores);
//complete each state by getting its closure. Next, generate gotos
// for the current state. All gotos must goto one of the states in
// the cores. So after insertion, goto will go to numStates-1
for(int count = 0;count < coreSize;count++)
{
cores[count].closure(code,numProduct,lookUp);//complete the state
int lSym = cores[count].getTransSym(code);
int stateNum = states.member(cores[count]);
//if found member returns subscript where found otherwise returns
// numStates the location of a new state
int newState =0;//need to know if there is a new state
if (stateNum==numStates)
//if we have a new state add it and compute gotos
{
states.addState(cores[count]);
//add a row to the gotos
gotos.addRow();
//this row reprents the new state and is not being filled here
numStates++;
#ifdef TRACE_STATES
out<<"State "<<stateNum<<endl;
cores[count].print(out,code,lookUp);
//show each state as it is created
#endif
newState =1;
}
if (gotos.value(currentState,lSym)!= -1)
{
cerr<<"Gotos["<<currentState<<<", "<<lookUp.getLexeme(lSym)
<<"] is ambiguous. Filled with a shift or goto\n";
#ifdef TRACE_STATES
out<<"Gotos["<<currentState<<", "<<lookUp.getLexeme(lSym)
<<"] is ambiguous. Filled with a shift or goto\n";
#endif
}
if (lookUp[lSym]->kind()==TerminalToken)
gotos.addAction(currentState,lSym,stateNum,lSym,ShiftAct,code);
else
gotos.addAction(currentState,lSym,stateNum,lSym,GotoAct,code);
if (newState)
addReduces(states[stateNum],stateNum,out);
}
currentState++;
}while (currentState < numStates);
}
void TAGCompiler::addReduces(ProductState nextState,int gnum, ostream &out)
{
for (int entNum = 0;entNum<nextState.size();entNum++)
{
int pos = nextState[entNum].position();
int pNum = nextState[entNum].productNumber();
if (pos == code[pNum].length()) //at the end of a production - generate reduces
{
for (int count = 0;count < numTokens;count++)
{
if (follows[code[pNum].left()].contains(count))
{
if (gotos.value(gnum,count) != -1)
//this is an ambiguous state issue warning
{
cerr<<"Replacing shift operation in gotos["
<<gnum<<", "
<< count<<"] with a reduce operation\n" ;
#ifdef TRACE_STATES
out<<"Replacing shift operation in gotos["
<<gnum<<", " << count
<<"] with a reduce operation\n" ;
#endif
}
if (gnum >1)//add a reduce to the row
gotos.addAction(gnum,count,pNum,0,ReduceAct,code);
else //compile is successful
gotos.addAction(gnum,count,pNum,0,AcceptAct,code);
}
}
}
}
}
The actual actions are stored as members of one of a set of classes that are descendents of a base class SLRAction defined here.
enum ActionValue {ErrorAct,ShiftAct,ReduceAct,GotoAct,AcceptAct, Action};
// SLRAction is a purely virtual class representing the actions in an SLR
// parse table. Each such entry will have a virtual function action to
// carry out the requirements of the SLR compiler.
class ActionArray; Forward declaration
class SLRAction
{
public:
SLRAction(int a=-1){actionNumber = a;}
ActionValue kind()const {return Action;}
virtual int action(StateStack&,const ActionArray&,Lexical &,
IdTable &,ThreeAddressCode &)const =0;
int value(){return actionNumber;}
// actions taken on StateStack depend on input token
// nature of action depends on descendent of SLRAction
static SLRAction* create(ActionValue a,int val,int tok,const CodeArray &code);
virtual ostream& print(ostream &s,const CodeArray &code,
String *vals,const LookUpTable &l)const
{return s<<actionNumber<<" ";}
protected:
int actionNumber;
virtual SLRAction* clone(int val,int tok,const CodeArray &code)=0;
};
class ErrorAction :public SLRAction
{
public:
ErrorAction(int s=-1):SLRAction(s){}
ActionValue kind()const {return ErrorAct;}
virtual int action(StateStack&,const ActionArray&,Lexical &,
IdTable &,ThreeAddressCode &)const
{cout<< "error"<<endl;return -1;}
virtual ostream& print(ostream &s,const CodeArray &code , String *vals,
const LookUpTable &l)const
{return s;}
private:
virtual SLRAction* clone(int val,int,const CodeArray &code)
{return new ErrorAction(val);}
};
class ShiftAction :public SLRAction
{
public:
ShiftAction(int s=-1,int t=-1):SLRAction(s){token = t;}
ActionValue kind()const {return ShiftAct;}
virtual int action(StateStack&,const ActionArray&,Lexical &,
IdTable &,ThreeAddressCode &)const ;
virtual ostream& print(ostream &s,const CodeArray &code,
String *vals,const LookUpTable &l)const
{s<<"\tshift " ;
SLRAction::print(s,code,vals,l);
s<<endl; return s;}
private:
virtual SLRAction* clone(int val,int tok,const CodeArray &code)
{return new ShiftAction(val,tok);}
int token;
};
class ReduceAction :public SLRAction
{
public :
ReduceAction(int s=-1,int pNum=0, int pSym=0 )
:SLRAction(s){popNum = pNum; pushSym = pSym;}
ActionValue kind()const {return ReduceAct;}
virtual int action(StateStack&,const ActionArray&,Lexical &,
IdTable &,ThreeAddressCode &)const ;
virtual ostream& print(ostream &s,const CodeArray &code,
String *vals,const LookUpTable &l)const
{s<<'\t' <<'\t' <<"reduce by " <<actionNumber<<' ';
code[actionNumber].print(s,l);s<<endl;return s;}
private:
virtual SLRAction* clone(int val,int,const CodeArray &code)
{return new ReduceAction(val,code[val].length(),code[val].left());}
int popNum;
int pushSym;
static Generators generators;
};
class GotoAction :public SLRAction
{
public:
GotoAction(int s=-1):SLRAction(s){}
ActionValue kind()const {return GotoAct;}
virtual int action(StateStack&,const ActionArray&,Lexical &,
IdTable &,ThreeAddressCode &)const {return actionNumber;}
virtual ostream& print(ostream &s,const CodeArray &code,
String *vals,const LookUpTable &l)const
{s<<"goto " ;
return SLRAction::print(s,code,vals,l);}
private:
virtual SLRAction* clone(int val,int,const CodeArray &code)
{return new GotoAction(val);}
};
class AcceptAction :public SLRAction
{
public:
AcceptAction():SLRAction(1){}
ActionValue kind()const {return AcceptAct;}
virtual int action(StateStack&,const ActionArray&,Lexical &,
IdTable &,ThreeAddressCode &)const
{cout << "Parse completed successfully " <<endl;
return -1;}
virtual ostream& print(ostream &s,const CodeArray &code,
String *vals,const LookUpTable &l)const
{s<<"accept " ;
return SLRAction::print(s,code,vals,l);}
private :
virtual SLRAction* clone(int ,int ,const CodeArray &)
{return new AcceptAction;}
};
typedef SLRAction * ActionPtr;
typedef Array<ActionPtr> Row;
class ActionArray
{
public :
ActionArray(int nc =0):acts(0,1){numRows = 0;numColumns = nc;}
int addRow();
void setRowWidth(int c){numColumns = c;}
int value(int r,int c)const {return acts[r][c]->value();}
ActionPtr& act(int row,int column)const ;//retrieve the action found in row and column
void addAction(int row,int column,int val,int tok, ActionValue act,
const CodeArray &code);//changes to a new action
void Execute(ostream &out,const CodeArray &code,const LookUpTable &l,
String vals[]);
ostream& print(ostream &s,const CodeArray &code,
String *vals,const LookUpTable &l)const ;
private :
Array<Row> acts;
int numRows;
int numColumns;
};