由正規(guī)(則)文法構(gòu)造正規(guī)(則)式

編譯原理實驗報告實驗名稱由正規(guī)（則）文法構(gòu)造正規(guī)（則）式實驗時間 院系 計算機科學(xué)與技術(shù)學(xué)院班級 學(xué)號 姓名1.試驗?zāi)康妮斎耄喝我獾恼?guī)文法。輸出：相應(yīng)的正規(guī)式。2.實驗原理（一）3型文法（正則文法，線性文法）如果對于某文法G,P中的每個規(guī)則具有下列形式：U::=T或U::=WT其中TGV；U,W￡V，則稱該文法G為左線性文法。TN如果對于某文法G,P中的每個規(guī)則具有下列形式：U::=T或U::=TW其中TGV；U,WGV，則稱該文法G為右線性文法。TN左線性文法和右線性文法通稱為3型文法或正則文法,有時又稱為有窮狀態(tài)文法,簡寫為RG。按照定義,對于正則文法應(yīng)用規(guī)則時,單個非終結(jié)符號只能被替換為單個終結(jié)符號,或被替換為單個非終結(jié)符號加上單個終結(jié)符號,或者被替換為單個終結(jié)符號加上單個非終結(jié)符號。3型文法所確定的語言為3型語言L3,3型語言可由確定的有限狀態(tài)自動機3來識別。程序設(shè)計語言的單詞可由正則文法產(chǎn)生,例如,標(biāo)識符的定義可由正則文法描述如下：＜標(biāo)識符＞::=＜字母＞/＜標(biāo)識符＞＜字母＞/＜標(biāo)識符＞＜數(shù)字＞顯然,該文法描述了以字母開頭的字母數(shù)字串的集合?，F(xiàn)在要引入另一種適合于描述單詞的表示法——正則表達(dá)式。正則表達(dá)式又稱為正則式,每個正則表達(dá)式描述的集合稱為正則集。之所以采用正則表達(dá)式來描述,主要基于以下幾點原因：（1）詞法規(guī)則簡單,無需上下文無關(guān)文法那樣嚴(yán)格的表示法,用正則式表示法來理解被定義的符號集合比理解由重寫規(guī)則集合定義的語言更為容易；從正則式構(gòu)造高效識別程序比上下文無關(guān)文法更容易；可以從某個正則式自動地構(gòu)造識別程序，它可以識別用該正則式表示的字符串集合中的字符串，從而減輕后面要介紹的詞法分析時的工作量?？捎糜谄渌鞣N信息流的處理，例如，已經(jīng)應(yīng)用于某些模式識別問題、文獻(xiàn)目錄檢索系統(tǒng)以及正文編輯程序等。正則表達(dá)式和正則集設(shè)有字母表上的正則表達(dá)式和它所表示的正則集遞歸地定義如下：&和e都是e上的正則表達(dá)式，它們所表示的正則集分別為｛￡｝和?,其中g(shù)是空串，e是空集；任意的是正則表達(dá)式，它所表示的正則集是｛a｝；如果el和e2是刀上的任意的正則表達(dá)式，且分別表示的正則集為L(el)和L(e2)，則：e1/e2也是正則表達(dá)式，表示的正則集為L(e1/e2)=L(e1)UL(e2)。ele2也是正則表達(dá)式，表示的正則集為L(e1e2)=L(e1)L(e2)。(e1)*也是正則表達(dá)式，表示的正則集為L((el)*)=L(e1)*。定義中(1)和(2)定義了原子正則表達(dá)式，而(3)則表明字母表E上的正則表達(dá)式可由原子正則表達(dá)式或較簡單的正則表達(dá)式通過聯(lián)合、連接與閉包運算構(gòu)成一般的正則表達(dá)式。正則表達(dá)式的性質(zhì)如果兩個正則表達(dá)式e1和e2表示的正則集相同，即值相等，則稱它們是等價的。記為e1=e2。正則表達(dá)式與正則文法的關(guān)系一個正則表達(dá)式的值是正則集，它是正則語言的另一種表示法。不難看出，除了符號e外，一個正則表達(dá)式的含義類似于正則文法的一個非終結(jié)符號規(guī)則右部的含義。例如，對于<數(shù)字〉：：=0/1/2/???/9，由非終結(jié)符數(shù)字所產(chǎn)生的字符串集合與正則表達(dá)式0/1/2/???/9所定義的字符串集合是相同的。正則集①,它對應(yīng)一個不包含任何句子的語言，引進(jìn)的目的主要是為了理論上的完備性。3..實驗內(nèi)容由正規(guī)（則）文法構(gòu)造正規(guī)（則）式4.實驗心得函數(shù)間的調(diào)用關(guān)系如下圖：5.實驗代碼與結(jié)果1）程序清單：#include<iostream>#include<string>usingnamespacestd;typedefstructCSS //定義一個產(chǎn)生式結(jié)構(gòu)體{stringleft;//定義產(chǎn)生式的左部stringright;//定義產(chǎn)生式的右部}CSS;boolZero(CSS*p,intn) //判斷0型文法{inti,j;for(i=0;i<n;i++)〃循環(huán)n次，即遍歷所有產(chǎn)生式{for(j=0;j<p[i].left.length();j++)//遍歷產(chǎn)生式左部每一個字符{if(p[i].left[j]>='A'&&p[i].left[j]<='Z') //判斷字符是否是非終結(jié)符break;}if(j==p[i].left.length()){cout<<"該文法不是0型文法"<<endl;return0;break;}}if(i==n)return1;//如果每個產(chǎn)生時都能找到非終結(jié)符}boolFirst(CSS*p,intn) //判斷1型文法{inti;if(Zero(p,n)) //先判斷是否是0型文法{for(i=0;i<n;i++){if((p[i].left.length()>p[i].right.length())&&p[i].right.length()!=NULL)//判斷產(chǎn)生式左部長度是否大于右部break;}if(i==n)return1;else{cout<<"該文法是0型文法"<<endl;return0;}elsereturn0;}boolSecond(CSS*p,intn) //判斷2型文法{inti;if(First(p,n)) //同上，先判斷低級文法是否成立{for(i=0;i<n;i++) //同上，遍歷所有文法產(chǎn)生式{if((p[i].left.length()!=1)||!(p[i].left[0]>='A'&&p[i].left[0]<='Z'))//判斷產(chǎn)生式左部長度是否為一，左部第一個是否是非終結(jié)符break;}if(i==n)return1;else{cout<<"該文法是1型文法"<<endl;return0;}}elsereturn0;}voidThird(CSS*p,intn) //判斷3型文法{inti;if(Second(p,n)) //同上，先判斷是否是2型文法{for(i=0;i<n;i++)//同上，遍歷文法所有的產(chǎn)生式{if((p[i].right.length()==0)||(p[i].right.length()>=3)||(p[i].right[0]>='A'&&p[i].right[O]<='Z'))〃判斷產(chǎn)生式右部字符個數(shù)是否在12之間，判斷右部第一個字符是否是非終結(jié)符break;}if(i==n){for(i=0;i<n;i++)if(p[i].right.length()==2){if(!(p[i].right[1]>='A'&&p[i].right[1]<='Z'))break;}}if(i==n){cout<<"該文法屬于3型文法"<<endl;}elsecout<<"該文法屬于2型文法"<<endl;}elsecout<<"該文法屬于2型文法"<<endl;}elsecout<<"結(jié)束"<<endl;}//正規(guī)文法轉(zhuǎn)換為正規(guī)式voidtransfer(CSS*p,intn){inti,j,m,flag;//合并產(chǎn)生式for(i=0;i<n;i++)for(j=i+1;j<n;j++){if((p[i].left==p[j].left)&&(p[i].right[1]==p[j].right[1])){if(p[i].right[l]=p[j].right[l]&&p[i].left[O]=p[j].right[l])〃合并形如A->aA,A->bA的產(chǎn)生式為A->aA|bA的形式{p[i].right=p[i].right+"|"+p[j].right;p[j].left="";p[j].right="";}elseif(p[i].right[1]==p[j].right[1]&&p[i].left[0]!=p[j].right[1])〃合并形如S->aA,S->bA的產(chǎn)生式為S->aA|bA的形式p[i].right=p[i].right+"|"+p[j].right;p[j].left="";p[j].right="";}}/*if(p[i].left==p[j].left&&p[j].right.length()==1&&p[i].left[0]!=p[i].right[1])//合并形如S->aA,S->a的產(chǎn)生式為S->aA|a的形式{p[i].right=p[i].right+"|"+p[j].right;p[j].left="";p[j].right="";}*///正規(guī)文法到正規(guī)式的轉(zhuǎn)換規(guī)則3if(p[i].right.length()==1&&p[j].right.length()==1&&p[i].left==p[j].left)//合并形如S->a,S->b,S->c的產(chǎn)生式為S->a|b|c的形式{p[i].right=p[i].right+"|"+p[j].right;p[j].left="";p[j].right="";}}〃提取形如S->aA|bA的公因式為S->(a|b)A的形式for(i=0;i<n;i++){flag=p[i].right.length();if(p[i].right.length()>2&&'A'<=p[i].right[1]&&p[i].right[1]<='Z'&&p[i].right[2]=='|'){for(j=1;j<flag-1;j=j+3){p[i].right[j]='';}if(j==flag-1)p[i].right="("+p[i].right.substr(0,p[i].right.length()-1)+")"+p[i].right.substr(p[i].right.length()-1);}}//正規(guī)文法到正規(guī)式的轉(zhuǎn)換規(guī)則2for(i=0;i<n;i++)if(p[i].left[0]==p[i].right[p[i].right.length()-1]&&p[i].right.length()>1){for(j=0;j<n;j++)if(p[i].left==p[j].left&&j!=i){for(m=0;m<p[j].right.length();m++)if('A'<=p[j].right[m]&&p[j].right[m]<='Z')break;if(m==p[j].right.length()){p[i].right=p[i].right.substr(0,p[i].right.length()-1)+"*"+"("+p[j].right+")“■Ip[j].right="";p[j].left="";}}}}//正規(guī)文法到正規(guī)式的轉(zhuǎn)換規(guī)則3flag=n;while(flag>=0)〃當(dāng)所有產(chǎn)生式的右部均為終結(jié)符構(gòu)成時停止轉(zhuǎn)換for(i=0,flag=flag-1;i<n;i++)for(j=0;j<p[i].right.length();j++)if('A'<=p[i].right[j]&&p[i].right[j]<='Z'){for(m=0;m<n;m++){if(p[m].left[0]==p[i].right[j]&&m!=i){p[i].right=p[i].right.substr(0,j)+p[m].right+p[i].right.substr(j+1);p[m].left="";p[m].right="";break;}}}//再次合并左部相等的產(chǎn)生式for(i=0;i<n;i++)for(j=0;j<n;j++){if(p[i].left[0]==p[j].left[0]&&i!=j){if(p[j].right.length()>1){p[i].right=p[i].right+"|"+"("+p[j].right+")";p[j].left="";p[j].right="";}else{p[i].right=p[i].right+"|"+p[j].right;p[j].left="";p[j].right="";}}}}voidmain(){inti,j,n;stringinput;cout<<"請輸入文法產(chǎn)生式個數(shù)N：";cin>>n;CSS*p=newCSS[n];//初始化產(chǎn)生式數(shù)組for(i=0;i<n;i++) //輸入產(chǎn)生式數(shù)組{input.erase();//清除cin>>input; //輸入for(j=0;j<input.length();j++)〃改變輸入數(shù)據(jù)的形式{if(input[j]=='-'){p[i].left=input.substr(0,j);p[i].right=input.substr(j+2,input.length());}}}Third(p,n); //調(diào)用文法類型判斷，自頂向下cout<<"該文法屬于正規(guī)文法，它的正規(guī)式如下："<<endl;transfer(p,n);for(i=0;i<n;i++)〃輸出轉(zhuǎn)換后的文法{

if(p[i].left[0]!=NULL){cout<<p[i].left<<"=";for(j=0;j<p[i].right.len