SNL編譯器設(shè)計實驗報告

編譯原理課程設(shè)計實驗報告目錄TOC\o"1-5"\h\z\o"CurrentDocument"第一部分實驗成果統(tǒng)計表1\o"CurrentDocument"第二部分實驗簡介2\o"CurrentDocument"第三部分詞法分析3\o"CurrentDocument"第四部分語法分析64.1LL(1)法語法分析74.2遞歸下降法語法分析10第五部分語義分析19\o"CurrentDocument"第六部分程序測試22\o"CurrentDocument"第七部分實驗總結(jié)與體會28

第一部分實驗成果統(tǒng)計表姓名性別班級學(xué)號所占比例個人成績?nèi)蝿?wù)分工：（請用小四號宋體填寫）詞法分析部分程序的調(diào)試與實現(xiàn)；LL（1）語法分析部分程序的調(diào)試與實現(xiàn)；遞歸下降語法分析部分程序的調(diào)試與實現(xiàn)；語義分析部分程序的調(diào)試與實現(xiàn)；成績評定：詞法分析遞歸下降LL(1)語義分析團隊成績教師簽章備注填寫說明：1、請將首頁紅色部分信息填全，其中：班級為2位數(shù)字，保留首位的0；學(xué)號為8位數(shù)字，計算機科學(xué)與技術(shù)學(xué)院以53開頭；所占比例為百分數(shù)，精確到個位數(shù)，且所有人的所占比例之和為100%；不足四人的分組請保留后面的多余空行，請勿修改該表的結(jié)構(gòu)。2、請根據(jù)實際情況填寫任務(wù)分工部分，主要任務(wù)包括：編譯系統(tǒng)的總體分析與設(shè)計，四個具體功能的設(shè)計與實現(xiàn)，對應(yīng)的測試與驗證過程（報告正文需要列出若干組具體測試樣例與對應(yīng)結(jié)果），系統(tǒng)界面的設(shè)計與美工，以及輔助工具、視圖和文件等。3、成績評定部分由指導(dǎo)教師填寫，請勿填寫和修改。第二部分實驗簡介本實驗中實現(xiàn)了SNL編譯系統(tǒng)中的詞法分析、語法分析和語義分析。其中語法分析包括遞歸下降分析方法和LL（1）分析方法。詞法分析，以源程序為輸入，生成單詞的內(nèi)部表示TOKEN序列。語法分析，以TOKEN序列為輸入進行語法分析，并生成整個源程序的語法分析樹。在SNL編譯程序中，采用了兩種語法分析方法實現(xiàn)：LL（1）和遞歸下降法。兩種語法分析的結(jié)果是一樣的。語義分析，以語法樹為輸入生成標識符的屬性符號表以及相關(guān)的各類信息表，如數(shù)組信息表，并進行相關(guān)的語義檢查。它們?nèi)叩年P(guān)系如下：第三部分詞法分析源程序一般表現(xiàn)為字符串（機器語言稱其為ASCII碼）序列的形式，而編譯程序的翻譯工作應(yīng)該在單詞一級上進行，這與自然語言的翻譯理解過程是類似的。因此要進行編譯工作，首先要把源程序的字符序列翻譯成單詞序列。詞法分析是編譯過程的第一階段。它的任務(wù)就是對輸入的字符串形式的源程序按順序進行掃描，根據(jù)源程序的詞法規(guī)則識別具有獨立意義的單詞（符號），并輸出與其等價的TOKEN序列。TOKEN是單詞（符號）的內(nèi)部表示。完成詞法分析任務(wù)的程序稱為詞法分析程序，通常也稱為詞法分析器或掃描器（scanner）oTOKEN是單詞在編譯程序處理過程中的一種內(nèi)部表示，也是詞法分析程序?qū)Τ绦蛑懈黝悊卧~進行處理之后的輸出形式。對于一種語言而言，如何對它的單詞進行分類，每一類單詞的TOKEN數(shù)據(jù)結(jié)構(gòu)的形式如何，都沒有固定的模式，可以隨編譯程序的不同而不同。通常TOKEN的結(jié)構(gòu)可以分成兩部分，單詞的語法信息和語義信息。其中語法信息記錄的是這個單詞的種類，語義信息則記錄著這個單詞的具體信息。這樣，就能為以后的語法分析和語義分析處理單詞做好準備。SNL語法分析對每類單詞的分析結(jié)果的TOKEN結(jié)構(gòu)為三元組（詞法信息、語義信息以及該單詞在源程序中的行號）。本SNL編譯器單詞的內(nèi)部表示如下：行號（便于出錯處理）TOKEN的內(nèi)部表示語法信息及其字符串表示語義信息及其字符串表示SNL語言的單詞分類如下：（1）：保留字保留字一般是由語言系統(tǒng)自身定義的，SNL語言中的保留字有program，while，if，fi等等。（2）：標識符用來標識程序中各個對象的名稱。由用戶自己定義用來表示變量名，數(shù)組名或者過程名等。SNL語言中標識符由字母開頭，字母、數(shù)字的任意組合組成的。（3）：常量用來表示各類常數(shù)。如字符型常量，實行常量，布爾常^量^等。（4）：運算符表示程序中算術(shù)運算、邏輯運算、字符運算的確定字符或字符串。SNL語言中的運算符有+，一，*，/，〈和:二六種運算符。（5）：界限符包括逗號分號等。SNL語言中的‘；’表示一條語句結(jié)束，‘.'表示程序結(jié)束等等。實現(xiàn)詞法分析器的注意事項：保留字和標識符名字的區(qū)分復(fù)合單詞的處理向前搜索及回退數(shù)字的轉(zhuǎn)換輸入時邊界的處理注釋的處理詞法分析主要的函數(shù)有：getTokenlist（）、getNextChar（）、ungetNextChar（）、reservedLookup（）、ChainToFile（）、printTokenlist（）。getTokenlist（）函數(shù)是最主要的函數(shù)，它每次從輸入緩沖區(qū)lineBuf字符串序列中超前讀一個（有時是兩個）字符，使用確定有限自動機DFA的直接轉(zhuǎn)向處理方法。超前讀的字符如不匹配的話，還需要回退。如果得到的TOKEN是標識符的話，還需要查詢保留字表以判斷該標識符是否是保留字。產(chǎn)生詞法錯誤的時候，僅僅略過產(chǎn)生錯誤的字符，不加改正。然后將得到的TOKEN存入鏈表，當整個源程序都分析完成的時候，將TOKEN鏈表中各個TOKEN存入文件Tokenlist.txt中，將來輸出顯示TOKEN時再從Tokenlist.txt中讀取。getNextChar（）函數(shù)被getTokenlist（）函數(shù)調(diào)用，每次從輸入緩沖區(qū)lineBuf中返回一個字符，如果lineBuf中的字符全部讀完后，再從TOKEN文件中讀取下一批。如此重復(fù)下去，直到源程序字符全部讀完為止。ungetNextChar（）函數(shù)被getTokenlist（）函數(shù)調(diào)用，當文件結(jié)束標志FileEnd沒有置位的時候，將lineBuf緩沖區(qū)中的讀取指針回退一個字符。reservedLookup（）函數(shù)用在當前TOKEN是標識符的時候，需要查保留字表來判斷該TOKEN是保留字還是普通標識符。ChainToFile（）函數(shù)用在源文件處理完畢后，將TOKEN鏈表中的TOKEN一個一個地存入文本文件Tokenlist.txt中。將來可以直接在文本文件中查看tokenlist，也可以在需要輸出顯示的時候從該文件中讀取TOKEN。printTokenlist（）函數(shù)用在需要在命令行輸出顯示Tokenlist的時候，從Tokenlist.txt中讀取TOKEN，然后顯示出來。主要函數(shù)getTokenlist()的流程圖如下:第四部分語法分析語法分析是編譯程序的第二階段，也是編譯程序的核心部分。語法分析的任務(wù)是，根據(jù)語言的語法規(guī)則，對源程序進行語法檢查，并識別出相應(yīng)的語法成分。按照SNL編譯程序的模型，語法分析的輸入時從詞法分析器輸出的源程序的TOKEN序列形式，然后根據(jù)語言的文法規(guī)則進行分析處理，語法分析的輸出是無語法錯誤的語法成分，表示成語法樹的形式。語言是具有獨立意義的單詞根據(jù)一定的語法規(guī)則組成的句子的集合，句子的結(jié)構(gòu)由語法規(guī)則給出，句子的含義由語義規(guī)則給出，而對語言的語法分析就是對語言的句子結(jié)構(gòu)的分析。歸于程序設(shè)計語言而言，它的句子就是程序，程序設(shè)計語言定義的是符合其語法規(guī)則的程序的集合，因此程序設(shè)計語言的語法分析的關(guān)鍵是識別程序（句子）的語法結(jié)構(gòu)。完成語法分析任務(wù)的程序成為語法分析程序，也稱為語法分析器或簡稱分析器。本編譯器的語法分析采用自頂向下的語法分析。自頂向下分析是從文法的開始符號出發(fā)，試圖為輸入串建立一個最左推導(dǎo)，或為輸入串構(gòu)造一個語法樹。這種分析是通過對當前句型的最左非終極符，反復(fù)使用他的不同的規(guī)則進行替換和展開，以匹配輸入串來實現(xiàn)的。語法分析檢查的錯誤有：程序的開始單詞錯，表達式的開始單詞錯，語句的卡是單詞錯，表達式的后記單詞錯，語句的后記單詞錯等。標識符和常量單詞錯。如域名不是標識符等。括號類錯誤。如begin_end不匹配，（-）不配對，［-］不配對，case-end不配對，if-then-end不配對等。分隔符錯。如賦值語句后面不是賦值號，標識符表或表達式的分隔符（或后繼符）錯。4.1LL（1）語法分析LL（1）語法分析方法是一種自頂向下的語法分析方法，它是LL（k）分析方法的特例，其中k表示向前看k個符號的意思。LL（1）語法分析程序由兩部分組成的：第一部分是語法分析表，也稱為LL（1）分析矩陣；第二部分是語法分析驅(qū)動程序。LL（1）矩陣的作用是幫助當前非終極符和當前輸入符確定應(yīng)該選擇的語法規(guī)則，它的行對應(yīng)非終極符，列對應(yīng)終極符，矩陣的值有兩種：一種是產(chǎn)生式編號。另外一種是錯誤編號。LL（1）分析程序工作過程首先初始化，即把開始符壓入棧中，以后的每步分析必是下面的四種情況之一：（1）分析棧的棧頂元素是終極符，則看其是否與輸入流的頭符相匹配，如果匹配成功，則去掉棧頂元素并讀入下一個單詞；若匹配不成功，則報錯。（2）棧頂是非終極符，則用棧頂和輸入流的當前單詞去查當前矩陣，如果查得的值是產(chǎn)生式編號，則把對應(yīng)的產(chǎn)生式右部逆序壓入棧中；如果查得的值為錯誤信息，則報錯。（3）棧己空，輸入流不空，這時輸入流報錯。（4）若棧己空，輸入流也空，則語法分析成功。LL（1）工作原理如下圖：abcdefghX1X1X1X1X2X3■■■LL（1）驅(qū)動程序?aX1—nLL⑴分析表SNL語法程序的實現(xiàn)采用手工操作構(gòu)造LL（1）分析表。LL（1）分析表用一個二維矩陣表示，其中每個非終極符對應(yīng)一行，每個終極符對應(yīng)一列，一個非終極符和一個終極符可以確定矩陣中的一個元素，元素的值表示該非終極符和該終極符對應(yīng)的產(chǎn)生式。SNL的LL（1）語法分析程序共用到四個棧，分別稱為：符號棧、語法樹棧、操作符棧和操作數(shù)棧。其中，符號棧用于進行SNL的LL（1）語法分析；其他的棧是為了在語法分析過程中同時生成與源程序結(jié)構(gòu)對應(yīng)的語法樹而設(shè)置的。語法樹棧用于聲明部分和語句部分的語法樹；操作符棧和操作數(shù)棧用于生成表達式部分的語法樹。處理聲明部分和語句部分的語法樹生成時，設(shè)置一個語法樹棧，存放語法樹節(jié)點中指向兒子或者兄弟節(jié)點的指針的地址。在生成當前語法樹節(jié)點時，如果以后需要對其兒子節(jié)點或者兄弟節(jié)點賦值，則按照處理順序的逆序?qū)⑦@些兒子節(jié)點或者兄弟節(jié)點的指針的地址壓入語法樹棧，后面生成它的兒子節(jié)點或者兄弟節(jié)點時，只需彈棧，并對相應(yīng)的指針進行賦值，就可以完成所需的語法樹節(jié)點的鏈接。處理表達式時，需要另外設(shè)置兩個棧，操作數(shù)棧和操作符棧，遇到操作數(shù)壓入操作數(shù)棧，遇到操作符，則進行判斷，如果當前操作符的優(yōu)先級高于操作符棧的棧頂操作符，直接壓入操作符棧；否則，彈出棧頂操作符，并彈出操作數(shù)棧頂?shù)膬蓚€操作數(shù)，生成相應(yīng)的子樹，并對新生成的子樹的父節(jié)點（操作符節(jié)點）進行循環(huán)判斷。LL（1）語法分析的主要函數(shù)有：parseLL1（）、CreatLL1Table（）、gettoken（）、priosity（）、predict（）、newnode（）、TreeToFile（）、printTree（）、StrToEnum（）、PushSym（）、PopSym（）、PushSynTree（）、PopSynTree（）、PushOp（）、PopOp（）、ReadOpStack（）、PushNum（）、PopNum（）等等parseLL1（）函數(shù)是最主要的函數(shù)。它利用LL（1）分析表和符號棧進行語法分析，并處理終極符不匹配和文件提前結(jié)束錯誤。函數(shù)處理完成后，得到整個語法樹。CreatLL1Table（）用于創(chuàng)建LL（1）分析表。用二維數(shù)組表示LL（1）分析表，初始化二維數(shù)組所有元素為0，根據(jù)給定的LL（1）文法，對產(chǎn)生式編號。對于每個產(chǎn)生式，左部的非終極符作為行號，其Predict集中每個元素分別作為列號，二維數(shù)組中行號、列號對應(yīng)的元素賦值為該產(chǎn)生式的編號。getToken（）函數(shù)每次從Tokenlist.txt文件中讀取一個TOKENpriosity（）用于判斷當前操作符的優(yōu)先級。優(yōu)先級由高到低排序為：乘法運算符〉加法運算符〉關(guān)系運算符〉左括號＞棧底標志END。predict（）函數(shù)根據(jù)產(chǎn)生式編號選擇一個要執(zhí)行的函數(shù)。newnode（）函數(shù)用于生成樹節(jié)點。TeeToFile（）函數(shù)用于將最后產(chǎn)生的語法樹寫入SynTree.txt文件，該文件可以查看語法樹，也可以在需要顯示輸出時從中讀取語法樹。printTree（）函數(shù)用于從SynTree.txt中讀出語法樹，然后輸出顯示。StrToEnum（）用于將從Tokenlist.txt中讀取的以字符串形式存在的TOKEN的Lex域轉(zhuǎn)換成LexType枚舉類型。PushSym（）用于將當前符號入棧到符號棧。PopSym（）用于將符號棧棧頂符號出棧。PushSynTree（）用于將當前語法樹節(jié)點中指向兒子或兄弟節(jié)點的指針的地址入棧到語法樹棧。PopSynTree（）用于將語法樹棧棧頂指向樹節(jié)點的指針的地址出棧。PushOp（）用于將當前操作符入棧到操作符棧。PopOp（）用于將操作符棧棧頂操作符出棧。ReadOpStack（）用于讀取操作符棧棧頂操作符。PushNum（）用于將當前操作數(shù)入棧。PopNum()用于將操作數(shù)棧棧頂操作數(shù)出棧。LL(1)語法分析主函數(shù)parseLLl()的算法框圖如下:TES〔返回再法樹根步點指針「8企皿歸)4.2遞歸下降法（一）、遞歸下降語法基本原理綜述語法分析是編譯程序的第二階段，語法分析的任務(wù)是根據(jù)語言的語法規(guī)則對源程序進行語法檢查，并識別出相應(yīng)的語法成分。簡單地說，語法分析就是根據(jù)語言的語法規(guī)則對語言的句子結(jié)構(gòu)進行分析，看源程序的句子結(jié)構(gòu)是否符合語言語法規(guī)則的要求。語法分析的輸入是從詞法分析器輸出的TOKEN序列形式，然后根據(jù)語言的文法規(guī)則進行分析處理，語法分析的輸出是無語法錯誤的語法分析樹的形式。這一部分主要介紹遞歸下降法語法分析的原理及實現(xiàn)。遞歸下降法是語法分析中比較容易理解的一種方法，因為其采用了遞歸的結(jié)構(gòu)和思想，但這也在一定程度上影響了程序的執(zhí)行效率，所以這種方法的優(yōu)點是容易實現(xiàn)，容易理解，缺點就是這種方法的執(zhí)行效率不如LL（1）高。遞歸下降法的主要原理是對每個終極符和非終極符按其產(chǎn)生式結(jié)構(gòu)構(gòu)造相應(yīng)的語法分析子程序，其中終極符產(chǎn)生匹配命令，而非終極符則產(chǎn)生過程調(diào)用命令。其中子程序結(jié)構(gòu)與產(chǎn)生式的結(jié)構(gòu)幾乎是一致的。前面我們已經(jīng)提到對于終極符將產(chǎn)生匹配命令山&七川（），match（）命令的定義如下：Match（x）無定義，x屬于Vn檢查token二x？若是，則移位；否則，報錯，x屬于Vt~~根據(jù)遞歸下降法的基本原理和思想，我們可以將遞歸下降法語法分析主程序?qū)懗扇缦碌男问?，這個程序形式就是我我們所編寫的遞歸下降法語法分析程序的主程序格式，這樣就可以容易構(gòu)造出一個文法的語法分析程序：Programptoken:類型；Begin讀入一個tokeiftoken屬于First(S)thenSelse報錯并停機End（二）、遞歸下降語法分析程序的主要處理對象及其依賴關(guān)系我們編寫的遞歸下降語法分析程序主要對一個程序的主要部分進行分析和檢查，其中主要包括程序頭、程序聲明、類型聲明、變量聲明、過程聲明、程序體（包括各種語句序列、表達式）等，下面對各部分做簡要的說明：程序頭：程序的開始，包括保留字以及程序的名字。程序聲明：包括程序的整個聲明部分，又可以細分為類型聲明、變量聲明、過程聲明等。類型聲明：用于定義類型，其中類型可以分為基本類型（整型、字符型等）、結(jié)構(gòu)類型（數(shù)組類型、記錄類型等）和自定義類型（類型名稱為標識符，實際類型為上述兩種類型）。變量聲明：用于聲明變量，定義變量類型。過程聲明：用于聲明過程，包括參數(shù)（變參、值參）、過程中的聲明和過程體。

