東南大學(xué)編譯原理詞法分析器實驗報告.doc

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

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