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

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

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

4、 規(guī)則段中 () 表示優(yōu)先級(jí)12.規(guī)則段中如果想將上述符號(hào)當(dāng)作字符來看待，則需要在該字符前加上轉(zhuǎn)義符13. 生成的 C+程序文件名為14. 生成程序中有 seuLex() 函數(shù)以供調(diào)用，其返回值為 int 型15. 用戶可以在規(guī)則段加入 return 語句4v1.0可編輯可修改3 概要設(shè)計(jì)與詳細(xì)設(shè)計(jì)（由總到分地介紹 SeuLex 和 SeuYACC的設(shè)計(jì)，包括模塊間的關(guān)系，具體的算法等。采用面向?qū)ο蠓椒ǖ模瑫r(shí)介紹類（或?qū)ο螅┲g的關(guān)系。在文字說明的同時(shí)，盡可能多采用規(guī)范的圖示方法。 ）概要設(shè)計(jì)（以描述模塊間關(guān)系為主）（圓角框粗體為5 個(gè)主要模塊，方框?yàn)榻换サ膶?duì)象實(shí)例。* 中綴轉(zhuǎn)后綴集成在5v

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

6、、 | 、 . ），分別表示（1 或多、 0 或 1、 0 或多、或、與） ；其中（+、 * ）是集合符號(hào)，針對(duì)單個(gè)或是（）中的字符個(gè)數(shù)進(jìn)行定義；而（| 、 . ）是對(duì)兩個(gè)字符的并與關(guān)系描述；因此只需要將（| 、. ）后綴即可；2. 對(duì)連續(xù)的多個(gè)字符需要添加 AND（優(yōu)先級(jí)高）即 “ . ” 是后期自動(dòng)加入 :if（ i 是字符） s+=i；if（ i+1 是字符）彈出棧中操作符壓入 . 6v1.0可編輯可修改3. 對(duì)含括號(hào)（擴(kuò)展的） ，因?yàn)槔ㄌ?hào)和 AND 優(yōu)先級(jí)高：if（ i 是 ( ） 壓入左括號(hào)i；if（ i 是 ) ） 彈出棧中所有操作符拋棄 ( if（ i 是 +、* ） s+=i

7、；if（ i 是 | ）彈出棧中已有的高優(yōu)先級(jí)（左結(jié)合）將| 壓入棧中；4. 為了區(qū)分原有的符號(hào)，將（ +、* 、 | 、. ）正規(guī)表達(dá)式運(yùn)算符設(shè)置為128-132 ，避免沖突。NFA：數(shù)據(jù)結(jié)構(gòu) :StateTable： NFA狀態(tài)轉(zhuǎn)換表，行為狀態(tài)數(shù)，列對(duì)應(yīng)0-127 的各個(gè)字符算法：1.根據(jù)書上的正規(guī)表達(dá)式轉(zhuǎn)NFA算法，將每一個(gè)正規(guī)表達(dá)式都轉(zhuǎn)換成一個(gè)NFA2.讀取 - 字符： 0-c-1 ，構(gòu)造出一個(gè)有兩個(gè)狀態(tài)的NFA。3.讀取 - 運(yùn)算符：（ +、 * 、 | 、 . ），如書上所示，進(jìn)行 NFA（ StateTable）的擴(kuò)展、修改。MergedNFA：數(shù)據(jù)結(jié)構(gòu) :StateTable算

8、法：把多個(gè) NFA連接到一起， 第一個(gè) NFA狀態(tài)（ 0-n ），則第二個(gè)為 （ n-n+m），依次修改狀態(tài)數(shù)，并復(fù)制原來的table到新的位置。DFA：7v1.0可編輯可修改數(shù)據(jù)結(jié)構(gòu) :StateTable： MergedNFANFA轉(zhuǎn)換表LinkedListSet UnmarkedDFAstates：新產(chǎn)生的還未進(jìn)行閉包運(yùn)算的狀態(tài)集HashMapSet, Integer DFAstates：產(chǎn)生的狀態(tài)集編號(hào)HashMapSet, Set DFAtrsTable：最終的 DFA狀態(tài)轉(zhuǎn)換表算法：1. 針對(duì) MergedNFA，求 epsilon 閉包，也就是可達(dá)路徑查詢。如書。2.從狀態(tài) 0出

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

10、tePatten），則記錄下狀態(tài)matchedState和匹配字符的長度matchedLength4. 如果跳轉(zhuǎn)的狀態(tài)為終止?fàn)顟B(tài)（ -1 ），無法進(jìn)行下去，則回溯找到最長的匹配長度和相應(yīng)的狀態(tài)，并進(jìn)行表達(dá)式對(duì)應(yīng)的動(dòng)作（cout ）。8v1.0可編輯可修改4 使用說明SeuLex 使用說明一般使用：將和目標(biāo)文件（默認(rèn)文件名為test ）放在同一目錄下。雙擊即可看到分析結(jié)果。修改規(guī)則：修改的規(guī)則，然后運(yùn)行java 程序得到新的 cpp 代碼。重新編譯運(yùn)行 cpp，就可以得到新的詞法分析器。9v1.0可編輯可修改5 測試用例與結(jié)果分析可以看到最后單獨(dú)“ dd”字符串在C程序編寫中并不完整也沒有意義，

11、詞法分析器只用于分析語句中的詞性，對(duì)語句的正確與否并無法判斷。所以詞法分析器要和語法分析器一起使用，才能檢測代碼的正確與否。10v1.0可編輯可修改6 課程設(shè)計(jì)總結(jié) （包括設(shè)計(jì)的總結(jié)和需要改進(jìn)的內(nèi)容）本次課程設(shè)計(jì)主要進(jìn)行Lex 的設(shè)計(jì)，了解了編譯器的工作原理以及動(dòng)態(tài)構(gòu)造編譯器的方法。詞法分析器對(duì)代碼中的詞句進(jìn)行分析分類，與模式匹配有所類似。本次試驗(yàn)中， 將任意的詞句規(guī)則轉(zhuǎn)化為正規(guī)表達(dá)式RE，然后就可以構(gòu)造出NFA-DFA轉(zhuǎn)換表，應(yīng)用在編譯器中就可以動(dòng)態(tài)的識(shí)別這一詞句。難點(diǎn)主要在于：將自然語言的詞句或者正則表達(dá)式轉(zhuǎn)換成RE，需要添加一些計(jì)算機(jī)可以識(shí)別的計(jì)算符；將 RE-NFA-DFA的轉(zhuǎn)換圖、 轉(zhuǎn)換表映射到代碼算法中，不止有 table表格，還需要用到集合Set 和棧 Stack 輔助操作； 最小化劃分時(shí)， 因?yàn)橛卸鄠€(gè)終止?fàn)顟B(tài)對(duì)應(yīng)著不同的表達(dá)式，所以對(duì)終止?fàn)顟B(tài)需要分開。改進(jìn)：對(duì)自然語言的識(shí)別使用的是關(guān)鍵字，如“、t等特殊分隔符，當(dāng)規(guī)則