深圳大學(xué)編譯原理實(shí)驗(yàn)報(bào)告蔡樹彬?qū)嶒?yàn)一

1、深 圳 大 學(xué) 實(shí) 驗(yàn) 報(bào) 告 課程名稱： 編譯原理 實(shí)驗(yàn)項(xiàng)目名稱： 文法分析方法及其應(yīng)用 學(xué)院： 計(jì)算機(jī)與軟件學(xué)院 專業(yè)： 軟件工程 指導(dǎo)教師： 蔡樹彬 報(bào)告人： 學(xué)號 班級： 實(shí)驗(yàn)時(shí)間： 2015年9月16日至10月28日 實(shí)驗(yàn)報(bào)告提交時(shí)間： 2015年11月10日 教務(wù)處制實(shí)驗(yàn)?zāi)康呐c要求：目的：針對分詞、停用詞過濾等文法分析應(yīng)用問題，設(shè)計(jì)并實(shí)現(xiàn)相應(yīng)的解決方案，再通過設(shè)計(jì)文法相關(guān)類族，以及實(shí)現(xiàn)文法化簡等方法，既加深對抽象的文法、推導(dǎo)、語言等形式語言理論基礎(chǔ)概念的理解與掌握，也加強(qiáng)對面向?qū)ο蟪绦蚓帉懩芰陀?jì)算思維的培養(yǎng)。要求: 第一部分： 分詞輸入：輸入是一個(gè)文本文件，里面的內(nèi)容是符合某個(gè)語

2、言語法、詞法要求的源代碼（語法可參考課本P104，包括語句表、for循環(huán)和賦值語句等），例如“position := initial + rate * 60;”；輸出：設(shè)計(jì)并實(shí)現(xiàn)對輸入文件的處理（禁用正則表達(dá)式），以獲得如下輸出，輸出是一個(gè)文本文件，對前面例子，里面內(nèi)容是：(標(biāo)識符，position)(賦值運(yùn)算符，:=)(標(biāo)識符，initial)(加法運(yùn)算符，+)(標(biāo)識符，rate)(乘法運(yùn)算符，*)(整數(shù)，60)(分隔符，; )第二部分：停用詞過濾，分為“產(chǎn)生隨機(jī)停用詞”、“產(chǎn)生隨機(jī)待過濾文本”和“過濾停用詞”3個(gè)小實(shí)驗(yàn)。產(chǎn)生隨機(jī)停用詞：生成一個(gè)文件長度和單詞平均長度可控的文本文件，要求字符

3、集為26個(gè)字母，每行生產(chǎn)一個(gè)單詞，每個(gè)單詞的長度隨機(jī)，全部單詞的平均長度可控制，通常為4、5（非嚴(yán)格要求），總共輸出的文件長度可控制。產(chǎn)生隨機(jī)待過濾文本：生成一個(gè)文件大小和單詞平均長度可控的文本文件，要求字符集為26個(gè)字母+“ ”（空格）+“rn”（回車換行）；從文件開始一直到結(jié)束，持續(xù)輸出，不額外換行（除非遇到生成的rn），總共輸出的文件大小可控制。過濾停用詞：寫一個(gè)程序，快速掃描待過濾文本，然后將待過濾文本中出現(xiàn)的所有停用詞，替換為“*”，要求禁用正則表達(dá)式，不要誤殺（例如，若停用詞包括“abc”，那么“abcd”等不應(yīng)該被誤殺。第三部分：文法化簡設(shè)計(jì)文法類，實(shí)現(xiàn)對文法GS=(Vt, Vn

4、, P, S)的文件讀寫，文法的文件表示形式以及內(nèi)存表示形式可自定義。本質(zhì)上，文法就是3個(gè)集合+1個(gè)符號，重點(diǎn)（難點(diǎn)）是產(chǎn)生式集合如何處理。文法的文本形式可根據(jù)自己需要自由定義。在前述的基礎(chǔ)上，實(shí)現(xiàn)文法化簡的無用符號及無用產(chǎn)生式消除算法（即課本算法2.1、2.2）。方法、步驟：要完成本實(shí)驗(yàn)，依據(jù)實(shí)驗(yàn)要求進(jìn)行分解，需要完成的實(shí)驗(yàn)步驟是：1. 如何讀寫文件?讀寫文法文件內(nèi)容，需要用到文件IO，查閱、復(fù)習(xí)文件IO操作。 寫文件的方法包含在頭文件include <fstream>中，通過ofstream cout("file.txt",ios:out)對文件進(jìn)行寫。 讀

