編譯原理課程設計ll遞歸下降分析器(編輯修改稿)

　

【文章內容簡介】 會自動選定錯誤行編譯成功，生成并顯示token串、符號表、四元式與目標代碼 [在此處鍵入]測試if與while語句，而且while嵌套在if當中測試goto語句，結果正確。[在此處鍵入]測試優化，輸入課件中的代碼，結果與課件一樣。陳火旺.《程序設計語言編譯原理》（第3版）.北京：、美 Alfred Ravi Sethi Jeffrey ，姜守旭譯.《編譯原理》.24 [在此處鍵入]北京：、美 Kenneth .《編譯原理及實踐》.北京：、金成植著.《編譯程序構造原理和實現技術》.北京：、體會和建議。直接拷貝好歹也檢查一下錯誤對于編譯原理的這次課程設計，自己經歷了從剛開始的不懂224。明白任務的要求和內容224。理論知識的了解224。開始著手寫代碼224。完成基本功能224。根據DFA及自頂向下等理論修改完善代碼等這些過程。自己著手寫詞法分析的時候還不清楚詞法分析的任務內容，還不知道詞法分析的結果是什么，詞法分析出錯的情況和類型有哪些，也總是將詞法分析和語法分析混在一起，不明白哪些錯誤在詞法分析中報，哪些錯誤在語法分析中判斷，后來經過查書、網上資料、請教同學等途徑逐步清晰了詞法分析的工作內容是從源代碼文件中獲取出Token，供語法分析使用。在充分了解了語法分析需要哪些信息時，我才真正了解了詞法分析的工作內容和目標，才知道詞法分析需要完成哪些任務獲取到哪些信息。充分了解了詞法分析的任務之后，就開始理論知識的學習。經過揣摩書上的例子，自己理解和掌握了怎么設計過濾注釋和分析程序中Token的DFA，于是開始根據設計好的DFA進行編碼，最后經過調試已經可以正確地完成詞法階段的任務了。這只是詞法分析的原始代碼，在之后還進行了兩次徹底的改動。雖然之前寫的詞法分析的代碼已經完成了詞法分析的需求，也是根據DFA的原理編寫的，但是在代碼結構上卻難以體現，在對書上的根據已知DFA寫代碼的例子進行了詳細的研究之后，發現自己的代碼并沒有像書上那樣完全按照所依據的DFA各狀態轉移的關系進行編寫，所以對代碼進行了重寫，像書上一樣嚴格按照狀態之間轉移的方式進行編寫，將狀態劃分成11個狀態，狀態分別按1~11進行標注，程序也按照DFA來編寫，也實現了詞法分析的功能。再后來寫報告的時候，發現分析出Token的那個DFA并不是最簡的，有很多多余的狀態，完全可以用一個flag標志來標識，從而簡化代碼結構，于是又重寫了一次詞法分析函數scan()的代碼，將狀態縮減為5個，且不再用15來表示，而是像書上那樣分別取了名字（START、INNUM、INID、INDBSYM、DONE），同時為了簡化代碼將輸出Token到文件的部分從scan()中剝離開來，而在Lexical類中加了一個printToken()的函數，使scan()函數邏輯更加清晰，使讀者能夠容易地將代碼與DFA進行查看比照。在寫語法分析的時候，已經對編譯器的語法分析的內容有了一定的了解，所以直接進行了理論的學習。首先自己對遞歸向下分析法進行了學習，將書上的幾個遞歸向下分析的偽代碼看過之后，自己對遞歸向下的分析方法的原理有了初步的認識，大概知道了根據文法怎么分析，但是對于如何編寫代碼卻還在此處鍵入]是難以下手，于是就對照TINY語言的文法看了幾遍書后面的TINY語言的遞歸向下分析的語法分析程序，這樣就基本知道了C語言的語法分析程序怎么寫。由于C語言給出的文法有左遞歸存在，于是自己將存在左遞歸的文法改寫成EBNF的形式，并據此進行代碼編寫。由于在編寫代碼的過程中需要確定分析是否正確或選擇多個文法中的某一個文法進行分析，有時必須探測需要的或下一個Token的類型，在這種情況下需要求First集合，在推導中若存在empty，又需要求Follow集合，所以這樣又需要我了解First集合和Follow集合，自己在程序中也根據求出的First集合和Follow集合進行判斷，以確定程序的走向。在編寫過程中，還有一類問題，就是存在公共左因子，如文法expression→ var = expression | simpleexpression，左因子為ID，在分析過程中，由于已經取出了一個ID的Token，且生成了一個IdK的節點，但是在當前狀態無法確定是哪一個推導，然而IdK節點已經生成，又無法回退，并且是使用自頂向下的分析方法，已經生成的IdK在程序上方無法使用，自己通過查閱資料等途徑的學習確定了在這種情形下的處理方式：將已經生成的IdK節點傳到下方的處理程序，所以TreeNode * simple_expression(TreeNode * k)、TreeNode * additive_expression(TreeNode * k)等函數都被設計成有節點類型參數的函數，目的就是將已經生成的節點傳到下面的分析函數中去。通過這次的編譯原理課程的學習和實踐，自己獲益良多。首先最基本的成果是完成了課程設計的任務，實現了編譯器的詞法分析和語法分析階段的功能，詞法分析主要能過濾注釋、分析出語法分析階段需要的Token并滿足語法階段的所有要求，能夠判別詞法分析階段是否出錯和出錯類型和位置。語法分析主要能根據遞歸向下的分析思想和C文法對詞法分析獲取的Token進行語法分析，能夠構造出語法樹，能夠判別語法分析過程中是否出錯以及出錯位置和錯誤類型。由于在編寫程序過程中，涉及到了正則表達式、DFA、提取公共左因子、消除左遞歸、EBNF、求First集合和Follow集合、遞歸向下分析方法以及編程語言方面的知識，所以，通過本次的課程設計的實踐，使得自己對編譯原理這門課的許多知識點有了更加深刻和具體的理解，而不再只限制于做題。此外，對以前那些已掌握的知識有了溫習和動手鍛煉的機會。如：以前在編譯原理課上雖然知道First集合和Follow集合怎么求的，卻不知道First集合和Follow集合到底是干什么的，通過編寫程序自己明白了他們的實際作用，使得自己不僅知其然還知其所以然，從而使得自己加深了對知識點的理解和掌握。由于以前編寫代碼都是使用JAVA語言，所以C/C++很多內容都忘記了，通過本次的實踐，自己又重新拾起了以前的知識。此外，由于在做報告的時候，需要描繪DFA和程序流程圖，使得自己初步掌握了使用visio和word畫圖的能力。此外，對于文檔的編寫和美化自己也獲得了許多有用的經驗。[第四篇：編譯原理課程設計報告武 漢 紡 織 大 學編譯原理課程設計實驗報告學院：數學與計算機 專業：計算機 姓名： 班級： 學號： 編譯原理編譯原理課設報告一、實驗目的加強對編譯程序的整體認識和了解，鞏固《編譯原理》課程所學知識。通過本次課程設計掌握編譯程序調試技巧和設計編譯程序一般的原則，加深對詞法分析、語法分析、語義分析等編譯階段及實用編譯系統的認識。使學生能將編譯理論與實際應用結合起來，提高學生軟件開發的能力。二、實驗內容1）仔細閱讀PL/0編譯程序文本（編譯原理(第二版)張素琴 呂映芝 蔣維杜 戴桂蘭 主編清華大學出版社），并上機調試通過。2）對PL/0語言進行下列擴充（1）擴充一維整型數組。擴充var數組：VAR （：）〈下界〉和〈上界〉可用常量標識名。（2）擴充條件語句的功能使其為：IFTHEN[ELSE]（3）增加repeat重復語句: REPEAT{。}UNTIL 可根據自己具體情況從中選擇2個以上題目進行擴充。三、實驗原理PL/0語言可以看成PASCAL語言的子集，它的編譯程序是一個編譯解釋執行系統。PL/0的目標程序為假想棧式計算機的匯編語言，與具體計算機無關。PL/0的編譯程序和目標程序的解釋執行程序都是用PASCAL語言書寫的，因此PL/0語言可在配備PASCAL語言的任何機器上實現。其編譯過程采用一趟掃描方式，以語法分析程序為核心，詞法分析和代碼生成程序都作為一個獨立的過程，當語法分析需要讀單詞時就調用詞法分析程序，而當語法分析正確需要生成相應的目標代碼時，則調用代碼生成程序。用表格管理程序建立變量、常量和過程表示符的說明與引用之間的信息聯系。當源程序編譯正確時，PL/0編譯程序自動調用解釋執行程序，對目標代碼進行解釋執行，并按用戶程序的要求輸入數據和輸出運行結果。四、實驗分析PL/0語言編譯程序采用以語法分析為核心、一遍掃描的編譯方法。詞法分析和代碼生成作為獨立的子程序供語法分析程序調用。語法分析的同時，提供了出錯報告和出錯恢復的功能。在源程序沒有錯誤編譯通過的情況下，調用類PCODE解釋程序解釋執行生成的類PCODE代碼。詞法分析子程序分析：詞法分析子程序名為GETSYM，功能是從源程序中讀出一個單詞符號（TOTAKEN），把它的信息放入全局變量 SYM、ID和NUM中，字符變量放入CH中，語法分析器需要單詞時，直接從這三個變量中獲得。Getch過程通過反復調用Getch子過程從源程序過獲取字符，并把它們拼成單詞。GETCH過程中使用了行緩沖區技術以提高程序運行效率。詞法分析器的分析過程：調用GETSYM時，它通過GETCH過程從源程序中獲得一個字符。如果這個字符是字母，則繼續獲取字符或數字，最終可以拼成一個單詞，查保留字表，如果查到為保留字，則把SYM變量賦成相應的保留字類型值；如果沒有查到，則這個單詞應是一個用戶自定義的標識符（可能是變量名、常量名或是過程的名字），把SYM置為IDENT，把這個單詞存入ID變量。查保留字表時使用了二分法查找以提高效率。如果Getch獲得的字符是數字，則繼續用Getch獲取數字，并把它們拼成一個整數或實數，然后把SYM置為 INTEGER或REAL，并把拼成的數值放入NUM變量。如果識別出其它合法的符號（比如：賦值號、大于號、小于等于號等），則把SYM則成相應的類型。如果遇到不合法的字符，把SYM置成NUL。語法分析子程序分析：語法分析子程序采用了自頂向下的遞歸子程序法，語法分析同時也根據程序的語義生成相應三元代碼，并提供了出錯處理的機制。語法分析主要由分程序分析過程（BLOCK）、參數變量分析過程（ParaDeclaration）、參數變量處理過程（ParaGetSub）、數組處理過程（ParaGetSub）、常量定義分析過程（ConstDeclaration）、變量定義分析過程（Vardeclaration）、語句分析過程（Statement）、表達式處理過程（Expression）、項處理過程（Term）、因子處理過程（Factor）和條件處理過程（Condition）構成。這些過程在結構上構成一個嵌套的層次結構。除此之外，還有出錯報告過程（Error）、代碼生成過程（Gen）、測試單詞合法性及出錯恢復過程（Test）、登錄名字表過程（Enter）、查詢名字表函數（Position）以及列出類 PCODE代碼過程（Listcode）作過語法分析的輔助過程。由PL/0的語法圖可知：一個完整的PL/0程序是由分程序和句號構成的。因此，本編譯程序在運行的時候，通過主程序中調用分程序處理過程block來分析分程序部分（分程序分析過程中還可能會遞歸調用block過程），然后，判斷最后讀入的符號是否為句號。如果是句號且分程序分析中未出錯，則是一個合法的PL/0程序，可以運行生成的代碼，否則就說明源PL/0程序是不合法的，輸出出錯提示即可。ifthenelse語句的處理：按if語句的語法，首先調用邏輯表達式處理過程處理if語句的條件，把相應的真假值放到數據棧頂。接下去記錄下代碼段分配位置（即下面生成的jpc指令的位置），然后生成 條件轉移jpc指令（遇0或遇假轉移），轉移地址未知暫時填0。然后調用語句處理過程處理 then語句后面的語句或語句塊。then后的語句處理完后，如果遇到else，就調用語句處理過程處理else語句后面的語句或語句塊，這時當前代碼段分配指針的位置就應該是上面的jpc指令的轉移位置。通過前面記錄下的jpc指令的位置，把它的跳轉位置改成當前的代碼段指針位置，否則沒遇到else，那么此時的當前代碼段分配指針的位置也是上面jpc指令的轉移位置，也是通過前面記錄下的jpc位置指令的位置，把它的跳轉到當前的代碼段指針位置。Repeat語句的處理：首先用CX1變量記下當前代碼段分配位置，作為循環的開始位置。然后通過遞歸調用語句分析過程分析，直到遇到until保留字，如果未對應until則出錯。調用條件表達式處理過程生成相應代碼把結果放在數據棧頂，再生成條件轉移指令，轉移位置為上面記錄的CX1。五、相關代碼及運行結果實驗代碼； ： include include include include include include ifndef WIRTH_ZYC_ define WIRTH_ZYC_ using namespace std。const int norw = 16。// reserved words 保留字的個數const int txmax = 100。// length of identifier table 標示符表的長度（容量）const int al = 10。// length of identifiers 標示符的最大長度const int nmax = 14。// digits in numbers 數字的最大長度 const int amax = 2047。// maximum address 尋址空間const int levmax = 3。// maximum depth of block nesting 最大允許的塊嵌套層數 const int cxmax = 200。// size of code array 類PCODE目標代碼數組長度（可容納代碼行數）const int lineLength = 82。// 行緩沖區長度typedef enum {NUL,IDENT,NUMBER,PLUS,MINUS,TIMES,SLASH,ODDSYM,EQL,NEQ,LSS,LEQ,GTR,GEQ,LPAREN，RPAREN,COMMA,SEMICOLON,PERIOD,BECOMES,BEGINSYM,ENDSYM,IFSYM,THENSYM,WHILESYM，WRITESYM,READSYM,DOSYM,CALLSYM,CONSTSYM,VA