編譯原理實(shí)驗(yàn)1Chomsky文法類型判斷

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