第5章

語法制導的翻譯主講：閆健恩計算機網絡與信息安全中心Email：yanjianen(@)1本章重點語法制導定義S屬性定義L屬性定義語法制導的翻譯方案設計語法制導定義和翻譯方案的關系自底向上實現L屬性的SDD2語法制導的翻譯5.1語法制導定義5.2SDD的求值順序5.3語法制導的翻譯方案3第五章語法制導的翻譯翻譯的任務首先是語義分析和正確性檢查，若正確，則翻譯成中間代碼或目標代碼。基本思想語法結構具有規定的語義根據翻譯的需要設置文法符號的屬性，以描述語法結構的語義。例如，一個變量的屬性有類型，層次，存儲地址等。表達式的屬性有類型，值等。屬性值的計算和產生式相聯系。隨著語法分析的進行，執行屬性值的計算，完成語義分析和翻譯的任務。45.1語法制導定義1.語義分析的任務語義檢查例：類型、運算、維數、越界語義處理例：變量的存儲分配例：表達式的求值例：語句的翻譯（中間代碼的生成）總目標：生成等價的中間代碼52.代碼結構計算學科：對信息（數據表示）描述和變換算法的系統研究變換：源、目標以及源與目標的對應關系語句的代碼結構語句分類：說明語句——符號表的查填可執行語句——指令代碼5.1語法制導定義63.典型處理方法（1）對應每一個產生式編制一個語義子程序，當一個產生式獲得匹配時，調用相應的語義子程序實現語義檢查與翻譯E→E1+T E.val:=E1.val+T.valT→T1*F T.val:=T1.val*F.valF→id F.val:=id.val適宜在完成歸約的時候進行5.1語法制導定義73.典型處理方法（2）在產生式的右部的適當位置，插入相應的語義動作，按照分析的進程，執行遇到的語義動作D→T{L.in:=T.type}LT→int{T.type:=integer}T→real{T.type:=real}L→{L1.in:=L.in}L1,id{…}語義——可以看成是相應文法符號的屬性適宜在進行推導時完成5.1語法制導定義8語義翻譯的流程輸入符號串

分析樹依賴圖語義規則的計算實際上，編譯中語義翻譯的實現并不是按圖中的流程處理的；而是隨語法分析的進展，識別出一個語法結構，就對它的語義進行分析和翻譯。94.什么是語法制導定義（SDD）上下文無關文法和屬性/規則的結合；屬性和文法符號相關聯規則和產生式相關聯根據需要，將文法符號和某些屬性相關聯，并通過語義規則來描述如何計算屬性的值E→E1+T E.code=E1.code||T.code||‘+’code表示了我們關心的表達式的逆波蘭表示，規則說明加法表達式的逆波蘭表示由兩個分量的逆波蘭表示并置，然后加上‘+’得到。5.1語法制導定義105.語法制導的翻譯

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

從結點ci到結點b構造一條有向邊；5.2.1依賴圖25例5.5依賴圖的例子3*2的注釋分析樹；T→FT’{T.val=T’.syn;

T’.inh=F.val;}邊e1、e2。可能的計算順序：1,2,3,4,5,6,7,8.91,3,5,2,4,6,7,8,926屬性值的計算順序可以按照依賴圖的拓撲排序計算各個屬性的值。如果圖中存在環，那么這個計算過程就無法進行。給定一個SDD，很難判定是否存在一棵分析樹，其對應的依賴圖包含環。但是特定類型的SDD一定不包含環，且有固定的排序模式。S屬性的SDDL屬性的SDD275.2.3S屬性的SDD每個屬性都是綜合屬性都是根據子構造的屬性計算整個構造的屬性。在依賴圖中，總是通過子結點的屬性值來計算父結點的屬性值。可以和自頂向下、自底向上的語法分析過程一起計算自底向上：在構造分析樹的子結點的同時計算相關的屬性自頂向下：遞歸子程序法中，在過程A()的最后計算A的屬性28在分析樹上計算SDD按照后序遍歷的順序計算屬性值即可postorder(N){ for(從左邊開始，對N的每個子結點C)

postorder(c);

對N的各個屬性求值；}在LR分析過程中，我們實際上不需要構造分析樹的結點。295.2.4L屬性的SDD每個屬性要么是綜合屬性，要么是繼承屬性，且產生式A→X1X2…Xn中計算Xi.a的規則只能使用A的繼承屬性Xi左邊的文法符號Xj的繼承屬性或綜合屬性。Xi自身的繼承或綜合屬性。且這些屬性的依賴關系不形成環。特點：依賴圖的邊總是從左到右，從下到上。在掃描過程中，計算一個屬性值時相關的依賴屬性都已經計算完成了。30帶有繼承屬性L.inh的語法制導定義

產生式語義規則

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

inh:=Linh

addtype(id

entry,Linh)Lid

addtype(id

entry,Linh)315.2.5具有受控副作用的語義規則屬性文法沒有副作用，但是會增加描述的復雜度比如語法分析時如果沒有副作用，符號表就必須作為屬性傳遞。可以把符號表作為全局變量，然后通過副作用函數來添加新標識符；受控的副作用不會對屬性求值產生約束，即可以按照任何拓撲屬性求值，不會影響最終結果。添加部分簡單的約束。32受控副作用的例子L→En

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