編譯原理實(shí)驗(yàn)全集

1、編譯原理實(shí)驗(yàn)指導(dǎo)編譯原理實(shí)驗(yàn)指導(dǎo) /19實(shí)驗(yàn)2自頂向下的語(yǔ)法分析目的在詞法分析的基礎(chǔ)上，熟悉自頂向下的語(yǔ)法分析方法。體驗(yàn)遞歸程序的特點(diǎn)。實(shí)現(xiàn)界面和業(yè)務(wù)邏輯代碼分離。實(shí)現(xiàn)異種平臺(tái)的訪問(wèn)。培養(yǎng)初步的軟件架構(gòu)的觀念。培養(yǎng)軟件設(shè)計(jì)及編程能力。知識(shí)終結(jié)符、非終結(jié)符及產(chǎn)生式所有的組成最終句子的單詞即為終結(jié)符。非終結(jié)符代表的是我們觀念上的語(yǔ)法范疇。如主語(yǔ)。謂語(yǔ)，名詞等。在高級(jí)語(yǔ)言中，語(yǔ)法范疇包括程序、說(shuō)明語(yǔ)句、可執(zhí)行語(yǔ)句、IF結(jié)構(gòu)、關(guān)系表達(dá)式、算術(shù)表達(dá)式等等。語(yǔ)法及語(yǔ)義分析語(yǔ)法分析只要求驗(yàn)證某個(gè)句子是否符合某個(gè)文法。關(guān)注的是結(jié)構(gòu)。而語(yǔ)義關(guān)注的是句子的含義。計(jì)算機(jī)本身無(wú)生命，無(wú)所謂真正地理解句子的含義。我們所

2、期望的計(jì)算機(jī)執(zhí)行相應(yīng)的語(yǔ)義是指：當(dāng)計(jì)算機(jī)程序掃描到某個(gè)句子后，所執(zhí)行的操作恰好符合這個(gè)句子所表達(dá)的意思。如掃描到一個(gè)“3+2”這樣一個(gè)字符串。自動(dòng)地把結(jié)果5算出來(lái)。而在語(yǔ)法分析中，所作的僅僅是判別這個(gè)句子的結(jié)構(gòu)是否合法。并不執(zhí)行計(jì)算。2.2.3FIRST集與FOLLOW集所謂FIRST集，本質(zhì)上就是第一個(gè)可能出現(xiàn)的符號(hào)構(gòu)成的集合。這個(gè)是可以由產(chǎn)生式本身得到的。因?yàn)槿魏尉渥佣际怯稍撐姆ǖ漠a(chǎn)生式推出來(lái)的。關(guān)于遞歸下降子程序的編寫(xiě)規(guī)則（請(qǐng)注意規(guī)則和下面的顏色對(duì)應(yīng)關(guān)系）：文法中的每個(gè)非終結(jié)符對(duì)應(yīng)一個(gè)過(guò)程（函數(shù)）。若某個(gè)非終結(jié)符有多個(gè)產(chǎn)生式候選，則根據(jù)當(dāng)前輸入符是否在某個(gè)候選的Select集選擇。每個(gè)候