5、文件的方法包含在頭文件include <cstdio>中，通過freopen("in.txt","r",stdin)對文件進(jìn)行讀。2. 如何分詞？第一部分實(shí)驗(yàn)要求進(jìn)行分詞，源代碼中的單詞可以分成3類，一類是約定的保留字，一類是普通標(biāo)識符，最后一類是數(shù)字2.1 如何識別保留字？2.2 如何識別標(biāo)識符？2.3 如何識別數(shù)字？特別的，如果你有多種方法來識別這3類單詞，那這些方法有何優(yōu)缺點(diǎn)？分析并作出你的選擇。 首先將保留字和和標(biāo)識符一一列舉出來，創(chuàng)建保留字表和標(biāo)識符表，然后對待識別文件進(jìn)行分類（分成保留字、標(biāo)識符、運(yùn)算符、分隔符），然后逐一比對，最

6、終不屬于以上分類的就是數(shù)字。 識別保留字時(shí)，可以選擇創(chuàng)建保留字及其名稱的表，直接與保留字逐個(gè)比較，然而看起來沒有將單詞分成三類的感覺，而創(chuàng)建表來比較的話看起來要簡潔很多，因此不用前者。識別整數(shù)時(shí)也可以根據(jù)ASCLL碼的值區(qū)間去判斷，但是這種方法不太直觀。3. 如何產(chǎn)生符合要求的隨機(jī)停用詞和待處理文本第二部分實(shí)驗(yàn)要求先產(chǎn)生隨機(jī)的停用詞和待處理文本，主要是如何產(chǎn)生符合要求的這些詞或文本？3.1 如何產(chǎn)生隨機(jī)停用詞？3.2 如何控制隨機(jī)停用詞的平均長度（而不是固定長度）？3.3 如何產(chǎn)生待處理文本中的“段落”？3.4 如何控制待處理文本的長度？1.調(diào)用srand(time(0),使得每次產(chǎn)生的隨機(jī)數(shù)

7、不同，定義一個(gè)string類型的字符串word，a+rand()%26即可產(chǎn)生a-z的字母，然后將每次產(chǎn)生的字母添加進(jìn)word中，即可產(chǎn)生隨機(jī)停用詞。 2.定義一個(gè)int變量length，用rand()函數(shù)隨機(jī)確定length的取值范圍，然后在循環(huán)中以length為判斷條件即可生成所需平均長度的停用詞。 3.建立的符號集中添加入”rn”即可產(chǎn)生段落。 4.定義一個(gè)int類型的變量len，用rand()函數(shù)隨機(jī)確定len的取值范圍，然后在產(chǎn)生停用詞的循環(huán)外嵌套一個(gè)循環(huán)，以len為判斷條件即可控制產(chǎn)生停用詞的個(gè)數(shù)，即處理文本的長度。4. 如何過濾停用詞第二部分實(shí)驗(yàn)最后要求把待處理文本中出現(xiàn)的停用詞

8、替換為“*”，那你如何準(zhǔn)確、快速判斷出文本中的停用詞？ 通過定義兩個(gè)指針變量，分別儲存生成的停用詞表和待處理文件，然后利用strcmp()函數(shù)對兩者進(jìn)行比較。若在遇到空格回車換行之前全部一致，則用“*”代替待處理文件中的單詞，最終輸出處理后的單詞。尤其注意對最后一個(gè)單詞的截?cái)嗵幚怼?. 如何設(shè)計(jì)文法類？文法類里面，有3個(gè)集合，1個(gè)特別的非終結(jié)符開始符號。集合應(yīng)如何表示？Set<aType>是常見的范型，可使用例如Set<Production>來表示產(chǎn)生式的集合。也可直接采用數(shù)組等形式來表示，那種方法更好？分析并做出你的設(shè)計(jì)。 類成員中，非終結(jié)符集合和終結(jié)符集合使用數(shù)組格

9、式儲存，這是一種常用的數(shù)據(jù)格式，它可以直接用下標(biāo)的方式獲取其中的數(shù)據(jù)，開始符號使用char類型，產(chǎn)生式集合同樣使用了數(shù)組格式。對于產(chǎn)生式集合，可以考慮使用了vector<string>格式，這種格式有push_back()函數(shù)可以向其添加元素，可以直接使用下標(biāo)法訪問成員，所以可以作為產(chǎn)生式集合。選用數(shù)組，主要是因?yàn)槠漭^為簡單。6. 如何實(shí)現(xiàn)無用文法的化簡算法？算法2.1、2.2課本已經(jīng)給出了說明，那你如何將算法說明變成代碼？有什么主要內(nèi)容？ 由于課本中提供了算法2.1、2.2的處理過程，因此在編程過程中基本的步驟是和課本上一樣的，但是具體的實(shí)現(xiàn)過程卻比課本上要復(fù)雜的多，比如求Vn，