程序體：由語句序列組成，語句主要包括賦值語句、條件語句、循環(huán)語句、輸入語句、輸出語句、返回語句、過程調(diào)用語句（可由讀入的標識符或者其它相應(yīng)的保留字來判定屬于哪一種語句，并選擇相應(yīng)的程序進行分析。）對語句的分析可能會涉及到對表達式的處理。-~給出了遞歸下降語法分析程序所要分析處理的各種語法成分，為了能更清楚直接地反映出各語法成分之間的依賴關(guān)系，參考實驗教材上的內(nèi)容，我們給出了遞歸下降語法分析中各語法成分的依賴圖，如下圖所示：圖1.遞歸下降語法分析中各語法成分的依賴關(guān)系

（三）、遞歸下降語法分析輸出結(jié)果一一語法分析樹根據(jù)上面的敘述，我們知道遞歸下降語法分析程序的輸入是通過詞法分析程序產(chǎn)生的TOKEN序列，而作為語法分析程序的輸出，我們給出了遞歸下降語法分析程序的統(tǒng)一規(guī)范化輸出結(jié)果一一語法分析樹的基本形式。我們編寫的遞歸下降語法分析程序最終的輸出結(jié)果就是下面語法樹的形式，只不過我們是以另一種形式組織并保存在.txt文件中，但核心的思想就是下圖所示的語法樹形式。該語法樹形式不僅體現(xiàn)了語法分析程序的輸出結(jié)果，還在一定程度上反映出了各語法分析成分之間的關(guān)系。圖2.語法分析樹（四）、遞歸下降語法分析程序主要函數(shù)介紹根據(jù)之前的分析和敘述，我們已經(jīng)對遞歸下降語法分析程序進行了最基本的闡述，這些基本的闡述可以使得我們很清楚地了解遞歸下降語法分析程序所要實現(xiàn)的功能、所要分析的對象以及優(yōu)缺點等。下面我們將對遞歸下降語法分析程序中的主要函數(shù)進行介紹，主要介紹函數(shù)的聲明和功能等，并在最后給出各主要函數(shù)之間的調(diào)用關(guān)系。按照這些函數(shù)的聲明和調(diào)用關(guān)系，我們便可以基本實現(xiàn)遞歸下降語法分析程序的功能。主要函數(shù)聲明：主要函數(shù)功能描述：TreeNode*parseMain(void)1.調(diào)用總程序處理分析函數(shù)：創(chuàng)建語法分析樹，同時處理文件的提前結(jié)束錯誤。TreeNode*program(void);2總程序處理分析程序：生成語法分析樹的根節(jié)點root，分別調(diào)用程序頭部分、聲明部分、程序體部分分析函數(shù)并成為語法樹的3個節(jié)點

