編譯原理第五章

第5章

語(yǔ)法制導(dǎo)的翻譯主講：閆健恩計(jì)算機(jī)網(wǎng)絡(luò)與信息安全中心Email：yanjianen(@)1本章重點(diǎn)語(yǔ)法制導(dǎo)定義S屬性定義L屬性定義語(yǔ)法制導(dǎo)的翻譯方案設(shè)計(jì)語(yǔ)法制導(dǎo)定義和翻譯方案的關(guān)系自底向上實(shí)現(xiàn)L屬性的SDD2語(yǔ)法制導(dǎo)的翻譯5.1語(yǔ)法制導(dǎo)定義5.2SDD的求值順序5.3語(yǔ)法制導(dǎo)的翻譯方案3第五章語(yǔ)法制導(dǎo)的翻譯翻譯的任務(wù)首先是語(yǔ)義分析和正確性檢查，若正確，則翻譯成中間代碼或目標(biāo)代碼?；舅枷胝Z(yǔ)法結(jié)構(gòu)具有規(guī)定的語(yǔ)義根據(jù)翻譯的需要設(shè)置文法符號(hào)的屬性，以描述語(yǔ)法結(jié)構(gòu)的語(yǔ)義。例如，一個(gè)變量的屬性有類(lèi)型，層次，存儲(chǔ)地址等。表達(dá)式的屬性有類(lèi)型，值等。屬性值的計(jì)算和產(chǎn)生式相聯(lián)系。隨著語(yǔ)法分析的進(jìn)行，執(zhí)行屬性值的計(jì)算，完成語(yǔ)義分析和翻譯的任務(wù)。45.1語(yǔ)法制導(dǎo)定義1.語(yǔ)義分析的任務(wù)語(yǔ)義檢查例：類(lèi)型、運(yùn)算、維數(shù)、越界語(yǔ)義處理例：變量的存儲(chǔ)分配例：表達(dá)式的求值例：語(yǔ)句的翻譯（中間代碼的生成）總目標(biāo)：生成等價(jià)的中間代碼52.代碼結(jié)構(gòu)計(jì)算學(xué)科：對(duì)信息（數(shù)據(jù)表示）描述和變換算法的系統(tǒng)研究變換：源、目標(biāo)以及源與目標(biāo)的對(duì)應(yīng)關(guān)系語(yǔ)句的代碼結(jié)構(gòu)語(yǔ)句分類(lèi)：說(shuō)明語(yǔ)句——符號(hào)表的查填可執(zhí)行語(yǔ)句——指令代碼5.1語(yǔ)法制導(dǎo)定義63.典型處理方法（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適宜在完成歸約的時(shí)候進(jìn)行5.1語(yǔ)法制導(dǎo)定義73.典型處理方法（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ǔ)義——可以看成是相應(yīng)文法符號(hào)的屬性適宜在進(jìn)行推導(dǎo)時(shí)完成5.1語(yǔ)法制導(dǎo)定義8語(yǔ)義翻譯的流程輸入符號(hào)串

分析樹(shù)依賴(lài)圖語(yǔ)義規(guī)則的計(jì)算實(shí)際上，編譯中語(yǔ)義翻譯的實(shí)現(xiàn)并不是按圖中的流程處理的；而是隨語(yǔ)法分析的進(jìn)展，識(shí)別出一個(gè)語(yǔ)法結(jié)構(gòu)，就對(duì)它的語(yǔ)義進(jìn)行分析和翻譯。94.什么是語(yǔ)法制導(dǎo)定義（SDD）上下文無(wú)關(guān)文法和屬性/規(guī)則的結(jié)合；屬性和文法符號(hào)相關(guān)聯(lián)規(guī)則和產(chǎn)生式相關(guān)聯(lián)根據(jù)需要，將文法符號(hào)和某些屬性相關(guān)聯(lián)，并通過(guò)語(yǔ)義規(guī)則來(lái)描述如何計(jì)算屬性的值E→E1+T E.code=E1.code||T.code||‘+’code表示了我們關(guān)心的表達(dá)式的逆波蘭表示，規(guī)則說(shuō)明加法表達(dá)式的逆波蘭表示由兩個(gè)分量的逆波蘭表示并置，然后加上‘+’得到。5.1語(yǔ)法制導(dǎo)定義105.語(yǔ)法制導(dǎo)的翻譯

