1、實驗三：正規文法到正規式的轉換一：要求輸入任意的正規文法,輸出相應的正規式二：實驗目的1. 熟練掌握正規文法到正規式的轉換規則2. 理解正規文法和正規式的等價性三：實驗原理1.一個正規語言可以由正規文法定義，也可以由正規式定義，對任意一個正規文法，存在一個定義同一個語言的正規式，反之，對每個正規式，存在生成同一個語言的正規文法2正規文法與正規式的轉換規則： 1 A-xB,B->y則：A=xy 2A-xA,A->y 則：A-x*y 3A-x，A-y 則：A=x|y四：數據結構與算法struct Chomskystring left; string right; ;void apart

2、(Chomsky *p,int i) /分開產生式左右部void VNVT(Chomsky *p)/求VN和VTint zero(Chomsky *p)/0型文法int one(Chomsky *p)/1型文法int two(Chomsky *p)/2型文法int three(Chomsky *p)/3型文法void change(Chomsky *p)/正規文法到正規式的轉換函數五：出錯分析1: #include<iostream>忽視了c+語言中的頭文件應當去掉.h，須再另加上using namespace std;2：規則分解不對，導致結果出錯。3：太多循環嵌套容易造成程序出

3、錯，養成把括號提前打好的習慣。六：實驗結果與分析不是正規文法的不能轉換：是正規文法的才可以轉換：七：源代碼#include<iostream>#include<string>using namespace std;#define max 50int NONE=1;string strings,noend,end;/非終結符與終結符存儲int n;/產生式總數struct Chomskystring left;string right; ; void apart(Chomsky *p,int i) /分開產生式左右部int j; for(j=0;j<strings.

4、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<n;i+) for(j=0;j<(int)pi.left.length();j+) if(pi.leftj>='A'&&pi.leftj<='Z')/非終結符判斷if(noend.find(pi.leftj)&g

5、t;100)noend+=pi.leftj; elseif(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;int zero(Chomsky *p

6、)/0型文法int flag(0),count(0); int i,j; for(i=0;i<n;i+) for(j=0;j<(int)pi.left.length();j+)if(pi.leftj>='A'&&pi.leftj<='Z') /有否非終結符flag+;if(flag>0)flag=0;count+;else break; /左部沒有非終結符，結束if(count=n) return 1; /屬于0型文法elsecout<<endl<<"所輸產生式不屬于任何文法。&qu

7、ot;<<endl;NONE=0;return 0;int one(Chomsky *p)/1型文法int flag(0); int i; if(zero(p)for(i=0;i<n;i+) if(pi.right.length()<pi.left.length() /右部長度是否小于左部flag+;break;elseflag-;if(flag>0)cout<<endl<<"此文法屬于0型文法，即短語文法。"<<endl; return 0; /不屬于1型文法else if(flag=0)return 1;

8、 /屬于1型文法elsereturn 0;int two(Chomsky *p)/2型文法int flag(0); int i; if(one(p)for(i=0;i<n;i+)if(pi.left.length()!=1)|!(pi.left0>='A'&&pi.left0<='Z') /左部不屬于一個字符或不屬于非終結符flag+;break;else flag-;if(flag>0)cout<<endl<<"此文法屬于1型文法，即上下文有關文法。"<<endl;

9、 return 0; /不屬于2型文法else if(flag=0)return 1; /屬于2型文法elsereturn 0;int three(Chomsky *p)/3型文法int flag=0;int i;if(two(p) for(i=0;i<n;i+) if(!(pi.right.length()=1|pi.right.length()=2)|(pi.right0>='A'&&pi.right0<='Z') /右部字符個數不是1或2，或首字符是非終結符 flag+; break; else if(pi.right.l

10、ength()=2)&&!(pi.right1>='A'&&pi.right1<='Z') /第二個字符不是非終結符 flag+; break; else flag-;if(flag>0) cout<<"此文法屬于2型文法，即上下文無關文法。"<<endl; i=n; return 0;else if(flag=0) cout<<"此文法屬于3型文法，即正規文法。"<<endl; return 1; else return 0

11、; void change(Chomsky *p)/正規文法到正規式的轉換函數int i,j,m,flag; /合并產生式for (i=0;i<n;i+)for(j=i+1;j<n;j+)if(pi.left=pj.left)&&(pi.right1=pj.right1)if(pi.right1=pj.right1&&pi.left0=pj.right1)/合并形如A->aA,A->bA的產生式為A->aA|bA的形式 pi.right=pi.right+"|"+pj.right; pj.left="&

12、quot; pj.right=""elseif(pi.right1=pj.right1&&pi.left0!=pj.right1)/合并形如S->aA,S->bA的產生式為S->aA|bA的形式 pi.right=pi.right+"|"+pj.right; pj.left="" pj.right="" if(pi.right.length()=1&&pj.right.length()=1&&pi.left=pj.left)/合并形如S->a,

13、S->b，S->c的產生式為S->a|b|c的形式pi.right=pi.right+"|"+pj.right; pj.left="" pj.right=""for(i=0;i<n;i+)/提取形如S->aA|bA的公因式為S->(a|b)A的形式 flag=pi.right.length(); if(pi.right.length()>2&&'A'<=pi.right1&&pi.right1<='Z'&&am

14、p;pi.right2='|') for(j=1;j<flag-1;j=j+3) pi.rightj=' ' if(j=flag-1) pi.right="("+pi.right.substr(0,pi.right.length()-1)+")"+pi.right.substr(pi.right.length()-1); for(i=0;i<n;i+) if(pi.left0=pi.rightpi.right.length()-1&&pi.right.length()>1) for(j=0

15、;j<n;j+) if(pi.left=pj.left&&j!=i) for(m=0;m<pj.right.length();m+) if('A'<=pj.rightm&&pj.rightm<='Z')break; if(m=pj.right.length() pi.right=pi.right.substr(0,pi.right.length()-1)+"*"+"("+pj.right+")" pj.right="" pj.l

16、eft="" flag=n; while(flag>=0)/當所有產生式的右部均為終結符構成時停止轉換 for(i=0,flag=flag-1;i<n;i+) for(j=0;j<pi.right.length();j+) if('A'<=pi.rightj&&pi.rightj<='Z') for(m=0;m<n;m+) if(pm.left0=pi.rightj&&m!=i) pi.right=pi.right.substr(0,j)+pm.right+pi.right.

17、substr(j+1); pm.left="" pm.right="" break; /再次合并左部相等的產生式 for(i=0;i<n;i+) for(j=0;j<n;j+) if(pi.left0=pj.left0&&i!=j) if(pj.right.length()>1) pi.right=pi.right+"|"+"("+pj.right+")" pj.left="" pj.right="" else pi.ri

18、ght=pi.right+"|"+pj.right; pj.left="" pj.right="" void main()int i,j; cout<<".編譯原理實驗三：正規文法到正規式的轉換."<<endl; cout<<"請輸入正規文法（三型文法）的產生式總數及各產生式："<<endl<<"其中左右部之間用'-'表示，空用'#'表示"<<endl; cin>>n; Chomsky *p=new Chomskymax; for(i=0;i<n;i+)cin>>strings; apart(p,i); VNVT(p);if(three(p)/只有當輸入為正規文法時才進行