简单优先.txt

实现简单优先分析功能 有一定的学习作用 功能有待改进

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


class simple 
{ 
public: 
simple(); 
void clear(); 
void init(); 
bool input();//输入规则，默认第一个非终结符号为文法标识符 
void print_bool(char c); 
void print(vector<string>m);//打印布尔矩阵 
void XU_LIE();//为输入的文法符号排序 
void B_EQUAL();//求等于关系的布尔矩阵 
void B_SMALL();//求小于关系的布尔矩阵 
void B_LARGE();//求大于关系的布尔矩阵 
void B_HEAD_TAIL();//分别求head和tail的布尔矩阵 
void B_HEAD_1();//求head+ 
void B_HEAD_2();//求head* 
void B_TAIL_1();//求tail+ 
void B_TAIL_TRAN();//求tail+的转置矩阵 
void warshall(vector<string>&amt;w1,vector<string>&amt;w);//warshall算法 
void mult(vector<string>&amt;m1,vector<string>&amt;m2,vector<string>&amt;m);//矩阵的乘法 
void check();//识别程序 
bool is_simple(); 
void check_1(); 
void get_symbol();//取符号 
void relation(char c);//判断优先关系 
void find_simple();//找最左简单短语 
void GUI_YUE(int k);//规约 
void result();//打印识别的结果 
private: 
vector<char>left;//存储所有规则的左部 
vector<string>right;//存储所有规则的右部 
int n;//规则的个数 
int num;//所有文法符号的个数 
string symbol;//存储文法符号序列 
string s;//存储输入的待识别的符号串 
vector<string>B_head; 
vector<string>B_head_1; 
vector<string>B_head_2; 
vector<string>B_tail; 
vector<string>B_tail_1; 
vector<string>B_tail_tran; 
vector<string>B_equal; 
vector<string>B_small; 
vector<string>B_large; 
vector<char>B_stack;//用于实现识别程序 
int pos;//确定下一个要识别的符号的位置 
}; 


simple::simple() 
{ 
n=0; 
num=0; 
pos=0; 
B_head.clear (); 
B_head_1.clear (); 
B_head_2.clear (); 
B_tail.clear (); 
B_tail_1.clear (); 
B_tail_tran.clear (); 
B_equal.clear (); 
B_small.clear (); 
B_large.clear (); 
B_stack.clear (); 

} 

void simple::init() 
{ 
string a; 
for(int i=0;i<num;i++) 
a+='0'; 
for(i=0;i<num;i++) 
{ 
B_head.push_back (a); 
B_tail.push_back (a); 
B_tail_tran.push_back (a); 
B_equal.push_back (a); 
B_small.push_back (a); 
B_large.push_back (a); 
} 
} 
void simple::clear () 
{ 
B_stack.clear (); 
pos=0; 
} 


bool simple::input () 
{ 
cout<<"输入必须为简单优先文法。"<<endl; 
cout<<"请输入规则个数。"<<endl; 
cin>>n; 
int x=getchar(); 
for(int i=0;i<n;i++) 
{ 
cout<<"请输入规则 "<<i+1<<endl; 
cout<<"左部："; 
char c; 
while(1) 
{ 
c=getchar(); 
if(!isupper(c)) 
{ 
char x; 
while((x=getchar())!='\n'); 
cout<<"规则左部必须为非终结符号（大写字母），请重新输入。"<<endl; 
} 
else break; 
} 
left.push_back (c); 
cout<<"右部："; 
string d; 
cin>>d; 
x=getchar(); 
int y=d.find ('|'); 
int y1=0; 
while(y!=-1) 
{ 
string d1; 
for(int j=y1;j<y;j++) 
d1+=d[j]; 
right.push_back (d1); 
left.push_back (c); 
y1=y+1; 
y=d.find ('|',y1); 
} 
string d1; 
for(int j=y1;j<d.length ();j++) 
d1+=d[j]; 
right.push_back (d1); 
} 
for( i=0;i<right.size ();i++) 
for(int j=0;j<right.size ();j++) 
if(right[j]==right[i]&amt;&amt;i!=j) 
{ 
cout<<"不是简单优先文法，请重新输入。"<<endl; 
return false; 
} 
return true; 
} 

bool simple::is_simple () 
{ 

for(int i=0;i<num;i++) 
for(int j=0;j<num;j++) 
if((B_equal[i][j]=='1'&amt;&amt;B_small[i][j]=='1')||(B_equal[i][j]=='1'&amt;&amt;B_large[i][j]=='1')||(B_small[i][j]=='1'&amt;&amt;B_large[i][j]=='1')) 
{ 
cout<<"不是简单优先文法，请重新输入。"<<endl; 
return false; 
} 
return true; 
} 


