編譯原理課程設計報告SeuLex

1、編譯原理課程設計設計報告 組長：廖桉冬 09012431 成員：陳世宇 09012430涂佳辰 09012429東南大學計算機科學與工程學院二0 1 5年5月設計任務名稱SeuLex完成時間5.22驗收時間本組成員情況學 號姓 名承 擔 的 任 務成 績09012431廖桉冬整體設計、代碼實現(xiàn)RE到NFA、NFA到DFA、DFA最小化、狀態(tài)轉(zhuǎn)換表的設計、cpp文件驅(qū)動09012430陳世宇.l解析09012429涂佳辰.cpp文件輸出注：本設計報告中各部分如果頁數(shù)不夠，請自行擴頁。原則是一定要把報告寫詳細，能說明本組設計的成果和特色，能夠反映小組中每個人的工作。報告中應該敘述設計中的每個模塊。

2、設計報告將是評定各人成績的重要依據(jù)之一。1 編譯對象與編譯功能1.1 編譯對象（作為編譯對象的C語言子集的詞法、語法描述）./SeuLex/Lex_Source_Code.l 是lex的源代碼文件，也是Lex解析的目標文件1.2 編譯功能（所完成的項目功能及對應的程序單元）1. SeuLex：主控程序入口2. LexFileReader：對lex輸入文件的解析，得到正規(guī)表達式3. Infix2Postfix：便于狀態(tài)集計算，中綴轉(zhuǎn)后綴，并將運算符(| * + ? .)特殊化4. NFA：對單一正規(guī)表達式，構(gòu)造NFA5. MergedNFA：多個NFA合并到一起，標記中止狀態(tài)6. DFA：確定化

3、NFA狀態(tài)、閉包運算、最小化DFA，比對中止狀態(tài)確定規(guī)約的表達式編號7. CodeGen：將數(shù)據(jù)代碼化寫入cpp，添加頭部、驅(qū)動程序2. 主要特色1. 正規(guī)定義段只接受形如A-Z的定義2. 規(guī)則段中.表示所有單個字符3. 規(guī)則段中*表示閉包運算4. 規(guī)則段中+表示一個或一個以上的重復5. 規(guī)則段中?表示空或一次6. 規(guī)則段中|表示或7. 規(guī)則段中連接運算符省略8. 規(guī)則段中表示或，如果里面有形如 A-Z 的內(nèi)容則表示 A|B|。 。 。|Z9. 規(guī)則段中表示花括號內(nèi)為正規(guī)定義，需要到正規(guī)定義段尋找其含義10. 規(guī)則段中”表示引號中的內(nèi)容是定義的完整字符11. 規(guī)則段中()表示優(yōu)先級12. 規(guī)則

4、段中如果想將上述符號當作字符來看待，則需要在該字符前加上轉(zhuǎn)義符13. 生成的 C+程序文件名為 Seu_Lex_Analysis.cpp14. 生成程序中有 seuLex()函數(shù)以供調(diào)用，其返回值為 int 型15. 用戶可以在規(guī)則段加入 return 語句3 概要設計與詳細設計（由總到分地介紹SeuLex和SeuYACC的設計，包括模塊間的關系，具體的算法等。采用面向?qū)ο蠓椒ǖ?，同時介紹類（或?qū)ο螅┲g的關系。在文字說明的同時，盡可能多采用規(guī)范的圖示方法。）3.1 概要設計（以描述模塊間關系為主）（圓角框粗體為5個主要模塊，方框為交互的對象實例。*中綴轉(zhuǎn)后綴集成在FileReader中）3.

5、2 詳細設計（以描述數(shù)據(jù)結(jié)構(gòu)及算法實現(xiàn)為主）LexFileReader：數(shù)據(jù)結(jié)構(gòu)：RandomAccessFile：隨機字節(jié)讀取，用于跳過部分數(shù)據(jù)，和讀取一行算法：1.根據(jù)各部分不同的分隔符“%、%、%”來讀取某一部分的數(shù)據(jù)，頭區(qū)域、規(guī)則定義、子程序；2.根據(jù)每行不同數(shù)據(jù)（表達式、動作）的分隔符“t”，將表達式和數(shù)據(jù)分別放到不同的數(shù)組存放；3.對含有正則表達式的表達式預先記錄，如果讀取到就按照正則表達式規(guī)則擴展。Infix2Postfix：數(shù)據(jù)結(jié)構(gòu)：Stack：用棧將中綴表達式轉(zhuǎn)化為后綴表達式算法：1. 區(qū)分有幾種運算符（+、？、*、|、.），分別表示（1或多、0或1、0或多、或、與）；其中（

