📄 -¦
字号:
#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>&w1,vector<string>&w);//warshall算法
void mult(vector<string>&m1,vector<string>&m2,vector<string>&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]&&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'&&B_small[i][j]=='1')||(B_equal[i][j]=='1'&&B_large[i][j]=='1')||(B_small[i][j]=='1'&&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>&w1,vector<string>&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> &m1,vector<string> &m2,vector<string> &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'&&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]=='#'&&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]=='#'&&B_stack[1]==left[0]&&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;
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -