語(yǔ)法制導(dǎo)的三地址代碼生成器

學(xué)習(xí)好資料歡迎下載學(xué)習(xí)好資料歡迎下載學(xué)習(xí)好資料歡迎下載實(shí)驗(yàn)二：語(yǔ)法制導(dǎo)的三地址代碼生成器一教學(xué)重點(diǎn)與實(shí)現(xiàn)的關(guān)鍵技術(shù)1.1自頂向下（top—down）分析概述自頂向下分析法包括：遞歸子程序法和預(yù)測(cè)分析法(LL(1))。自頂向下就是從文法的開(kāi)始符號(hào)出發(fā)，向下推導(dǎo)，推出句子。這種方法是帶“回溯”的。其主旨是：對(duì)任何輸入串，試圖用一切可能的辦法，從文法開(kāi)始符號(hào)（根）出發(fā)，自頂向下地為輸入串建立一棵語(yǔ)法樹(shù)?；蛘哒f(shuō)，為輸入串尋找一個(gè)最左推導(dǎo)。這種分析過(guò)程本質(zhì)上是一種試探過(guò)程，是反復(fù)使用不同產(chǎn)生式謀求匹配輸入串的過(guò)程。例：G為：S→xAyA→**|*，輸入串：x**ySTxAyTx**ySS**xyA**xyA在子樹(shù)A通過(guò)試探匹配后，才進(jìn)行下一個(gè)符號(hào)y的匹配。實(shí)現(xiàn)這種自頂向下的帶回溯試探法的一個(gè)簡(jiǎn)單途徑是讓每個(gè)非終結(jié)符對(duì)應(yīng)一個(gè)遞歸子程序。每個(gè)子程序可作為一個(gè)布爾過(guò)程。一旦發(fā)現(xiàn)它的某個(gè)侯選與輸入串相匹配，就用這個(gè)侯選去擴(kuò)展語(yǔ)法樹(shù)，并返回“真”值；否則，保持原來(lái)的語(yǔ)法樹(shù)和IP值不變，并返回“假”值。這種分析法有許多困難和缺點(diǎn)。首先，是文法的左遞歸問(wèn)題。其次，回溯會(huì)碰到一大堆麻煩事情。第三，在上述的自頂向下分析過(guò)程中，當(dāng)一個(gè)非終結(jié)符用某一候選匹配成功時(shí)，這種成功可能是暫時(shí)的。第四，當(dāng)最終報(bào)告分析不成功時(shí)，難于知道輸入串中出錯(cuò)的確切位置。1.2LL（1）分析法技術(shù)自頂向下分析方法不允許文法含有任何左遞歸。為構(gòu)造不帶回溯的自頂向下分析算法，首先要消除文法的左遞歸性，并找出無(wú)回溯的充分必要條件。LL（1）分析法主要用于消除左遞歸和克服回溯的方法。1.2.1左遞歸的消除直接左遞歸ATAα間接左遞歸 AT+Aα左遞歸的消除方法：將A→Aα|β替換為A→βA′和A′→αA′｜ε例：表達(dá)式文法直接左遞歸的消除E→TE’E→TE’E’→+TE’|εT→FT’T’→*FT’｜εF→(E)｜idE→E+T｜TT→T*F｜FF→(E)｜id例：間接左遞歸的消除S→Ac|c A→Bb|b B→Sa|a將B的定義代入A產(chǎn)生式得：A→Sab|ab|b將A的定義代入S產(chǎn)生式得:S→Sabc|abc|bc|c消除直接左遞歸： S→abcS’|bcS’|cS’ S’→abcS’|ε刪除“多余的”產(chǎn)生式：A→Sab|ab|b和B→Sa|a結(jié)果： S→abcS’|bcS’|cS’ S’→abcS’|ε消除左遞歸的一般方法：用產(chǎn)生式組A?β1B|β2B|…|βnBB?α1B|α2B|…|αnB|ε替換產(chǎn)生式組A→Aα1|Aα2|…|Aαn|β1|β2|…|βm其中：B為新變量，相當(dāng)于A’消除左遞歸的算法：Ⅰ、把文法G的所有非終結(jié)符按任一種順序排列成A1，A2，……，An；按此順序執(zhí)行；Ⅱ、FORi:=1tonDOBeginFORj:=1toi-1DO把形如Ai?Ajγ的規(guī)則改寫(xiě)成Ai?δ1γ│δ2γ│……│δkγ。其中Aj?δ1│δ2│……│δk是關(guān)于Pj的所有規(guī)則；消除關(guān)于Pi規(guī)則的直接左遞歸性ENDⅢ、化簡(jiǎn)由（Ⅱ）所得的文法。即去除那些從開(kāi)始符號(hào)出發(fā)永遠(yuǎn)無(wú)法到達(dá)的非終結(jié)符的產(chǎn)生規(guī)則，為非終結(jié)符編號(hào)，再采用代入法將間接左遞歸變?yōu)橹苯幼筮f歸，消除直接左遞歸。1.2.2消除回溯、提左因子欲構(gòu)造行之有效的自頂向下的分析器，必須消除回溯。為了消除回溯就必須保證：對(duì)文法的任何非終結(jié)符，當(dāng)要用它去匹配輸入串時(shí)，能夠根據(jù)它所面臨的輸入符號(hào)準(zhǔn)確地指派它的一個(gè)侯選去執(zhí)行任務(wù)，并且此侯選的工作結(jié)果應(yīng)是確信無(wú)疑的。也就是說(shuō)，若此侯選獲得成功匹配，那么，這種匹配決不會(huì)是虛假的；若此侯選無(wú)法完成匹配任務(wù)，則任何其它侯選也肯定無(wú)法完成。但是，如何把一個(gè)文法改造成任何非終結(jié)符的所有侯選首符集兩兩不相交呢？其辦法是，提取公共左因子。例：if語(yǔ)句的原始文法S→ifEthenS|ifEthenSelseS|other遇到if時(shí)難以判斷用哪一個(gè)產(chǎn)生式進(jìn)行匹配（推導(dǎo)）存在左因子ifEthenS提取作因子：S→ifEthenSS’|otherS'→ε|elseS左因子提取方法：將形如A→αβ1|αβ2|…|αβn|γ1|γ2|…|γm的規(guī)則改寫(xiě)為A→αA'|γ1|γ2|…|γm和A'→β1|β2|…|βn1.2.3候選式的確定與回溯(Backtracking)當(dāng)要進(jìn)行某個(gè)語(yǔ)法變量的推導(dǎo)時(shí)，希望能夠根據(jù)當(dāng)前符號(hào)確定候選式。如果有幾個(gè)候選式（右部）左端第一個(gè)符號(hào)相同，則分析器無(wú)法根據(jù)當(dāng)前輸入符號(hào)選擇產(chǎn)生式，只能試探。因此，希望尋找一類(lèi)文法，我們可以方便地根據(jù)當(dāng)前輸入符合確定正確的候選式。為了描述方便，我們定義文法符號(hào)的FIRST（首符號(hào)集）和非終結(jié)符的FOLLOW（后續(xù)符號(hào)集）：FIRST集：對(duì)于"α∈(VT∪VN)*定義:α的首符號(hào)集FIRST(α)={a|αT*a…，a∈VT*}FOLLOW集：對(duì)于"A∈VN定義A的后續(xù)符號(hào)集：FOLLOW(A)={a|ST*…Aa…，a∈VT}求FIRST(X)的算法：1)對(duì)"x∈VT，F(xiàn)IRST(x)={x}；2)對(duì)"X∈VN，取FIRST(X)的初值： {a|X→a…∈P}； X→ε?PFIRST(X)= {a|X→a…∈P}∪{ε}； X→ε∈P3)對(duì)"X∈VN，重復(fù)如下過(guò)程，直到所有FIRST集不變?nèi)鬤→Y…∈P，且Y∈VN，則FIRST(X)=FIRST(X)∪(FIRST(Y)-{ε})；若X→Y1…Yn∈P，且Y1...Yi-1T*ε，則對(duì)k=1到i-1:FIRST(X)=FIRST(X)∪(FIRST(Yk)-{ε})；若Y1...YnT*ε，則FIRST(X)=FIRST(X)∪{ε}求FOLLOW(A)的算法：對(duì)于所有非終結(jié)符,重復(fù)進(jìn)行以下計(jì)算1)將#加入到FOLLOW(S)#為句子的結(jié)束符2)若A→αBβ，則FOLLOW(B)=FOLLOW(B)∪FIRST(β)–{ε}3)如果A→αB或A→αBβ，且βT*ε，A≠B，則FOLLOW(B)=FOLLOW(B)∪FOLLOW(A)1.2.4LL（1）分析條件對(duì)G的任意變量A，A→α1|α2|…|αn是所有A產(chǎn)生式，它們滿(mǎn)足下列條件，則稱(chēng)G是LL(1)文法：Ⅰ、FIRST(αi)∩FIRST(αj)=Φi≠jⅡ、且當(dāng)ε∈FIRST(αj)時(shí)，F(xiàn)OLLOW(A)∩FIRST(αi)=ΦLL(1)文法是自頂向下方法能夠處理的一類(lèi)文法：第一個(gè)L表示從左向右掃描輸入符號(hào)串；第二個(gè)L表示生成最左推導(dǎo)；1表示讀入一個(gè)符號(hào)可確定下一步推導(dǎo)。例：表達(dá)式文法是LL(1)文法E→TE'E'→+TE'｜εT→FT'T'→*FT'｜εF→(E)｜id考察E':+不在FOLLOW(E')={),#}T':*不在FOLLOW(T')={+,),#}F:(和id不同例：非LL(1)文法的不確定性對(duì)文法S→cAdA→ab|a輸入cad的分析不確定性的解決方法：1)采用回溯算法2）將非LL(1)文法改寫(xiě)為等價(jià)的LL(1)文法3）無(wú)法改寫(xiě)時(shí)，增加其它的判別因素1.3遞歸子程序法當(dāng)一個(gè)文法滿(mǎn)足LL（1）條件時(shí)，我們就可以為它構(gòu)造一個(gè)不帶回溯的自頂向下分析器（又稱(chēng)遞歸下降分析器），這個(gè)分析器是由一組遞歸過(guò)程組成的，每個(gè)過(guò)程對(duì)應(yīng)文法的一個(gè)非終結(jié)符。這種分析方法稱(chēng)為遞歸子程序法。具體做法為：對(duì)應(yīng)每個(gè)語(yǔ)法變量設(shè)置一個(gè)處理子程序：即對(duì)于每條產(chǎn)生式規(guī)則：A→X1X2…Xk…Xn當(dāng)遇到Xk是終極符號(hào)時(shí)直接進(jìn)行匹配當(dāng)遇到Xk是語(yǔ)法變量時(shí)就調(diào)用Xk對(duì)應(yīng)的處理子程序要求處理子程序是可以遞歸調(diào)用的例如：簡(jiǎn)單算術(shù)表達(dá)式的分析器E的子程序(E→T(+T)*)procedureE;beginT; Ｔ的過(guò)程調(diào)用whilelookhead='+'dobegin 當(dāng)前符號(hào)等于＋時(shí)match(‘+’); 處理終結(jié)符＋T Ｔ的過(guò)程調(diào)用endend; lookhead：當(dāng)前符號(hào)實(shí)現(xiàn)遞歸子程序的一個(gè)有效工具是狀態(tài)轉(zhuǎn)換圖。語(yǔ)法分析器和詞法分析器的狀態(tài)轉(zhuǎn)換圖不同，每個(gè)非終結(jié)符對(duì)應(yīng)一個(gè)狀態(tài)轉(zhuǎn)換圖，邊上的標(biāo)記是記號(hào)和非終結(jié)符。記號(hào)上的轉(zhuǎn)換意味著如果該記號(hào)是下一個(gè)輸入符號(hào)，就應(yīng)進(jìn)行轉(zhuǎn)換。非終結(jié)符A上的轉(zhuǎn)換是對(duì)與A對(duì)應(yīng)的過(guò)程的調(diào)用，從文法構(gòu)造語(yǔ)法圖，對(duì)每個(gè)非終結(jié)符A執(zhí)行如下操作：創(chuàng)建一個(gè)開(kāi)始狀態(tài)和一個(gè)終止?fàn)顟B(tài)（返回狀態(tài)）。對(duì)每個(gè)產(chǎn)生式A→X1X2…Xn，創(chuàng)建一條從開(kāi)始狀態(tài)到終止?fàn)顟B(tài)的路徑，邊上的標(biāo)記分別為X1，X2，…，Xn。開(kāi)始，分析器進(jìn)入狀態(tài)圖的開(kāi)始狀態(tài)，輸入指針指向輸入符號(hào)串的第一個(gè)符號(hào)。如果經(jīng)過(guò)一些動(dòng)作后，它進(jìn)入狀態(tài)s，且從狀態(tài)s到狀態(tài)t的邊上標(biāo)記了終結(jié)符a，此時(shí)下一個(gè)輸入符又正好是a，則分析器將輸入指針向右移動(dòng)一位，并進(jìn)入狀態(tài)t。另一方面，如果邊上標(biāo)記的是非終結(jié)符A，則分析器進(jìn)入A的初始狀態(tài)，但不移動(dòng)輸入指針。一旦到達(dá)A的終態(tài)，則立刻進(jìn)入狀態(tài)t，事實(shí)上，分析器從狀態(tài)s轉(zhuǎn)移到狀態(tài)t時(shí)，它已經(jīng)從輸入符號(hào)串“讀”了A（調(diào)用A對(duì)應(yīng)的過(guò)程）。最后，如果從s到t有一條標(biāo)記為ε的邊，那么分析器從狀態(tài)s直接進(jìn)入狀態(tài)t而不移動(dòng)輸入指針。遞歸子程序法小結(jié)：1）構(gòu)造文法2）改造文法：消除二義性和左遞歸、提取左因子3）求每個(gè)候選式的FIRST集和每個(gè)變量的FOLLOW集4）檢查是不是LL(1)文法，不是LL(1),說(shuō)明文法的復(fù)雜性超過(guò)自頂向下方法的分析能力，需要附加新的“信息”5）按照LL(1)文法畫(huà)語(yǔ)法圖6）化簡(jiǎn)語(yǔ)法圖7）按照簡(jiǎn)化后的語(yǔ)法圖，為每個(gè)非終結(jié)符設(shè)置一個(gè)分析子程序。事實(shí)上，如果有一個(gè)恰當(dāng)?shù)奈姆?，可以直接根?jù)每個(gè)語(yǔ)法變量的產(chǎn)生式設(shè)計(jì)相應(yīng)的程序。遞歸子程序法優(yōu)點(diǎn)：1）直觀、簡(jiǎn)單、可讀性好2）便于擴(kuò)充遞歸子程序法缺點(diǎn)：1)遞歸算法的實(shí)現(xiàn)效率低2)處理能力相對(duì)有限3)通用性差，難以自動(dòng)生成實(shí)驗(yàn)二的語(yǔ)法分析部分建議學(xué)生采用遞歸子程序法實(shí)現(xiàn)。當(dāng)?shù)诙€(gè)實(shí)驗(yàn)被分解為兩個(gè)實(shí)驗(yàn)時(shí)，則先采用遞歸子程序法實(shí)現(xiàn)一個(gè)自頂向下的語(yǔ)法分析器。1.4預(yù)測(cè)分析法實(shí)現(xiàn)LL（1）分析的另一種有效方法是預(yù)測(cè)分析法。一個(gè)預(yù)測(cè)分析器的組成為：一個(gè)通用的控制算法；一個(gè)分析棧，#為棧底符號(hào)；一個(gè)輸入緩沖區(qū)，#為輸入串結(jié)束符；一個(gè)統(tǒng)一形式的分析表M；（不同語(yǔ)言使用內(nèi)容不同的分析表）。主要通過(guò)一張分析表和一個(gè)分析棧進(jìn)行聯(lián)合控制。其模型如下：a1a2……ai……an#棧S#控制程序預(yù)測(cè)分析表M輸出的產(chǎn)生式序列分析方式：輸入指針指向輸入串的第一個(gè)字符，分析棧中存放棧底符號(hào)#和文法的開(kāi)始符號(hào)S。根據(jù)棧頂符號(hào)A和讀入的符號(hào)a，查看分析表M，以決定相應(yīng)的動(dòng)作，其關(guān)鍵是分析表的構(gòu)造。預(yù)測(cè)分析表的構(gòu)造算法：1)對(duì)于每一產(chǎn)生式A→α，執(zhí)行2)和3)；2)對(duì)于FIRST(α)中的每一終結(jié)符a,將A→α填入M[A,a]；3)如果ε屬于FIRST(α)，則對(duì)FOLLOW(A)中的每個(gè)符號(hào)b，將A→α填入M[A,b]；若ε屬于FIRST(α)，且#在FOLLOW(A)，則將A→α填入M[A,#]；4)將所有無(wú)定義的M[A,b]標(biāo)上錯(cuò)誤標(biāo)志預(yù)測(cè)分析法的步驟：1）構(gòu)造文法。2）改造文法：消除二義性、消除左遞歸、提取左因子。3）求每個(gè)候選式的FIRST集和變量的FOLLOW集。4）檢查是不是LL(1)文法，若不是LL(1),說(shuō)明文法的復(fù)雜性超過(guò)自頂向下方法的分析能力，需要附加新的“信息”。5）構(gòu)造預(yù)測(cè)分析表。6）實(shí)現(xiàn)預(yù)測(cè)分析器。出錯(cuò)處理問(wèn)題：對(duì)語(yǔ)法變量A，如果M[A,a]無(wú)定義，并且a屬于FOLLOW(A)，則增加M[A,a]為“同步點(diǎn)”(synch)。預(yù)測(cè)分析法的優(yōu)點(diǎn)：1）效率高2）便于維護(hù)、自動(dòng)生成由于我們建議學(xué)生采用遞歸子程序法自己手工地實(shí)現(xiàn)一個(gè)自頂向下的語(yǔ)法分析器，關(guān)于預(yù)測(cè)分析器的設(shè)計(jì)實(shí)現(xiàn)細(xì)節(jié)就不在這里贅述。1.5屬性文法和語(yǔ)法制導(dǎo)翻譯目前實(shí)際應(yīng)用中比較流行的語(yǔ)義描述和語(yǔ)義處理的方法主要還是屬性文法和語(yǔ)法制導(dǎo)翻譯方法。屬性文法是在上下文無(wú)關(guān)文法的基礎(chǔ)上，為每個(gè)文法符號(hào)（終結(jié)符或非終結(jié)符）配備若干相關(guān)的“值”（稱(chēng)為屬性），是Knuth在1968年提出的。這些屬性代表與文法符號(hào)相關(guān)信息，例如它的類(lèi)型、值、代碼序列、符號(hào)表內(nèi)容等等。屬性與變量一樣，可以進(jìn)行計(jì)算和傳遞。屬性文法的特點(diǎn)：（1）是一種接近形式化的語(yǔ)義描述方法（2）長(zhǎng)于描述靜態(tài)語(yǔ)義、短于描述動(dòng)態(tài)語(yǔ)義（3）每個(gè)語(yǔ)法符號(hào)有相應(yīng)的屬性符號(hào)（4）每個(gè)產(chǎn)生式有相應(yīng)的計(jì)算屬性的規(guī)則（5）屬性變量:=屬性表達(dá)式舉例：產(chǎn)生式 屬性（計(jì)算）規(guī)則/語(yǔ)義規(guī)則E→E1+E2 E.val:=E1.val+E2.valE→E1*E2 E.val:=E1.val*E2.valE→(E1) E.val:=E1.valE→id E.val:=id.val屬性文法的定義：三元組：Ａ＝（Ｇ，Ｖ，Ｆ）Ｇ是上下文無(wú)關(guān)文法Ｖ屬性的有窮集Ｆ關(guān)于屬性的計(jì)算規(guī)則屬性及其計(jì)算規(guī)則：語(yǔ)義信息作為終結(jié)符和非終結(jié)符的屬性。語(yǔ)義分析為產(chǎn)生式相關(guān)的屬性計(jì)算：每個(gè)產(chǎn)生式設(shè)置語(yǔ)義規(guī)則，描述各屬性的關(guān)系——計(jì)算規(guī)則。屬性的設(shè)定：根據(jù)文法符號(hào)的語(yǔ)義，為文法符號(hào)設(shè)置屬性，用來(lái)表示文法符號(hào)的語(yǔ)義。終結(jié)符使用單詞的屬性（id.val）保留字：if,begin,function,……常數(shù)：40.12,232,80,“TCP/IP”標(biāo)識(shí)符：sum,tcc,id語(yǔ)法變量根據(jù)實(shí)際需要設(shè)定屬性表達(dá)式E：E.type，E.val例如：計(jì)算器的屬性文法要完成一個(gè)輸入表達(dá)式值的計(jì)算和顯示——翻譯用文法描述要完成的動(dòng)作：L→EE→E1+T|TT→T1*F|FF→(E)|digit如何描述翻譯過(guò)程？請(qǐng)看如下屬性文法：L→E print(E.val)（L的虛屬性）E→E1+T E.val:=E1.val+T.valE→T E.val:=T.valT→T1*F T.val:=T1.val*F.valT→F T.val:=F.valF→(E) F.val:=E.valF→digit F.val:=digit.lexval其中，lexval是單詞digit的屬性下面簡(jiǎn)述一下屬性的分類(lèi)繼承屬性設(shè)A→X1X2…Xn為一個(gè)產(chǎn)生式，Xi的屬性Xi.in=f(c,c1,c2,…,ci-1)c,c1,c2,…,ci-1是A,X1，X2，…，Xi-1的屬性叫做繼承(Inherited)屬性AAx1x2xnxk…1≤k<i≤n推導(dǎo)分析較自然Xi.inc1c2ckcnc綜合屬性設(shè)A→X1X2…Xn為一個(gè)產(chǎn)生式A.s=f(c1,c2,…,ck)c1,c2,…,ck是X1，X2，…，Xn的屬性和A的繼承屬性A.s是從其子結(jié)點(diǎn)的屬性值計(jì)算出來(lái)的這種屬性叫做綜合(Synthesized)屬性。AAx1x2xn適應(yīng)：歸約分析A.sc1c2cnA.in固有屬性語(yǔ)言中的標(biāo)識(shí)符、常數(shù)（數(shù)值的、符號(hào)的）、常量，它們的屬性是用戶(hù)給定的、不變的。T→int T.type:=integer固有(Inherent)屬性（單詞屬性），歸類(lèi)于綜合屬性。屬性的計(jì)算：綜合屬性是自底向上按照語(yǔ)義規(guī)則來(lái)計(jì)算各結(jié)點(diǎn)的綜合屬性值——在歸約時(shí)進(jìn)行計(jì)算繼承屬性是根據(jù)依賴(lài)關(guān)系決定計(jì)算順序的任意一個(gè)拓?fù)渑判颍═opologicalSort)。固有屬性在詞法分析時(shí)計(jì)算。例：3*5+4的分析樹(shù)與屬性計(jì)算：語(yǔ)法制導(dǎo)翻譯屬性加工的過(guò)程即是語(yǔ)義處理的過(guò)程。對(duì)于文法的每個(gè)產(chǎn)生式都配備了一組屬性的計(jì)算規(guī)則，稱(chēng)為語(yǔ)義規(guī)則。語(yǔ)法制導(dǎo)翻譯是在進(jìn)行語(yǔ)法分析的同時(shí)，完成相應(yīng)的語(yǔ)義處理。例如：E→E1+E2 E.val:=E1.val+E2.val如何根據(jù)被識(shí)別出的語(yǔ)法成分進(jìn)行語(yǔ)義處理？語(yǔ)義——可以看成是相應(yīng)文法符號(hào)的屬性。（1）對(duì)應(yīng)每一個(gè)產(chǎn)生式編制一個(gè)語(yǔ)義子程序，當(dāng)一個(gè)產(chǎn)生式獲得匹配時(shí)，調(diào)用相應(yīng)的語(yǔ)義子程序?qū)崿F(xiàn)語(yǔ)義檢查與翻譯。例如：E→E1+T E.val:=E1.val+T.valT→T1*F T.val:=T1.val*F.valF→id F.val:=id.val以上翻譯模式適應(yīng)在完成歸約的時(shí)候進(jìn)行。（2）在產(chǎn)生式的右部的適當(dāng)位置，插入相應(yīng)的語(yǔ)義動(dòng)作，按照分析的進(jìn)程，執(zhí)行遇到的語(yǔ)義動(dòng)作D→T{L.in:=T.type}LT→int{T.type:=integer}T→real{T.type:=real}L→{L1.in:=L.in}L1,id{…}以上翻譯模式適應(yīng)在進(jìn)行推導(dǎo)時(shí)完成對(duì)應(yīng)語(yǔ)法基本分析方法（Top-down、Bottom-up）1.6實(shí)現(xiàn)的關(guān)鍵技術(shù)提示對(duì)于“語(yǔ)法制導(dǎo)的三地址代碼生成器的編制”實(shí)驗(yàn)而言，除了能正確地畫(huà)出語(yǔ)法圖并化簡(jiǎn)，求出FIRST,FOLLW集外，在實(shí)現(xiàn)過(guò)程中還要想方設(shè)法保證輸出的產(chǎn)生式規(guī)則（三地址代碼）嚴(yán)格按照自頂向下、從左至右的順序進(jìn)行，為了達(dá)到這一要求，需要在每次調(diào)用與某個(gè)語(yǔ)法變量相應(yīng)的處理程序時(shí)，一進(jìn)入過(guò)程就輸出該規(guī)則（生成相應(yīng)的三地址代碼），而在有些情況下，為了正確地選擇匹配的規(guī)則（生成相應(yīng)的三地址代碼）必須連續(xù)向前看若干的符號(hào)（token），這時(shí)應(yīng)想到如何把分析過(guò)的符號(hào)暫時(shí)保存起來(lái)（事實(shí)上棧是解決這類(lèi)問(wèn)題的良好選擇）。這些難點(diǎn)的最終解決，正體現(xiàn)了計(jì)算機(jī)學(xué)科的魅力所在，它要求每個(gè)從事這項(xiàng)工作的人“既要想得對(duì)，也要做得到”。二具體實(shí)驗(yàn)要求2.1實(shí)驗(yàn)?zāi)康恼莆沼?jì)算機(jī)語(yǔ)言的語(yǔ)法分析器設(shè)計(jì)與屬性文法應(yīng)用的實(shí)現(xiàn)方法。2.3實(shí)驗(yàn)內(nèi)容編制一個(gè)能夠進(jìn)行語(yǔ)法分析并生成三地址代碼的微型編譯程序。2.4實(shí)驗(yàn)要求1考慮下述語(yǔ)法制導(dǎo)定義中文法，采用遞歸子程序法，改寫(xiě)文法，構(gòu)造語(yǔ)法分析器；2考慮下述語(yǔ)法制導(dǎo)定義中語(yǔ)義規(guī)則，改寫(xiě)語(yǔ)法分析器，構(gòu)造三地址代碼生成器。產(chǎn)生式語(yǔ)義規(guī)則S → id=ES.code=E.code||gen(id.place’:=’E.place)S → ifCthenS1C.true=newlabel;C.false=S.next;S1.next=S.next;S.code=C.code||gen(E.true’:’)||S1.codeS → ifCthenS1elseS2C.true=newlabel;C.false=newlabel;S1.next=S2.next=S.next;S.code=C.code||gen(E.true’:’)||S1.code||gen(‘goto’,S.next)||gen(E.false’:’)||S2.codeS →whileCdoS1S.begin=newlabel;C.true=newlabel;C.false=S.next;S1.next=S.begin;S.code=gen(S.begin’:’)||C.code||gen(E.true’:’)||S1.code||gen(‘goto’S.begin);C → E1>E2C.code=E1.code||E2.code||gen(‘if’E1.place’>’E2.place’goto’C.true)||gen(‘goto’C.false)C → E1<E2C.code=E1.code||E2.code||gen(‘if’E1.place’<’E2.place’goto’C.true)||gen(‘goto’C.false)C → E1=E2C.code=E1.code||E2.code||gen(‘if’E1.place’=’E2.place’goto’C.true)||gen(‘goto’C.false)E → E1+TE.place=newtemp;E.code=E1.code||T.code||gen(E.place’:=’E1.place’+’T.place)E → E1-TE.place=newtemp;E.code=E1.code||T.code||gen(E.place’:=’E1.place’-’T.place)E → TE.place=T.place;E.code=T.codeT → FT.place=F.place;T.code=F.codeT → T1*FT.place=newtemp;T.code=T1.code||F.code||gen(T.place’:=’T1.place’*’F.place)T → T1/FT.place=newtemp;T.code=T1.code||F.code||gen(T.place’:=’T1.place’/’F.place)F → (E)F.place=E.place;F.code=E.codeF → idF.place=;F.code=‘‘F → int8F.place=int8.value;F.code=‘‘F → int10F.place=int10.value;F.code=‘‘F → int16F.place=int16.value;F.code=‘‘2.5實(shí)驗(yàn)環(huán)境★PC微機(jī)★DOS操作系統(tǒng)或Windows操作系統(tǒng)★TurboC程序集成環(huán)境或VisualC++程序集成環(huán)境2.6實(shí)驗(yàn)步驟1考慮給定的文法，消除左遞歸，提取左因子。2編制并化簡(jiǎn)語(yǔ)法圖3編制遞歸子程序的算法