由正规文法构造正规(则)式.docx

编译原理实验报告
实验名称 由正规（则）文法构造正规（则）式
实验时间
院系 计算机科学与技术学院
班级
学号
姓名

输入：任意的正规文法。
输出：相应的正规式。

（一）3型文return 0;
break;
}
}
if(i==n)return 1;//如果每个产生时都能找到非终结符
}
bool First(CSS *p,int n) //判断 1 型文法
{
int i;
if(Zero(p,n)) //先判断是否是0型文法
{
for(i=0;i<n;i++)
{
if((p[i].()>p[i].())&&p[i].()!=NULL) // 判断产生式左部长度是否大于右部
break;
}
if(i==n)return 1;
else{
cout<<"该文法是0型文法"<<endl;
return 0;
}
else
return 0;
}
bool Second(CSS *p,int n) 〃判断 2 型文法
{
int i;
if(First(p,n)) 〃同上，先判断低级文法是否成立
{
for(i=0;i<n;i++) //同上，遍历所有文法产生式
{
if((p[i].()!=1)
|| !(p[i].left[0]>='A'&&p[i].left[0]<='Z')) //判断产生式左部长度是否为一，左 部第一个是否是非终结符
break;
}
if(i==n)return 1;
else{
cout<<"该文法是1型文法"<<endl;
return 0;
}
}
else
return 0;
}
void Third(CSS *p,int n) //判断 3 型文法
{
int i;
if(Second(p,n)) //同上，先判断是否是2型文法
{
for(i=0;i<n;i++) 〃同上，遍历文法所有的产生式
{
if((p[i].()=0)||(p[i].()>=3)||(p[i].right[0]>='A'& &p[i].right[0]<='Z')) 〃判断产生式右部字符个数是否在12之间，判断右部第一个字 符是否是非终结符
break;
}
if(i==n)
for(i=0;i<n;i++)
{
if(p[i].()==2)
{
if(!(p[i].right[1]>='A'&&p[i].right[1]<='Z'))break;
}
}
if(i==n)
{
cout<<"该文法属于3型文法"<<endl;
}
else
cout<<"该文法属于2型文法“<<endl;
}
else cout<<"该文法属于2型文法“<<endl;
}
else
cout<<"结束"<<endl;
}
〃正规文法转换为正规式
void transfer(CSS *p,int n)
{
int i,j,m,flag;
〃合并产生式
for (i=0;i<n;i++)
for(j=i+1;j<n;j++)
{
if((p[i].left=p[j].left)&&(p[i].right[1]=p[j].right[1]))
{
if(p[i].right[1]=p[j].right[1]&&p[i].left[0]=p[j].right[1])// 合并形如
A->aA,A->bA的产生式为A->aA|bA的形式
{
p[i].right=p[i].right+"|"+p[j].right;
p[j].left="";
p[j].right="”;
}
else
if(p[i].right[1]=p[j].right[1]&&p[i].left[0]!=p[j].right[1])
〃合并形如S->aA,S->bA的产生式为S->aA|bA的形式
p[i].right=p[i].right+"|"+p[j].right;
p[j].left="";
p[j].right="”;
}
}
/*
if(p[i].left=p[j].left&&p[j].()=1&&p[i].left[0]!=p[i].right[1
])//合并形如S->aA,S->a的产生式为S->aA|a的形式
{
p[i].right=p[i].right+"|"+p[j].right;