正规文法到正规式转换.docx

编译原理实验报告
实验名称
实验时间 2015年5月19日
院系 计算机科学与技术学院
班级
学号 姓名
1. 实验目的
输入：任意的正规文法。 输出：相应的正规式。
2. 实验原理
3 型文法（正则文法eft)&&(p[i].right[1]==p[j].right[1]))
{ p[i].right=p[i].right+"l"+p[j].right; p[j].left="";
p[j].right="";
}
〃合并:转换规则3(合并如S->a,S->b, S->c--->S->alblc的形式)
if(p[i].()==1&&p[j].()==1&&p[i].left==p[j].left) {
p[i].right=p[i].right+"l"+p[j].right; p[j].left="";
p[j].right="";
}
}
}
〃提取公因式:如S->aAlbA--->S->(alb)A的形式
for(i=0; i<n; i++)
{ flag=p[i].();
if(p[i].()>2&&'A'<=p[i].right[1]&&p[i].right[1]<='Z'&&p[i].right[2]=='l') {
for(j=1; j<flag-1; j=j+3)
{ p[i].right[j]=' ';//S->a lb ;
}
if(j==flag-1)
p[i].right="("+p[i].(0,p[i].()-1)+")"+p[i].(p[i].
()-1);//S->(alb)A;
}
}
//转换规则 (A->xA|y--->A->x*(y))
for(i=0; i<n; i++)
{//P[i]=A->(a|d)A(a|d) if(p[i].left[0]==p[i].right[p[i].()-1]&&p[i].()>1) {
for(j=0; j<n; j++)
{
if(p[i].left==p[j].left&&j!=i)
{//p[j]=A->a|d
for(m=0; m<p[j].(); m++) if('A'<=p[j].right[m]&&p[j].right[m]<='Z') break;
if(m==p[j] ・right・length ())//无非终结符的产生式右部
{
p[i]・right=p[i]・right・substr(0,p[i]・right・length()-1)+"*"+"("+p[j]・right+")";//A->(a|d)*(a|d) p[j]・right="";
p[j]・left="";
}
}
}
}
}
〃转换规则 2・2(S->(xx)A A->aA 转化为 S->(xx)a*A)
for(i=0; i<n; i++)
{
if(p[i].()>1 &&