TreeNode*programHead(void)3程序頭部分分析處理函數(shù)：根據(jù)讀入的單詞，匹配保留字PROTGRAM,記錄程序名于程序頭結(jié)點，匹配IDTreeNode*declarePart(void)4程序聲明部分分析函數(shù)：根據(jù)文法產(chǎn)生式創(chuàng)建新的類型聲明標志節(jié)點、變量聲明標志節(jié)點。調(diào)用類型聲明部分處理函數(shù)TypeDec()、變量聲明部分處理函數(shù)VarDec()、過程聲明部分處理函數(shù)ProcDec()TreeNode*typeDec(void)5類型聲明部分處理函數(shù)：根據(jù)讀入的下個單詞，若當前單詞為TYPE，調(diào)用函數(shù)typeDeclaration()并賦值給t，則函數(shù)返回t，否則返回NULLTreeNode*typeDeclaration(void)6類型聲明中的其他函數(shù)：根據(jù)文法產(chǎn)生式，匹配保留字TYPE，調(diào)用函數(shù)TypeDecList()并賦值給t，若t為NULL則顯示提示信息。函數(shù)返回tTreeNode*typeDecList(void)7函數(shù)聲明中的其它函數(shù)：根據(jù)文法產(chǎn)生式，創(chuàng)建新的聲明類型節(jié)點"若申請成功，調(diào)用函數(shù)TypeId()，匹配保留字EQ,調(diào)用函數(shù)TypeDef()，匹配保留字SEMI，調(diào)用函數(shù)TypeDecMore()，返回值賦值給t的成員sibling，函數(shù)返回tTreeNode*typeDecMore(void)8類型聲明中的其它函數(shù)：該函數(shù)根據(jù)讀入的單詞，或者調(diào)用函數(shù)TypeDecList()并賦值給t，則函數(shù)返回t;或者什么都不做，或者跳過此錯誤單詞，讀入下一個單詞，返回NULLvoidtypeId(TreeNode*t)9類型聲明中類型標識符處理分析程序：該函數(shù)根據(jù)讀入的單詞，判斷TOKEN.Lex=ID的值，如果為真則將TOKEN.Sem字符串拷貝到參數(shù)t的成員[tnum]中，其中tnum是用來記錄namne個數(shù)的臨時變量。然后再將tnum加1送回參數(shù)t的成員attr.idnumvoidtypeDef(TreeNode*t)10具體類型處理分析函數(shù)：該函數(shù)根據(jù)讀入的單詞，或者調(diào)用BaseType()，或者調(diào)用structureType()，或者復(fù)制標識符名稱、匹配標識符，或者跳過錯誤單詞，讀入下一個單詞voidbaseType(TreeNode*t)11基本類型分析處理函數(shù)：該函數(shù)根據(jù)讀入的單詞判斷執(zhí)行哪個分支voidstructureType(TreeNode*t)12結(jié)構(gòu)類型處理分析函數(shù)：該函數(shù)根據(jù)讀入的單詞判斷選擇調(diào)用函數(shù)ArrayType(),或者調(diào)用函數(shù)RecType()voidarrayType(TreeNode*t)13數(shù)組類型的分析處理函數(shù)：該函數(shù)對讀入的單詞進行匹配，并記錄數(shù)組的上界和下界，再匹配保留字，最后調(diào)用基本類型函數(shù)°yBaseType(),記錄數(shù)組的子類型voidrecType(TreeNode*t)14記錄類型的處理分析函數(shù)：該函數(shù)對讀入的單詞進行匹配，調(diào)用記錄中的域函數(shù)FieldRec(),最后再對讀入的單詞進行匹配TreeNode*fieldDecList(void)15記錄類型中的域聲明處理分析函數(shù)：該函數(shù)根據(jù)讀入的單詞判斷記錄域中的變量屬于哪種類型，根據(jù)產(chǎn)生式的select集合判斷執(zhí)行哪個分支程序。其中相同類型的變量id用“，”分隔開，其名稱記錄在語法書的同一個節(jié)點中，不同類型的變量節(jié)點互為兄弟節(jié)點TreeNode*fieldDecMore(void)16記錄類型中的其他域聲明處理分析函數(shù)：該函數(shù)根據(jù)文法產(chǎn)生式判斷讀入的單詞，若為END，則不做任何處理；若為INTEGER,CHAR或者ARRAY，則調(diào)用FieldDecList()遞歸處理函數(shù)；

