編譯原理試驗(yàn)全集

目錄目錄TOC\o"1-5"\h\z\o"CurrentDocument"實(shí)驗(yàn)1詞法分析 2\o"CurrentDocument"目的 2\o"CurrentDocument"內(nèi)容 2\o"CurrentDocument"知識 2\o"CurrentDocument"步驟 2問題及解答 4實(shí)驗(yàn)報(bào)告要求 4\o"CurrentDocument"實(shí)驗(yàn)2 自頂向下的語法分析 5\o"CurrentDocument"目的 5\o"CurrentDocument"知識 5\o"CurrentDocument"內(nèi)容 6\o"CurrentDocument"步驟 10問題及解答 10\o"CurrentDocument"提高 10\o"CurrentDocument"實(shí)驗(yàn)報(bào)告要求 10\o"CurrentDocument"實(shí)驗(yàn)3 自底向上的語法分析 12\o"CurrentDocument"目的 12\o"CurrentDocument"內(nèi)容 12\o"CurrentDocument"步驟 14\o"CurrentDocument"問題 14\o"CurrentDocument"實(shí)驗(yàn)報(bào)告要求 14\o"CurrentDocument"實(shí)驗(yàn)4語義分析 15\o"CurrentDocument"目的 15\o"CurrentDocument"知識 15\o"CurrentDocument"內(nèi)容 17\o"CurrentDocument"步驟 18實(shí)驗(yàn)報(bào)告要求 18實(shí)驗(yàn)5中間代碼生成實(shí)驗(yàn)6 代碼優(yōu)化與代碼生成1/19編譯原理實(shí)驗(yàn)指導(dǎo)相關(guān)說明實(shí)驗(yàn)1、2要求獨(dú)立完成。實(shí)驗(yàn)3、實(shí)驗(yàn)4的實(shí)現(xiàn)代碼（VC++工程）均已調(diào)試成功，打包在目錄中（lab3,lab4）。希望認(rèn)真學(xué)習(xí)的同學(xué)多看看。由于時(shí)間關(guān)系，許多地方還沒來得及做好，本手冊的內(nèi)容可能比較繁瑣。歡迎大家提出問題和意見。時(shí)間比較緊的同學(xué)也請關(guān)注每個(gè)實(shí)驗(yàn)?zāi)┪驳膶?shí)驗(yàn)報(bào)告要求。期末實(shí)驗(yàn)占 10分。實(shí)驗(yàn)1詞法分析目的構(gòu)造詞法分析器，熟悉編譯程序詞法分析過程。掌握 LEX自動(dòng)生成工具的使用。內(nèi)容從本實(shí)驗(yàn)開始，用C語言實(shí)現(xiàn)一個(gè)編譯系統(tǒng)。詞法分析是其第一步。采用 Lex工具自動(dòng)生成大大簡化了其中的內(nèi)容。因此本實(shí)驗(yàn)的重心并不在如何操作， 而是在于怎樣編寫Lex源程序。而要編寫Lex源程序，首先要定義源語言，即該編譯系統(tǒng)所實(shí)現(xiàn)的語言。這里作為例子，我們以C++為基礎(chǔ)，采用其部分單詞，因此不妨將我們定義的這種語言稱之為MiniC++。知識Lex是一個(gè)詞法分析器的自動(dòng)構(gòu)造工具。相關(guān)資料較多。步驟1、在編寫LEX源程序前，首先要定義一種高級語言。找出其中所有單詞。并進(jìn)行編碼。高級語言可以是已經(jīng)存在的一種語言，如， C,Pascal,Basic。也可以是自己構(gòu)造的一種語言。當(dāng)然，考慮到后續(xù)實(shí)現(xiàn)的難度，可以簡化許多內(nèi)容。如不考慮數(shù)組，不考慮For循環(huán)等。將定義好的單詞編碼用一個(gè)表表達(dá)出來。如我們這里的 MiniC++的單詞定義如下：保留字內(nèi)部編碼運(yùn)算符號內(nèi)部編碼其他符號內(nèi)部編碼if1+8(19else2-9)20while3*10;21cout4/11{22cin5**12)23>>（輸入）6==13=24<<（輸出）7<14數(shù)字25>15標(biāo)識符26<=16,272/19>=17var28<>18說明:（1）由于只允許數(shù)字，所以不作變量類型。所有類型都是var。（2）單詞編碼無任何約束，只要方便可行。要知道，我們構(gòu)造的是一個(gè)獨(dú)立的自包含的系統(tǒng)。所有的東西都是我們自己定義的。而編碼只是便于機(jī)器內(nèi)部識別。只要后面的語法分析，語義分析都按這個(gè)編碼即可。2、將flex.rar展開在一個(gè)目錄中，如E:\flex。3、根據(jù)上述單詞編碼編寫LEX源程序。LEX源程序是純文本文件，任何文本編輯器均具備這一功能（如用記事本打開即可）。保存時(shí)文件名任取。這里假設(shè)命名為LexDemo.txt。為后續(xù)操作簡便，將該文件保存在 E:\flex子目錄中。4、編譯LEX源程序。生成lexyy.c。5、使用C語言環(huán)境打開lexyy.c。編譯運(yùn)行，最終生成lexyy.exe。根據(jù)我們現(xiàn)有的情況，可以使用三種方案，任選其一。 （建議使用命令行工具，實(shí)際上更簡單。 ）（1）使用VC建立一個(gè)工程（Project），將lexyy.c加入到該工程。實(shí)際上，最好拷貝lexyy.c到相應(yīng)的目錄。然后編譯，產(chǎn)生的lexyy.exe文件在該工程目錄下的Debug子目錄中。（2）使用VC的命令行工具。格式為：<VC的安裝路徑>\bin\CLlexyy.c如：VC安裝在D:\”ProgramFiles”下。則命令為：D:\"ProgramFiles"\"MicrosoftVisualStudio"\VC98\Bin\CLlexyy.c（3）使用TC命令行工具。<TC的安裝路徑>\bin\TCClexyy.cD:\TC20\bin\TCClexyy.c6、寫一段該語言測試代碼進(jìn)行測試。如：While（i<2）{Cout<<10;}則輸出序列為：3,019,015,07、根據(jù)單詞編碼序列對照上面的表進(jìn)行驗(yàn)證。（1）每個(gè)單詞對應(yīng)一對數(shù)，第一個(gè)數(shù)為其編碼。第二個(gè)數(shù)為該單詞的附加屬性。如無該屬性則置0。3/19編譯原理實(shí)驗(yàn)指導(dǎo)（2）如單詞為標(biāo)識符，其屬性應(yīng)該為符號表的入口地址。但考慮到學(xué)詞法分析時(shí)，還不熟悉符號表的機(jī)制，因而暫時(shí)也置0問題及解答1、涉及到命令行操作，考慮到仍有許多同學(xué)對 DOS命令不熟悉。希望自行加強(qiáng)。2、如采用VisualC++編譯，則先要建一個(gè)工程，將lexyy.c加入。3、如果采用TC編譯，則建議用TCC命令行工具。4、由于LEX只能處理單字節(jié)的字符，請?jiān)贚EX源程序中千萬不要用中文注釋。保存時(shí)一定要看清楚類型，必須是ANSI類型。實(shí)驗(yàn)報(bào)告要求1、目的2、內(nèi)容（1）單詞及編碼定義（設(shè)計(jì)一種高級語言（或子集）的單詞其編碼，見前面的表）（2）部分LEX代碼（3）測試（寫出兩個(gè)測試句子：所有單詞正確，含有錯(cuò)誤單詞的句子）3、總結(jié)（心得）4/19編譯原理實(shí)驗(yàn)指導(dǎo)實(shí)驗(yàn)2實(shí)驗(yàn)2自頂向下的語法分析目的在詞法分析的基礎(chǔ)上，熟悉自頂向下的語法分析方法。體驗(yàn)遞歸程序的特點(diǎn)。實(shí)現(xiàn)界面和業(yè)務(wù)邏輯代碼分離。實(shí)現(xiàn)異種平臺的訪問。培養(yǎng)初步的軟件架構(gòu)的觀念。培養(yǎng)軟件設(shè)計(jì)及編程能力。知識終結(jié)符、非終結(jié)符及產(chǎn)生式所有的組成最終句子的單詞即為終結(jié)符。非終結(jié)符代表的是我們觀念上的語法范疇。如主語。謂語，名詞等。在高級語言中，語法范疇包括程序、說明語句、可執(zhí)行語句、IF結(jié)構(gòu)、關(guān)系表達(dá)式、算術(shù)表達(dá)式等等。語法及語義分析語法分析只要求驗(yàn)證某個(gè)句子是否符合某個(gè)文法。關(guān)注的是結(jié)構(gòu)。而語義關(guān)注的是句子的含義。計(jì)算機(jī)本身無生命，無所謂真正地理解句子的含義。我們所期望的計(jì)算機(jī)執(zhí)行相應(yīng)的語義是指：當(dāng)計(jì)算機(jī)程序掃描到某個(gè)句子后，所執(zhí)行的操作恰好符合這個(gè)句子所表達(dá)的意思。如掃描到一個(gè)“ 3+2”這樣一個(gè)字符串。自動(dòng)地把結(jié)果 5算出來。而在語法分析中，所作的僅僅是判別這個(gè)句子的結(jié)構(gòu)是否合法。并不執(zhí)行計(jì)算。FIRST集與FOLLOW集所謂FIRST集，本質(zhì)上就是第一個(gè)可能出現(xiàn)的符號構(gòu)成的集合。這個(gè)是可以由產(chǎn)生式本身得到的。因?yàn)槿魏尉渥佣际怯稍撐姆ǖ漠a(chǎn)生式推出來的。關(guān)于遞歸下降子程序的編寫規(guī)則（請注意規(guī)則和下面的顏色對應(yīng)關(guān)系）：（1）文法中的每個(gè)非終結(jié)符對應(yīng)一個(gè)過程（函數(shù)）（2）若某個(gè)非終結(jié)符有多個(gè)產(chǎn)生式候選，則根據(jù)當(dāng)前輸入符是否在某個(gè)候選的Select集選擇。每個(gè)候選對應(yīng)一個(gè)if分支。（3）選擇好候選之后，對產(chǎn)生式候選的右部的符號由左到右依次處理。①若為終結(jié)符。則將該符號和當(dāng)前輸入符號進(jìn)行判等操作 。若相等，繼續(xù)。否則轉(zhuǎn)③②若為非終結(jié)符，則調(diào)用該非終結(jié)符所對應(yīng)的過程 。③若當(dāng)前掃描的符號為當(dāng)前候選的第一個(gè)符號，且當(dāng)前產(chǎn)生式有￡候選.則不作出錯(cuò)處理。否則均出錯(cuò)處理。例1：S今（S）|acharstr口；…〃待檢查的串intip; //掃描指針例2:S3（S）Ibcharstr口；…〃待檢查的串intip; //掃描指針5/19

