實驗1-詞法分析程序的設(shè)計與開發(fā)

1、編譯原理實驗報告課程名稱： 編譯原理班級： 計算1614實驗成績：指導教師： 付永鋼姓名： 施心萍實驗項目名稱：實驗一 詞法分析程序設(shè)計與開發(fā)學號： 7上機實踐日期： 一、實驗目的 深入理解有限自動機及其應用 掌握詞法分析程序的開發(fā)。 掌握根據(jù)語言的詞法規(guī)則構(gòu)造識別其單詞的有限自動機的方法 深入理解詞法分析程序自動生成原理二、實驗要求 掌握各類單詞的形式描述用直接轉(zhuǎn)向法實現(xiàn)有限自動機的代碼編寫。 獨立完成PL0語言的詞法分析器。 掌握詞法分析程序自動生成工具LEX的使用。三、實驗原理詞法分析是編譯過程的第一階段。它的任務(wù)就是對輸入的字符串形式的源程序按順序進行掃描，根據(jù)源程序的詞法規(guī)則識別具有

2、獨立意義的單詞（符號），并輸出與其等價的Token序列。有限自動機是描述程序設(shè)計語言單詞構(gòu)成的工具，而狀態(tài)轉(zhuǎn)換圖是有限自動機的比較直觀的描述方法。我們使用確定的有限狀態(tài)自動機，簡記為DFA。PL/0的語言的詞法分析器將要完成以下工作：（1）跳過分隔符（如空格，回車，制表符）；（2）識別諸如begin，end，if，while等保留字；（3）識別非保留字的一般標識符，此標識符值（字符序列）賦給全局量id，而全局量sym賦值為SYM_IDENTIFIER。（4）識別數(shù)字序列，當前值賦給全局量NUM，sym則置為SYM_NUMBER；（5）識別:=，=之類的特殊符號，全局量sym則分別被賦值為SYM

3、_BECOMES，SYM_LEQ，SYM_GEQ等。相關(guān)過程（函數(shù)）有g(shù)etsym()，getch()，其中g(shù)etch()為獲取單個字符的過程，除此之外，它還完成：（1）識別且跳過行結(jié)束符；（2）將輸入源文件復寫到輸出文件；（3）產(chǎn)生一份程序列表，輸出相應行號或指令計數(shù)器的值。下面給出能夠識別PL0語言中各類單詞的DFA：根據(jù)語言的詞法規(guī)則構(gòu)造出識別其單詞的確定有限自動機DFA, 僅僅是詞法分析程序的一個形式模型，距離詞法分析程序的真正實現(xiàn)還有一定的距離。狀態(tài)轉(zhuǎn)換圖的程序?qū)崿F(xiàn)通常是采用直接轉(zhuǎn)向法。直接轉(zhuǎn)向法又稱為程序中心法，是把狀態(tài)轉(zhuǎn)換圖看成一個流程圖，從狀態(tài)轉(zhuǎn)換圖的初態(tài)開始，對它的每一個狀態(tài)

4、結(jié)點都編寫一段相應的程序。四、實驗步驟一、 構(gòu)造識別單詞的自動機1.根據(jù)給定的詞法構(gòu)成規(guī)則對程序語言的單詞按類構(gòu)造出相應的狀態(tài)轉(zhuǎn)換圖，并根據(jù)具體需求對該狀態(tài)轉(zhuǎn)換圖進行完善。2. 對各類單詞的狀態(tài)轉(zhuǎn)換圖合并，構(gòu)成一個能識別語言所有單詞的狀態(tài)轉(zhuǎn)換圖。合并步驟為：(1) 將各類單詞的狀態(tài)轉(zhuǎn)換圖的初始狀態(tài)合并為一個唯一的初態(tài)；(2) 化簡調(diào)整狀態(tài)沖突和對沖突狀態(tài)重新編號；(3) 對上述形成的狀態(tài)圖進行修正，以滿足識別合適單詞的要求。(4) 如有必要，在合適的位置增加出錯狀態(tài)。二、 用直接轉(zhuǎn)向法實現(xiàn)有限自動機的代碼，生成對應的詞法分析程序。要嚴格按照給出的DFA，對每個狀態(tài)編寫對應的識別代碼，然后對每個

5、狀態(tài)的代碼用合適的分支、循環(huán)等語句進行整合，完成整個代碼的合成工作，并上機進行調(diào)試。對實現(xiàn)的代碼進行測試，給出合適的測試用例（要求至少有3個用例，二個正確識別所有的保留字、標識符、分界符、數(shù)字等；另外一個識別錯誤的單詞。1. 樣例1輸入輸出 生成的txt程序列表2. 樣例2輸入（部分）輸出（部分）生成的txt程序列表（部分）3. 樣例3（小數(shù)）三、 用自動生成工具LEX生成上述給定DFA所對應的PL0語言的詞法分析程序。并進行調(diào)試，用上述3個測試用例進行測試，給出測試結(jié)果。編寫LEX文件運用flex生成lex.yy.c文件運行結(jié)果樣例1樣例2（部分）樣例3（小數(shù)）五、實驗小結(jié)FLEX通過對LE

6、X源文件的掃描自動生成相應的語法分析函數(shù)，生成lex.yy.c程序。LEX具有“最長匹配原則”和“最先匹配原則”，能夠使用簡潔的正規(guī)表達式去實現(xiàn)語法分析程序，而且lex.yy.c中定義了很多用戶可定義的全局變量以及在LEX源文件的動作中可調(diào)用的函數(shù)和宏，具有良好的可移植性。但是LEX對源文件的格式要求非常嚴格，而且LEX本身的查錯能力很弱，所以書寫時一定要特別注意。C語言提供大量的函數(shù)，其中包括系統(tǒng)生成的函數(shù)和用戶定義的函數(shù)，語法也很容易理解，使用C語言實現(xiàn)語法分析程序可以較好地掌握程序的分支和流程，但是代碼量很多，容易出現(xiàn)錯誤，書寫的時候需要特別細心。實驗的處理單詞集(僅供參考)（注：單詞種類統(tǒng)一分類如下：）單詞符號 單詞種類空0標識符 1整數(shù) 2+ 3- 4 * 5 /6= 7 8 9 10= 12(13) 14