否則讀入下一個TOKEN序列，函數(shù)返回tvoididList(TreeNode*t)17記錄類型域中標識符名處理分析程序：該函數(shù)根據(jù)文法產(chǎn)生式，匹配標識符ID，記錄標識符名稱，調(diào)用遞歸處理函數(shù)IdMore()voididMore(TreeNode*t)18記錄類型域中其他標識符名處理分析程序：該函數(shù)根據(jù)文法產(chǎn)生式判斷讀入的單詞，處理調(diào)用相應(yīng)的函數(shù)TreeNode*varDec(void)19變量聲明處理分析程序：該函數(shù)根據(jù)文法產(chǎn)生式判斷讀入的單詞，處理調(diào)用相應(yīng)的函數(shù)。如果處理成功則返回t，否則返回NULL。TreeNode*varDeclaration(void)20變量聲明部分處理程序：該函數(shù)根據(jù)文法產(chǎn)生式，匹配保留字VAR，調(diào)用函數(shù)VarDecList()函數(shù)。處理成功返回t，否則返回NULLTreeNode*varDecList(void)21變量聲明部分處理程序：該函數(shù)根據(jù)文法產(chǎn)生式調(diào)用相應(yīng)的變量聲明部分的處理函數(shù)TypeDef(),VarIdList(),VarDecMore(。處理成功返回t，否則返回NULLTreeNode*varDecMore(void)22變量聲明部分處理程序：該函數(shù)根據(jù)文法產(chǎn)生式。由讀入的單詞判斷執(zhí)行哪個分支，最后返回tvoidvarIdList(TreeNode*t)23變量聲明部分變量名部分處理程序：該函數(shù)根據(jù)文法產(chǎn)生式，匹配標識符名ID，記錄標識符名稱，調(diào)用函數(shù)VarIdMore()。voidvarIdMore(TreeNode*t)24變量聲明部分變量名部分處理程序：該函數(shù)根據(jù)文法產(chǎn)生式，由讀入的單詞判斷執(zhí)行哪個分支(判斷是否還有其他變量)TreeNode*procDec(void)25過程聲明部分總的處理分析程序：該函數(shù)根據(jù)文法產(chǎn)生式判斷當前單詞，若為BEGIN則不做任何動作，若為PROCEDURE，則調(diào)用過程聲明函數(shù)ProcDeclaration(t)，否則讀入下一個單詞。函數(shù)返回tTreeNode*procDeclaration(void)26該函數(shù)根據(jù)文法產(chǎn)生式匹配保留字PROCEDURE，調(diào)用過程名函數(shù)ProcName(),參數(shù)函數(shù)ParamList()，過程體內(nèi)部聲明部分函數(shù)ProcDecPart()，過程體函數(shù)ProcBody()。成功則返回t，否則返回NULL。voidparamList(TreeNode*t)27過程聲明中的參數(shù)聲明部分的處理分析程序：該函數(shù)根據(jù)文法產(chǎn)生式判斷讀入的單詞，若為RPAREN，則不做任何動作；若為INTEGER,CHAR,ARRAY,RECORD,ID,VAR則調(diào)用參數(shù)聲明序列處理函數(shù)ParamDecList(t),否則讀下一個TOKEN序列TreeNode*paramDecList(void)28過程聲明中的參數(shù)聲明序列的處理分析程序：該函數(shù)根據(jù)文法產(chǎn)生式調(diào)用函數(shù)Param(),返回指針t；調(diào)用函數(shù)paramMore(),返回指針p。若p不為NULL，則將p賦值給t的成員變量siblingo若處理成功則返回指針t，否則返回NULLTreeNode*paramMore(void)29過程聲明中的參數(shù)聲明其他部分的處理分析程序：該函數(shù)根據(jù)文法產(chǎn)生式，由讀入的單詞判斷執(zhí)行哪個分支(判斷是否還有其他參數(shù)聲明)。TreeNode*Param(void)30過程聲明中的參數(shù)聲明中參數(shù)部分的處理分析程序：該函數(shù)根據(jù)文法產(chǎn)生式，由讀入的單詞判斷執(zhí)行哪個分支程序，即判斷是值參還是變參。處理成功返回t，否則返回NULLvoidformList(TreeNode*t)31過程聲明中的參數(shù)聲明中參數(shù)名部分的處理分析程序：該函數(shù)根據(jù)文法產(chǎn)生式，記錄參數(shù)聲明中的參數(shù)名稱，匹配保留字

ID,調(diào)用FidMore()函數(shù)。voidfidMore(TreeNode*t)32過程聲明中的參數(shù)聲明中參數(shù)名部分的處理分析程序：該函數(shù)根據(jù)文法產(chǎn)生式，有讀入的單詞判斷執(zhí)行哪個分支程序。TreeNode*procDecPart(void)33過程中聲明部分的分析處理程序：該函數(shù)根據(jù)文法產(chǎn)生式，調(diào)用聲明部分函數(shù)DeclarationPart(),如果處理成功則返回t，否則返回NULL。TreeNode*procBody(void)34過程體部分處理分析程序：該函數(shù)根據(jù)文法產(chǎn)生式，調(diào)用程序體部分函數(shù)ProgramBody().成功則返回t，否則返回NULL。TreeNode*programBody(void)35主程序體部分處理分析程序：根據(jù)文法產(chǎn)生式創(chuàng)建新的語句標志類型語法樹節(jié)點，并匹配保留字，調(diào)用語句序列函數(shù)StmList()TreeNode*stmList(void)36語句序列部分處理分析程序：根據(jù)文法產(chǎn)生式，調(diào)用語句處理函數(shù)Stm()，返回指針t；調(diào)用更多語句處理函數(shù)StmMore(),返回指針p，并使p成為t的兄弟節(jié)點。TreeNode*stmMore(void)37更多語句部分處理分析程序：根據(jù)文法產(chǎn)生式，由讀入的單詞判斷執(zhí)行哪個分支，即是否有更多的語句。TreeNode*stm(void)38語句遞歸處理分析程序：根據(jù)讀入的單詞和每條產(chǎn)生式的Predict集選擇調(diào)用相應(yīng)的語句處理函數(shù)。(書中有更詳細的說明)TreeNode*assCall(void)39賦值語句和過程調(diào)用語句部分的處理分析程序：根據(jù)讀入的單詞選擇相應(yīng)的處理程序(賦值語句處理程序和過程調(diào)用語句處理程序)TreeNode*assingmentRest(void)40賦值語句處理分析函數(shù)：根據(jù)文法產(chǎn)生式，創(chuàng)建新的賦值語句類型語法樹節(jié)點。匹配保留字EQ，調(diào)用表達式函數(shù)Exp()。TreeNode*conditionalStm(void)41條件語句處理分析程序：該函數(shù)根據(jù)文法產(chǎn)生式匹配保留字IF，調(diào)用表達式函數(shù)Exp()；匹配保留字THEN，調(diào)用語句序列函數(shù)StmL()(此處的語句序列函數(shù)不同于前處的StmList()函數(shù)。具體更詳盡的說明見書P104)TreeNode*loopStm(void)42循環(huán)語句處理分析程序：根據(jù)文法產(chǎn)生式，匹配保留字WHILE，調(diào)用表達式處理函數(shù)Exp(),再匹配保留字DO,調(diào)用語句序列處理函數(shù)，最后匹配保留字ENDWH。TreeNode*inputStm(void)43輸入語句的處理分析函數(shù)：根據(jù)文法產(chǎn)生式，創(chuàng)建新的輸入語句類型語法樹節(jié)點t，匹配保留字READ,LPAREN,記錄標識符名稱，匹配ID,RPAREN。TreeNode*outputStm(void)44輸出語句處理分析程序：根據(jù)文法產(chǎn)生式，創(chuàng)建新的輸出語句類型語法樹節(jié)點t，匹配保留字WRITE，LPAREN，調(diào)用函數(shù)Exp()，匹配保留字RPARENoTreeNode*returnStm(void)45過程返回語句處理分析程序：根據(jù)文法產(chǎn)生式，創(chuàng)建新的過程返回類型的語法樹節(jié)點t，匹配保留字RETURNo

TreeNode*callStmRest(void)46過程調(diào)用語句處理分析程序：根據(jù)文法產(chǎn)生式，創(chuàng)建新的過程調(diào)用類型語法樹節(jié)點t，匹配保留字LPAREN,調(diào)用實參處理分析函數(shù)ActParamList(),匹配RPAREN。TreeNode*actParamList(void)47實參部分處理分析程序：根據(jù)讀入的單詞選擇執(zhí)行哪段程序(有參數(shù)或者無參數(shù))TreeNode*actParamMore(void)48更多實參部分處理分析程序：根據(jù)讀入的單詞決定執(zhí)行哪段分支程序。TreeNode*exp(void)49表達式遞歸處理分析程序：根據(jù)文法產(chǎn)生式，調(diào)用相應(yīng)的遞歸處理函數(shù)。TreeNode*simple_exp(void)50根據(jù)文法產(chǎn)生式，調(diào)用相應(yīng)的遞歸處理函數(shù)。TreeNode*term(void)51項遞歸處理分析程序：根據(jù)文法產(chǎn)生式，調(diào)用相應(yīng)的遞歸處理函數(shù)。TreeNode*factor(void)52因子遞歸處理分析程序：根據(jù)文法產(chǎn)生式，調(diào)用相應(yīng)的遞歸處理函數(shù)。TreeNode*variable(void)53變量處理程序：根據(jù)產(chǎn)生式，生成一個新的表達式節(jié)點t，如果創(chuàng)建成功且當前單詞為ID，則記錄并匹配ID，調(diào)用變量其余部分處理函數(shù)variMore(t),返回t。voidvariMore(TreeNode*t)54變量其余部分處理程序：根據(jù)文法產(chǎn)生式，調(diào)用相應(yīng)的遞歸處理函數(shù)。如果當前單詞為ASSIGN等，則不作任何處理；如果當前單詞為LMIDPAREN，則調(diào)用Exp()處理表達式；如果當前單詞為DOT，則匹配DOT處理域變量函數(shù)fieldvar();否則讀下一個TOKENTreeNode*fieldvar(void)55域變量部分處理過程：根據(jù)文法產(chǎn)生式，生成一個新的表達式節(jié)點t，如果創(chuàng)建成功且當前單詞為ID，則記錄并匹配ID，調(diào)用域變量其余部分處理函數(shù)fieldvarMore(t)，返回tvoidfieldvarMore(TreeNode*t)56域變量其他部分處理過程：根據(jù)文法產(chǎn)生式，調(diào)用相應(yīng)的遞歸處理函數(shù)。如果當前單詞為ASSIGN，則不作任何處理；如果當前單詞為LMIDPAREN，則調(diào)用Exp()處理表達；否則讀入下一個TOKENvoidmatch(LexTypeexpected)57終極符匹配處理程序：該函數(shù)將當前單詞與函數(shù)參數(shù)給定的單詞相比較，如果一致則取下一個單詞，都則退出語法分析程序。圖3.主要函數(shù)的調(diào)用關(guān)系（六）、遞歸下降語法分析實驗總結(jié)與體會通過將近8周的學(xué)習(xí)和編程，我實現(xiàn)了遞歸下降語法分析程序的基本功能并且通過調(diào)試可以使得程序能正確運行并產(chǎn)生預(yù)期的結(jié)果。雖然我參考了書中很多內(nèi)容才將本模塊程序?qū)崿F(xiàn)，但是這個過程使我受益匪淺：我學(xué)會了上網(wǎng)搜集相關(guān)內(nèi)容和源程序；也鍛煉了我的學(xué)習(xí)和調(diào)試程序的能力；同時對于一些不完善的細節(jié)我通過自己的努力進行重新編程和糾錯，最終完成了程序的相關(guān)功能；更重要的是我學(xué)會了與小組成員更好更高效地交流和合作，從而使得我們能順利地完成了這次編程任務(wù)。大學(xué)三年以來，我們還是第一次接觸這么大型的程序開發(fā)，感覺很新鮮，很有成就感，這個過程也使得我們對高級語言編程更加熟練。不過由于時間和個人能力有限，我的源程序很大一部分都參考了實驗書中的內(nèi)容，所以實驗效果不是很理想。不過通過這次實驗確實讓我學(xué)到很多，我也會借此繼續(xù)完善和強化自己，爭取能不斷地提高自己編程和實踐能力，為以后的研究生學(xué)習(xí)和工作打下基礎(chǔ)。第五部分符號表管理與語義分析一、概述語義分析(SemanticAnalysis)是任何編譯程序必不可少的一個階段，也是編譯程序中最實質(zhì)性的工作。在整個編譯過程中，詞法分析和語法分析是對源程序形式上的識別和處理，而語義分析程序是對源程序的語義做相應(yīng)的處理工作。語義分析的主要任務(wù)是針對語法分析后得到的內(nèi)部結(jié)構(gòu)進行語義處理，既要做相應(yīng)的語義分析檢查工作，還要為后面的編譯工作提供足夠的信息，這些信息包括標識符的語義信息、類型信息、過程信息等。二、語義分析的主要任務(wù)構(gòu)造符號表和信息表進行語義錯誤檢查，主要包括標識符重復(fù)定義、標識符未聲明、標符類型不符、引用不合法等如果語義分析無錯誤，輸出符號表內(nèi)容，否則將錯誤信息輸出到指定文件中符號表格式標識符名：類型信息層號偏移直/間接變量示例a:intTyvarkindLevel=0Offset=7dir錯誤信息格式(行號)：標識符名錯誤信息示例(5)：a未聲明的類型標識符三、具體實現(xiàn)1.符號表設(shè)計與實現(xiàn)本程序的符號表的構(gòu)建是使用駐留法進行實現(xiàn)的，從而在程序運行結(jié)束時，所有標識符的信息均能繼續(xù)保存在符號表中，方便進行后續(xù)操作，且使用駐留法實現(xiàn)的符號表更易理解和操作。SymbTable*scope[128];//符號標定義，大小為128intsymbtop;//存儲符號表末尾下標，初始為-1typedefstructsymbtable{charidname[10];〃存儲標識符名稱，為“#”是表示一層的結(jié)束AttributeIRattrIR;//存儲標識符詳細信息intnext;//當標識符名為“#”時有效，存儲該層入口結(jié)點在scope中的位置}SymbTable;//符號表結(jié)點定義private:intstack[10];//存儲每一層入口結(jié)點在scope中的位置voidPush(ints);//每進入新的一層時，將入口結(jié)點下標入棧intPop();//沒離開一層時，將入口結(jié)點下標出棧intGetTop();//獲取當前層的起始位置示例：SNL源代碼為：programptypet1=integer;vart1v1;procedureq(varintegeri);procedurer(integerj)beginwrite(j);endbeginr(i);i:=i+10;endbeginread(v1);q(v1)end.則生成的符號表為：位置IdnameattrIRnext0t1詳細信息-11V1詳細信息-14—2q詳細信息-13i詳細信息-14r詳細信息-15j詳細信息-16#NULL2—7#NULL4—2,語義分析部分設(shè)計與實現(xiàn)(2)主要函數(shù)聲明及其功能voidStart(TreeNode*t);〃語法分析部分入口函數(shù)，輸入為語法分析部分生成的語法樹的根節(jié)點，函數(shù)體內(nèi)包含語法分析的主題框架boolEnter(char*id,AttributeIR*Att,SymbTable**Entry);〃參數(shù)為標識符名，指向詳細信息的指針，以及指向符號表的指針的指針，函數(shù)功能是查尋標識符定義是否正確，如果正確將Att中的信息填寫入符號表，否則返回falseboolFindAll(char*id,SymbTable**Entry);〃在整個符號表中查找標識符名為id的項boolFind(char*id,SymbTable**Entry);〃在當前層符號表中查找標識符名為id的項boolFindField(char*id,FieldChain*head,FieldChain**Entry);//在record類型的域中查找標識符為id的域voidPrintSymbTable();〃當源程序沒有語義錯誤時，將符號表中各項按照格式輸出到命令行中TypeIR*TypeProcess(TreeNode*t,DecKinddeckind);〃將結(jié)點中的項按照其類型信息進行處理，如果沒有錯誤，生成其類型的內(nèi)部表示voidTypeDecPart(TreeNode*t);//類型聲明部分的處理函數(shù)voidVarDecPart(TreeNode*t);〃變量聲明部分的處理函數(shù)voidprocDecPart(TreeNode*t);〃過程聲明部分的處理函數(shù)voidBody(TreeNode*t);〃語句部分的處理函數(shù)voidstatement(TreeNode*t);〃根據(jù)語句結(jié)點項中的類型信息轉(zhuǎn)向不同的語句處理函數(shù)TypeIR*Expr(TreeNode*t,AccessKind*Ekind);〃對表達式進行處理，并生成其內(nèi)部表示voidErrorList(intline,char*name,char*message);〃將錯誤信息輸出到err.txt中boolCompat(TypeIR*tp1,TypeIR*tp2);〃判斷tp1與tp2的類型是否相容

