编译原理实验四正规式到正规文法的转换.doc
实验四：正规式到正规文法的转换一：要求输入任意的正规式,输出相应的正规文法二：实验目的1. 熟练掌握正规式到正规文法的转换规那么2. 理解正规文法和正规式的等价性三：实验原理1.一个正规语言可以由正规文法定义，也可以由正规式定义，对任意一个正规文法，存在一个定义同一个语言的正规式，反之，对每个正规式，存在生成同一个语言的正规文法2正规文法与正规式的转换规那么： 1 A-xB,B->y那么：A=xy2A-xA,A->y 那么：A-x*y 3A-x，A-y 那么：A=x|y四：数据结构与算法struct Chomskystring left; string right; ;void apart(Chomsky *p,int i) /分开产生式左右部void VNVT(Chomsky *p)/求VN和VTvoid print(Chomsky *p)/输出四元组，即正规文法void change(Chomsky *p)/正规式到正规文法的转换函数五：出错分析1:自定义的变量容易弄混，注释清楚很重要。很容易导致没有定义这种错误。2：if条件判断容不明确，字符串的分段获取不清楚。3：程序没有写出来，实验失败。六：实验结果与分析七：源代码#include<iostream>#include<string>using namespace std;#define max 50int NONE=1;int RELEFT=1;string strings,noend,end;/非终结符与终结符存储string r;/正规式int m=1;/记录产生式的个数struct Chomsky/正规文法结构存储string left;string right; ; void apart(Chomsky *p,int i) /分开产生式左右部int j;for(j=0;j<strings.length();j+)if(stringsj='-')pi.left=strings.substr(0,j);pi.right=strings.substr(j+1,strings.length()-j);void VNVT(Chomsky *p)/求VN和VTint i,j;for(i=0;i<m;i+) for(j=0;j<(int)pi.left.length();j+) if(pi.leftj>='A'&&pi.leftj<='Z')/非终结符判断if(noend.find(pi.leftj)>100)noend+=pi.leftj; else if(end.find(pi.leftj)>100)end+=pi.leftj;for(j=0;j<(int)pi.right.length();j+) if(!(pi.rightj>='A'&&pi.rightj<='Z')/终结符判断if(end.find(pi.rightj)>100)end+=pi.rightj;else if(noend.find(pi.rightj)>100)noend+=pi.rightj;void print(Chomsky *p)/输出四元组int i;cout<<endl<<"G="<<noend<<","<<end<<",P,"<<noend0<<"，其中P由以下产生式组成："<<endl;for(i=0;i<m;i+) cout<<pi.left<<"->"<<pi.right<<endl;void change(string q)/正规式到正规文法的转换函数/*char S;/文法开始符号p0.left=S;/将正规式r重写为S->r形式存储在正规文法的第一条p0.right=q;int n;/记录文法右边的长度n=p0.right.length;for(int i=0;i<n;i+)if(p0.right.i=)*/void main()int i,j; cout<<".编译原理实验四：正规式到正规文法的转换."<<endl;Chomsky *p=new Chomskymax; cout<<"请输入须转换的正规式："<<endl;cin>>r;cout<<"r="<<r<<endl;change(r);cout<<"转换后的正规文法是："<<endl;print(p);/输出最后的正规文法8 / 8