10、Vt和P時(shí)，課本上是直接將其置為空，然后向其添加內(nèi)容，但代碼實(shí)現(xiàn)的過程中，我們需要用到Vn，Vt和P來進(jìn)行判斷和篩選，所以只能通過新建臨時(shí)的集合的方式，經(jīng)過課本上的方法處理之后再臨時(shí)的集合賦值給Vn、Vt和P。在課本描述為重復(fù)進(jìn)行的步驟中，我們需要用到循環(huán)，并且循環(huán)里面需要有判斷語句甚至是嵌套另一個(gè)循環(huán)。實(shí)驗(yàn)過程及內(nèi)容： 實(shí)驗(yàn)過程及內(nèi)容，處理代碼設(shè)計(jì)說明、代碼及其注釋外，特別關(guān)注編程過程。 要求，至少有一張照片，照片上出現(xiàn)你（正面）+正在寫的代碼（電腦要有外觀）實(shí)驗(yàn)1_1代碼：#include <iostream>#include <fstream>#include &

11、lt;string>using namespace std;#define N 100char strN;string KeyWordN="int","if","else","for","while","return","main" /僅列出常見關(guān)鍵字string symbol1N="+","-","*","/","%"string symbol2N=

12、"!","&","|","&&","|"string symbol3N="<",">","=","<=",">="int GetClassify(char c); /分類函數(shù)void LexicalAnalyzer(string s,int k); /詞法分析器void GetIdentifier(string s,int k); /標(biāo)識符函數(shù)voi

13、d GetOperator(string s,int k); /運(yùn)算符函數(shù)void GetSeparator(); /分隔符函數(shù)int main()ifstream fin("string.txt");fin>>noskipws; /讀取空白字符int pos=0;int i;while(!fin.eof()fin>>strpos;pos+;cout<<"測試語句:"<<str<<endl;string String=""int key,curKey;key=GetClass

14、ify(str0); curKey=GetClassify(str0);for(i=0;i<pos;i+)curKey=GetClassify(stri);if(curKey=key && curKey!=2) /同類繼續(xù)添加String+=stri;else /發(fā)現(xiàn)不同類對前面的字符串進(jìn)行判斷LexicalAnalyzer(String,key);String=""if(curKey!=0)String+=stri;key=curKey;return 0;/分成四類int GetClassify(char c) if(c=' ' |

15、c='n') /空格或換行return 0;if(c>='A' && c<='Z') | (c>='a' && c<='z') | (c>='0' && c<='9') | c='_' | c='.') /標(biāo)識符或整數(shù)或關(guān)鍵字return 1;else if(c='(' | c=')' | c='' | c='&#

16、39; | c='') /分隔符return 2;else return 3; /運(yùn)算符/詞法分析器void LexicalAnalyzer(string s,int k)if(s!="")if(k=1) /標(biāo)識符或整數(shù)或關(guān)鍵字 GetIdentifier(s,k);else if(k=2) /分隔符 GetSeparator();else if(k=3) /運(yùn)算符 GetOperator(s,k);cout<<s<<")"<<endl;/標(biāo)識符函數(shù)void GetIdentifier(string s

17、,int k)int i;bool flag1=false;for(i=0;i<s.length();i+)if(si='.')flag1=false;break;if(si>'9' | si<'0')flag1=true;break;if(flag1=true)bool flag2=true;for(i=0;i<7;i+)if(s=KeyWordi)cout<<"(關(guān)鍵字,"flag2=false;if(flag2)cout<<"(標(biāo)識符,"elsebool

18、 flag3=true;for(i=0;i<s.length();i+)if(si='.')flag3=false;cout<<"(浮點(diǎn)數(shù),"break;if(flag3)cout<<"(整數(shù),"/運(yùn)算符函數(shù)void GetOperator(string s,int k)int i;for(i=0;i<5;i+)if(s=symbol1i)switch(i)case 0:cout<<"(加法運(yùn)算符,"break;case 1:cout<<"(減法運(yùn)算