3、選對(duì)應(yīng)一個(gè)if分支。選擇好候選之后，對(duì)產(chǎn)生式候選的右部的符號(hào)由左到右依次處理。若為終結(jié)符。則將該符號(hào)和當(dāng)前輸入符號(hào)進(jìn)行判等操作。若相等，繼續(xù)。否則轉(zhuǎn)若為非終結(jié)符，則調(diào)用該非終結(jié)符所對(duì)應(yīng)的過(guò)程。若當(dāng)前掃描的符號(hào)為當(dāng)前候選的第一個(gè)符號(hào)，且當(dāng)前產(chǎn)生式有候選.則不作出錯(cuò)處理。否則均出錯(cuò)處理。例1:Sf（S）lacharstr口；/待檢查的串intip;掃描指針例2:Sf（S）lcharstr口；待檢查的串intip；掃描指針voidS()/只有一個(gè)非終結(jié)符Sif(strip=()/處理S個(gè)(S)候選ip+;S();if(strip=)ip+;elseerror();elseif(strip=a)/處理

4、S今a候選ip+；else/對(duì)應(yīng)第1符號(hào)error();/但無(wú)候選項(xiàng)，必須出錯(cuò)。voidS()/只有一個(gè)非終結(jié)符Sif(strip=()ip+;S();if(strip=)ip+;elseerror();/不是第1個(gè)符號(hào)，出錯(cuò)。elseif(strip=a)ip+;不作出錯(cuò)處理。需要注意的是，本例比較的是字符。而本實(shí)驗(yàn)中用的是符號(hào)（單詞）編碼，是經(jīng)過(guò)詞法分析后的編碼。也就是后面定義的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ǔ)法檢驗(yàn)。要實(shí)現(xiàn)實(shí)數(shù)的加、減、

5、乘、除、乘方幾種運(yùn)算。這幾種運(yùn)算構(gòu)成了三種優(yōu)先級(jí)。因此文法的表達(dá)和課堂上不一樣。根據(jù)需要設(shè)計(jì)所有的非終結(jié)符?？梢砸援a(chǎn)生式為核心。在設(shè)計(jì)的過(guò)程中逐步引入非終結(jié)符。一一+-一e-*-/一eNf*f（”“）”/此括號(hào)非彼括號(hào)，故用引號(hào)括起來(lái)。f$num/經(jīng)過(guò)詞法分析，數(shù)字被認(rèn)為是終結(jié)符。f非終結(jié)符定義符號(hào)定義符號(hào)定義算術(shù)表達(dá)式消除左遞歸的算術(shù)子表達(dá)式優(yōu)先級(jí)為3的子項(xiàng)消除左遞歸且優(yōu)先級(jí)為3的子項(xiàng)優(yōu)先級(jí)為2的子項(xiàng)消除左遞歸且優(yōu)先級(jí)為2的子項(xiàng)優(yōu)先級(jí)為1的子項(xiàng)說(shuō)明：優(yōu)先級(jí)的編號(hào)越小，其運(yùn)算（歸約）的次序先。基于LEX自動(dòng)構(gòu)造器地詞法分析程序的重構(gòu)（任選）對(duì)于大型編譯系統(tǒng)而言，往往存在多遍掃描的可能性。將詞法

6、分析程序構(gòu)造成獨(dú)立的過(guò)程有很大的好處。但對(duì)于我們這個(gè)小型的文本計(jì)算器而言。將詞法分析構(gòu)造成依附于語(yǔ)法分析的子過(guò)程可能更加合理。因此我們需要對(duì)詞法分析程序進(jìn)行重構(gòu)。本實(shí)驗(yàn)只要求實(shí)現(xiàn)表達(dá)式的求值。因此，只需要使用原來(lái)集合的部分單詞。對(duì)詞法分析程序進(jìn)行重構(gòu)，使之成為語(yǔ)法分析程序的子程序。通過(guò)全局變量的方式加工數(shù)據(jù)，輸入表達(dá)式串，輸出編碼及屬性序列，分別存放在兩個(gè)全局的整型數(shù)組中。因此需要作如下變更：?jiǎn)卧~的編碼在語(yǔ)法分析和詞法分析中都需要，因而同一集中在一個(gè)頭文件token.h中。以后，無(wú)論是詞法、語(yǔ)法、語(yǔ)義分析，均用這套編碼。以下是部分語(yǔ)句：#ifndefTOKEN/*終結(jié)符定義*/#define$

7、add20/*+*/#define$sub21/*/#define$assign37/*=*/#define$num38/*常數(shù)*/#define$eps40/*/*非終結(jié)符定義*/*邏輯表達(dá)說(shuō)明*/#define_E113/*算術(shù)表達(dá)式*/定義兩全局整型數(shù)tokens口和attribs口分別用于表示詞法分析后的單詞編碼和屬性對(duì)集。該定義在token.h中，其定義格式如下：#defineMAXTOKEN100inttokensMAXTOKEN;/*單詞編碼序列，可容納100個(gè)*/intattribsMAXTOKEN;/*單詞屬性編碼序列*/intip;/*當(dāng)前符號(hào)(單詞編碼)指針*/#endi

8、f將上述token.h加入到Lex文件的第1部分，替換掉原來(lái)的定義。%#defineYYSTYPEdouble#include#include#includetypes.h#includehash.h#includetoken.hfloatval=0;%第2部分為正規(guī)式單詞的定義。實(shí)際這里只用到數(shù)字，也可以不變。每掃描到一個(gè)單詞，對(duì)應(yīng)的處理動(dòng)作為：將該單詞的編碼和屬性分別寫(xiě)入到tokens和attribs數(shù)組中。具體在Lex第3部分如下編程：+addToken($add,0);-addToken($sub,0);digitssscanf(yytext,%f,&val);/數(shù)字。將數(shù)字的值拷貝進(jìn)

9、整型變量val。其中addToken(inttoken,intattrib)函數(shù)定義在第4部分：voidaddToken(inttoken,intattr)if(ipR)pi=curOp-R;/出棧。for(inti=0;iS)/Si入棧push(s,getName(code),code,curOp-S,0);/當(dāng)前符號(hào)、狀態(tài)入棧outputStacks(s);opState=1;/當(dāng)前為移進(jìn)狀態(tài)elseerror（語(yǔ)法錯(cuò)誤!）/return0;（4）主程序及輸入輸出（5）錯(cuò)誤處理測(cè)試要求）成功的輸入串）詞法錯(cuò)誤串）語(yǔ)法錯(cuò)誤串步驟1、建立C語(yǔ)言工程2、加入單詞編碼頭文件。3、編寫(xiě)相關(guān)代碼4、在

