1、第五章 語法制導的翻譯趙建華南京大學計算機系2010年3月介紹 使用上下文無關文法引導語言的翻譯 CFG的非終結符號代表了語言的某個構造 程序設計語言的構造由更小的構造組合而成 一個構造的語義可以由小構造的含義綜合而來 比如：表達式x+y的類型由x、y的類型和運算符+決定。 也可以從附近的構造繼承而來 比如：聲明int x;中x的類型由它左邊的類型表達式決定。語法制導定義和語法制導翻譯 語法制導定義： 將文法符號和某些屬性相關聯， 并通過語義規則來描述如何計算屬性的值 EE1+TE.code=E1.code|T.code | + 屬性code代表中綴表達式的逆波蘭表示，規則說明加法表達式的逆波

2、蘭表示由兩個分量的逆波蘭表示并置，然后加上+得到。 語法制導翻譯： 在產生式體中加入語義動作，并在適當的時候執行這些語義動作 EE1+Tprint +;語法制導的定義（SDD） SDD是上下文無關文法和屬性/規則的結合； 屬性和文法符號相關聯，按照需要來確定各個文法符號需要哪些屬性 規則和產生式相關聯 對于文法符號X和屬性a，我們用X.a表示分析樹中的某個標號為X的結點的值。 一個分析樹結點和它的分支對應于一個產生式規則，而對應的語義規則確定了這些結點上的屬性的取值。分析樹和屬性值(1) 假設我們需要知道一個表達式的類型，以及對應代碼將它的值存放在何處，我們就需要兩個屬性：type，place