19、符,"break;case 2:cout<<"(乘法運(yùn)算符,"break;case 3:cout<<"(除法運(yùn)算符,"break;case 4:cout<<"(求余運(yùn)算符,"break;for(i=0;i<5;i+)if(s=symbol2i)cout<<"(條件運(yùn)算符,"for(i=0;i<5;i+)if(s=symbol3i)cout<<"(關(guān)系運(yùn)算符,"if(s=":=")cout<

20、<"(賦值運(yùn)算符,"else if(s="-" | s="+")cout<<"(操作運(yùn)算符,"else if(s="<<" | s=">>")cout<<"(移位運(yùn)算符,"/分隔符函數(shù)void GetSeparator() cout<<"(分隔符,"實(shí)驗(yàn)1_2_1代碼：#include <iostream>#include <string>#inc

21、lude <fstream>#include <cmath>#include <ctime>using namespace std;/隨機(jī)產(chǎn)生長度為size的單詞string GetStopWords(int size);int main()string str; int i,rows,aver; cout<<"請輸入行數(shù)和單詞平均長度:"<<endl; srand(unsigned) time(NULL); /利用種子函數(shù)產(chǎn)生偽隨機(jī)數(shù)ofstream cout("test.txt",ios:o

22、ut); /將產(chǎn)生單詞輸出到test.txtcin>>rows>>aver;for(i=1;i<=rows;i+)int length;if(i%2)if(i=rows)length=aver;elselength=rand()%(2*aver-1)+1;elselength=2*aver-length;str=GetStopWords(length);cout<<str<<endl;return 0;/隨機(jī)產(chǎn)生長度為size的單詞string GetStopWords(int size) int flag;string str="

23、;"for(int i=0;i<size;i+)char ch;ch=char(rand()%26+97); flag=rand()%2; /大小寫隨機(jī)產(chǎn)生if(flag) ch-=32; /將字符ch轉(zhuǎn)換成大寫str+=ch;return str;實(shí)驗(yàn)1_2_2代碼：#include <iostream>#include <string>#include <fstream>#include <cmath>#include <ctime>using namespace std;/隨機(jī)產(chǎn)生長度為size的單詞string

24、 GetFiles(int size); int main()int count,k,length;int num=1; string str; cout<<"請輸入文件大小和單詞平均長度:"<<endl; srand(unsigned)time(0); /利用種子函數(shù)產(chǎn)生偽隨機(jī)數(shù) ofstream cout("test.txt",ios:out); /將產(chǎn)生單詞輸出到test.txt cin>>count>>k;while(count>0)if(num%2)length=rand()%(2*k-1)

25、+1;elselength=2*k-length;if(length>count) /判斷是否發(fā)生截?cái)鄉(xiāng)ength=count;str=GetRandomString(length);cout<<str;count-=length;bool flag=false;if(count>1)if(rand()%2) /隨機(jī)產(chǎn)生回車換行 cout<<endl;count-=2;flag=true;if(!flag)if(count>0) /產(chǎn)生空格cout<<" "count-;num+;return 0;/隨機(jī)產(chǎn)生長度為siz

26、e的字符串string GetFiles(int size) int flag;string str=""for(int i=0;i<size;i+)char ch;ch=char(rand()%26+97); flag=rand()%2; /大小寫隨機(jī)產(chǎn)生if(flag) ch-=32; /將字符ch轉(zhuǎn)換成大寫str+=ch;return str;實(shí)驗(yàn)1_2_3代碼：#include<iostream>#include<string>#include<fstream>#include<ctime>#include<

27、;cstdio>#include<cstdlib>using namespace std;void GetStopWords(); /獲得停用詞表void GetFiles(); /獲得待處理文件void SettleFiles(); /替換文件函數(shù)char *v,*f; /v是停用詞,f是待處理文件int n,length; /n是禁用詞個(gè)數(shù),length是禁用詞的平均長度int size,len; /size為待處理文件大小,len為單詞平均長度int num,*key; /num是單詞個(gè)數(shù),key用來記錄實(shí)際長度int main()GetStopWords();GetF

28、iles();SettleFiles();return 0;/替換文件函數(shù)void SettleFiles()int i,j,k;ofstream cout("result.txt",ios:out);for(i=0;i<num;i+)for(j=0;j<n/2*2;j+)if(!strcmp(fi,vj)for(k=0;k<keyi;k+)fik='*'for(i=0;i<num;i+)for(j=0;j<=keyi;j+)cout<<fij;實(shí)驗(yàn)1_3_1代碼：/定義文法類class Grammarprivate

29、:char VnMAX; /非終結(jié)符號集int Vn_num; /非終結(jié)符號數(shù)目char VtMAX; /終結(jié)符號集int Vt_num; /終結(jié)符號數(shù)目string pMAX; /產(chǎn)生式集合int P_num; /產(chǎn)生式數(shù)目char start; /起始符號public:void Initial(); /初始化及輸入文法類 void Display(); /輸出化簡后的文法void RemoveProduction(); /無用產(chǎn)生式消除void RemoveSingle(); /單產(chǎn)生式消除;實(shí)驗(yàn)1_3_2代碼：#include <iostream>#include <s

30、tring>#include <fstream>#include <cstdio>using namespace std;const int MAX=100;/定義文法類class Grammarprivate:char VnMAX; /非終結(jié)符號集int Vn_num; /非終結(jié)符號數(shù)目char VtMAX; /終結(jié)符號集int Vt_num; /終結(jié)符號數(shù)目string pMAX; /產(chǎn)生式集合int P_num; /產(chǎn)生式數(shù)目char start; /起始符號public:void Initial(); /初始化及輸入文法類 void Display();

31、/輸出化簡后的文法void RemoveProduction(); /無用產(chǎn)生式消除void RemoveSingle(); /單產(chǎn)生式消除;void Grammar:Initial() int i=0,j=0,k=0,num; for(i=0;i<MAX;i+) /初始化賦值Vni='0'Vti='0'pi='0'i=0;cout<<"輸入非終結(jié)符個(gè)數(shù)以及非終結(jié)符:"cin>>num;while(num-)cin>>Vn+i; Vn_num=i; cout<<"

32、輸入終結(jié)符個(gè)數(shù)以及終結(jié)符:"cin>>num;while(num-)cin>>Vt+j; Vt_num=j; cout<<"輸入產(chǎn)生式個(gè)數(shù)以及產(chǎn)生式:"cin>>num;while(num-)cin>>p+k; P_num=k; cout<<"輸入起始符號:"cin>>start;void Grammar:RemoveProduction() char Vn1MAX; string p1MAX; int pos=0,test=0; int i,j,k,t;/*算

33、法2.1* for(i=1;i<=P_num;i+) test=0; for(j=3;pij!=NULL;j+) for(k=1;k<=Vt_num;k+) if(pij=Vtk) test+; if(test=(j-3) pos+; Vn1pos=pi0; p1pos=pi; int n=0; while(pos!=n) n=pos; for(i=1;i<=P_num;i+) bool temp=true; for(t=1;t<=pos;t+)if(p1t=pi)temp=false; if(temp) test=0; for(j=3;pij!=NULL;j+) fo

34、r(k=1;k<=Vt_num;k+) if(pij=Vtk) test+; for(k=1;k<=pos;k+) if(pij=Vn1k) test+; if(test=(j-3) pos+; Vn1pos=pi0; p1pos=pi; /*算法2.2* char Vn2MAX;Vn21=start;int nvn=1;int check=nvn; string p2MAX;int np=0; char vt2MAX;int nvt=0; n=0; while(n!=(nvn+nvt) n=nvn+nvt; for(i=1;i<=pos;i+) if(p1i0=Vn2che

35、ck&&check<=nvn) p2+np=p1i; for(j=3;p1ij!=NULL;j+) for(k=1;k<=Vt_num;k+) if(p1ij=Vtk) int temp=1; for(t=1;t<=nvt;t+)if(Vtk=vt2t)temp=0; if(temp) vt2+nvt=p1ij; for(k=1;k<=Vn_num;k+) if(p1ij=Vnk) int temp=1; for(t=1;t<=nvn;t+)if(Vnk=Vn2t)temp=0; if(temp) Vn2+nvn=p1ij; check+; for

36、(i=0;i<MAX;i+) Vni='0'Vti='0'pi='0' for(i=1;i<=nvn;i+)Vni=Vn2i;Vn_num=nvn; for(i=1;i<=nvt;i+)Vti=vt2i;Vt_num=nvt; for(i=1;i<=np;i+) pi=p2i;P_num=np;void Grammar:Display() ofstream cout("test.txt",ios:out); int i; cout<<"非終結(jié)符號集合Vn:" for(i=

37、1;i<Vn_num;i+)cout<<Vni<<"," cout<<Vni<<""<<endl; cout<<"終結(jié)符號集合Vt:" for(i=1;i<Vt_num;i+)cout<<Vti<<"," cout<<Vti<<""<<endl; cout<<"產(chǎn)生式集合P:" for(i=1;i<P_num;i+)

38、cout<<pi<<"," cout<<pi<<""<<endl;void Grammar:RemoveSingle() int i,j,k,t; string p1MAX;int cp1=P_num; for(i=1;i<=P_num;i+)p1i=pi; for(i=1;i<=cp1;i+) if(p1i4=NULL) int temp=0; for(t=1;t<=Vn_num;t+) if(p1i3=Vnt) temp=1; if(temp) for(j=1;j<=cp1;j+) if(p1j0=p1i3) p1+cp1=p1i+p1j; int len=p1i.length()+p1j.length(); for(k=