第六部分程序運行與測試一、被測源程序無錯誤情況下的運行結(jié)果Thesourcefileis:Linel：《簡單的過程調(diào)用，測試變參的傳遞》Line2:progranppLine3:uarintegerul:Line4：charc:LineS：Line6：procedupef(>；Line?：beginLineS:ul：=2Line?:end.LinelQ：Linell：ppocedupet1()；Linel2:uar-inteffef-ul；Linel3:beg-inLinel4：ul:=1LinelE：end.LinelG:Linel?：beg-inLinelS:r-ead<ul>；■Linel9:1Line20：wr-lte(uiJ；Line21:f<>；*Line22:write<ui>|Line23:end.［蜘暮泠圖6.1測試源程序

Le>cica.1=To]ccnlist：:hPROGRAMpi^agt^aniIDPPbUARuai'bTMTEfiFHintegfer2ID3SEHIi4GHARchat'4IDc4SEMI1APHOCFDIIHFDmcedm^eGIDFGLP^REN<6RPAREN>6!>EH117BEGINbeginRTDulSASSIGN-=QIMTG29ENDend11FKOGEDUKEpi'ocedui'e11IDtl11T-PftnFMC11RPAREN>11SEHII12叩Ruai'121NTEGEHinteger12IDul12KFMT—13BEGINbejjin14IDvl14ASSIGN■=141NTG115ENDend17RFCTMbeefinISREAD1'ead18LPflREN<18IDulINHFRHEN>18SEMI119IDtl19LPftREH<19RPftREH19SEMII20WRITEwrite29LPAREN<20IDul29RPAREN20SEMI)21IDf21LPAREH<21RPAREN21SEMI■22WRITEwrite22LPAREN<22IDul22RPAREH23ENDend23DOT-24ENDFILE圖6.2詞法分析結(jié)果

