編譯原理實驗1Chomsky文法類型判斷

編譯原理實驗報告實驗名稱Chomsky文法類型判斷實驗時間2014年4月2日院系計算機科學與技術(shù)學院班級科技(2)班學號E01114174姓名徐帥試驗目的輸入：一組任意的規(guī)則。輸出：相應的Chomsky文法的類型。實驗原理1．0型文法（短語文法）如果對于某文法G，P中的每個規(guī)則具有下列形式： u::=v其中u∈V＋，v∈V*，則稱該文法G為0型文法或短語文法，簡寫為PSG。0型文法或短語結(jié)構(gòu)文法的相應語言稱為0型語言或短語結(jié)構(gòu)語言L0。這種文法由于沒有其他任何限制，因此0型文法也稱為無限制文法，其相應的語言稱為無限制性語言。任何0型語言都是遞歸可枚舉的，故0型語言又稱遞歸可枚舉集。這種語言可由圖靈機（Turning）來識別。2．1型文法（上下文有關(guān)文法）如果對于某文法G，P中的每個規(guī)則具有下列形式： xUy::=xuy其中U∈VN；u∈V＋；x，y∈V*，則稱該文法G為1型文法或上下文有關(guān)文法，也稱上下文敏感文法，簡寫為CSG。1型文法的規(guī)則左部的U和右部的u具有相同的上文x和下文y，利用該規(guī)則進行推導時，要用u替換U，必須在前面有x和后面有y的情況下才能進行，顯示了上下文有關(guān)的特性。1型文法所確定的語言為1型語言L1，1型語言可由線性有界自動機來識別。 3．2型文法（上下文無關(guān)文法）如果對于某文法G，P中的每個規(guī)則具有下列形式： U::=u其中U∈VN；u∈V＋，則稱該文法G為2型文法或上下文無關(guān)文法，簡寫為CFG。按照這條規(guī)則，對于上下文無關(guān)文法，利用該規(guī)則進行推導時，無需考慮非終結(jié)符U所在的上下文，總能用u替換U，或者將u歸約為U，顯示了上下文無關(guān)的特點。2型文法所確定的語言為2型語言L2，2型語言可由非確定的下推自動機來識別。一般定義程序設(shè)計語言的文法是上下文無關(guān)的。如C語言便是如此。因此，上下文無關(guān)文法及相應語言引起了人們較大的興趣與重視。4．3型文法（正則文法，線性文法）如果對于某文法G，P中的每個規(guī)則具有下列形式： U::=T或U::=WT其中T∈VT；U,W∈VN，則稱該文法G為左線性文法。如果對于某文法G，P中的每個規(guī)則具有下列形式： U::=T或U::=TW其中T∈VT；U,W∈VN，則稱該文法G為右線性文法。左線性文法和右線性文法通稱為3型文法或正則文法，有時又稱為有窮狀態(tài) if(i==m) return1;//說明該文法是0型 else { cout<<"該文法不是0型文法!"<<endl; return0; }}boolwenfa1(GZ*p)//判斷1型文法{ inti; if(wenfa0(p)) { for(i=0;i<m;i++)//遍歷所有的產(chǎn)生式 { if(p[i].right.length()>=p[i].left.length())//判斷產(chǎn)生式右邊是否大于左邊 continue; else break; } if(i==m) return1;//說明該文法是1型 else { cout<<"該文法是0型文法!"<<endl; return0; } } else return0;}boolwenfa2(GZ*p)//判斷2型文法{ inti; if(wenfa1(p)) { for(i=0;i<m;i++)//遍歷所有的產(chǎn)生式 { if(p[i].left.length()==1&&(p[i].left[0]>'A'&&p[i].left[0]<'Z')) continue; else break; } if(i==m) return1;//說明該文法是2型 else { cout<<"該文法是1型文法!"<<endl; return0; } } else return0;}boolwenfa3(GZ*p)//判斷3型文法{ inti; if(wenfa2(p)) { for(i=0;i<m;i++)//遍歷所有的產(chǎn)生式 { if((p[i].right[0]>='a'&&p[i].right[0]<='z')&&p[i].right.length()>=1&&p[i].right.length()<=2)//判斷產(chǎn)生式右邊第一個字符是否是終結(jié)符以及規(guī)定左邊的字符個數(shù)為1或2 if((p[i].right.length()==2)&&(p[i].right[1]>='a'&&p[i].right[1]<='z')) break; else continue; else break; } if(i==m) { cout<<"該文法是3型文法!"<<endl; return1; } else { cout<<"該文法是2型文法!"<<endl; return0; } } else return0;}voidoutput(GZ*p)//輸出終結(jié)符和非終結(jié)符{ inti,j,k; intvn=0;//記錄非終結(jié)字符個數(shù) intvt=0;//記錄終結(jié)字符個數(shù) for(i=0;i<m;i++)//遍歷整個產(chǎn)生式 { for(j=0;j<p[i].whole.length();j++)//遍歷產(chǎn)生式的整個字符 { if(p[i].whole[j]>='A'&&p[i].whole[j]<='Z')//判斷字符是否為非終結(jié)字符 { for(k=0;k<=vn;k++)//遍歷整個非終結(jié)符集合，判斷是否有重復 { if(Vn[k]==p[i].whole[j]) break; else continue; } if(k>vn)//說明沒有重復 { Vn[vn]=p[i].whole[j]; vn++; } } if(p[i].whole[j]>='a'&&p[i].whole[j]<='z')//判斷字符是否為非終結(jié)字符 { for(k=0;k<=vt;k++)//遍歷整個非終結(jié)符集合，判斷是否有重復 { if(Vt[k]==p[i].whole[j]) break; else continue; } if(k>vt)//說明沒有重復 { Vt[vt]=p[i].whole[j]; vt++; } } } } cout<<"\n"; cout<<"非終結(jié)符為:\n"; for(i=0;i<vn;i++)//輸出非終結(jié)字符 cout<<Vn[i]<<""; cout<<"\n"; cout<<"\n"; cout<<"終結(jié)符為:\n"; for(i=0;i<vt;i++)//輸出非終結(jié)字符 cout<<Vt[i]<<""; cout<<"\n";}voidmain(){ inti,j; stringin;//記錄輸入的產(chǎn)生式 cout<<"請輸入文法產(chǎn)生式的個數(shù)!\n"; cin>>m; GZ*p=newGZ[m]; cout<<"請再輸入文法規(guī)則:\n"; for(i=0;i<m;i++)//輸入產(chǎn)生式數(shù)組 { cin>>in; for(j=0;j<in.length();j++)//將產(chǎn)生式分為左式和右式 { if(in[j]=='-') { p[i].left=in.substr(0,j);