東南大學(xué)編譯原理詞法分析器實(shí)驗(yàn)報(bào)告.doc

詞法分析設(shè)計(jì)1. 實(shí)驗(yàn)?zāi)康耐ㄟ^(guò)本實(shí)驗(yàn)的編程實(shí)踐，了解詞法分析的任務(wù)，掌握詞法分析程序設(shè)計(jì)的原理和構(gòu)造方法，對(duì)編譯的基本概念、原理和方法有完整的和清楚的理解，并能正確地、熟練地運(yùn)用。2. 實(shí)驗(yàn)內(nèi)容用C+語(yǔ)言實(shí)現(xiàn)對(duì)C+語(yǔ)言子集的源程序進(jìn)行詞法分析。通過(guò)輸入源程序從左到右對(duì)字符串進(jìn)行掃描和分解，依次輸出各個(gè)單詞的內(nèi)部編碼及單詞符號(hào)自身值；若遇到錯(cuò)誤則顯示“Error”，然后跳過(guò)錯(cuò)誤部分繼續(xù)顯示；同時(shí)進(jìn)行標(biāo)識(shí)符登記符號(hào)表的管理。 3.實(shí)驗(yàn)原理本次實(shí)驗(yàn)采用NFA->DFA->DFA0的過(guò)程: 對(duì)待分析的簡(jiǎn)單的詞法（關(guān)鍵詞/id/num/運(yùn)算符/空白符等）先分別建立自己的FA，然后將他們用產(chǎn)生式連接起來(lái)并設(shè)置一個(gè)唯一的開(kāi)始符，終結(jié)符不合并。待分析的簡(jiǎn)單的詞法（1）關(guān)鍵字： "asm","auto","bool","break","case","catch","char","class","const","const_cast"等（2）界符（查表） "",",","(",")","","","",""（3） 運(yùn)算符"*","/","%","+","-","<<","=",">>","&","","|","+","-","+=","-=","*=","/=","%=","&=","=","|="relop：（4） 其他單詞是標(biāo)識(shí)符（ID）和整型常數(shù)（SUM），通過(guò)正規(guī)式定義。 id/keywords: digit: （5） 空格有空白、制表符和換行符組成?？崭褚话阌脕?lái)分隔ID、SUM、運(yùn)算符、界符和關(guān)鍵字，詞法分析階段通常被忽略。 空白、制表符和換行符:4.相關(guān)自動(dòng)機(jī)描述DFA:DFA0： 5. 流程圖5.核心數(shù)據(jù)結(jié)構(gòu)描述（1）生成的token序列由name、type、attr保存。struct token string name; string type; int attr; ; （2）本文的大多數(shù)數(shù)據(jù)結(jié)構(gòu)都用map來(lái)保存，優(yōu)點(diǎn)是查找方便，大大提高時(shí)間復(fù)雜度。 map<string,int> Keywords; /保存關(guān)鍵字 map<string,int> Sep; /保存界符map<string,int> Relop; /保存比較運(yùn)算符map<string,int> Op; /保存其他運(yùn)算符map<string,int>id; /保存輸入字符串中的idmap<string,int>num; /保存數(shù)字vector<token>Token; /保存token序列，大小未知，所以采用vector保存6.核心算法描述（1）void addToken(string s,int type）s為找到的字符串，type為可能類型。 將分析出來(lái)的token()序列添加到Token序列表中。如果是類型為1，查看關(guān)鍵詞表，若找到，其類型為關(guān)鍵詞并將其以類型為關(guān)鍵詞存儲(chǔ)到Token表中；若未找到，則查找id表，若找到，說(shuō)明該id已經(jīng)出現(xiàn)過(guò)，否則添加新的id到id表中，將該i字符串以類型為id添加到Token表中。如果類型為2，在界符表中查找，如果找到以類型為界符存儲(chǔ)到Token表中，同理其他幾種類型?？赡茴愋蜑?-5，如果出現(xiàn)其他類型表示是詞法分析器中發(fā)現(xiàn)額錯(cuò)誤，將錯(cuò)誤信息記錄下來(lái)。void addToken(string s,int type) switch(type)case 1: l_it=Keywords.find(s); if (l_it!=Keywords.end() token t=s,"keywords",l_it->second; Token.push_back(t); elsel_it=id.find(s); if (l_it=id.end() ids=idNum; token t=s,"id",idNum+; Token.push_back(t); else token t=s,"id",l_it->second; Token.push_back(t); break;case 2:l_it=Sep.find(s); if (l_it!=Sep.end() token t=s,"separatrix",l_it->second; Token.push_back(t); break;case 3:l_it=Op.find(s); if (l_it!=Op.end() token t=s,"op",l_it->second; Token.push_back(t); break;case 4:l_it=Relop.find(s); if (l_it!=Relop.end() token t=s,"relop",l_it->second; Token.push_back(t); break;case 5: l_it=num.find(s); if (l_it=num.end() nums=nNum; token t=s,"num",nNum+; Token.push_back(t); else token t=s,"num",l_it->second; Token.push_back(t); break; default: /error token t=s,"id",-1; Token.push_back(t); break; （2） void lexical() 詞法分析器，按字符讀入文法并對(duì)其進(jìn)行處理。從狀態(tài)0開(kāi)始處理，如果是空白符則一直在狀態(tài)0，如果第一個(gè)字符為字母，繼續(xù)往后尋找，直至不是字母或是數(shù)字結(jié)束；若第一個(gè)字符為數(shù)字，將其拼湊成一個(gè)數(shù)字，數(shù)字可以有小數(shù)點(diǎn)等，詳細(xì)見(jiàn)狀態(tài)轉(zhuǎn)換圖，注意以數(shù)字開(kāi)頭容易出現(xiàn)一種例如3a類型的錯(cuò)誤，所以以數(shù)字開(kāi)頭的一定要往下多找一個(gè)，看最后一個(gè)數(shù)字后面是否為空白符或界符或者其他允許出現(xiàn)的符號(hào)，如果后面緊跟著字母則報(bào)錯(cuò)。如上同理分析運(yùn)算符等。注意每次處理完遇到一個(gè)字符串都要將其送到addToken()添加到Token表中并回到狀態(tài)0，繼續(xù)往下處理。 void lexical()fstream ln("E:ln.txt"); char ch,tempch; int state=0; string s="",key="" while(!ln.eof() switch(state) case 0: ch=ln.get(); s=ch; if (ch=13|ch=10|ch=32|ch=9) state=0; s="" else if (ch=<) state=1; else if (ch=) state=6;else if (ch=>) state=9;else if (isLetter(ch) state=13;else if (isDigit(ch) state=15; else if (ch=+|ch=-|ch=*|ch=/|ch=&|ch=|) state=20; tempch=ch; else if (ch=) state=44; else if (isSep(ch)!=-1) state=47;else if (isOp(s)!=-1) state=48; else if (isRelop(s)!=-1) state=49; else state=50; /error break; case 1: ch=ln.get(); if(ch=|ch=>) state=2; else if(ch=<) state=4; else state=5; break; case 2: s+=ch; addToken(s,4); state=0; break; case 4: s+=ch; addToken(s,3); state=0; break;case 5: /* addToken(s,4); ln.seekg(-1,ios:cur); state=0; break;case 6: ch=ln.get(); if(ch=) state=7; else state=8; break;case 7: s+=ch; addToken(s,4); state=0; break;case 8: /* addToken(s,3); ln.seekg(-1,ios:cur); state=0; break;case 9: ch=ln.get(); if(ch=) state=10; else if(ch=>) state=11; else state=12; break;case 10: s+=ch; addToken(s,4); state=0;break;case 11:s+=ch;addToken(s,3); state=0; break; case 12: /* state=0;addToken(s,4); ln.seekg(-1,ios:cur); break;case 13: ch=ln.get(); if(isDigit(ch)|isLetter(ch) s+=ch; else state=14; break; case 14: /* state=0;addToken(s,1); ln.seekg(-1,ios:cur);break;case 15: ch=ln.get(); if (isDigit(ch) s+=ch; else if (ch=.)s+=ch; state=16; else state=18; break; case 16: ch=ln.get(); s+=ch;if (isDigit(ch) state=17; else state=50; /error break;case 17: ch=ln.get(); if (isDigit(ch) s+=ch; state=17; else state=18; break; case 18: /* if (isLetter(ch) s+=ch; state=50; elseaddToken(s,5); ln.seekg(-1,ios:cur); state=0; break;case 20: ch=ln.get(); if(ch=tempch|ch=) state=21; else state=23; break;case 21: s+=ch; addToken(s,3); state=0; break; case 23:addToken(s,3); ln.seekg(-1,ios:cur); state=0; break; case 44: ch=ln.get(); if (ch=) state=45; else state=46; break;case 45: s+=ch; addToken(s,3); break; case 46:addToken(s,3); ln.seekg(-1,ios:cur); break;case 47:addToken(s,2); state=0; break; case 48:addToken(s,3); state=0;break; case 49: addToken(s,4); state=0; break; case 50: /error while(ch=ln.get()!=EOF) if(isSep(ch)!=-1|ch=13|ch=10|ch=32|ch=9) break; else s+=ch; addToken(s,6); /error ln.seekg(-1,ios:cur); state=0; break;default: break; 7.測(cè)試用例待測(cè)字符串：void fun() int a=2,b=3,3a; a+;b-; a+=b; b*=a; int c=a+4; int d=b*5; 產(chǎn)生結(jié)果在out.txt中（注意，無(wú)論輸入輸出文件都要保存在E盤根目錄下） 8.出現(xiàn)的問(wèn)題與解決方案 本實(shí)驗(yàn)的難點(diǎn)就是進(jìn)行有效地進(jìn)行狀態(tài)如轉(zhuǎn)換，先對(duì)每一個(gè)簡(jiǎn)單部分，如空白符、id、digit等畫出自動(dòng)機(jī)狀態(tài)，然后由NFA->DFA，添加一個(gè)唯一的初始狀態(tài)，產(chǎn)生式連接。再將DFA中等價(jià)的狀態(tài)合并最后變成DFA0。這樣便大大簡(jiǎn)化了代碼量，也使得邏輯思維更加清晰。 9.自我體會(huì) 將理論運(yùn)用到實(shí)際，不僅可以幫我們更好地復(fù)習(xí)理論知識(shí)，還可以讓我們發(fā)發(fā)掘到一些更深刻層面上的東西。通過(guò)本次實(shí)驗(yàn)，我深入了解了詞法分析的過(guò)程，對(duì)NFA,DFA,DFA0之間的轉(zhuǎn)換也更能更加熟練地運(yùn)用。這次實(shí)驗(yàn)還有許多需要加強(qiáng)的地方，比如還可以對(duì)id的類型進(jìn)行明確分類，是函數(shù)還是變量，是什么類型的，返回類型是什么等等。之后有機(jī)會(huì)的話，我一定會(huì)更加深入的研究，將這個(gè)實(shí)驗(yàn)更加完善。