10、命令行下運(yùn)行，進(jìn)行測(cè)試。問(wèn)題時(shí)間關(guān)系，許多地方還沒(méi)來(lái)得及作好，但歡迎大家提出問(wèn)題。實(shí)驗(yàn)報(bào)告要求目的內(nèi)容數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：文字描述，不要求寫(xiě)代碼主要模塊：主分析過(guò)程（代碼或流程圖）堆棧操作：push、pop（將函數(shù)名寫(xiě)出）分析表操作：（將函數(shù)名寫(xiě)出）詞法分析輔助過(guò)程：（將函數(shù)名寫(xiě)出）輸入輸出及錯(cuò)誤處理：（將函數(shù)名寫(xiě)出）（期末考試實(shí)驗(yàn)占10分。其中本實(shí)驗(yàn)將根據(jù)內(nèi)容記分，并直接記入期末成績(jī)?？蓞⒖妓酱a，如自己有另外實(shí)現(xiàn)也可，需提交代碼）測(cè)試：語(yǔ)法正確的表達(dá)式。語(yǔ)法錯(cuò)誤的表達(dá)式。詞法錯(cuò)誤的表達(dá)式?？偨Y(jié)（心得）實(shí)驗(yàn)4語(yǔ)義分析目的屬性文法及語(yǔ)法制導(dǎo)翻譯和遞歸下降的語(yǔ)法分析結(jié)合，構(gòu)造語(yǔ)義分析程序。以表達(dá)式文

11、法為例，構(gòu)造文本計(jì)算器演示程序。知識(shí)1、設(shè)計(jì)屬性文法。以一個(gè)例子加以說(shuō)明：考察文法G（E）:EfTLLf+TLIeTf$num我們可以從以下幾個(gè)方面去理解。下標(biāo)的含義首先考慮到產(chǎn)生式中不止一個(gè)E,在語(yǔ)法分析中由于在不同的時(shí)間不同的地方處理，因而不會(huì)產(chǎn)生歧義。但在語(yǔ)義分析中，任何一個(gè)符號(hào)的屬性都可在上下文中出現(xiàn)，因而有必要加以區(qū)分。通常通過(guò)設(shè)置下標(biāo)的方式來(lái)區(qū)分。Lf+TL1有了下標(biāo)L和L1就能加以區(qū)分?？梢赃@么說(shuō)，L、L1不是“同個(gè)”非終結(jié)符，但是是“同類”非終結(jié)符。因此，屬性文法設(shè)計(jì)的第一步就是把同一產(chǎn)生式候選中的相同符號(hào)加以下標(biāo)。屬性的設(shè)計(jì)屬性是為每個(gè)符號(hào)配置的。終結(jié)符得屬性通常通過(guò)詞法分析

12、得到。非終結(jié)符的屬性通常為上下文的屬性計(jì)算得到。首先考慮全局的，即整個(gè)文法最終要求什么。將其數(shù)據(jù)化作為開(kāi)始符號(hào)得屬性。在上例中，表達(dá)式最終是求若干個(gè)數(shù)之和的結(jié)果值。因此為非終結(jié)符E配備一個(gè)屬性s，表示E所展開(kāi)的子表達(dá)式的值。再考慮葉子結(jié)點(diǎn)能夠獲取到什么信息。葉子都是終結(jié)符，信息實(shí)際上是通過(guò)詞法分析獲取的單詞語(yǔ)義。如“2”，分析程序掃描到文本字符“2”，將其轉(zhuǎn)換成二進(jìn)制的值2。但在語(yǔ)法分析中，只是將其解釋為“數(shù)字”，用$num表示。而二進(jìn)制的值2只是作為$num的一個(gè)屬性,不妨記為$num.v。最后考慮語(yǔ)法樹(shù)中的支干結(jié)點(diǎn)需要傳遞些什么數(shù)據(jù)，根據(jù)相應(yīng)的數(shù)據(jù)定義相應(yīng)的屬性。設(shè)計(jì)屬性時(shí)，必須明確兩點(diǎn)：

