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

《编译原理实验四正规式到正规文法的转换.doc》由会员分享，可在线阅读，更多相关《编译原理实验四正规式到正规文法的转换.doc（8页珍藏版）》请在课桌文档上搜索。

1、实验四：正规式到正规文法的转换一：要求输入任意的正规式,输出相应的正规文法二：实验目的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(Cho

2、msky *p,int i) /分开产生式左右部void VNVT(Chomsky *p)/求VN和VTvoid print(Chomsky *p)/输出四元组，即正规文法void change(Chomsky *p)/正规式到正规文法的转换函数五：出错分析1:自定义的变量容易弄混，注释清楚很重要。很容易导致没有定义这种错误。2：if条件判断容不明确，字符串的分段获取不清楚。3：程序没有写出来，实验失败。六：实验结果与分析七：源代码#include#includeusing namespace std;#define max 50int NONE=1;int RELEFT=1;string s

3、trings,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(stringsj=-)pi.left=strings.substr(0,j);pi.right=strings.substr(j+1,strings.length()-j);void VNVT(Chomsky *p)/求VN和VT

4、int i,j;for(i=0;im;i+) for(j=0;j=A&pi.leftj100)noend+=pi.leftj; else if(end.find(pi.leftj)100)end+=pi.leftj;for(j=0;j=A&pi.rightj100)end+=pi.rightj;else if(noend.find(pi.rightj)100)noend+=pi.rightj;void print(Chomsky *p)/输出四元组int i;coutendlG=noend,end,P,noend0，其中P由以下产生式组成：endl;for(i=0;im;i+) coutpi.leftpi.rightr形式存储在正规文法的第一条p0.right=q;int n;/记录文法右边的长度n=p0.right.length;for(int i=0;in;i+)if(p0.right.i=)*/void main()int i,j; cout.编译原理实验四：正规式到正规文法的转换.endl;Chomsky *p=new Chomskymax; cout请输入须转换的正规式：r;coutr=rendl;change(r);cout转换后的正规文法是：endl;print(p);/输出最后的正规文法8 / 8