程序代码如下：
#include <cstdio> #include <set> #include <cstdlib> #include <cctype> #include <functional> #include <cmath> #include <cstring> #include <string> #include <queue> #include <stack> #include <iostream> #include <vector> #include <map> #include <algorithm> #define esp 1e-6 using namespace std; const int maxn = 1e5 + 7, mod = 1e9 + 7; int prio_table[300][300]; vector<char>VN; vector<char>VT; bool vis_VN[30]; bool vis_VT[300]; bool LL_flag=true; void init_visit() { for(int i=0;i<26;i++) vis_VN[i]=true; for(int i=0;i<300;i++) vis_VT[i]=true; for(int i=0;i<300;i++) for(int j=0;j<300;j++) { prio_table[i][j]=-2; } } map<char,vector<string> >mp;//用来存文法 bool is_VN(char x)//判断是否是非终结符 { if(x>='A'&&x<='Z') return true; else return false; } bool is_VT(char x) { return !is_VN(x); } set<char> FIRSTVT(char vnch) { set<char>ans; for(int i=0;i<mp[vnch].size();i++) { string s=mp[vnch][i]; if(!is_VN(s[0])) ans.insert(s[0]); else { if(s.length()>1) ans.insert(s[1]); if(s[0]!=vnch) { set<char>ss=FIRSTVT(s[0]); set<char>::iterator it; for(it=ss.begin();it!=ss.end();it++) { ans.insert(*it); } } } } return ans; } set<char> LASTVT(char vnch) { set<char>ans; for(int i=0;i<mp[vnch].size();i++) { string s=mp[vnch][i]; int s_end=s.length()-1; if(!is_VN(s[s_end])) { ans.insert(s[s_end]); } else { if(s_end>0) ans.insert(s[s_end-1]); if(s[s_end]!=vnch) { set<char>ss=LASTVT(s[s_end]); set<char>::iterator it; for(it=ss.begin();it!=ss.end();it++) { ans.insert(*it); } } } } return ans; } void show_FIRSTVT() { for(int i=0;i<VN.size();i++) { cout<<VN[i]<<" : "; set<char>::iterator it; set<char>ss=FIRSTVT(VN[i]); for(it=ss.begin();it!=ss.end();it++) { cout<<(*it)<<" "; } cout<<endl; } } void show_LASTVT() { cout<<"LASTVT:"<<endl; for(int i=0;i<VN.size();i++) { cout<<VN[i]<<" : "; set<char>::iterator it; set<char>ss=LASTVT(VN[i]); for(it=ss.begin();it!=ss.end();it++) { cout<<(*it)<<" "; } cout<<endl; } } void build_prio_table() { char chf='#'; set<char>::iterator itf; set<char>ss1=FIRSTVT(VN[0]); for(itf=ss1.begin();itf!=ss1.end();itf++) { prio_table[(int)chf][(*itf)]=-1; } set<char>ss2=LASTVT(VN[0]); for(itf=ss2.begin();itf!=ss2.end();itf++) { prio_table[(*itf)][(int)chf]=1; } prio_table[(int)chf][(int)chf]=0; for(int i=0;i<VN.size();i++) { for(int j=0;j<mp[VN[i]].size();j++) { string s=mp[VN[i]][j]; for(int k=0;k<s.length();k++) { if(is_VT(s[k])&&k+1<s.length()&&is_VT(s[k+1]))//...ab... prio_table[s[k]][s[k+1]]=0; if(is_VT(s[k])&&k+2<s.length()&&is_VN(s[k+1])&&is_VT(s[k+2]))//...aNb... prio_table[s[k]][s[k+2]]=0; if(is_VT(s[k])&&k+1<s.length()&&is_VN(s[k+1]))//...aN... { set<char>first=FIRSTVT(s[k+1]); set<char>::iterator it; for(it=first.begin();it!=first.end();it++) { prio_table[s[k]][(*it)]=-1; } } if(is_VN(s[k])&&k+1<s.length()&&is_VT(s[k+1]))//...Na... { set<char>last=LASTVT(s[k]); set<char>::iterator it; for(it=last.begin();it!=last.end();it++) { prio_table[(*it)][s[k+1]]=1; } } } } } } void show_prio_table() { cout<<"优先表如下："<<endl; cout<<" "; for(int i=0;i<VT.size();i++) printf("%10c",VT[i]); cout<<endl; for(int i=0;i<VT.size();i++) { cout<<VT[i]; for(int j=0;j<VT.size();j++) { cout<<" "; if(prio_table[VT[i]][VT[j]]==1) cout<<">"; else if(prio_table[VT[i]][VT[j]]==0) cout<<"="; else if(prio_table[VT[i]][VT[j]]==-1) cout<<"<"; else cout<<" "; } cout<<endl; } } set<string>scome; int main() { init_visit(); int k=1; char vn; string str; while(cin>>vn&&vn!='#'&&cin>>str) { if(vis_VN[vn-'A']==true)//不重复存vn { VN.push_back(vn); vis_VN[vn-'A']=false; } mp[vn].push_back(str);//代表vn可以推导出str for(int i=0;i<str.size();i++) { if(!is_VN(str[i])&&vis_VT[(int)str[i]]==true&&str[i]!='0') { VT.push_back(str[i]); vis_VT[(int)str[i]]=false; } } string sf=str; for(int i=0;i<sf.length();i++) { if(is_VN(sf[i])) sf[i]='N'; } scome.insert(sf); } VT.push_back('#'); show_FIRSTVT(); show_LASTVT(); build_prio_table(); show_prio_table(); cout<<"input a string"<<endl; string checkstr; while(cin>>checkstr) { string stackstr="#"; checkstr+='#'; while(stackstr!="#N#") { cout<<stackstr; for(int i=1;i<30-stackstr.length()-checkstr.length();i++) cout<<" "; cout<<checkstr<<endl; char ch=checkstr[0]; //无优先关系，error if((is_VN(stackstr[stackstr.length()-1])&&prio_table[stackstr[stackstr.length()-2]][ch]==-2)||(is_VT(stackstr[stackstr.length()-1])&&prio_table[stackstr[stackstr.length()-1]][ch]==-2)) { cout<<"error"<<endl; break; } //移入 if((is_VT(stackstr[stackstr.length()-1])&&prio_table[stackstr[stackstr.length()-1]][ch]<=0)||(is_VN(stackstr[stackstr.length()-1])&&prio_table[stackstr[stackstr.length()-2]][ch]<=0)) { stackstr+=ch; checkstr.erase(checkstr.begin()); } else { string test=""; int strend=stackstr.length()-1; if(is_VN(stackstr[strend])) { strend--; } int j; for(j=strend-1;j>=0;j--) { if(is_VN(stackstr[j])) { j--; if(prio_table[stackstr[j]][stackstr[j+2]]==-1) { break; } } else { if(prio_table[stackstr[j]][stackstr[j+1]]==-1) { break; } } } for(int k=j+1;k<stackstr.length();k++) test+=stackstr[k]; if(scome.count(test)==0) { cout<<"error"<<endl; break; } stackstr.erase(stackstr.begin()+j+1,stackstr.end()); stackstr+='N'; } } if(stackstr=="#N#") cout<<"OK"<<endl; cout<<"input a string"<<endl; } return 0; }
样例：
E E+T E E-T E T T T*F T T/F T F F (E) F i # E E+T E T T T*F T F F P!F F P P i P (E) #