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

《東南大學(xué)編譯原理詞法分析器實(shí)驗(yàn)報(bào)告.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《東南大學(xué)編譯原理詞法分析器實(shí)驗(yàn)報(bào)告.doc（11頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

詞法分析設(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 Keywords; //保存關(guān)鍵字 map Sep; //保存界符 map Relop; //保存比較運(yùn)算符 map Op; //保存其他運(yùn)算符 mapid; //保存輸入字符串中的id mapnum; //保存數(shù)字 vectorToken; //保存token序列，大小未知，所以采用vector保存 6. 核心算法描述 （1）void addToken(string s,int type）s為找到的字符串，type為可能類(lèi)型。 將分析出來(lái)的token()序列添加到Token序列表中。如果是類(lèi)型為1，查看關(guān)鍵詞表，若找到，其類(lèi)型為關(guān)鍵詞并將其以類(lèi)型為關(guān)鍵詞存儲(chǔ)到Token表中；若未找到，則查找id表，若找到，說(shuō)明該id已經(jīng)出現(xiàn)過(guò)，否則添加新的id到id表中，將該i字符串以類(lèi)型為id添加到Token表中。如果類(lèi)型為2，在界符表中查找，如果找到以類(lèi)型為界符存儲(chǔ)到Token表中，同理其他幾種類(lèi)型。可能類(lèi)型為1--5，如果出現(xiàn)其他類(lèi)型表示是詞法分析器中發(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); }else{ l_it=id.find(s); if (l_it==id.end()) { id[s]=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()) { num[s]=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類(lèi)型的錯(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; }else{ addToken(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盤(pán)根目錄下） 8. 出現(xiàn)的問(wèn)題與解決方案 本實(shí)驗(yàn)的難點(diǎn)就是進(jìn)行有效地進(jìn)行狀態(tài)如轉(zhuǎn)換，先對(duì)每一個(gè)簡(jiǎn)單部分，如空白符、id、digit等畫(huà)出自動(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的類(lèi)型進(jìn)行明確分類(lèi)，是函數(shù)還是變量，是什么類(lèi)型的，返回類(lèi)型是什么等等。之后有機(jī)會(huì)的話，我一定會(huì)更加深入的研究，將這個(gè)實(shí)驗(yàn)更加完善。