编译原理实验四：正规式到正规文法的转换解读.doc

实验四：正规式到正规文法的转换 一：要求 输入任意的正规式,输出相应的正规文法 二：实验目的 熟练掌握正规式到正规文法的转换规则 理解正规文法和正规式的等价性 三：实验原理1.一个正规语言可以由正规文法定义，也可以由正规式定义，对任意一个正规文法，存在一个定义同一个语言的正规式，反之，对每个正规式，存在生成同一个语言的正规文法 2正规文法与正规式的转换规则： 1． A-〉xB,B-y则：A=xy 2．A-〉xA,A-y 则：A-〉x*y 3．A-〉x，A-〉y 则：A=x|y 四：数据结构与算法 struct Chomsky { string left; string right; }; void apart(Chomsky *p,int i) //分开产生式左右部 void VNVT(Chomsky *p)//求VN和VT void print(Chomsky *p)//输出四元组，即正规文法 void change(Chomsky *p)//正规式到正规文法的转换函数 五：出错分析 1: 自定义的变量容易弄混，注释清楚很重要。很容易导致没有定义这种错误。 2：if条件判断内容不明确，字符串的分段获取不清楚。 3：程序没有写出来，实验失败。 六：实验结果与分析 七：源代码 #includeiostream #includestring using namespace std; #define max 50 int 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;jstrings.length();j++) if(strings[j]==-) { p[i].left=strings.substr(0,j); p[i].right=strings.substr(j+1,strings.length()-j); } } void VNVT(Chomsky *p)//求VN和VT { int i,j; for(i=0;im;i++) { for(j=0;j(int)p[i].left.length();j++) { if((p[i].left[j]=Ap[i].left[j]=Z))//非终结符判断 { if(noend.find(p[i].left[j])100) noend+=p[i].left[j]; } else { if(end.find(p[i].left[j])100) end+=p[i].left[j]; } } for(j=0;j(int)p[i].right.length();j++) { if(!(p[i].right[j]=Ap[i].right[j]=Z))//终结符判断 { if(end.find(p[i].right[j])100) end+=p[i].right[j]; } else { if(noend.find(p[i].right[j])100) noend+=p[i].right[j]; } } } } void print(Chomsky *p)//输出四元组 { int i; coutendlG=（{noend},{end},P,noend[0]），其中P由下列产生式组成：endl; for(i=0;im;i++) coutp[i].left-p[i].rightendl; } void change(string q)//正规式到正规文法的转换函数 { /*char S;//文法开始符号 p[0].left=S;//将正规式r重写为S-r形式存储在正规文法的第一条 p[0].right=q; int n;//记录文法右边的长度 n=p[0].right.length; for(int i=0;in;i++) { if(p[0].right.[i]==) }*/ } void main() { int i,j; cout...............