srmain.cpp

lex files for given decription used as assignment in compiler design

//IIT2006021
//Arunanshu Pandey
#include<iostream>
#include<string>
#include<list>
#include<vector>
#include<algorithm>
#include<stack>
#include<fstream>
using namespace std;

                  //Class Declaration

class Production
{
	public:
		char lhs;//left hand side
		string rhs;//right hand side

		Production(string s1,string s2)
		{
			lhs = s1[0];
			rhs = s2;
		}

};


class DisplayTable
{
	public:
      // Construction of Output Table
		string oStack,oinput_buffer,oAction;

		DisplayTable(string s1,string s2,string s3)
		{
			oStack       = s1;
			oinput_buffer    = s2;
			oAction      = s3;
		}

};


class CurrentState
{

	public:
      // Pointer that points current state
       // a saved state from avoiding data hinderance of the table
		string      csStack,cslPBuffer;
		vector<DisplayTable*> csOutput;

		CurrentState(string s1,string s2,vector<DisplayTable*> s3)
		{
			csStack = s1;
			cslPBuffer = s2;
			csOutput = s3;

		}

};

class ShiftReduce
{
   bool accept;                // semaphore to track grammer accepted      
   vector<Production*>   grammer;      // LHS and RHS
   vector<DisplayTable*> output;       // Stack input_buffer Action
   string localStack,localinput_buffer;// temporary Stack and input_buffer
   char start_symbol;                  // start symbol
   stack<CurrentState*> current_state; //CurrentState stack
   
   // Append Grammer from Input File
   bool appendGrammer(string p)
   {
	  string::size_type cp,lpos;
	   string lhs,rhs;
    // Case : E->
	 if((lpos = p.find_first_of("->"))==string::npos)
		return false;
    
    // LHS Character Extraction
      Production* prod_var;
       lhs = p.substr(0,lpos);
    // RHS Character Extraction (leaving characters "->")
       string temp = p.substr(lpos+2);
    // Case : E->E+T|T
	 while((cp = temp.find_first_of("|")) != string::npos)
	 {
		rhs = temp.substr(0,cp);
		temp = temp.substr(cp+1);    //leaving character "|"
		prod_var = new Production(lhs,rhs);
		grammer.push_back(prod_var);//Saving 1)E->E+T 2)E->T
	 }
    //Saving the Remaining
	   prod_var = new Production(lhs,temp);
	   grammer.push_back(prod_var);
	
    return true;
   }
   
   //BackTrack Algorithm
   void backtrackProduction(void)
   {
   //updating the Current State and pushing it to stack
	CurrentState* state_backup = new CurrentState(localStack,localinput_buffer,output);
    current_state.push(state_backup);
    
   // other variable declaration
	CurrentState* temp;
	DisplayTable* optmp;
	 
	while((!current_state.empty()) && (!accept))
    {
     // retrieving TOS in state_backup and removing it from STACK
     state_backup = current_state.top();
  	 current_state.pop();
	 localStack = state_backup->csStack;
	 localinput_buffer = state_backup->cslPBuffer;
	 output = state_backup->csOutput;
        		
	 // Searching Table Begins Here
     if(isAccept())
     {
	  accept = true;
	  optmp = new DisplayTable(localStack,localinput_buffer,"ACCEPT");
	  output.push_back(optmp);
	   break;
     }		
     //localinput_buffer.size()>1 implies id$
     // First Time Methodology must be shift operation only
     // Process it & backup in stack
	 else if(localinput_buffer.size()>1)
	 {
      optmp = new DisplayTable(localStack,localinput_buffer,"SHIFT");
	   output.push_back(optmp);
		
	  //shift() updates CurrentState by capturing a single string
	  	     shift();
	  // update current_state
	  temp = new CurrentState(localStack,localinput_buffer,output);
	  current_state.push(temp);
	  localStack = state_backup->csStack;
	  localinput_buffer = state_backup->cslPBuffer;
	  output = state_backup->csOutput;
	 }
	// rhstr =  A String of Pointers that has all LHS 
     vector<string>* rhstr;
	 for(int i=1;i<localStack.size();i++)
	 {
      // id+id$ => 1)id 2)id+ 3)id+id
	  rhstr = searchLeftString(localStack.substr(localStack.size()-i));
	  if(rhstr->empty());//no production for.eg. id+
	  else
      {
	   for(int j=0;j<rhstr->size();j++)
	   {
	    optmp = new DisplayTable(localStack,localinput_buffer,"REDUCE");
	    output.push_back(optmp);
	 		reduce(i,rhstr->at(j));
		temp = new CurrentState(localStack,localinput_buffer,output);
		current_state.push(temp);

        localStack = state_backup->csStack;
        localinput_buffer = state_backup->cslPBuffer;
        output = state_backup->csOutput;
       }
      }
     }
    }
    if(!accept)
    {
  	  optmp = new DisplayTable(localStack,localinput_buffer,"REJECT");
      output.push_back(optmp);
    }
   }
    // this module searches for the correspondng LHS of a production
    vector<string>* searchLeftString(string rhs)
    {
	  vector<string>* lhs_pointer = new vector<string>();
	  for(int i=0;i<grammer.size();i++)
	  {
		if(grammer[i]->rhs == rhs)
		{
			string f=" ";
			f[0] = grammer[i]->lhs;
            // getting LHS for given RHS
             // getting all productions that are derived from LHS
			if(   find(lhs_pointer->begin(),lhs_pointer->end(),f)  ==    lhs_pointer->end() )
				lhs_pointer->push_back(f);
		}
	  }
	return lhs_pointer;
   }
   
