由正规文法构造正规式

编译原理实验

编译原理实验

实验名称：由正规文法构造正规式 姓名： 学号： 教师签字： 成绩：

编译原理实验

实验名称:由正规文法构造正规式 实验目的：设计并实现将正规文法转化为正规式的方法， 从而更好地理解正规文法与正规式之间的 等价性。

实验原理：一个正规语言可以由正规文法定义，也可以由正规式定义，对任意一个正规 文法存在一个定义同一个语言的正规式。

正规文法到正规式的转换规则 文法产生式正规式 A –>xB A ->xA | y A -> x A -> y B -> y A = xy A= x * y A= x | y

实验代码：#include<iostream> #include<string> #include<queue> using namespace std; struct lefts { char head; //文法的左部 string right; //文法的右部 }; lefts *p=new lefts[10]; int N; //******************************

编译原理实验

string leftdec(char a) { int i; string s1; queue<int>eqvn; queue<int>ineqvn;

//左递归时调用

queue<int>qvt; for(i=0;i<N;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()<2) //队列的大小 { 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,'*');

//前后的非终止符相等时的位 //置 i 记录到队列中去如 S-Sa //前后的非终止符不相等时的位 //置 i 记录到队列中去如 S-Aa //右边仅有终结符石记录其位置 i

编译原理实验

} if(ineqvn.size()<2) { 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()<2) { 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; queue<int>eqvn; queue<int>ineqvn; queue<int>qvt; for(i=0;i<N;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()<2) { 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()<2) { if(!ineqv

n.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()<2) { 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; queue<char>qchar; cout<<"请输入正规文法和正规文法的数目"<<endl;

编译原理实验

cin>>N; for(i=0;i<N;i++) { cin>>p[i].head>>b>>p[i].right; } cout<<"请输入产生式的标示符"<<endl; cin>>a; for(i=0;i<N;i++)///判断左递归还是右递归 { if(p[i].right.length()==2 && p[i].right[0]<='Z' && p[i].right[0]>='A') { left=true; break; } } if(!left) cout<<rightdec(a)<<endl; else cout<<leftdec(a)<<endl; return 0; }

实验截图：