在產(chǎn)生式體中加入語(yǔ)義動(dòng)作，并在適當(dāng)?shù)臅r(shí)候執(zhí)行這些語(yǔ)義動(dòng)作E→E1+T {print‘+’;}5.1語(yǔ)法制導(dǎo)定義11綜合屬性(synthesizedattribute)：分析樹(shù)結(jié)點(diǎn)N上的非終結(jié)符號(hào)A的屬性值由N的產(chǎn)生式所關(guān)聯(lián)的語(yǔ)義規(guī)則來(lái)定義，又稱(chēng)為S-屬性定義。必然通過(guò)N的子結(jié)點(diǎn)或N本身的屬性值來(lái)定義繼承屬性(inheritedattribute)：分析樹(shù)結(jié)點(diǎn)N的屬性值由N的父結(jié)點(diǎn)所關(guān)聯(lián)的語(yǔ)義規(guī)則來(lái)定義。又稱(chēng)為L(zhǎng)-屬性定義。依賴(lài)于N的父結(jié)點(diǎn)、N本身和N的兄弟結(jié)點(diǎn)上的屬性值。5.1.1繼承屬性和綜合屬性12不允許N的繼承屬性通過(guò)N的子結(jié)點(diǎn)上的屬性來(lái)定義，但是允許N的綜合屬性依賴(lài)于N本身的繼承屬性。終結(jié)符號(hào)有綜合屬性（由詞法分析獲得），但是沒(méi)有繼承屬性。5.1.1繼承屬性和綜合屬性13語(yǔ)法制導(dǎo)定義（SDD）的例子目標(biāo)：計(jì)算表達(dá)式L的值（屬性val）計(jì)算L的val值需要E的val值E的val值又依賴(lài)于E和T的val值…終結(jié)符號(hào)digit有綜合屬性lexval。14注釋語(yǔ)法分析樹(shù)在分析樹(shù)上求值有助于翻譯方案的可視化，便于理解。包含了各個(gè)結(jié)點(diǎn)的各屬性值的語(yǔ)法分析樹(shù)5.1.2翻譯方案的可視化15注釋語(yǔ)法分析樹(shù)構(gòu)造注釋語(yǔ)法分析樹(shù)步驟：對(duì)于任意的輸入串，首先構(gòu)造出相應(yīng)的分析樹(shù)。根據(jù)結(jié)點(diǎn)上的文法符號(hào)，每個(gè)結(jié)點(diǎn)都有相應(yīng)的屬性值按照分析樹(shù)中的分支對(duì)應(yīng)的文法產(chǎn)生式，應(yīng)用相應(yīng)的語(yǔ)義規(guī)則計(jì)算屬性值。如果某個(gè)規(guī)則N的屬性a為f(N1.b1,N2.b2,……,Nk.bk)，那么我們需要先算N1.b1,N2.b2,……,Nk.bk的值。16如果可以給各個(gè)屬性值排出順序，那么這個(gè)注釋分析樹(shù)就可以計(jì)算得到。S屬性的SDD一定可以按照自底向上的方式求值。但是下面的SDD不能計(jì)算A→B A.s=B.i；B.i=A.s+1；5.1.2翻譯方案的可視化17digitlexval=3Fval=3Tval=3digitlexval=5Fval=5Tval=15*Eval=15+digitlexval=4Fval=4Tval=4Eval=19Lval=19n例5.2輸入：3*5+4n的注釋語(yǔ)法分析樹(shù)18適用于自頂向下分析的SDD前面的表達(dá)式文法存在直接左遞歸，因此無(wú)法直接用自頂向下方法處理。消除左遞歸之后，無(wú)法直接使用屬性val進(jìn)行處理：比如規(guī)則：T→FT’T’→*FT’T對(duì)應(yīng)的項(xiàng)中，第一個(gè)因子對(duì)應(yīng)于F，而運(yùn)算符在T’中。19相同表達(dá)式的不同文法的比較輸入串：3*4*5請(qǐng)觀(guān)察左邊的T對(duì)應(yīng)的部分，和右邊的T’對(duì)應(yīng)部分計(jì)算方法：把T’之外的部分的值繼承給T’。TF*digit:4digit:5TTFdigit:3F*TF*εT’TFF*digit:3digit:4T’T’digit:520適用于自頂向下分析的SDD注意：T’的屬性inh實(shí)際上是繼承了相應(yīng)的*號(hào)的左運(yùn)算分量。21例5.33*5的注釋分析樹(shù)請(qǐng)觀(guān)察inh屬性是如何傳遞的。225.2SDD的求值順序在對(duì)SDD的求值過(guò)程中，如果結(jié)點(diǎn)N的屬性a依賴(lài)于結(jié)點(diǎn)M1的屬性a1，M2的屬性a2，…。那么必須先計(jì)算出Mi的屬性，才能計(jì)算N的屬性a。顯然，這些值的計(jì)算順序應(yīng)該形成一個(gè)偏序關(guān)系。235.2.1依賴(lài)圖依賴(lài)圖描述了某棵特定的分析樹(shù)上的各個(gè)屬性實(shí)例之間的信息流（計(jì)算順序）從實(shí)例a1到實(shí)例a2的有向邊表示計(jì)算a2時(shí)需要a1的值。（必須先計(jì)算a2，再計(jì)算a1）24依賴(lài)圖的構(gòu)造方法for分析樹(shù)中的每個(gè)結(jié)點(diǎn)ndofor與結(jié)點(diǎn)n對(duì)應(yīng)的文法符號(hào)的每個(gè)屬性ado在依賴(lài)圖中為a構(gòu)造一個(gè)結(jié)點(diǎn)；for分析樹(shù)的每個(gè)結(jié)點(diǎn)ndofor結(jié)點(diǎn)n所用產(chǎn)生式對(duì)應(yīng)的每條語(yǔ)義規(guī)則b:＝f（c1，c2，…，ck)dofori:=1tokdo