   void shift(void)
   {
	localStack.append(localinput_buffer.substr(0,1));
	localinput_buffer = localinput_buffer.substr(1);
   }
   
   void reduce(int rhsize,string rls)
   {
   // rhsize = pointer that the reduce is tracking
	rhsize = localStack.size()-rhsize;
	localStack = localStack.substr(0,rhsize);
	localStack.append(rls);
   }
   
   bool isAccept(void)
   {
    // input_buffer = $; Stack = $<start_symbol>
	 if((localinput_buffer.size() == 1)   &&
		(localStack.size()==2)&&(localStack[localStack.size()-1] == start_symbol))
	 return true;
	return false;
   }
   /*bool isReject(void)
   {
	  if((localinput_buffer.size() == 1)  &&  
        ((localStack.size()!=2)||(localStack[localStack.size()-1] != start_symbol))   )
	  return true;
	 return false;
    }//since REJECT needs more critereon it is not included*/
    
   void displaySRTable(void)
   {
	cout<<"\tSTACK\t"<<"\tInput BUFFER\t"<<"\tACTION\t\n\n";
	for(int i=0;i<output.size();i++)
	{
		if(output[i]->oinput_buffer.size()<8)
			cout<<"\t"<< output[i]->oStack <<"\t"<<"\t"<< output[i]->oinput_buffer <<"\t\t"<<"\t"<< output[i]->oAction <<"\t"<<"\n";
		else
			cout<<"\t"<< output[i]->oStack <<"\t"<<"\t"<< output[i]->oinput_buffer <<"\t"<<"\t"<< output[i]->oAction <<"\t"<<"\n";
	}
	if(accept)
		cout<<"\n\nACCEPTED";
	else
		cout<<"\n\nREJECTED";
  }
  public:
   ShiftReduce()
   {
     fstream in;
     string iFile,buffer;
     this->accept = false;
      
     cout<<"INPUT FILE : ";cin>>iFile;
     in.open(iFile.c_str(),ios::in);
     if(!in)
       cerr<<"\nNo Input file Found!";
     else
     {
	   cout<<"Input string: ";cin>>this->localinput_buffer;
       in>>buffer;
	   this->start_symbol = buffer[0];
	   
       while(!in.eof())
	   {
	    in>>buffer;
	    appendGrammer(buffer);
	   }
	   
	   this->localStack.append("$");
  	   this->localinput_buffer.append("$");
	  
       backtrackProduction();
	   displaySRTable();
     }
   }
};
int main()
{	
    ShiftReduce s;
//	getch();
	return 1;
}