语法制导的翻译
繼詞法分析和文法分析之后，本文將介紹使用上下文無關文法來引導對語言的翻譯。
SDD
語法制導定義（Syntax-Directed Definition，SDD）是一個上下文無關文法和屬性及語義規則的結合。屬性和文法符號相關聯，語義規則和產生式相關聯，文法符號X的屬性a表示為X.a。
非終結符號可以有兩種屬性：
- 綜合屬性：如果語法分析樹上的結點N的某個屬性a只能通過N的子結點和N本身的屬性值來定義，那么屬性a是結點N的一個綜合屬性；
- 繼承屬性：如果語法分析樹上的結點N的某個屬性b只能通過N的父結點、N本身和N的兄弟結點的屬性值來定義，那么屬性a是結點N的一個繼承屬性。
終結符號可以有綜合屬性，但不能有繼承屬性，終結符號的屬性是由詞法分析器提供的詞法值。
綜合屬性
如果語法分析樹中的結點N的某個屬性a只能通過N的子結點或N本身的屬性值來定義，那么屬性a是結點N的一個綜合屬性。
對表達式文法G：
E → E+T | TT → T*F | FF → (E) | id它對應的SDD如下：
其中，屬性val是文法符號的數值，屬性lexval是由詞法分析器返回的數值。為id1*id2+id3構建語法分析樹，其中，id1、id2、id3的lexval屬性分別為3、4、5：
在這棵語法分析樹中，所有結點的屬性都被顯示了出來，這樣的語法分析樹也稱為注釋語法分析樹。
繼承屬性
如果語法分析樹上的結點N的某個屬性b只能通過N的父結點、N本身和N的兄弟結點的屬性值來定義，那么屬性a是結點N的一個繼承屬性。
考慮上一小節中的表達式文法的非左遞歸形式G’：
E → TE'E'→ +TE' | εT → FT'T'→ *FT' | εF → (E) | id它對應的SDD如下：
其中，屬性val是文法符號的數值，屬性lexval是由詞法分析器返回的數值，屬性inh是一個繼承屬性，屬性syn是一個綜合屬性。為id1*id2+id3構建語法分析樹，其中，id1、id2、id3的lexval屬性分別為3、4、5：
在這棵語法分析樹中，屬性inh“向下地傳遞參數”，屬性syn“向上地返回結果”，關于繼承屬性和綜合屬性的求值順序將在下一小節介紹。
SDD的求值順序
和終結符號的綜合屬性直接由詞法分析器給出不同，非終結符號的綜合屬性和繼承屬性都或多或少地依賴于其他屬性，因此確定一棵注釋語法分析樹中屬性的求值順序是十分重要的，依賴圖可以幫助我們完成這個工作。
依賴圖描述了某個語法分析樹中的屬性實例之間的信息流，從一個屬性實例到另一個屬性實例的邊表示計算第二個屬性實例需要用到第一個屬性實例的值。具體地講，一個依賴圖包括：
- 屬性結點：對于語法分析樹中的每個結點N，N的每個屬性在依賴圖中都有一個結點；
- 綜合屬性的邊：如果和產生式p關聯的語義規則通過X.a的值定義了綜合屬性Y.b的值，那么在依賴圖中有一條從X.a到Y.b的邊；
- 繼承屬性的邊：如果和產生式p關聯的語義規則通過X.a的值定義了繼承屬性Y.b的值，那么在依賴圖中有一條從X.a到Y.b的邊。
得到依賴圖后，如果這個依賴圖中沒有環，那么這個依賴圖至少存在一個拓撲排序。假設依賴圖的結點集合為N，邊集合為E，計算此依賴圖的拓撲排序的步驟為：
- 構建一個序列A，A的長度為len(N)，將i初始化為0；
- 從N中選出一個入度為0的結點n，從N中刪除n且從E中刪除所有以n為起點的邊，將A[i]設為n，同時將i加1；
- 如果N不為空，重復步驟2，否則排序結束，得到拓撲序列A[0]、A[1]、…、A[len(N)-1]。
考慮圖1的注釋語法分析樹，它的依賴圖如下，結點前的標號是拓撲排序后的結果：
考慮圖2的注釋語法分析樹，它的依賴圖如下，結點前的標號是拓撲排序后的結果：
到這里，我們已經知道了如何借助依賴圖確定一棵注釋語法分析樹中屬性的求值順序。但是，不是所有的注釋語法分析樹都能通過依賴圖找到一個拓撲排序，如果依賴圖中存在環，那么這個依賴圖沒有拓撲排序。如果我們能小心地定義SDD中的語義規則使得其依賴圖中沒有環，那么我們一定能夠確定此SDD中屬性的求值順序，下面介紹的S屬性的SDD和L屬性的SDD一定能確定屬性的求值順序。
S屬性的SDD
如果一個SDD的每個屬性都是綜合屬性，那么這個SDD是一個S屬性的SDD。
對于一個S屬性的SDD，可以按照語法分析樹結點的任何自底向上順序來計算它的各個屬性值。S屬性的SDD可以在自底向上的語法分析過程中實現。
L屬性的SDD
L屬性的SDD的思想是在一個產生式體所關聯的各個屬性之間，依賴圖的邊總是從左到右，而不能從右到左。也就是說，每個屬性必須滿足如下條件：
- 要么是一個綜合屬性；
- 要么是一個繼承屬性，但是它的語義規則有這些限制：假設有產生式A→X1X2…Xn和繼承屬性Xi.a，Xi.a的計算規則只能使用A的繼承屬性以及Xj（1<=j<=i）的綜合屬性或繼承屬性，并且Xi的全部屬性組成的依賴圖中不存在環。
L屬性的SDD可以在自頂向下的語法分析過程中實現。
SDT
語法制導的翻譯方案（Syntax-Directed Translation scheme，SDT）是SDD的一種補充，它是在其產生式體中嵌入程序片段的一個上下文無關文法，這些程序片段稱為語義動作，它們可以出現在產生式體中的任何地方。通常情況下，語義動作的兩邊要加上花括號，如果花括號作為文法符號出現，則要給它們加上引號。
實現SDT的通用方法
語義動作可以放在產生式體中的任何位置，當一個語義動作左邊的所有符號都被處理完后該動作立即執行。更具體的，對產生式A→X{a}Y，有：
- 如果語法分析過程是自底向上的，那么當X出現在語法分析棧的棧頂時立即執行動作a；
- 如果語法分析過程是自頂向下的，那么當試圖展開Y（Y是非終結符號）或在輸入中檢測到Y（Y是終結符號）之前執行動作a。
通用的SDT實現方法如下：
- 忽略語義動作，對輸入進行語法分析，并產生一棵語法分析樹；
- 然后檢查每個內部結點N，假設它的產生式是A→α。將α中的各個動作當作N的附加子結點加入，使得N的子結點從左到右和α中的符號及動作完全一致；
- 對這棵語法分析樹進行前序遍歷，并且當訪問到一個以某個動作為標號的結點時立即執行此動作。
對于表1顯示的SDD，把它轉換成SDT：
注意到，此SDT和相應的SDD相比，只有前兩個產生式的語義動作和原來的語義規則不同。由于這兩個產生式的產生式頭已經是開始符號，因此相應的語義動作需要把實現結果輸出。由此SDT構建的嵌入了動作的語法分析樹如下：
對上面的語法分析樹進行前序遍歷，每遇到一個動作就立即執行它，遍歷完成后就實現了此SDT。
在語法分析過程中實現SDT
可以在語法分析過程中實現的SDT包括后綴SDT和L屬性定義的SDT，后綴SDT通常在自底向上的語法分析過程中實現，L屬性定義的SDT通常在自頂向下的語法分析過程中實現。注意，不是所有的SDT都能在語法分析過程中實現。
后綴SDT
如果一個SDD的基礎文法是LR文法并且此SDD是S屬性定義的，那么我們可以構造這樣一個SDT，其中的每個動作都放在產生式的最后，并且在按照這個產生式將產生式體歸約為產生式頭的時候執行這個動作。像這樣所有動作都在產生式體最右端的SDT也稱為后綴翻譯方案（后綴SDT）。
將一個S屬性定義的且基礎文法為LR文法的SDD轉換為一個SDT的規則如下：
- 將計算一個產生式頭的綜合屬性的動作放置在這個產生式體的最右端。
注意到，由于表1中的SDD是S屬性定義的且其基礎文法G是LR文法，因此可以把它轉換成后綴SDT，表3中的SDT就是此SDD的一個轉換形式。下面我們進一步改進表3中的SDT，使其能夠在語法分析過程中實現：
表4中的stack表示LR語法分析棧，top指向棧頂。為了幫助讀者理解這個SDT中的語義動作，以產生式F→(E)為例，考慮將(E)歸約成F的過程，如圖6所示：
圖6顯示了把(E)歸約成F的LR語法分析過程。圖6(a)是即將把(E)歸約成F的語法分析棧快照，此時有stack[top]=")"，stack[top-1]="E"，stack[top-2]="("。執行的歸約動作是連續3次出棧操作（將”)”、”E”、”(“依次彈出棧頂，如圖6(b)）和1次入棧操作（將”F”壓入棧頂，如圖6(c)）。注意到，(c)中的top相當于(a)中的top-2，也就是說，F實際上出現在(a)中的stack[top-2]處；另外，由于E.val將被賦值給F.val，并且E出現在(a)中的stack[top-1]處，因此在(a)中有stack[top-2].val=stack[top-1].val；將(a)變成(c)還需要執行2次出棧操作（實際上是3次出棧操作和1次入棧操作），因此還需要把top指針向下移動2位。
從SDT中消除左遞歸
在詳細介紹如何在語法分析過程中實現L屬性定義的SDT之前，我們先來介紹如何從SDT中消除左遞歸。在介紹語法分析的時候我們知道了帶有左遞歸的文法不能按照自頂向下的方式進行語法分析，并且我們還知道如何從一個左遞歸的文法中消除左遞歸。當文法是SDT的一部分時，我們還需要考慮如何處理其中的語義動作。
情況1
最簡單的情況是，我們只需要關心一個SDT中動作的執行順序。在這種情況下，當對文法進行消除左遞歸的轉換時，可以簡單地將動作當成終結符號處理。之所以可以這樣做，是因為對文法的轉換保持了由文法生成的符號串中終結符號的順序。舉個例子，對下面的SDT：
E → E+T { print('+'); }E → T將動作看作終結符號，消除左遞歸后得到的SDT為：
E → TRR → +T { print('+'); } R | ε情況2
另一種比較復雜的情況是，一個SDT的動作包含了對屬性值的計算。舉個例子，對下面的SDT：
A → A1Y { A.a = g(A1.a, Y.y); }A → X { A.a = f(X.x); }其中，f和g是兩個任意的函數，對基礎文法消除左遞歸得到：
A → XRR → YR | ε現在嘗試在文法中加入語義動作。我們給文法符號R附加上兩個屬性，一個屬性i是繼承屬性，它用來保存函數f和g的結果，另一個屬性s是綜合屬性，它會在計算結束后返回最終的計算結果。得到的SDT為：
A → X { R.i = f(X.x); } R { A.a = R.s; }R → Y { R1.i = g(R.i, Y.y); } R1 { R.s = R1.s; }R → ε { R.s = R.i; }我們用注釋語法分析樹來展示對SDT消除左遞歸前后的變化（這里省略了對R.s的計算）：
L屬性定義的SDT
如果一個SDD的基礎文法能夠以自頂向下的方式進行語法分析，并且此SDD是L屬性定義的，那么我們可以把這個SDD轉換成一個L屬性定義的SDT。
將一個L屬性定義的SDD轉換為一個SDT的規則如下：
- 將計算某個非終結符號A的繼承屬性的動作插入到產生式體中緊靠在A的本次出現之前的位置上。如果A的多個繼承屬性以無環的方式相互依賴，就需要對這些屬性的求值動作進行排序，以便先計算需要的屬性；
- 將計算一個產生式頭的綜合屬性的動作放置在這個產生式體的最右端。
在語法分析過程中實現L屬性定義的SDT的方法包括：
- 使用一個遞歸下降的語法分析器。它為每個非終結符號都建立一個函數，對應于非終結符號A的函數以參數的形式接受A的繼承屬性，并返回A的綜合屬性；
- 使用一個遞歸下降的語法分析器，以邊掃描邊生成的方式生成代碼；
- 與LL語法分析器結合實現一個SDT。屬性的值存放在語法分析棧中，各個規則從棧中的已知位置獲取需要的屬性值；
- 與LR語法分析器結合實現一個SDT。如果基礎文法是LL的，我們總是可以按照自底向上的方式來處理語法分析和翻譯過程。
在遞歸下降語法分析過程中進行翻譯
一個遞歸下降的語法分析器對每個非終結符號A都有一個函數A，我們可以把這個語法分析器擴展為一個翻譯器：
- 函數A的參數是非終結符號A的繼承屬性，返回值是非終結符號A的綜合屬性；
- 在函數A的函數體中進行語法分析并處理屬性。
舉個例子，考慮表2中的SDD，非終結符號E對應的函數E如下：
float E() {float Tval = T();float EQUOTEinh = Tval;float EQUOTEsyn = EQUOTE(EQUOTEinh);float Eval = EQUOTEsyn;return Eval;
}在函數E中，首先，注意到函數E沒有任何參數，這是因為非終結符號E沒有任何繼承屬性；其次，在E的函數體中，調用了函數T和函數EQUOTE，前者對應于非終結符號T（T也沒有任何繼承屬性），后者對應于非終結符號E’（E’有一個繼承屬性）；最后，定義了一系列變量來保存繼承屬性或綜合屬性（實際上是為了方便讀者理解才定義了如此多的變量），并返回了計算結果。
另外，非終結符號E’對于的函數EQUOTE如下：
float EQUOTE(float EQUOTEinh) {if (下一個輸入符號為'+') {讀取輸入return EQUOTE(EQUOTEinh + T());} else if (輸入已經結束) {return EQUOTEinh;} else {...}
}邊掃描邊生成代碼
對上面的例子，如果需要在調用函數EQUOTE的過程中打印出表達式，而不是返回最后的結果，那么可以一邊掃描一邊生成代碼。使用這個方法需要滿足的條件是：每個非終結符號存在一個綜合屬性作為主屬性，對主屬性的求值是將相關產生式體中的非終結符號的主屬性值連接起來得到的（連接時也可能包括非主屬性），各個非終結符號的主屬性值在連接運算中出現的順序和這些非終結符號在產生式體中出現的順序相同。
修改函數EQUOTE，使其打印出表達式：
float EQUOTE(float EQUOTEinh) {if (下一個輸入符號為'+') {讀取輸入print(EQUOTEinh);print('+');float Tval = T();return EQUOTE(EQUOTEinh + Tval);} else if (輸入已經結束) {return EQUOTEinh;} else {...}
}L屬性的SDD與LL語法分析
對于一個基礎文法是LL文法的L屬性的SDD，如果我們已經把它轉換成了一個L屬性定義的SDT，那么我們可以在LL語法分析過程中完成對它的翻譯。
為了在LL語法分析過程中實現L屬性定義的SDT，語法分析棧需要被擴展，擴展后的語法分析棧可以存放三種記錄：
- 代表終結符號和非終結符號的記錄，實際上是狀態記錄；
- 動作記錄。非終結符號A的繼承屬性放在表示A的棧記錄中，對A的繼承屬性求值的代碼放在一個緊靠在A的棧記錄之上的動作記錄中；
- 綜合記錄。非終結符號A的綜合屬性放在一個緊靠在A的棧記錄之下的綜合記錄中。
在語法分析過程中，某些屬性值可能會被拷貝到動作記錄或綜合記錄中，這是因為一個分析表驅動的LL語法分析器模擬了一個最左推導過程。舉個例子，當語法分析器按照一個產生式A→BC對棧頂的非終結符號A展開時，棧頂的A被替換為BC，假設C有一個繼承屬性C.i依賴于A的某個屬性，但是此時已經無法訪問到A，因此我們需要把A的屬性臨時拷貝到C的動作記錄中，這樣一來，C在計算其屬性C.i時就能找到這個依賴屬性了。
下圖是用文法G’中的產生式E'→ +TE'對E’進行展開的語法分析過程：
我們對這個語法分析過程進行分析：
- 圖8(a)中展示了即將展開
E'的語法分析棧，此時棧頂是E'的棧記錄，緊跟其后的是E'的綜合記錄，假設E'.inh已經被拷貝給了E1'的動作記錄中的EQUOTEval； - 圖8(b)用產生式體
+TE1'替換了E'。一開始，+的棧記錄在棧頂，它將和輸入進行匹配，在匹配完成后，它被彈出棧頂，T的棧記錄變為棧頂； - 由于
T的棧記錄位于棧頂，因此會用某個產生式對符號T進行展開，當這個展開過程結束后，T的綜合記錄將位于棧頂，并且該記錄中的val屬性值已經被賦值了； - 由于
E1'的繼承屬性依賴于T.val，因此在將T的綜合記錄彈出棧頂之前，還需要把T.val拷貝給E1'的動作記錄中的Tval； - 此時
E1'的動作記錄位于棧頂，它使用兩個拷貝的屬性值計算E1'.inh，計算的結果被放入E1'的棧記錄中； - 由于
E1'的棧記錄位于棧頂，因此會用某個產生式對符號E1'進行展開，當這個展開過程結束后，E1'的綜合記錄將位于棧頂，并且該記錄中的syn屬性值已經被賦值了； E1'的綜合記錄將E1'.syn賦值給E'.syn，到這里，用產生式體+TE1'展開E'的過程結束。
L屬性的SDD與LR語法分析
我們可以使用自底向上的方法來完成任何可以用自頂向下方式完成的翻譯過程，也就是說，對一個基礎文法為LL文法的L屬性的SDD，我們可以修改這個文法，使得可以在LR語法分析過程中實現這個新文法上的SDD。具體的方法包括：
- 將給定的基礎文法為LL文法的L屬性的SDD轉換成SDT，這樣的SDT在每個非終結符號之前放置語義動作計算它的繼承屬性，并且在產生式最右端放置一個語義動作計算綜合屬性；
- 對每個內嵌的語義動作，向這個文法中引入一個標記非終結符號來替換它。每個這樣的位置都有一個不同的標記，并且對于任意一個標記M都有一個產生式M→ε；
- 如果標記非終結符號M在某個產生式A→α{a}β中替換了語義動作a，對a進行修改得到a’，并且將a’關聯到M→ε上。這個動作a’將動作a需要的A或α中符號的任何屬性作為M的繼承屬性進行拷貝，并且按照a中的方法計算各個屬性，計算得到的屬性將作為M的綜合屬性。
對表2中的SDD，先將其轉換成SDT：
以這個SDT中的產生式E'→+TE1'為例，它的LR語法分析過程如下：
圖9(a)中首先對產生式E'→+TE1'進行變換，引入了一個標記非終結符號M對嵌入的動作{E1'.inh=E'.inh+T.val}進行替換，其中，E'.inh和T.val將作為M的兩個繼承屬性，E1'.inh將作為M的綜合屬性。
圖9(b)中是LR語法分析棧，我們假設接下來的輸入能夠匹配產生式體+TME1'并且最終被歸約成產生式頭E'。在這個語法分析棧中，我們不知道棧頂的記錄代表了哪一個文法符號（或者狀態），但是我們一定能確定這個記錄中的某個字段保存了E’的inh屬性。
圖9(c)中顯示了即將把產生式體+TME1'歸約成產生式頭E'之前的語法分析棧。我們對從圖9(b)到圖9(c)的LR語法分析過程進行詳細的分析：
- 語法分析棧的初始狀態如圖9(b)所示，此時棧頂的記錄保存了E’的inh屬性；
- 由于檢測到的下一個輸入的文法符號是”+”，因此識別出的產生式肯定是
E'→+TME1'； - 假設接下來的輸入被成功歸約成T，此時棧頂是代表非終結符號T的記錄，該記錄中保存了T的val屬性。由于我們已經確定了產生式是
E'→+TME1'，因此我們可以確定下一步是把ε歸約成M； - 在把ε歸約成M時，棧頂是代表標記非終結符號M的記錄，并且會執行一個動作，這個動作把E.inh（位于stack[top-3]的記錄中）和T.val（位于stack[top-1]的記錄中）分別拷貝給M的i和j屬性，同時使用屬性i和j計算它的綜合屬性s，屬性s實際上是下一個非終結符號E1’的繼承屬性；
- 假設接下來的輸入被成功歸約成E1’，此時棧頂是代表非終結符號E1’的記錄，計算E1’的syn屬性時用到的E1’的inh屬性是從代表M的記錄中拿到的，這種情況下，代表M的記錄相當于圖9(b)中棧頂的記錄，唯一的區別是這里我們能夠知道保存E1’.inh的記錄是代表M的記錄；
- 由于句柄
+TME1'已經位于棧頂，因此我們可以把+TME1'歸約成E'，此時會執行一個動作，這個動作把E1’.syn拷貝到stack[top-3]記錄中，并執行3次出棧操作（實際上是4次出棧操作和1次入棧操作）。到這里，從圖9(b)到圖9(c)的LR語法分析過程結束。
歡迎關注微信公眾號fightingZh?(?>?<?)?
總結
- 上一篇： Codeforces Round #63
- 下一篇： Linux/macOS 安装 Kaldi