void simple::XU_LIE () 
{ 
int i=0; 
symbol+=left[i++]; 
while(i<left.size ()) 
{ 
if(symbol.find (left[i])==-1) 
symbol+=left[i]; 
i++; 
} 
for(i=0;i<right.size ();i++) 
for(int j=0;j<right[i].length ();j++) 
if(!isupper(right[i][j])) 
if(symbol.find(right[i][j])==-1) 
symbol+=right[i][j]; 
num=symbol.length (); 
cout<<"该文法的所有符号次序为："<<endl; 
for(i=0;i<symbol.length ();i++) 
cout<<" "<<i+1<<"="<<symbol[i]; 
cout<<endl; 
init(); 
} 

void simple::B_EQUAL () 
{ 
for(int i=0;i<right.size ();i++) 
{ 
if(right[i].length ()==1)continue; 
for(int j=0;j+1<right[i].length ();j++) 
{ 
int x=symbol.find (right[i][j]); 
int y=symbol.find (right[i][j+1]); 
B_equal[x][y]='1'; 
} 
} 
//cout<<"B_=:"<<endl; 
//print(B_equal); 
} 

void simple::B_HEAD_TAIL () 
{ 
for(int i=0;i<left.size ();i++) 
{ 
int x=symbol.find (left[i]); 
int y=symbol.find (right[i][0]); 
int l=right[i].length ()-1; 
int z=symbol.find (right[i][l]); 
B_head[x][y]='1'; 
B_tail[x][z]='1'; 

} 
//cout<<"B_head:"<<endl; 
// print(B_head); 
// cout<<"B_tail"<<endl; 
//print(B_tail); 
} 

void simple::B_HEAD_1 () 
{ 
//cout<<"B_head+:"<<endl; 
warshall(B_head,B_head_1); 
//print(B_tail_1); 

} 

void simple::B_TAIL_1 () 
{ 
//cout<<"B_tail+:"<<endl; 
warshall(B_tail,B_tail_1); 
//print(B_tail_1); 
} 

void simple::B_HEAD_2 () 
{ 
for(int i=0;i<num;i++) 
B_head_2.push_back (B_head_1[i]); 
for(i=0;i<num;i++) 
B_head_2[i][i]='1'; 
// cout<<"B_head*:"<<endl; 
// print(B_head_2); 
} 

void simple::B_TAIL_TRAN () 
{ 
for(int i=0;i<num;i++) 
for(int j=0;j<num;j++) 
B_tail_tran[i][j]=B_tail_1[j][i]; 
// cout<<"B_tail_tran:"<<endl; 
//print(B_tail_tran); 

} 


void simple::warshall (vector<string>&amt;w1,vector<string>&amt;w) 
{ 
int x=w1.size (); 
for(int i=0;i<x;i++) 
w.push_back (w1[i]); 
for(i=0;i<x;i++) 
for(int j=0;j<x;j++) 
{ 
if(w[j][i]=='1') 
for(int k=0;k<x;k++) 
{ 
if(w[j][k]!='0'||w[i][k]!='0') 
w[j][k]='1'; 
} 
} 
} 

void simple::mult (vector<string> &amt;m1,vector<string> &amt;m2,vector<string> &amt;m) 
{ 
m.clear (); 
int x=m1.size();string p; 
for(int t=0;t<x;t++)p+='0'; 
for(int l=0;l<x;l++) 
m.push_back (p); 
for(int i=0;i<x;i++) 
for(int j=0;j<x;j++) 
{ 
char c='0'; 
for(int k=0;k<x;k++) 
{ 
if(m1[i][k]=='1'&amt;&amt;m2[k][j]=='1') 
{ 
c='1'; 
break; 
} 
} 
m[i][j]=c; 
} 
} 


void simple::B_SMALL() 
{ //cout<<"B_<-:"<<endl; 
mult(B_equal,B_head_1,B_small); 
//print(B_small); 
} 

void simple::B_LARGE () 
{ 
vector<string>q; 
mult(B_tail_tran,B_equal,q); 
mult(q,B_head_2,B_large); 
for(int i=0;i<num;i++) 
for(int j=0;j<num;j++) 
if(B_large[i][j]=='1') 
if(isupper(symbol[j])) 
B_large[i][j]='0'; 
//cout<<"B_->:"<<endl; 
//print(B_large); 
} 

void simple::check () 
{ 
clear(); 
cout<<"请输入要识别的符号串。"<<endl; 
cin>>s; 
check_1(); 
} 

