語法制導的三地址代碼生成器

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