13、支干（非葉子，非根）結(jié)點(diǎn)的屬性主要功能是傳遞數(shù)據(jù)和中間計(jì)算。要按樹(shù)的遍歷順序來(lái)考慮。因?yàn)闊o(wú)論是自頂向下還是自底向上，本質(zhì)上都是對(duì)樹(shù)的一次遍歷（這點(diǎn)在上課實(shí)講過(guò)）。4、一個(gè)結(jié)點(diǎn)可以有多個(gè)屬性。本例中，非終結(jié)符L結(jié)點(diǎn)不僅負(fù)責(zé)傳遞屬性，還要完成計(jì)算。定義兩個(gè)屬性變量，i表示輸入屬性，s表示計(jì)算結(jié)果。235的屬性文法語(yǔ)法樹(shù)（3）屬性的計(jì)算規(guī)則設(shè)計(jì)規(guī)則：根據(jù)實(shí)例語(yǔ)法樹(shù)，考慮其自左至右遍歷的順序。分析其數(shù)據(jù)傳遞和計(jì)算方法。結(jié)合產(chǎn)生式。將傳遞和計(jì)算規(guī)則提煉到產(chǎn)生式中。如上例，設(shè)計(jì)的屬性文法如下：E3TL.i=T.sLE.s=L.sL3+TL1.i=L.i+T.sL1L.s=L1.sL3L.s=L.iT3$n

14、umT.s=$num.v如何根據(jù)屬性文法設(shè)計(jì)遞歸下降子程序關(guān)于遞歸下降的語(yǔ)義分析，清華版的教材沒(méi)有提及。國(guó)防科大版的教材有初步的介紹。這里以一個(gè)簡(jiǎn)單的例子說(shuō)明如何實(shí)現(xiàn)。繼續(xù)考察上例,即將表達(dá)式中的加法單獨(dú)抽取出來(lái)，其語(yǔ)義就是加法。每個(gè)非終結(jié)符對(duì)應(yīng)一個(gè)過(guò)程繼承屬性作為輸入?yún)?shù)綜合屬性作為返回值如：/E-TL.i=T.sLE.s=L.sfloatE()floatTs,Ls;/Ts,Ls分別表示T.s、L.兩個(gè)屬性Ts=T();Ls=L(Ts);returnLs;本實(shí)驗(yàn)的主要內(nèi)容在于實(shí)現(xiàn)一個(gè)文本計(jì)算器。屬性文法設(shè)計(jì)由于使用了遞歸下降的語(yǔ)法分析，則必須考慮是否為L(zhǎng)L文法。針對(duì)表達(dá)式文法，需要選用消除了

15、左遞歸的文法。根據(jù)教材上的版本進(jìn)行改造，考慮了四則混合運(yùn)算的情況。設(shè)計(jì)文法如下：EfTL.i=T.sLE.s=L.sLf+TL1.i=L.i+T.sL1L.s=L1.sLf-TL1.i=L.i-T.sL1L.s=L1.sLfL.s=L.iTfFR.i=F.sRT.s=R.sRf*FR1.i=R.i*F.sL1R.s=R1.sRf/FR1.i=R.i/F.sL1R.s=R1.sRfR.s=R.iFf(E)F.s=E.iFf$numF.s=$num.val遞歸下降的語(yǔ)義分析程序的設(shè)計(jì)。這里列舉兩個(gè)，其余的自行設(shè)計(jì)：/R-*FR1.i=R.i*F.sR1R.s=R1.s/R-/FR1.i=R.i/F

16、.sR1R.s=R1.s/R-R.s=R.ifloatR(floatRi)floatFs,Rs;if(code=$mul)/乘法*code=lexyy();Fs=F();Rs=R(Ri*Fs);elseif(code=$div)/除法/code=lexyy();Fs=F();Rs=R(Ri/Fs);elseRs=Ri;returnRs;/F-(E)F.s=E.s/F-$numF.s=$num.valfloatF()floats;if(code=$llbr)/是否為(code=lexyy();/再讀一個(gè)單詞s=E();if(code!=$lrbr)/是否為)error(括號(hào)不匹配)code=lexyy();elseif(code=$num)s=curValue;/取出數(shù)值code=lexyy();/讀下一個(gè)單詞elseerror(表達(dá)式語(yǔ)法錯(cuò)誤)；returns;步驟對(duì)問(wèn)題本身進(jìn)行細(xì)致的分析，先在紙上設(shè)計(jì)好屬性文法(屬性文法相當(dāng)于藍(lán)圖)。2、建立VC+工程，命名主文件，加入=捻695的頭文件。將前面詞法分析、出錯(cuò)處理、輸入輸出等的相關(guān)函數(shù)加入。根據(jù)屬性文法編寫(xiě)遞歸下降子程序代碼。設(shè)計(jì)主程序。6、測(cè)試。代碼編好后可按F10進(jìn)行單步跟蹤。測(cè)試用例包括：正確的表達(dá)式。詞法錯(cuò)誤的表達(dá)式。語(yǔ)法錯(cuò)誤的表達(dá)式樣。實(shí)驗(yàn)報(bào)告要求1、目的2、內(nèi)容(1)基于算術(shù)運(yùn)算