abc.txt

消除文法左递规算法的实现left eliminate grammar rules delivery algorithm implementation

#include <iostream> 
#include <string> 
#include <vector> 
using namespace std;

struct Rule
{
string left;   //规则左部,因为输入的为2型文法,
string right;   //规则右部
};

struct RuleDat
{
string left;
vector <string> right;
};


class RemoveLRec
{
private:
vector<Rule> grammar;      //文法
Rule rul;         //规则
vector<string> Dleft;   
vector<RuleDat> grammardata;  
RuleDat ruledata;


public:
RemoveLRec(){}
~RemoveLRec(){}
void ChangeInput (string input);   //输入分析
void Show();        //
void RemoveDirect();      //消除直接左递归
void RemoveIndirect();      //消除间接左递归
void DataChange (int C);     //存储结构转换
void RuleClean();       //清理无用规则
};
////////////////////////////////////////////////////////

//#include "RemoveLRec.h"

void RemoveLRec::ChangeInput (string input)   //扫描字符串,遇到'-'停止,
{               //并跳两格
int help1=0;
rul.left.erase();
rul.right.erase();
for (int i=0; i<input.size();i++)
{
   if (input[i]=='-')
   {
    help1=i;
    break;
   
   }
   rul.left+=input[i];
   //rule.left.push_back (input.at(i));
   //cout<<"******";
}
//cout<<help1;
if (help1!=1)
{
   cout<<"不符合要求!!";
   exit(0);
}

help1=help1+2;
for (i=help1;i<input.size();i++)
{
   rul.right+=input[i];
  
}
   grammar.push_back(rul);

}


/******************************************/

void RemoveLRec::RemoveDirect()
{
string Z="\'";
string C;
int l=0;
Dleft.clear();
int i,j;
for ( i=0; i<grammar.size(); i++)
{
   if (grammar[i].right.size() == 1) continue;
   if (grammar[i].right.find (grammar[i].left) == 0)//查找右部是否含有左部的非终结符
   {
    l=0;
    for ( j=0;j<Dleft.size(); j++)
     if ( Dleft[j] == grammar[i].left)
      l=1;
    if (l==0)
     Dleft.push_back (grammar[i].left);//规则右部放入一组向量里
    l=0;
   }
}
for ( i=0; i<grammar.size(); i++)
{
   for ( j=0;j<Dleft.size(); j++)
   {
    if (grammar[i].left == Dleft[j])
    {
     C = grammar[i].left + Z;
     if (grammar[i].right.find (grammar[i].left)!= 0)
      grammar[i].right += C;
     else 
     {
      grammar[i].right = grammar[i].right.substr (1);
      grammar[i].right += C;
      grammar[i].left += Z;
     }
     

    }
   }

}
for (j=0;j<Dleft.size(); j++)
{
   rul.left.erase ();
   rul.right.erase ();
   rul.left = Dleft[j] + Z;
   rul.right = "\0";
   grammar.push_back (rul);

}
rul.left.erase ();
rul.right.erase ();
}


void RemoveLRec::RemoveIndirect()
{
 int l=0;
 int i,j;
for ( i=0; i<grammar.size(); i++)
{
   for ( j=0;j<Dleft.size(); j++)
    if ( Dleft[j] == grammar[i].left)
    l=1;
   if (l==0)
   {
    Dleft.push_back (grammar[i].left);
   }
   l=0;
}
 string help;
DataChange (0);
for ( i=0; i<grammardata.size(); i++)
   for ( j=0; j<i; j++)
   {
    for (int k=0; k<grammardata[i].right.size(); k++)
    {
    
     if (grammardata[i].right.at(k).find (grammardata[j].left) == 0)
     {
     
      {
       for (int p=0; p<grammardata[j].right.size(); p++)
       {
        help.erase();
        help=grammardata[j].right.at(p) + grammardata[i].right.at(k).substr (1);
        grammardata[i].right.push_back (help);
       }
       vector<string>::iterator itr = grammardata[i].right.begin();
       while (itr != grammardata[i].right.end())
       {
        if (*itr == grammardata[i].right.at(k) )
        grammardata[i].right.erase(itr);
        ++itr;
       }
      } 
     }
    }
   }
DataChange (1);

}