void simple::check_1 ()//检查是否包含非该文法符号的符号，有，则不是文法的句子，否则继续识别 
{ 
for(int i=0;i<s.length();i++) 
if(symbol.find (s[i])==-1) 
break; 
if(i<s.length ()) 
cout<<"输入的不是该文法的句子。1"<<endl; 
else 
{ 
B_stack.push_back ('#'); 
s+='#'; 
get_symbol(); 
} 
} 

void simple::get_symbol() 
{ 
char c=s[pos++]; 
relation(c); 
} 

void simple::relation (char c) 
{ 
int x=symbol.find (c); 
int y=symbol.find (B_stack.back ()); 
if(x==-1) 
find_simple(); 
else if(y==-1) 
{ 
B_stack.push_back (c); 
get_symbol(); 
} 
else if(B_large[y][x]=='1') 
find_simple(); 
else 
{ 
B_stack.push_back (c); 
get_symbol(); 
} 
} 

void simple::find_simple () 
{ 
int k=B_stack.size ()-1; 
loop1:if(s[pos-1]=='#'&amt;&amt;B_stack.back ()=='#')//栈和输入串中都只剩‘#’ 
cout<<"输入的不是该文法的句子。2"<<endl; 
else if(B_stack[k-1]=='#') 
GUI_YUE(k); 
else 
{ 
int x=symbol.find (B_stack[k-1]); 
int y=symbol.find (B_stack[k]); 
if(B_small[x][y]=='1') 
GUI_YUE(k); 
else 
{ 
k--; 
goto loop1; 
} 
} 
} 
void simple::GUI_YUE(int k) 
{ 
int k1=k; 
int i=0; 
for(;i<right.size ();i++) 
{ 
int y=B_stack.size ()-k; 
int x=right[i].length (); 
int j=0; 
if(x!=y)continue; 
else 
{ 
for(;j<x;j++) 
if(right[i][j]!=B_stack[k++]) 
break; 
} 
if(j>=x) 
{ 
while(y>0) 
{ 
B_stack.pop_back (); 
y--; 
} 
B_stack.push_back (left[i]); 
break; 
} 
else k=k1; 
} 
if(i>=right.size ())result(); 
else relation(s[pos-1]); 
} 

void simple::result () 
{ 
if(B_stack.size ()==2) 
if(B_stack[0]=='#'&amt;&amt;B_stack[1]==left[0]&amt;&amt;s[pos-1]=='#') 
{ 
cout<<"输入的符号串是文法的句子。"<<endl; 
return; 
} 
cout<<"输入的不是该文法的句子。"<<endl; 
} 

void simple::print_bool (char c) 
{ 
switch(c) 
{ 
case'a':print(B_head);break; 
case'b':print(B_tail);break; 
case'c':print(B_head_1);break; 
case'd':print(B_tail_1);break; 
case'e':print(B_tail_tran);break; 
case'f':print(B_equal);break; 
case'g':print(B_small);break; 
case'h':print(B_large);break; 
default:return; 
} 
} 

void simple::print (vector<string>m) 
{ 
for(int i=0;i<m.size ();i++) 
{ 
cout<<symbol[i]<<" "; 
for(int j=0;j<m[i].length ();j++) 
cout<<m[i][j]<<" "; 
cout<<endl; 
} 
} 


void main() 
{ 
loop: simple f; 
if(f.input ()==true) 
{ 
f.XU_LIE (); 
f.B_EQUAL (); 
f.B_HEAD_TAIL (); 
f.B_HEAD_1 (); 
f.B_TAIL_1 (); 
f.B_HEAD_2 (); 
f.B_TAIL_TRAN (); 
f.B_SMALL (); 
f.B_LARGE (); 
char ch; 
do{ 

cout<<"请选择："<<endl; 
cout<<"'a':print(B_head)"<<endl; 
cout<<"'b':print(B_tail)"<<endl; 
cout<<"'c':print(B_head_1)"<<endl; 
cout<<"'d':print(B_tail_1)"<<endl; 
cout<<"'e':print(B_tail_tran)"<<endl; 
cout<<"'f':print(B_equal)"<<endl; 
cout<<"'g':print(B_small)"<<endl; 
cout<<"'h':print(B_large)"<<endl; 
cout<<"'i':识别句子"<<endl; 
cin>>ch; 
f.print_bool (ch); 
}while(ch=='a'||ch=='b'||ch=='c'||ch=='d'||ch=='e'||ch=='f'||ch=='g'||ch=='h'); 
if(f.is_simple ()==true) 
{ 
loop2:f.check (); 
char c; 
cout<<"是否继续识别：[Y/N]？"<<endl; 
cin>>c; 
if(c=='y'||c=='Y') goto loop2; 
} 
} 
char d; 
cout<<"是否继续：[Y/N]？"<<endl; 
cin>>d; 
if(d=='y'||d=='Y') goto loop; 
}