文法化简 消除空产生式 单元产生式 消除无用符号

#include<bits/stdc++.h> using namespace std; #define endl "\n" class st { public: char left; string right; int isinV_= 0; }; char start; char V[50],V_[50],V1[50]; char T[50],T1[50]; char unit1[10],unit2[10]; int unit2_num,unit1_num; st s0[10],s1[10],s[50],s2[50]; int vnum=0,tnum=0,pnum=0,count1=0,count2=0,count3=0,count4=0,count5,new1,countf; int isinT(char n) { for(int i = 0;i<tnum;i++) { if(T[i] == n) return 1; } return 0; } int isinT1(char n) { for(int i = 0;i<count5;i++) { if(T1[i] == n) return 1; } return 0; } int f_isinV(char n) { for(int i =0;i < vnum;i++) { if(V[i] == n) return 1; } return 0; } int f_isinV_(char n) { for(int i =0;i < count2;i++) { if(V_[i] == n) return 1; } return 0; } int f_isinV1(char n) { for(int i =0;i < count4;i++) { if(V1[i] == n) return 1; } return 0; } void update() { for(int i = 0;i<new1;i++) { if(f_isinV_(s[i].left)) { int flag = 1; for(int j=0;j<s[i].right.length();j++) { if(!(isinT(s[i].right[j])||f_isinV_(s[i].right[j]))) flag = 0; } if(flag==1) s1[count3++] = s[i]; //s1为第二类过滤后的产生式 个数count3 // cout<<s[i].left<<" "<<s[i].right<<endl; } } } void update1() { for(int i = 0;i<count3;i++) { if(f_isinV1(s1[i].left)) { s2[countf++] = s1[i]; // cout<<s[i].left<<" "<<s[i].right<<endl; } } } int main() { cout<<"Enter V num:"<<endl; cin>>vnum; cout<<"Enter V:"<<endl; for(int i =0;i<vnum;i++) cin>>V[i]; cout<<"Enter start:"<<endl; cin>>start; cout<<"Enter T num:"<<endl; cin>>tnum; cout<<"Enter T:"<<endl; for(int i =0;i<tnum;i++) cin>>T[i]; cout<<"Enter production num:"<<endl; cin>>pnum; cout<<"Enter production"<<endl; for(int i =0;i<pnum;i++) { cin>>s0[i].left; cin>>s0[i].right; count1++; } for(int i =0;i<pnum;i++) { if(s0[i].right.length() == 1 && f_isinV(s0[i].right[0])) { unit1[unit1_num++] = s0[i].left; unit2[unit2_num++] = s0[i].right[0]; } if(!(s0[i].right.length() == 1 && f_isinV(s0[i].right[0]))) //unit { s[new1++] = s0[i]; } } for(int i =0;i<unit1_num;i++) { char tu1 = unit1[i]; char tu2 = unit2[i]; int tu2_c = 0; string a[100]; for(int j=0;j<pnum;j++) { if(s0[j].left == tu2) { a[tu2_c++] = s0[j].right; } } for(int j=0;j<tu2_c;j++) { st tmp; tmp.left = tu1; tmp.right = a[j]; s[new1++] = tmp; } } //此时s存放消除单元产生式后的产生式，new1是其个数 cout<<endl<<"消除单元产生式后:"<<endl; for(int i=0;i<new1;i++) { cout<<s[i].left<<"->"<<s[i].right<<endl; } //消除第二类（推导不出） for(int i =0;i<new1;i++) { int flag = 1; for(int j=0;j<s[i].right.length();j++) { if(!isinT(s[i].right[j])) flag = 0; } if(flag == 1) { s[i].isinV_ = 1; V_[count2++] = s[i].left; } } int ll = 50; while(ll) { for(int i =0;i<new1;i++) { if(!s[i].isinV_) { int flag = 1; for(int j=0;j<s[i].right.length();j++) { if(!(isinT(s[i].right[j]) || f_isinV_(s[i].right[j]))) flag = 0; } if(flag == 1) { if(!f_isinV_(s[i].left)) { s[i].isinV_ = 1; V_[count2++] = s[i].left; } } } } ll--; } update(); cout<<endl<<"消除第二类:"<<endl; for(int i = 0;i<count3;i++) cout<<s1[i].left<<"->"<<s1[i].right<<endl; //V_存放第二类过滤后的有效变元 //消除第一类 //V1存放第一类过滤后的有效变元 V1[count4++] = start; int lll = 50; while(lll) { for(int i =0;i<count4;i++) { for(int j=0;j<count3;j++) { if(s[j].left == V1[i]) { for(int k =0;k<s[j].right.length();k++) { { if(isinT(s[j].right[k])) { if(!isinT1(s[j].right[k])) T1[count5++] = s[j].right[k]; } if(f_isinV_(s[j].right[k])) { if(!f_isinV1(s[j].right[k])) V1[count4++] = s[j].right[k]; } } } } } } lll--; } update1(); cout<<endl<<"消除第一类，最终结果为:"<<endl; for(int i = 0;i<countf;i++) cout<<s2[i].left<<"->"<<s2[i].right<<endl; }