從結(jié)點(diǎn)ci到結(jié)點(diǎn)b構(gòu)造一條有向邊；5.2.1依賴(lài)圖25例5.5依賴(lài)圖的例子3*2的注釋分析樹(shù)；T→FT’{T.val=T’.syn;

T’.inh=F.val;}邊e1、e2。可能的計(jì)算順序：1,2,3,4,5,6,7,8.91,3,5,2,4,6,7,8,926屬性值的計(jì)算順序可以按照依賴(lài)圖的拓?fù)渑判蛴?jì)算各個(gè)屬性的值。如果圖中存在環(huán)，那么這個(gè)計(jì)算過(guò)程就無(wú)法進(jìn)行。給定一個(gè)SDD，很難判定是否存在一棵分析樹(shù)，其對(duì)應(yīng)的依賴(lài)圖包含環(huán)。但是特定類(lèi)型的SDD一定不包含環(huán)，且有固定的排序模式。S屬性的SDDL屬性的SDD275.2.3S屬性的SDD每個(gè)屬性都是綜合屬性都是根據(jù)子構(gòu)造的屬性計(jì)算整個(gè)構(gòu)造的屬性。在依賴(lài)圖中，總是通過(guò)子結(jié)點(diǎn)的屬性值來(lái)計(jì)算父結(jié)點(diǎn)的屬性值?？梢院妥皂斚蛳?、自底向上的語(yǔ)法分析過(guò)程一起計(jì)算自底向上：在構(gòu)造分析樹(shù)的子結(jié)點(diǎn)的同時(shí)計(jì)算相關(guān)的屬性自頂向下：遞歸子程序法中，在過(guò)程A()的最后計(jì)算A的屬性28在分析樹(shù)上計(jì)算SDD按照后序遍歷的順序計(jì)算屬性值即可postorder(N){ for(從左邊開(kāi)始，對(duì)N的每個(gè)子結(jié)點(diǎn)C)

postorder(c);

對(duì)N的各個(gè)屬性求值；}在LR分析過(guò)程中，我們實(shí)際上不需要構(gòu)造分析樹(shù)的結(jié)點(diǎn)。295.2.4L屬性的SDD每個(gè)屬性要么是綜合屬性，要么是繼承屬性，且產(chǎn)生式A→X1X2…Xn中計(jì)算Xi.a的規(guī)則只能使用A的繼承屬性Xi左邊的文法符號(hào)Xj的繼承屬性或綜合屬性。Xi自身的繼承或綜合屬性。且這些屬性的依賴(lài)關(guān)系不形成環(huán)。特點(diǎn)：依賴(lài)圖的邊總是從左到右，從下到上。在掃描過(guò)程中，計(jì)算一個(gè)屬性值時(shí)相關(guān)的依賴(lài)屬性都已經(jīng)計(jì)算完成了。30帶有繼承屬性L(fǎng).inh的語(yǔ)法制導(dǎo)定義