3、； 產生式規則：EE1+T 語義規則：(假設只有int/float類型） E.type = if (E1.type=T.type) T.type else float E.place = newTempPlace(); /返回一個新的內存位置； 產生式規則：Fid F.type = lookupIDTable(id.lexValue)-type; F.place = lookupIDTable(id.lexValue)-address;分析樹和屬性值(2) a+b*c的語法分析樹以及屬性值EET+TFidTF*Fididid.lexValue=aF.Type = FLOATF.Place =

4、&aT.Type = FLOATT.Place = &aE.Type = FLOATE.Place = &aT.Type = INTT.Place = &tmpF.Type = INTF.Place = &cid.lexValue=cid.lexValue=b假設a,b,c是已經聲明的全局變量，a的類型為FLOAT，b,c的類型為INT中間未標明的T和F的type和address都是INT和&b;E.Type = FLOATE.Place = &tmp2繼承屬性和綜合屬性 綜合屬性(synthesized attribute)：在分析樹結

5、點N上的非終結符號A的屬性值由N對應的產生式所關聯的語義規則來定義。 通過N的子結點或N本身的屬性值來定義 繼承屬性(inherited attribute)：結點N的屬性值由N的父結點所關聯的語義規則來定義。 依賴于N的父結點、N本身和N的兄弟結點上的屬性值。 不允許N的繼承屬性通過N的子結點上的屬性來定義，但是允許N的綜合屬性依賴于N本身的繼承屬性。 終結符號有綜合屬性（由詞法分析獲得），但是沒有繼承屬性。SDD的例子 目標：計算表達式行L的值（屬性val） 計算L的val值需要E的val值 E的val值又依賴于E和T的val值 終結符號digit有綜合屬性lexval。S屬性的SDD 只

6、包含綜合屬性的SDD稱為S屬性的SDD。 每個語義規則都根據產生式體中的屬性值來計算頭部非終結符號的屬性值。 S屬性的SDD可以和LR語法分析器一起實現 棧中的狀態可以附加相應的屬性值 在進行歸約時，按照語義規則計算歸約得到的符號的屬性值。 語義規則不應該有復雜的副作用 要求副作用不影響其它屬性的求值 沒有副作用的SDD稱為屬性文法。語法分析樹上的SDD求值（1） 實踐中很少先構造語法分析樹再進行SDD求值 但在分析樹上求值有助于翻譯方案的可視化，便于理解。 注釋語法分析樹 包含了各個結點的各屬性值的語法分析樹 步驟： 對于任意的輸入串，首先構造出相應的分析樹。 給各個結點（根據其文法符號）加

7、上相應的屬性值 按照語義規則計算這些屬性值即可語法分析樹上的SDD求值（2） 按照分析樹中的分支對應的文法產生式，應用相應的語義規則計算屬性值 計算順序問題： 如果某個結點N的屬性a為f(N1.b1,N2.b2,Nk.bk)，那么我們需要先算出N1.b1,N2.b2,Nk.bk的值。 如果我們可以給各個屬性值排出計算順序，那么這個注釋分析樹就可以計算得到。 S屬性的SDD一定可以按照自底向上的方式求值。 下面的SDD不能計算 ABA.s=B.i；B.i=A.s+1；注釋分析樹的例子適用于自頂向下分析的SDD 前面的表達式文法存在直接左遞歸，因此無法直接用自頂向下方法處理。 消除左遞歸之后，我們

8、無法直接使用屬性val進行處理： 比如規則：TFTT*FT T對應的項中，第一個因子對應于F，而運算符卻在T中。 需要繼承屬性來完成這樣的計算相同表達式的不同文法的比較 輸入串：3*4*5 請觀察左邊的T對應的部分，和右邊的T對應部分 Ti和Ti恰好互補 計算方法：把T之外部分的值繼承給T。T3F*digit:4digit:5T2T1Fdigit:3F*TF*T3FF*digit:3digit:4T2T1digit:5適用于自頂向下分析的SDD 注意：T的屬性inh實際上繼承了相應的*號的左運算分量。3*5的注釋分析樹 請觀察inh屬性是如何傳遞的。消直接左遞歸時語義規則的處理 假設： AA1

9、YA.a = g(A1.a, Y.a) AXA.a = f(X.x) 那么 A XRR.i = f(X.x); A.a = R.s R YR1R1.i = g(R.i, Y.y); R.s=R1.s R R.s = R.i 新文法中R對應的部分和原文法中A對應的部分互補； 對于AXY1Y2Yn；如果R對應于YYiYn；互補的A對應于AY1Yi-1 R.i等于互補的A的A.sSDD的求值順序 在對SDD的求值過程中，如果結點N的屬性a依賴于結點M1的屬性a1，M2的屬性a2，。那么我們必須先計算出Mi的屬性，才能計算N的屬性a。 使用依賴圖來表示計算順序。 顯然，這些值的計算順序應該形成一個偏序

10、關系。如果依賴圖中出現了環，表示屬性值無法計算依賴圖 描述了某棵特定的分析樹上各個屬性實例之間的信息流（計算順序） 從實例a1到實例a2的有向邊表示計算a2時需要a1的值。（必須先計算a2，再計算a1） 對于標號為X的分析樹結點N，和X關聯的每個屬性a都對應依賴圖的一個結點N.a。 結點N對應的產生式的語義規則通過X.c計算了A.b的值，且在分析樹中X和A分別對應于N1和N2，那么從N1.c到N2.b有一條邊。 N1和N2可以等于/不等于N。依賴圖的例子 3*2的注釋分析樹；TFT T.val = T.syn; T.inh = F.val; 邊e1、e2。 可能的計算順序： 1,2,3,4,5

11、,6,7,8.9 1,3,5,2,4,6,7,8,9屬性值的計算順序 各個屬性的值需要按照依賴圖的拓撲順序計算。 如果依賴圖中存在環，則屬性計算無法進行。 給定一個SDD，很難判定是否存在一棵分析樹，其對應的依賴圖包含環。 但是特定類型的SDD一定不包含環，且有固定的排序模式 S屬性的SDD L屬性的SDD 對于這些類型的SDD，我們可以確定屬性的計算順序，且可以把不需要的屬性（及分析樹結點）拋棄以提高效率S屬性的SDD 每個屬性都是綜合屬性 都是根據子構造的屬性計算出父構造的屬性。 在依賴圖中，總是通過子結點的屬性值來計算父結點的屬性值。可以和自頂向下、自底向上的語法分析過程一起計算 自底向

12、上： 在構造分析樹的結點的同時計算相關的屬性（此時其子結點的屬性必然已經計算完畢） 自頂向下： 遞歸子程序法中，在過程A()的最后計算A的屬性（此時A調用的其他過程（對應于子結構）已經調用完畢）在分析樹上計算SDD 按照后序遍歷的順序計算屬性值即可postorder(N)for(從左邊開始，對N的每個子結點C)postorder(c); /遞歸調用返回時，各子結點的屬性計算完畢對N的各個屬性求值； 在LR分析過程中，我們實際上不需要構造分析樹的結點。L屬性的SDD 每個屬性 要么是綜合屬性， 要么是繼承屬性，且產生式AX1X2Xn中計算Xi.a的規則只能使用 A的繼承屬性 Xi左邊的文法符號X

13、j的繼承屬性或綜合屬性。 Xi自身的繼承或綜合屬性。且這些屬性之間的依賴關系不形成環。 特點： 依賴圖的邊： 繼承屬性從左到右，從上到下。 綜合屬性從下到上 在掃描過程中，計算一個屬性值時，和它相關的依賴屬性都已經計算完畢。L屬性SDD和自頂向下語法分析 在遞歸子程序法中實現L屬性 對于每個非終結符號A，其對應的過程的參數為繼承屬性，返回值為綜合屬性 在處理規則AX1X2Xn時， 在調用Xi()之前計算Xi的繼承屬性值，然后以它們為參數調用Xi()； 在產生式對應代碼的最后計算A的綜合屬性 注意：如果所有的文法符號的屬性計算按上面的方式進行，計算順序必然和依賴關系一致。L屬性SDD的例子 非L

14、屬性的例子： ABCA.s=B.b；B.i=f(C.c, A.s)各子程序的類型 int T( ); int T1(int inh); int F( );文法符文法符號號函數名函數名 綜合屬性綜合屬性/類類型型返回類返回類型型繼承屬性繼承屬性/類型類型參數類型參數類型TTval / intint無無TT1syn / int intinh / intintFFval / intint無無考慮一下：如果有多個繼承屬性/多個綜合屬性是如何處理遞歸子程序法中實現L屬性SDDint T( )if(curToken = digit) /digit是first(FT)中唯一的符號/處理規則TFT。intfv

15、al = F( );/F的綜合屬性Value；intt1inh = fval;/計算T的繼承屬性intt1syn = T1(t1inh);/計算得到T的綜合屬性inttval = t1syn;/計算得到T的綜合屬性returntval;/返回T的綜合屬性elseerror();/報錯注意：if(curToken = )肯定不對，因為不是一個符號對規則中某個文法符號X的處理：1、計算X的所有繼承屬性的值2、用這些值調用子函數X；返回值保存在某個變量中。具有受控副作用的語義規則 屬性文法沒有副作用，但增加了描述的復雜度 比如語法分析時如果沒有副作用，標識符表就必須作為屬性傳遞。 可以把標識符表作為

16、全局變量，然后通過副作用函數來添加新標識符； 受控的副作用 不會對屬性求值產生約束，即可以按照任何拓撲順序求值，不會影響最終結果。 或者對求值過程添加簡單的約束。受控副作用的例子 LE nprint(E.val) 通過副作用打印出E的值 總是在最后執行，而且不會影響其它屬性的求值 變量聲明的SDD中的副作用 addType將標識符的類型信息加入到標識符表中。 只要標識符不被重復聲明，標識符的類型信息總是正確的。語法制導翻譯的應用例子 抽象語法樹的構造 基本類型和數組類型的L屬性定義構造抽象語法樹的SDD 抽象語法樹 每個結點代表一個語法結構；對應于一個運算符； 結點的每個子結點代表其子結構；對

17、應于運算分量； 表示這些子結構按照特定方式組成了較大的結構。 可以忽略掉一些標點符號等非本質的東西。 語法樹的表示方法 每個結點用一個對象表示 對象有多個域 葉子結點中只存放詞法值； 內部結點中存放了op值和參數（通常指向其它結點）；構造簡單表達式的語法樹的SDD 屬性E.node指向E對應的語法樹的根結點；表達式語法樹的構造過程 輸入：a-4+c 步驟： p1=new Leaf(id, entry_a) p2=new Leaf(num, 4); p3=new Node(-, p1,p2); p4=new Leaf(id, entry_c); p5=new Node(+, p3,p4);自頂向

18、下方式處理的L屬性定義（1） 在消左遞歸時，按照規則得到此SDD自頂向下方式處理的L屬性定義（2） 對于這個SDD，各屬性值的計算過程實際上和原來S屬性定義中的計算過程一致。 繼承屬性可以把值從一個結構傳遞到另一個并列的結構；也可把值從父結構傳遞到子結構。 抽象語法樹和分析樹不一致時，繼承屬性很有用。類型結構 簡化的類型表達式的語法 TB CBint | float CnumC | 生成類型表達式的SDD類型的含義 類型包括兩個部分：TB C 基本類型B 分量C 分量形如34 表示3X4的二維數組 int 34 數組構造算符array array(3,array(4,int)表示抽象的3X4的

19、二維數組類型表達式的生成過程 輸入：int 23語法制導的翻譯方案 語法制導的翻譯方案（SDT）是在產生式體中嵌入程序片斷（語義動作）的上下文無關文法 SDT的基本實現方法： 建立語法分析樹； 將語義動作看作是虛擬的結點； 從左到右、深度優先地遍歷分析樹，在訪問虛擬結點時執行相應動作 用SDT實現兩類重要的SDD 基本文法是LR的，SDD是S屬性的 基本文法是LL的，SDD是L屬性的例子 語句3*4*5的分析樹如右 DFS可知動作執行順序 A71,A5, A72, A41, A73, A42, A2 注意，一個動作的不同實例所訪問的屬性值屬于不同的結點T3F*digit:4digit:5T2T

20、1Fdigit:3F*EA7A71A72A5A41A42A2A73可在語法分析過程中實現的SDT 實現SDT時，實際上并不會真的構造語法分析樹，而是在分析過程中執行語義動作 即使基礎文法可以應用某種分析技術，仍可能因為動作的緣故導致此技術不可應用 判斷是否可在分析過程中實現 將每個語義動作替換為一個獨有的標記非終結符號；每個標記非終結符號M的產生式為M。 如果新的文法可以由某種方法進行分析，那么這個SDT就可以在這個分析過程中實現。 注意：這個方法沒有考慮變量值的傳遞等要求。判斷SDT可否用特定分析技術實現例子 LE n M1M1 EE+T M2M2 ET M3M3 后綴翻譯方案 文法可以自底

21、向上分析且SDD是S屬性的，比然可以構造出后綴SDT 后綴SDT：所有動作都在產生式最右端的SDT 構造方法： 將每個語義規則看作是一個賦值語義動作 將所有的語義動作放在規則的最右端后綴翻譯方案的例子 實現桌上計算器的后綴SDT注意動作中對屬性值的引用： 我們允許語句引用全局變量，局部變量，文法符號的屬性。 文法符號的屬性只能被賦值一次；后綴SDT的語法分析棧實現 可以在LR語法分析的過程中實現 歸約時執行相應的語義動作 定義用于記錄各文法符號的屬性的union結構 棧中的每個文法符號（或者說狀態）都附帶一個這樣的union類型的值； 在按照產生式AXYZ歸約時，Z的屬性可以在棧頂找到，Y的屬

22、性可以在下一個位置找到，X的屬性可以在再下一個位置找到。分析棧實現的例子 假設語法分析棧存放在一個被稱為stack的記錄數組中，下標top指向棧頂； stacktop是這個棧的棧頂； stacktop-1指向棧頂下一個位置； 如果不同的文法符號有不同的屬性集合，我們可以使用union來保存這些屬性值。 歸約時能夠知道棧頂向下的各個符號分別是什么；因此我們也能夠確定各個union中究竟存放了什么樣的值后綴SDT的棧實現 這個SDT中沒有局部變量，不會產生和局部變量有關的問題注意：stacktop-i和文法符號的對應產生式內部帶有語義動作的SDT 動作左邊的所有符號（以及動作）處理完成后，就立刻執

23、行這個動作 BXaY 自底向上分析時，在X出現在棧頂時執行動作a 自頂向下分析時，在試圖展開Y或者在輸入中檢測到Y的時刻執行a 不是所有的SDT都可以在分析過程中實現 但是后綴SDT以及L屬性對應的SDT可以在分析時完成。 對于一般的SDT，都可以先建立分析樹（語義動作作為虛擬的結點），然后進行前序遍歷并執行動作。消左遞歸時SDT的轉換 如果動作不涉及屬性值，可以把動作當作終結符號進行處理，然后消左遞歸 原始的產生式 EE1+T print(+); ET 轉換后得到 E T R R + T print (+); R R L屬性的SDT 從L屬性到SDT的轉換 將每個語義規則看作是一個賦值語義動

24、作 將賦值語義動作放到相應產生式的適當位置 計算A的繼承屬性的動作插入到產生式體中對應的A的左邊 如果A的繼承屬性之間具有依賴關系，則需要對計算動作進行排序 計算產生式頭的綜合屬性的動作在產生式的最右邊。L屬性的SDT的例子 SDD 繼承屬性： next：語句結束后應該跳轉到的標號 true、false：C為真/假時應該跳轉到的標號 綜合屬性code表示代碼轉換 語義動作 (a) L1=new( )和L2=new( )：計算臨時值 (b) C.false = S.next; C.true = L2：計算C的繼承屬性 (c) S1.next = L1：計算S1的繼承屬性 (d) S.code=

25、：計算S的綜合屬型 根據放置語義動作的規則得到如下SDT b在C之前；c在S1之前；d在最右端 a可以放在最前面L屬性的SDD的實現 使用遞歸下降的語法分析器 每個非終結符號對應一個函數 函數的參數接受繼承屬性 返回值包含了綜合屬性 在函數體中 首先選擇適當的產生式 使用局部變量來保存屬性 對于產生式體中的終結符號，讀入符號并獲取其（經詞法分析得到的）綜合屬性 對于非終結符號，使用適當的方式調用相應函數，并記錄返回值。遞歸下降法實現L屬性SDD的例子邊掃描邊生成屬性（1） 當屬性值的體積很大時，對屬性值進行運算的效率很低 比如code（代碼）可能是一個上百K的串，對其進行并置等運算會比較低效

26、可以逐步生成屬性的各個部分，并增量式添加到最終的屬性值中 條件： 存在一個主屬性，且主屬性是綜合屬性 在各產生式中，主屬性是通過產生式體中各個非終結符號的主屬性連接（并置）得到的。同時還會連接一些其它的元素。 各非終結符號的主屬性的連接順序和它在產生式體中的順序相同邊掃描邊生成屬性（2） 基本思想 只需要在適當的時候“發出”非主屬性的元素，即把這些元素拼接到適當的地方 舉例說明 假設我們在掃描一個非終結符號對應的語法結構時，調用相應的函數，并生成主屬性； S while (C) S1 S.code = Label | L1 |C.code |Label | L2 | S1.code 處理S時，先調用C，再調用S（對應于S1） 如果各個函數把主屬性打印出來，我們處理while語句時，只需要先打印Label L1，再調用C（打印了C的代碼），再打印Label L2，再調用S（打印S1的代碼） 對于這個規則而言，只需要打印Label L1和Label L2。