void RemoveLRec::DataChange (int C)
{ 
int i,j;
if (C==0)
{
   int l=0;
   grammardata.clear();
   ruledata.left.erase();
   ruledata.right.clear();
   ruledata.left = grammar[0].left;
   ruledata.right.push_back (grammar[0].right);
   grammardata.push_back (ruledata);
   for ( i=1; i<grammar.size(); i++)     //存储转换
   {
    for ( j=0; j<grammardata.size(); j++)
    {
     if (grammar[i].left == grammardata[j].left)
     {
      grammardata[j].right.push_back (grammar[i].right);
      l=1;
      break;
     }
    }
    if (l==0)
    {
     ruledata.left.erase();
     ruledata.right.clear();
     ruledata.left = grammar[i].left;
     ruledata.right.push_back (grammar[i].right);
     grammardata.push_back (ruledata);
    }
    l=0;
   }
}
if (C==1)
{
   grammar.clear();
   for ( i=0; i<grammardata.size(); i++)
// for (i=grammardata.size()-1; i>=0; i--)
   {
    rul.left.erase();
    rul.right.erase();
    rul.left = grammardata[i].left;
    for ( j=0; j<grammardata[i].right.size(); j++)
    {
     rul.right = grammardata[i].right.at(j);
     grammar.push_back (rul);
    }
   }
}



}


void RemoveLRec::RuleClean()
{
int l=0;
int i,j;
vector<string> help1 ,help2;
DataChange (0);         //用复杂的数据存储方式
for ( i=grammardata.size()-1; i>0; i--)
   help1.push_back (grammardata[i].left);
for ( i=1; i<help1.size(); i++)
{
   l=0;
   for ( j=0; j<grammardata[0].right.size(); j++)
   { 
    if (grammardata[0].right.at(j).find (help1[i]) == string::npos )
     l=1;
    else{
     l=0; break;
    }
   }
   if (l==0)
   {
    vector<string>::iterator itr = &help1[i];
    help2.push_back (help1[i]);
    help1.erase(itr);
   }
}
for ( i=0; i<help2.size(); i++)
{
   for ( j=0; j<grammardata.size(); j++)
   {
    if (help2[i] == grammardata[j].left)
     for (int k=0; k<grammardata[j].right.size(); k++)
     { 
      l=0;
      for (int p=0; p<help1.size(); p++)
      {
       if (grammardata[j].right.at(k).find (help1[p]) == string::npos )
        l=1;
       else{l=0; break;}
      }
      if (l==0)
      {
       vector<string>::iterator itr = &help1[p];
       help2.push_back (help1[p]);
       help1.erase(itr);
      }  
     }   
   }
}
for ( i=0; i<help1.size(); i++)
   for ( j=0; j<grammardata.size(); j++)
   {
    if (help1[i] == grammardata[j].left)
    {
     vector<RuleDat>::iterator itr =&grammardata[j] ;
     grammardata.erase(itr);
    } 
   }
DataChange (1);
}

/******************************************/
void RemoveLRec::Show()
{int i;
cout<<"输入的文法为:"<<endl;
for ( i=0; i<grammar.size(); i++)
   cout<<grammar[i].left<<"\t-->\t"<<grammar[i].right<<endl;
RemoveIndirect();
RemoveDirect();
/*********************************************
cout<<"辅助数据为:"<<endl;
for ( i=0; i<grammardata.size(); i++)
{
    cout<<grammardata[i].left<<endl;
   for (int j=0; j<grammardata[i].right.size(); j++)
    cout<<"\t--> "<<grammardata[i].right.at(j)<<endl;
}*/
// for (i=0; i<Dleft.size(); i++)
//   cout<<Dleft[i]<<" ";
RuleClean();
cout<<"************************************"<<endl;
cout<<"转化的文法为:"<<endl;
for ( i=0; i<grammar.size(); i++)
   cout<<grammar[i].left<<"\t-->\t"<<grammar[i].right<<endl;

// cout<<"**"<<grammardata.size()<<endl;


}

///////////////////////////////////////////////////

//#include "RemoveLRec.h"
void main()
{
int num=1;
string input;
RemoveLRec rlr;
char v;
int N;
cout<<"个数:";
cin>>N;
cout<<"请输入规则:"<<endl; 
for (int i=0; i<N; i++)
{
   input.erase();
   cin>>input;
  getline(cin,input); 
   rlr.ChangeInput(input);
}
   while (num==1)
{
   input.erase();
   cout<<"请输入规则:"<<endl; 
   getline(cin,input); 



   rlr.ChangeInput(input);
   cout<<"继续输入吗?(Y/N)";
   cin>>v;
   cin.ignore(1,'\n');
   if (v=='N')
    num=0;
}

rlr.Show();
}