產(chǎn)生式語(yǔ)義規(guī)則

DTLLinh:=TtypeTintTtype:=integerTfloatTtype:=floatLL1,idL1

inh:=Linh

addtype(id

entry,Linh)Lid

addtype(id

entry,Linh)315.2.5具有受控副作用的語(yǔ)義規(guī)則屬性文法沒(méi)有副作用，但是會(huì)增加描述的復(fù)雜度比如語(yǔ)法分析時(shí)如果沒(méi)有副作用，符號(hào)表就必須作為屬性傳遞。可以把符號(hào)表作為全局變量，然后通過(guò)副作用函數(shù)來(lái)添加新標(biāo)識(shí)符；受控的副作用不會(huì)對(duì)屬性求值產(chǎn)生約束，即可以按照任何拓?fù)鋵傩郧笾担粫?huì)影響最終結(jié)果。添加部分簡(jiǎn)單的約束。32受控副作用的例子L→En

print(E.val)通過(guò)副作用打印出E的值總是在最后執(zhí)行，且不會(huì)影響其它屬性的求值變量聲明的SDD中的副作用addType將標(biāo)識(shí)符的類(lèi)型信息加入到標(biāo)識(shí)符表中。只要標(biāo)識(shí)符不被重復(fù)聲明，標(biāo)識(shí)符的類(lèi)型信息總是正確的。335.3語(yǔ)法制導(dǎo)的翻譯方案語(yǔ)法制導(dǎo)的翻譯方案（SDT）是在產(chǎn)生式體中嵌入程序片斷（語(yǔ)義動(dòng)作）的上下文無(wú)關(guān)文法SDT的基本實(shí)現(xiàn)方法：建立語(yǔ)法分析樹(shù)；從左到右、深度優(yōu)先地執(zhí)行這些動(dòng)作用SDT實(shí)現(xiàn)兩類(lèi)重要的SDD基本文法是LR的，SDD是S屬性的基本文法是LL的，SDD是L屬性的34可在語(yǔ)法分析過(guò)程中實(shí)現(xiàn)的SDT實(shí)際實(shí)現(xiàn)SDT時(shí)，并不會(huì)真的構(gòu)造語(yǔ)法分析樹(shù)，而是在分析過(guò)程中執(zhí)行語(yǔ)義動(dòng)作判斷是否可在分析過(guò)程中實(shí)現(xiàn)將每個(gè)語(yǔ)義動(dòng)作替換為一個(gè)獨(dú)有的標(biāo)記非終結(jié)符號(hào)；每個(gè)標(biāo)記非終結(jié)符號(hào)M的產(chǎn)生式為M→ε。如果新的文法可以由某種方法進(jìn)行分析，那么這個(gè)SDT就可以在這個(gè)分析過(guò)程中實(shí)現(xiàn)。注意：這個(gè)斷言沒(méi)有考慮變量值的傳遞等要求。355.3.1后綴翻譯方案文法可以自底向上分析且SDD是S屬性的可以構(gòu)造出SDT，且所有的動(dòng)作都放在產(chǎn)生式最后；分析過(guò)程中在按照這個(gè)產(chǎn)生式歸約時(shí)執(zhí)行這個(gè)動(dòng)作；計(jì)算得到的屬性值放在棧中；所有動(dòng)作都在產(chǎn)生式最右端的SDT稱(chēng)為后綴翻譯方案361后綴翻譯方案的例子實(shí)現(xiàn)桌上計(jì)算機(jī)的后綴SDT372后綴SDT的語(yǔ)法分析棧實(shí)現(xiàn)可以在LR語(yǔ)法分析的過(guò)程中實(shí)現(xiàn)歸約時(shí)執(zhí)行相應(yīng)的語(yǔ)義動(dòng)作定義可以記錄各個(gè)文法符號(hào)的屬性的union結(jié)構(gòu)棧中的每個(gè)文法符號(hào)（或者狀態(tài)）的附帶一個(gè)這樣的結(jié)構(gòu)的值；在按照產(chǎn)生式A→XYZ歸約時(shí)，Z的屬性可以在棧頂找到，Y的屬性可以在下一個(gè)位置找到，X的屬性可以在再下一個(gè)位置找到。38例5.15分析棧實(shí)現(xiàn)的例子假設(shè)語(yǔ)法分析棧存放在一個(gè)被稱(chēng)為stack的記錄數(shù)組中，下標(biāo)top指向棧頂；stack[top]指向這個(gè)棧的棧頂；stack[top-1]指向棧頂下一個(gè)位置；如果不同的文法符號(hào)有不同的屬性集合，我們可以使用union來(lái)保存這些屬性值。（歸約時(shí)，我們知道棧頂向下的各個(gè)符號(hào)分別是什么）39這個(gè)SDT中沒(méi)有局部變量，不會(huì)產(chǎn)生和局部變量有關(guān)的問(wèn)題403產(chǎn)生式內(nèi)部帶有語(yǔ)義動(dòng)作的SDT一個(gè)動(dòng)作左部的所有符號(hào)（以及動(dòng)作）處理完成后，就立刻執(zhí)行這個(gè)動(dòng)作B→X{a}Y自底向上分析時(shí)，a在X出現(xiàn)在棧頂時(shí)執(zhí)行自頂向下分析時(shí)，在試圖展開(kāi)Y或者在輸入中檢測(cè)到Y(jié)時(shí)執(zhí)行a不是所有的SDT都可以在分析過(guò)程中實(shí)現(xiàn)但是后綴SDT以及實(shí)現(xiàn)L屬性的SDT可以在分析時(shí)完成。對(duì)于所有的SDT，都可以先建立分析樹(shù)（語(yǔ)義動(dòng)作作為虛擬的結(jié)點(diǎn)），然后進(jìn)行前序遍歷并執(zhí)行動(dòng)作。414L屬性定義的SDTL屬性SDD轉(zhuǎn)換為SDT的規(guī)則：將計(jì)算非終結(jié)符號(hào)A繼承屬性的動(dòng)作放在產(chǎn)生式中緊靠A之前，如果A有多個(gè)屬性，要注意屬性計(jì)算的順序；將計(jì)算產(chǎn)生式頭的綜合屬性的動(dòng)作放在產(chǎn)生式的最右端。42例5.19L屬性的SDT的例子繼承屬性：Next：語(yǔ)句結(jié)束后應(yīng)該跳轉(zhuǎn)到的標(biāo)號(hào)true、false：C為真/假時(shí)應(yīng)該跳轉(zhuǎn)到的標(biāo)號(hào)綜合屬性code表示代碼435L屬性的SDD的實(shí)現(xiàn)使用遞歸下降的語(yǔ)法分析器每個(gè)非終結(jié)符號(hào)對(duì)應(yīng)一個(gè)函數(shù)函數(shù)的參數(shù)接受繼承屬性返回值包含了綜合屬性在函數(shù)體中，首先選擇適當(dāng)?shù)漠a(chǎn)生式使用局部變量來(lái)保存屬性對(duì)于產(chǎn)生式體中的終結(jié)符號(hào)，讀入符號(hào)并獲取其（經(jīng)詞法分析得到的）綜合屬性對(duì)于非終結(jié)符號(hào)，使用適當(dāng)?shù)姆绞秸{(diào)用相應(yīng)函數(shù)，并記錄返回值。446L屬性的自底向上實(shí)現(xiàn)（1）以L(fǎng)L文法為基礎(chǔ)的L屬性SDD可以在LR語(yǔ)法分析過(guò)程中實(shí)現(xiàn)方法：首先構(gòu)造出L屬性SDD的SDT，即在非終結(jié)符號(hào)前計(jì)算其繼承屬性若有產(chǎn)生式A→α{a