編譯原理實(shí)驗(yàn)指導(dǎo)voidS(){//只有一個(gè)非終結(jié)符Sif(str[ip]==’('){//處理S個(gè)(S)候選ip++;S();if(str[ip]==’)’)ip++;elseerror();)elseif(str[ip]==’a’){//處理S->a候選ip++;}else //對應(yīng)第1符號error(); //但無b候選項(xiàng)，必須出錯(cuò)。voidS(){ //只有一個(gè)非終結(jié)符Sif(str[ip]=='('){ip++;S();if(str[ip]==')')ip++;elseerror();//不是第1個(gè)符號，出錯(cuò)。}elseif(str[ip]=='a'){ip++;} 〃不作出錯(cuò)處理。需要注意的是，本例比較的是字符。而本實(shí)驗(yàn)中用的是符號（單詞）編碼，是經(jīng)過詞法分析后的編碼。也就是后面定義的 token數(shù)組相當(dāng)于本例的str。這點(diǎn)變通能力希望大家有。關(guān)于這三條規(guī)則的具體運(yùn)用，可看模板代碼。實(shí)現(xiàn)了兩個(gè)非終結(jié)符，其余的需要同學(xué)們自己去實(shí)現(xiàn)。內(nèi)容本實(shí)驗(yàn)的目標(biāo)是實(shí)現(xiàn)一個(gè)文本計(jì)算器的語法檢驗(yàn)。要實(shí)現(xiàn)實(shí)數(shù)的加、減、乘、除、

乘方幾種運(yùn)算。這幾種運(yùn)算構(gòu)成了三種優(yōu)先級。因此文法的表達(dá)和課堂上不一樣。根據(jù)需要設(shè)計(jì)所有的非終結(jié)符。可以以產(chǎn)生式為核心。在設(shè)計(jì)的過程中逐步引入非終結(jié)符。<E>一<L><A><A>一+<L><A><A>--<L><A><A>一￡<L>-><M><B><B>->*<M><B><B>->/<M><B><B>一￡6/19編譯原理實(shí)驗(yàn)指導(dǎo)<M>f<N><C><C>f**<N><C><N>f"（”<E>“）” 〃此括號非彼括號，故用引號括起來。<N>f$num 〃經(jīng)過詞法分析，數(shù)字被認(rèn)為是終結(jié)符。<N>f￡非終結(jié)符定義符號定義符號定義<E>算術(shù)表達(dá)式<A>消除左遞歸的算術(shù)子表達(dá)式<L>優(yōu)先級為3的子項(xiàng)<B>消除左遞歸且優(yōu)先級為3的子項(xiàng)<M>優(yōu)先級為2的子項(xiàng)<C>消除左遞歸且優(yōu)先級為2的子項(xiàng)<N>優(yōu)先級為1的子項(xiàng)說明：優(yōu)先級的編號越小，其運(yùn)算（歸約）的次序先?；贚EX自動(dòng)構(gòu)造器地詞法分析程序的重構(gòu)（任選）對于大型編譯系統(tǒng)而言，往往存在多遍掃描的可能性。將詞法分析程序構(gòu)造成獨(dú)立的過程有很大的好處。但對于我們這個(gè)小型的文本計(jì)算器而言。將詞法分析構(gòu)造成依附于語法分析的子過程可能更加合理。因此我們需要對詞法分析程序進(jìn)行重構(gòu)。本實(shí)驗(yàn)只要求實(shí)現(xiàn)表達(dá)式的求值。因此，只需要使用原來集合的部分單詞。對詞法分析程序進(jìn)行重構(gòu)，使之成為語法分析程序的子程序 。通過全局變量的方式加工數(shù)據(jù)，輸入表達(dá)式串，輸出編碼及屬性序列，分別存放在兩個(gè)全局的整型數(shù)組中。因此需要作如下變更：（1）單詞的編碼在語法分析和詞法分析中都需要，因而同一集中在一個(gè)頭文件token.h中。以后，無論是詞法、語法、語義分析，均用這套編碼。以下是部分語句：#ifndefTOKEN/*終結(jié)符定義*/#define$add20/*+*/#define$sub21/**/(((#define$assign37/*^*/#define$num38/*常數(shù)*/#define$eps40/*￡*/7/19編譯原理實(shí)驗(yàn)指導(dǎo)/*非終結(jié)符定義*/ /*邏輯表達(dá) 說明*/#define_E113 /*<E> 算術(shù)表達(dá)式*/(2) 定義兩全局整型數(shù) tokens口和attribs[]分別用于表示詞法分析后的單詞編碼和屬性對集。該定義在token.h中，其定義格式如下：#defineMAXTOKEN100inttokens[MAXTOKEN];/*單詞編碼序列，可容納 100個(gè)*/intattribs[MAXTOKEN]; /*單詞屬性編碼序列 */intip; /*當(dāng)前符號(單詞編碼)指針 */#endif將上述token.h加入到Lex文件的第1部分，替換掉原來的定義。%{#defineYYSTYPEdouble#include<ctype.h>#include<stdlib.h>#include"types.h"#include"hash.h"#include"token.h"floatval=0;%}(3)第2部分為正規(guī)式單詞的定義。實(shí)際這里只用到數(shù)字，也可以不變。(4)每掃描到一個(gè)單詞，對應(yīng)的處理動(dòng)作為：將該單詞的編碼和屬性分別寫入到tokens和attribs數(shù)組中。具體在Lex第3部分如下編程："+" {addToken($add,0);}"-" {addToken($sub,0);}…{digits}{sscanf(yytext,"%f",&val); //數(shù)字。將數(shù)字的值拷貝進(jìn)整型變量 val。其中addToken(inttoken,intattrib) 函數(shù)定義在第4部分：voidaddToken(inttoken,intattr){if(ip<MAXTOKEN){tokens[ip]=token;attribs[ip]=attr;ip++;}}建議大家統(tǒng)一再看看expToken.txt源文件。(5)主程序無需打開輸出文件，每掃描到一個(gè)單詞，系統(tǒng)會(huì)自動(dòng)用相應(yīng)的代碼塊，8/19

編譯原理實(shí)驗(yàn)指導(dǎo)即，調(diào)用addToken函數(shù)執(zhí)行相應(yīng)的工作。這都在 Lex自動(dòng)生成的函數(shù)lexyy()內(nèi)部處理。因此語法分析主程序只需要調(diào)用 lexyy()函數(shù)即可。自編代碼的詞法分析器構(gòu)造(任選)該程序相對而言較為簡單，以下列舉詞法分析主程序。詳細(xì)內(nèi)容見參考代碼。//從流中讀取一個(gè)單詞intlexyy(){charch='';if(bufChar=='')while(isBlank(ch))ch=fgetc(stream);//跳過所有的空格回車else{//else{//使用了超前搜索的情況ch=bufChar;bufChar='';//bufChar='';//用空格清掉超期搜索字符。if(ch=='+')return$add;elseif(ch=='-')return$sub;elseif(ch=='*')return$mul;elseif(ch=='/')return$div;elseif(ch=='(')return$llbr;elseif(ch==')')return$lrbr;elseif(ch=='#')return$sharp;elseif(isDigit(ch))bufChar=ch;//超期搜索緩沖wip=0;bufChar=ch;//超期搜索緩沖wip=0;//單詞指針清0returnreadNum();//讀取整個(gè)數(shù)字，返回?cái)?shù)字的單詞編碼，而數(shù)字的值暫存returnreadNum();于curValue變量。elseerror("詞法錯(cuò)誤");9/19編譯原理實(shí)驗(yàn)指導(dǎo)return0;)主程序的編寫voidmain(){/*執(zhí)行詞法分析*/lexyy();/*執(zhí)行語法分析*/E(); /*調(diào)用開始符號所對應(yīng)的過程進(jìn)行分析。*/printf("語法正確.")； /*如能執(zhí)行到這里，證明中途沒出錯(cuò) */)若上述代碼放在LEX文件中，請把中文注釋去掉，同時(shí)保存類型設(shè)為 ANSI。步驟1、重構(gòu)詞法分析程序設(shè)計(jì)文法定義不回溯且考慮到三種優(yōu)先級的表達(dá)式計(jì)算的文法，前面是一參考實(shí)現(xiàn)。最好能根據(jù)要求獨(dú)立設(shè)計(jì)文法。2、建立C語言工程建立語法分析主程序文件，假定命名為：express.c。同時(shí)將該token.h加入。3、編寫遞歸下降程序根據(jù)文法，按要求在express中編寫遞歸下降子程序。如感覺比較困難，請參照遞歸下降法4、編寫測試主程序(基本要求)構(gòu)造一命令行的輸入程序，即輸入表達(dá)式串。輸出語法分析成功與否。輸出結(jié)果為“語法正確”“語法錯(cuò)誤”。5、程序系統(tǒng)調(diào)試驗(yàn)證結(jié)果問題及解答請大家提出意見和建議，以便改進(jìn)本手冊。提高1、實(shí)現(xiàn)一個(gè)完整的高級語言子集。2、建立圖形界面，對本實(shí)驗(yàn)內(nèi)容進(jìn)行包裝。3、選取針對某些結(jié)構(gòu)化文檔，如XML建立語法分析器。實(shí)驗(yàn)報(bào)告要求考慮到大家的實(shí)際情況，實(shí)驗(yàn)報(bào)告只要求實(shí)現(xiàn)基于字符的分析過程。其提綱如下：1、目的2、內(nèi)容10/19編譯原理實(shí)驗(yàn)指導(dǎo)先介紹下該程序主要功能文法E今TE’ E’二+TE’I￡T今FT’T’=*FT’l￡Ff（E）li遞歸下降過程（附上代碼）測試用例3、總結(jié)（心得）11/19編譯原理實(shí)驗(yàn)指導(dǎo)實(shí)驗(yàn)3實(shí)驗(yàn)3自底向上的語法分析目的1、掌握SLR法進(jìn)行語法分析的原理。2、設(shè)計(jì)相應(yīng)得數(shù)據(jù)結(jié)構(gòu)及編碼，實(shí)施算法的相關(guān)要素的機(jī)內(nèi)表示。3、掌握語法分析器的設(shè)計(jì)與調(diào)試；內(nèi)容1、算法的數(shù)據(jù)結(jié)構(gòu)（1）分析表分析表采用二維持?jǐn)?shù)組，其中第0行存放表頭。intat[MAXROW][MAXCOL]; 〃分析表（2）堆棧由于符號棧與狀態(tài)棧通常同步操作，可將二棧合二為一。堆棧元素可用結(jié)構(gòu)體包裝相應(yīng)的數(shù)據(jù)?！ù矸墙K結(jié)符和終結(jié)符（由于符號棧和狀態(tài)棧均為同步操作。通過結(jié)構(gòu)體的方式實(shí)現(xiàn)堆棧合并）typedefstructT{charname; 〃名稱（便于外部輸出）intcode; 〃編碼（便于內(nèi)部處理）intstate; 〃狀態(tài)intvalue; 〃該非終結(jié)符的值}Token;〃堆棧類型typedefstructS1{Tokenbody[MAXSIZE]; 〃堆棧體intip; 〃棧頂指針}TokenStack;（3）產(chǎn)生式的表示〃產(chǎn)生式候選記錄表typedefstructProduction{charleftName; 〃左部名稱intleftCode; 〃左部編碼intrightLen; 〃右部長度，決定出棧數(shù)。}Prod;12/19

編譯原理實(shí)驗(yàn)指導(dǎo)2、程序模塊的劃分（1）堆棧操作的相關(guān)函數(shù)（2）分析表操作（3）主分析過程〃對一個(gè)輸入符號執(zhí)行分析〃說明：由于堆棧集成為一個(gè)，所以堆棧操作可以不指出堆棧變量。intanalysis(TokenStack*s,intcode){intcurState,curOp,pi; 〃當(dāng)前狀態(tài)，操作，產(chǎn)生式編號curState=getState(s); 〃獲取當(dāng)前狀態(tài)curOp=getOperate(curState,code); 〃獲取當(dāng)前操作if(curOp==-1)error("分析表中未定義")；if(curOp==ACC){〃輸入串正確出口〃歸約代碼〃去掉R〃輸入串正確出口〃歸約代碼〃去掉R標(biāo)識，得到產(chǎn)生式編號)elseif(curOp>R){pi=curOp-R;〃出棧。for(inti=0;i<p[pi].rightLen;i++){〃查對應(yīng)的產(chǎn)生式候選登記表〃出棧。pop(s);）curState=getState（s）; 〃獲取當(dāng)前棧頂狀態(tài)。curOp=getOperate（curState,p[pi].leftCode）;//查Goto表獲取跳轉(zhuǎn)的狀態(tài)?！ǚ枟Ｈ霔?〃狀態(tài)入棧（即查Goto表對應(yīng)的值，所以G與S必須相等）//（語法分析階段：不考慮語義，故value參數(shù)為0）push(s,p[pi].leftName,p[pi].leftCode,curOp-S,0);outputStacks(s);opState=0; 〃當(dāng)前為歸約狀態(tài))elseif(curOp>S){ //Si入棧push(s,getName(code),code,curOp-S,0);//當(dāng)前符號、狀態(tài)入棧outputStacks(s);opState=1; 〃當(dāng)前為移進(jìn)狀態(tài))else13/19編譯原理實(shí)驗(yàn)指導(dǎo)error（"語法錯(cuò)誤!"）； 〃return0;）（4）主程序及輸入輸出（5）錯(cuò)誤處理3、測試要求（1）成功的輸入串（2）詞法錯(cuò)誤串（3）語法錯(cuò)誤串步驟1、建立c語言工程2、加入單詞編碼頭文件。3、編寫相關(guān)代碼4、在命令行下運(yùn)行，進(jìn)行測試。問題時(shí)間關(guān)系，許多地方還沒來得及作好，但歡迎大家提出問題。實(shí)驗(yàn)報(bào)告要求1、目的2、內(nèi)容數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：文字描述，不要求寫代碼主要模塊：①主分析過程（代碼或流程圖）堆棧操作：push、pop…（將函數(shù)名寫出）分析表操作：（將函數(shù)名寫出）④詞法分析輔助過程：（將函數(shù)名寫出）輸入輸出及錯(cuò)誤處理：（將函數(shù)名寫出）（期末考試實(shí)驗(yàn)占10分。其中本實(shí)驗(yàn)將根據(jù)內(nèi)容記分，并直接記入期末成績。可參考所附代碼，如自己有另外實(shí)現(xiàn)也可，需提交代碼）測試：語法正確的表達(dá)式。②語法錯(cuò)誤的表達(dá)式。③詞法錯(cuò)誤的表達(dá)式。3、總結(jié)（心得）14/19編譯原理實(shí)驗(yàn)指導(dǎo)實(shí)驗(yàn)4語義分析目的1、屬性文法及語法制導(dǎo)翻譯和遞歸下降的語法分析結(jié)合，構(gòu)造語義分析程序。2、以表達(dá)式文法為例，構(gòu)造文本計(jì)算器演示程序。知識1、設(shè)計(jì)屬性文法。以一個(gè)例子加以說明：考察文法G（E）:E3TLL—+TLI￡T3$num我們可以從以下幾個(gè)方面去理解。下標(biāo)的含義首先考慮到產(chǎn)生式中不止一個(gè)E，在語法分析中由于在不同的時(shí)間不同的地方處理，因而不會(huì)產(chǎn)生歧義。但在語義分析中，任何一個(gè)符號的屬性都可在上下文中出現(xiàn)，因而有必要加以區(qū)分。通常通過設(shè)置下標(biāo)的方式來區(qū)分。L3+TL1有了下標(biāo)L和L1就能加以區(qū)分?？梢赃@么說，L、L1不是“同個(gè)”非終結(jié)符，但是是“同類”非終結(jié)符。因此，屬性文法設(shè)計(jì)的第一步就是把同一產(chǎn)生式候選中的相同符號加以下標(biāo)。（2）屬性的設(shè)計(jì)屬性是為每個(gè)符號配置的。終結(jié)符得屬性通常通過詞法分析得到。非終結(jié)符的屬性通常為上下文的屬性計(jì)算得到。首先考慮全局的，即整個(gè)文法最終要求什么。將其數(shù)據(jù)化作為開始符號得屬性。在上例中，表達(dá)式最終是求若干個(gè)數(shù)之和的結(jié)果值。因此為非終結(jié)符E配備一個(gè)屬性s，表示E所展開的子表達(dá)式的值。再考慮葉子結(jié)點(diǎn)能夠獲取到什么信息。葉子都是終結(jié)符，信息實(shí)際上是通過詞法分析獲取的單詞語義。如“2”，分析程序掃描到文本字符“2”，將其轉(zhuǎn)換成二進(jìn)制的值2。但在語法分析中，只是將其解釋為“數(shù)字”，用$num表示。而二進(jìn)制的值2只是作為$num的一個(gè)屬性,不妨記為$num.v。最后考慮語法樹中的支干結(jié)點(diǎn)需要傳遞些什么數(shù)據(jù)，根據(jù)相應(yīng)的數(shù)據(jù)定義相應(yīng)的屬性。設(shè)計(jì)屬性時(shí)，必須明確兩點(diǎn)：3、支干（非葉子，非根）結(jié)點(diǎn)的屬性主要功能是傳遞數(shù)據(jù)和中間計(jì)算。要按樹的遍歷順序來考慮。因?yàn)闊o論是自頂向下還是自底向上，本質(zhì)上都是對樹的一次遍歷（這點(diǎn)在上課實(shí)講過）。15/19編譯原理實(shí)驗(yàn)指導(dǎo)4、一個(gè)結(jié)點(diǎn)可以有多個(gè)屬性。本例中，非終結(jié)符L結(jié)點(diǎn)不僅負(fù)責(zé)傳遞屬性，還要完成計(jì)算。定義兩個(gè)屬性變量，i表示輸入屬性，s表示計(jì)算結(jié)果。2+3+5的屬性文法語法樹(3)屬性的計(jì)算規(guī)則設(shè)計(jì)規(guī)則：①根據(jù)實(shí)例語法樹，考慮其自左至右遍歷的順序。分析其數(shù)據(jù)傳遞和計(jì)算方法。②結(jié)合產(chǎn)生式。將傳遞和計(jì)算規(guī)則提煉到產(chǎn)生式中。如上例，設(shè)計(jì)的屬性文法如下：E3T{L.i=T.s}L{E.s=L.s}L3+T{L1.i=L.i+T.s}L1{L.s=L1.s}L3￡{L.s=L.i}T3$num{T.s=$num.v}5、如何根據(jù)屬性文法設(shè)計(jì)遞歸下降子程序關(guān)于遞歸下降的語義分析，清華版的教材沒有提及。國防科大版的教材有初步的介紹。這里以一個(gè)簡單的例子說明如何實(shí)現(xiàn)。繼續(xù)考察上例，即將表達(dá)式中的加法單獨(dú)抽取出來，其語義就是加法。每個(gè)非終結(jié)符對應(yīng)一個(gè)過程繼承屬性作為輸入?yún)?shù)綜合屬性作為返回值如：//E->T{L.i=T.s}L{E.s=L.s}floatE(){16/19編譯原理實(shí)驗(yàn)指導(dǎo)floatTs,Ls;//Ts,Ls分別表示T.s、L.兩個(gè)屬性Ts=T();Ls=L(Ts);returnLs;)內(nèi)容本實(shí)驗(yàn)的主要內(nèi)容在于實(shí)現(xiàn)一個(gè)文本計(jì)算器。屬性文法設(shè)計(jì)由于使用了遞歸下降的語法分析，則必須考慮是否為LL文法。針對表達(dá)式文法，需要選用消除了左遞歸的文法。根據(jù)教材上的版本進(jìn)行改造，考慮了四則混合運(yùn)算的情況。設(shè)計(jì)文法如下：EfT{L.i=T.s}L{E.s=L.s}Lf+T{L1.i=L.i+T.s}L1{L.s=L1.s}Lf-T{L1.i=L.i-T.s}L1{L.s=L1.s}Lf￡{L.s=L.i}TfF{R.i=F.s}R{T.s=R.s}Rf*F{R1.i=R.i