編譯原理課程設(shè)計(jì)報(bào)告SeuLex

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

2、設(shè)計(jì)報(bào)告將是評(píng)定各人成績(jī)的重要依據(jù)之一。1 編譯對(duì)象與編譯功能1.1 編譯對(duì)象（作為編譯對(duì)象的C語言子集的詞法、語法描述）./SeuLex/Lex_Source_Code.l 是lex的源代碼文件，也是Lex解析的目標(biāo)文件1.2 編譯功能（所完成的項(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：確定化

3、NFA狀態(tài)、閉包運(yùn)算、最小化DFA，比對(duì)中止?fàn)顟B(tài)確定規(guī)約的表達(dá)式編號(hào)7. CodeGen：將數(shù)據(jù)代碼化寫入cpp，添加頭部、驅(qū)動(dòng)程序2. 主要特色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. 規(guī)則段中()表示優(yōu)先級(jí)12. 規(guī)則

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

5、2 詳細(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)算符（+、？、*、|、.），分別表示（1或多、0或1、0或多、或、與）；其中（

6、+、？、*）是集合符號(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是字符） 彈出棧中操作符 壓入.3.對(duì)含括號(hào)（擴(kuò)展的），因?yàn)槔ㄌ?hào)和AND優(yōu)先級(jí)高： if（i是(） 壓入左括號(hào)i ； if（i是)） 彈出棧中所有操作符 拋棄( if（i是+、？、*）s+=i； if（i是|）彈出棧中已有的高優(yōu)先級(jí)（左結(jié)合） 將|壓入棧中；4.為了區(qū)分原有的符號(hào)，將（+、？、*、|、.）正規(guī)表達(dá)式運(yùn)算符設(shè)置為128-132，避免沖

7、突。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算法：把多個(gè)NFA連接到一起，第一個(gè)NFA狀態(tài)（0->n），則第二個(gè)為（n->n+m），依次修改狀態(tài)數(shù)，并復(fù)制原來的table到新的位置。DFA：數(shù)據(jù)結(jié)構(gòu):StateT

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

9、tates，編號(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)可歸約（屬于StatePatten），則記錄下狀態(tài)matchedState和匹配字符的長(zhǎng)

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

11、獨(dú)“dd”字符串在C程序編寫中并不完整也沒有意義，詞法分析器只用于分析語句中的詞性，對(duì)語句的正確與否并無法判斷。 所以詞法分析器要和語法分析器一起使用，才能檢測(cè)代碼的正確與否。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等