6、+、？、*）是集合符號，針對單個或是（）中的字符個數(shù)進行定義；而（|、.）是對兩個字符的并與關系描述；因此只需要將（|、.）后綴即可；2.對連續(xù)的多個字符需要添加AND（優(yōu)先級高）即“.”是后期自動加入: if（i是字符） s+=i ； if（i+1是字符） 彈出棧中操作符 壓入.3.對含括號（擴展的），因為括號和AND優(yōu)先級高： if（i是(） 壓入左括號i ； if（i是)） 彈出棧中所有操作符 拋棄( if（i是+、？、*）s+=i； if（i是|）彈出棧中已有的高優(yōu)先級（左結(jié)合） 將|壓入棧中；4.為了區(qū)分原有的符號，將（+、？、*、|、.）正規(guī)表達式運算符設置為128-132，避免沖

7、突。NFA：數(shù)據(jù)結(jié)構(gòu):StateTable：NFA狀態(tài)轉(zhuǎn)換表，行為狀態(tài)數(shù)，列對應0-127的各個字符算法：1. 根據(jù)書上的正規(guī)表達式轉(zhuǎn)NFA算法，將每一個正規(guī)表達式都轉(zhuǎn)換成一個NFA2. 讀取->字符：0-c->1，構(gòu)造出一個有兩個狀態(tài)的NFA。3. 讀取->運算符：（+、？、*、|、.），如書上所示，進行NFA（StateTable）的擴展、修改。MergedNFA：數(shù)據(jù)結(jié)構(gòu):StateTable算法：把多個NFA連接到一起，第一個NFA狀態(tài)（0->n），則第二個為（n->n+m），依次修改狀態(tài)數(shù)，并復制原來的table到新的位置。DFA：數(shù)據(jù)結(jié)構(gòu):StateT

8、able：MergedNFANFA轉(zhuǎn)換表LinkedList<Set<Integer>> UnmarkedDFAstates：新產(chǎn)生的還未進行閉包運算的狀態(tài)集HashMap<Set<Integer>, Integer> DFAstates：產(chǎn)生的狀態(tài)集編號HashMap<Set<Integer>, Set<Integer>> DFAtrsTable：最終的DFA狀態(tài)轉(zhuǎn)換表算法：1. 針對MergedNFA，求epsilon閉包，也就是可達路徑查詢。如書。2. 從狀態(tài)0出發(fā)求epsilon閉包，將集合放入DFAs

9、tates，編號為0(I0)；3. 對狀態(tài)集I0尋找所有可能的跳轉(zhuǎn)路徑move(I0,c)，并求epsilon閉包，得到新的集合I： if(I已經(jīng)存在) 在DFA狀態(tài)表中改寫上對應的(In,c)=m；if(I不存在) 將I加入未標記 和編號組（自動編號）4.對未標記的狀態(tài)集進行步驟2，直到全部都標記好CodeGen：算法：將所有的規(guī)則、轉(zhuǎn)換表寫入cpp文件。驅(qū)動程序：1. 按照最大匹配串的原則；2. 讀取目標文件，用字符指針進行讀??；3. 每讀取一個，就在規(guī)則表（DFA狀態(tài)表）上找到跳轉(zhuǎn)的狀態(tài)，如果這個狀態(tài)可歸約（屬于StatePatten），則記錄下狀態(tài)matchedState和匹配字符的長

10、度matchedLength4. 如果跳轉(zhuǎn)的狀態(tài)為終止狀態(tài)（-1），無法進行下去，則回溯找到最長的匹配長度和相應的狀態(tài)，并進行表達式對應的動作（cout）。4 使用說明4.1 SeuLex使用說明 一般使用： 將Seu_Lex_Analysis.exe和目標test.c文件（默認文件名為test）放在同一目錄下。雙擊Seu_Lex_Analysis.exe即可看到分析結(jié)果。修改規(guī)則： 修改Lex_Source_Code.l的規(guī)則，然后運行java程序得到新的cpp代碼。 重新編譯運行cpp，就可以得到新的Seu_Lex_Analysis.exe詞法分析器。5 測試用例與結(jié)果分析 可以看到最后單

11、獨“dd”字符串在C程序編寫中并不完整也沒有意義，詞法分析器只用于分析語句中的詞性，對語句的正確與否并無法判斷。 所以詞法分析器要和語法分析器一起使用，才能檢測代碼的正確與否。6 課程設計總結(jié)（包括設計的總結(jié)和需要改進的內(nèi)容）本次課程設計主要進行Lex的設計，了解了編譯器的工作原理以及動態(tài)構(gòu)造編譯器的方法。詞法分析器對代碼中的詞句進行分析分類，與模式匹配有所類似。本次試驗中，將任意的詞句規(guī)則轉(zhuǎn)化為正規(guī)表達式RE，然后就可以構(gòu)造出NFA-DFA轉(zhuǎn)換表，應用在編譯器中就可以動態(tài)的識別這一詞句。難點主要在于：將自然語言的詞句或者正則表達式轉(zhuǎn)換成RE，需要添加一些計算機可以識別的計算符；將RE-NFA-DFA的轉(zhuǎn)換圖、轉(zhuǎn)換表映射到代碼算法中，不止有table表格，還需要用到集合Set和棧Stack輔助操作；最小化劃分時，因為有多個終止狀態(tài)對應著不同的表達式，所以對終止狀態(tài)需要分開。改進：對自然語言的識別使用的是關鍵字，如“、t等