Is^ntaxanalysis：:IS^nta_xTi'ee:Line24：PpqKLine2:Ph&adKppLineS:UarKLine3:DecKIntegerKvlLine4：DecKCharKcLine6：ProcDecKfLine?；StnlKLine8:StmtKAssignKLine8:ExpKUarlKIdUul,Line8:ExpKConstK2Linell：PpocDbcKtlLinel2：UarKLinel2：DecHIntegerKulLinel3：GtnlKLinel4：StmtKAssignKLinel4：ExpKUariKIdUulLinel4：ExpHConstK1Linel7：StnlKLinelS：StntHReadHulLinel9：StntKC^llKLine!?：ExpKUariKIdUtlLineSStntKUriteKLine20：ExpKUariKIdUvlLineSl：StntKCallKLine21：ExpKUariKIdUfLine22:StntKWriteKLine22:ExpKUariKIdUul圖6.3語法分析結(jié)果Hosenka.nticet'i'Di's?SybmTableasFqIIovjs:vi:intTyvarKindLevel=0Offset=7dirc:cha.rTyvarKindLevel=0Offset=8dirf:procKindLevel=0tl:ppocKindLevel-1ul：intTyuapKindLevel=2Offset=7dirtl:ppocKindLevel=0ul:intTyuapKindLevel=1Offset=7dir圖6.4語義分析符號表ThesDiti'ceFileis:Linel:匕簡單的過程調(diào)用，洌試變參的傳遞｝Line2:program_ppLineS:uarintegerul；Lin&4：charc；Lin或:Line&:proceduref<>；Line?：begfinLine8:ul：=2Line?:endLinelO：Linell：proceduretl<>；Linel