由正规文法构造正规式
实验名称:由正规文法构造正规式
实验目的：
设计并实现将正规文法转化为正规式的方法，从而更好地理解正规文法与正规式之间的等价性。
实验原理：
一个正规语言可以由正规文法定义，也可以由正规式定义，对任意一个正规文法存在一个定义同一个语言的正规式。
正规文法到正规式的转换规则
文法产生式正规式
A –>xB B -> y A = xy
A ->xA | y A = x * y
A -> x A -> y A = x | y
实验代码：
#include
#include
#include
using namespace std;
struct lefts
{
char head; //文法的左部
string right; //文法的右部
};
lefts *p=new lefts[10];
int N;
//******************************
string leftdec(char a) //左递归时调用
{
int i;
string s1;
queueeqvn; //前后的非终止符相等时的位
//置i 记录到队列中去如S-Sa
queueineqvn; //前后的非终止符不相等时的位
//置i 记录到队列中去如S-Aa
queueqvt; //右边仅有终结符石记录其位置i
for(i=0;i
{
if(p[i].head==a)
{
if( p[i].right.length()==2 ) //字符串的长度
{
if(p[i].right[0]==a)
eqvn.push(i);
else
ineqvn.push(i);
}
else
{
qvt.push(i);
}
}
}
if(eqvn.size()
{
if(!eqvn.empty())
{
s1.append(1,p[eqvn.front()].right[1]); //将队列所指的位置
//的终结符加到串s1的末尾 s1.append(1,'*');
}
}
else
{
s1.append(1,'(');
s1.append(1,p[eqvn.front()].right[1]);
eqvn.pop();
s1.append(1,'|');
s1.append(1,p[eqvn.front()].right[1]);
s1.append(1,')');
s1.append(1,'*');
}
if(ineqvn.size()
{
if(!ineqvn.empty())
{
s1=s1+leftdec(p[ineqvn.front()].right[0]);//递归调用如产生
//式S->Aa,A就被递归调用了。 s1.append(1,p[ineqvn.front()].right[1]);
}
}
else
{
s1.append(1,'(');
s1+=leftdec(p[ineqvn.front()].right[0]);
s1.append(1,p[ineqvn.front()].right[1]);
ineqvn.pop();
s1.append(1,'|');
s1+=leftdec(p[ineqvn.front()].right[0]);
s1.append(1,p[ineqvn.front()].right[1]);
s1.append(1,')');
}
if(qvt.size()
{
if(!qvt.empty())
{
s1.append(1,'|');
s1.append(1,p[qvt.front()].right[0]);
}
}
else
{
s1.append(1,'|');
s1.append(1,'(');
s1.append(1,p[qvt.front()].right[0]);
s1.append(1,'|');
qvt.pop();
s1.append(1,p[qvt.front()].right[0]);
s1.append(1,')');
}
return s1;
}
//**********************
string rightdec(char a) //右递归时调用
{
int i;
string s1;
queueeqvn;
queueineqvn;
queueqvt;
for(i=0;i
{
if(p[i].head==a)
{
if( p[i].right.length()==2 )
{
if(p[i].right[1]==a)
eqvn.push(i);
else
ineqvn.push(i);
}
else
{
qvt.push(i);
}
}
}
if(eqvn.size()
{
if(!eqvn.empty())
{
s1.append(1,p[eqvn.front()].right[0]);
s1.append(1,'*');
}
}
else
{
s1.append(1,'(');
s1.append(1,p[eqvn.front()].right[0]);
eqvn.pop();
s1.append(1,'|');
s1.append(1,p[eqvn.front()].right[0]);
s1.append(1,')');
s1.append(1,'*');
}
if(ineqvn.size()
{
if(!ineqvn.empty())
{
s1.append(1,p[ineqvn.front()].right[0]);
s1=s1+rightdec(p[ineqvn.front()].right[1]);
}
}
else
{
s1.append(1,'(');
s1.append(1,p[ineqvn.front()].right[0]);
s1+=rightdec(p[ineqvn.front()].right[1]);
ineqvn.pop();
s1.append(1,p[ineqvn.front()].right[0]);
s1+=rightdec(p[ineqvn.front()].right[1]);
s1.append(1,')');
}
if(qvt.size()
{
if(!qvt.empty())
{
s1.append(1,'|');
s1.append(1,p[qvt.front()].right[0]);
}
}
else
{
s1.append(1,'|');
s1.append(1,'(');
s1.append(1,p[qvt.front()].right[0]);
s1.append(1,'|');
qvt.pop();
s1.append(1,p[qvt.front()].right[0]);
s1.append(1,')');
}
return s1;
}
//********************
int main()
{
int i;
bool left=false;
string s1[10],s2,s3;
chara,b;
queueqchar;
cout
cin>>N;
for(i=0;i
{
cin>>p[i].head>>b>>p[i].right;
}
cout
cin>>a;
for(i=0;i
{
if(p[i].right.length()==2 && p[i].right[0]='A') {
left=true;
break;
}
}
if(!left)
cout
else
cout
return 0;
}
实验截图：