🌈?個人主頁：十二月的貓-CSDN博客
🔥?系列專欄：?🏀編譯原理_十二月的貓的博客-CSDN博客

💪🏻?十二月的寒冬阻擋不了春天的腳步，十二點的黑夜遮蔽不住黎明的曙光?

目錄

1. 前言

2. 章節(jié)導(dǎo)讀

3. 屬性文法

3.1?綜合屬性與繼承屬性

綜合屬性

繼承屬性

3.2 不同屬性文法?

S-SDD

L-SDD

4. 語法制導(dǎo)定義（SSD）

4.1 根據(jù)屬性文法構(gòu)造分析樹（依賴圖）

4.1.1 S-SDD分析樹

4.1.2 L-SDD分析樹

?編輯

4.2 分析樹的計算順序

5?抽象語法樹

6. 語法制導(dǎo)翻譯?

5.1?S屬性文法的自下而上計算（語法制導(dǎo)翻譯的實現(xiàn)）

7. 總結(jié)

---

1. 前言

為什么打算開始這一系列的文章——編譯原理🎄🎄

其實本學(xué)期開始就一直想持續(xù)更新，陸陸續(xù)續(xù)主要更新了實驗部分。

正好趁著快要考試，便和大家一起花費幾天的時間回顧編譯原理的知識點。

目前，十二月貓的回顧計劃如下🔞🔞：

祝大家都能取得好成績呀~~🥰🥰?

---

參考書籍：

英文名：Compilers: Principles,Techniques,and Tools （龍書）🦖

作者：Alfred V.Aho,Ravi Sethi,Jeffrey D.Ullman?

????????1．本課程介紹編譯器構(gòu)造的一般原理和基本實現(xiàn)方法，主要介紹編譯器的各個階段：詞法分析、語法分析、語義分析、中間代碼生成、代碼優(yōu)化和目標(biāo)代碼生成。

????????2．本課程在介紹命令式程序設(shè)計語言實現(xiàn)技術(shù)的同時，強調(diào)一些相關(guān)的理論知識，如形式語言和自動機理論、語法制導(dǎo)的定義和屬性文法、類型論等。

????????3．本課程強調(diào)形式化描述技術(shù)，并以語法制導(dǎo)定義作為翻譯的主要描述工具。

????????4．本課程強調(diào)對編譯原理和技術(shù)在宏觀上的理解，而不把讀者的注意力分散到一些枝節(jié)的算法上，如計算開始符號集合和后繼符號集合的算法，回填技術(shù)等。作為原理性的教材，本書介紹基本的理論和方法，而不偏向于某種源語言或目標(biāo)機器。

2. 章節(jié)導(dǎo)讀

????????如果問起來編譯原理最迷的一章是什么，很多同學(xué)的回答將會是這一章，課本里講了眾多的不知道為什么會有的定義和莫名其妙的附加規(guī)則，但偏偏沒有講它們是為什么來的。你如果不信，想想這幾個問題，為什么會有屬性文法？有了那么多語法分析方法找出了語法錯誤對編譯器難道不夠么？它跟語法分析有什么聯(lián)系呢？
????????首先我們要清楚編譯器的工作并不是僅限于我們表面上在IDE里寫程序時給我們提醒各種錯誤，其更重要的工作是將我們的源程序翻譯成“目標(biāo)代碼”，翻譯成機器能切切實實執(zhí)行的代碼，這是它最初最核心的功能。也就是說編譯器首先要理解我們的源程序到底是想讓機器干什么，這就是“語義”！你說，學(xué)到目前的章節(jié)為止，編譯器有能力知道么？
????????沒有哦，編譯器現(xiàn)在通過詞法，語法分析只知道了“結(jié)構(gòu)”，舉個例子，它現(xiàn)在知道 “if (a > b) { i++}”是符合語法的，“if (a > b) { i + }”是不符合語法的因為構(gòu)造不出語法分析樹，但真的 a > b了，計算機應(yīng)該干什么呢？它現(xiàn)在還不知道該i++呢！只有我們學(xué)完了這兩章，通過附加語義規(guī)則讓計算機理解了if E {S}這個語法結(jié)構(gòu)的語義是如果E是真的，就執(zhí)行S的操作，我們才有可能讓計算機理解并執(zhí)行我們的源程序。
????????第六章主要站在方法論的角度討論可以用什么樣的方式來對不同的屬性文法進行翻譯，而第七章則舉出了幾個常用的例子（如何翻譯布爾表達式的語義，如何翻譯控制語句的語義）來應(yīng)用第六章討論的方法，明白所處的位置了吧，讓我們開始！

一定要看🥰🥰🥰：

• 表示語義——屬性文法
• 語義分析——屬性求值
• 屬性求值——屬性先后計算順序
• 屬性先后計算順序——依賴圖和拓撲排序
• 語義分析和語法分析同時進行——兩者順序需要一樣

3. 屬性文法

屬性文法用來表示語義

拿個實在的例子，對于臺式計算器的語法制導(dǎo)定義

????????左邊的一列我們前幾章都熟悉，是產(chǎn)生式，右邊的就是導(dǎo)讀中解釋的“語義規(guī)則”，即告訴計算機看到左邊產(chǎn)生式該干什么，比如看到 E —>?E1 + T這樣的語法結(jié)構(gòu)，語義規(guī)則告訴計算機應(yīng)當(dāng)做加法把E和T的值加起來E.val := E1 .val + T.val。

????????屬性文法的定義由此而來，我們把左邊的產(chǎn)生式和右邊的語義規(guī)則的結(jié)合叫屬性文法，對于每個文法符號（如E），它都有對應(yīng)的屬性（如.value）。

關(guān)鍵點：

• 屬性文法 = 產(chǎn)生式 + 語義規(guī)則
• 在語義規(guī)則中給了文法以屬性

3.1?綜合屬性與繼承屬性

????????綜合屬性是信息流流向產(chǎn)生式左部的屬性，在語法樹中體現(xiàn)為S屬性節(jié)點被其子節(jié)點的屬性值確立；繼承屬性是流向產(chǎn)生式右部的屬性，在語法樹中體現(xiàn)為被其父節(jié)點或兄弟節(jié)點的某些屬性值確立的。

簡單來說：

• 綜合屬性就是從右流向左的屬性，從分析樹的下面流向上面。
• 繼承屬性就是從左流向右部的屬性，從兄弟節(jié)點和父節(jié)點流過來的屬性

綜合屬性

在分析樹上結(jié)點N的綜合屬性通過N的子節(jié)點和N本身的屬性值來定義。

例如對于產(chǎn)生式E→E1+TE→E1?+T，綜合屬性對應(yīng)的語義規(guī)則可以是E.val=E1.val+T.valE.val=E1?.val+T.val。

終結(jié)符可以具有綜合屬性。終結(jié)符的綜合屬性值是由詞法分析器提供的詞法值，因此在SDD中沒有計算終結(jié)符屬性值的語義規(guī)則。

繼承屬性

在分析樹上N結(jié)點的繼承屬性只能通過N的父節(jié)點、兄弟節(jié)點或者N本身的屬性值來定義。

終結(jié)符沒有繼承屬性，終結(jié)符從詞法分析器處獲得的屬性值被歸為綜合屬性值。

3.2 不同屬性文法?

右邊語義規(guī)則存在不同的寫法，這會產(chǎn)生不同的屬性文法類型。

不同的屬性文法處理的方法也不同。

出現(xiàn)不同屬性文法的原因就是為了匹配語義分析的流程，讓語義分析和語法分析同時進行

S-SDD

僅僅使用綜合屬性的SDD稱為S屬性的SDD，也叫S-屬性定義，S-SDD。

例如：

這里面所有屬性均是綜合屬性，都是根據(jù)子構(gòu)造的屬性 計算出父構(gòu)造的屬性，所以可以自底向上的計算每個屬性。

L-SDD

L-屬性定義，也叫L屬性的SDD或者L-SDD。

一個SDD是L-屬性定義，當(dāng)且僅當(dāng)它的每個屬性要么是一個綜合屬性，要么是滿足如下條件的繼承屬性：假設(shè)存在一個產(chǎn)生式A→X1X2...Xn，其右部符號Xi(1≤i≤n)的繼承屬性僅依賴于下列屬性：

• A的繼承屬性
• 產(chǎn)生式中XiXi?左邊的符號?X1,X2,…,Xi?1 的屬性
• Xi本身的屬性，但Xi的全部屬性不能在依賴圖中形成環(huán)路

所以對于L-SDD，所有的分析樹屬性都依賴于左邊或者下邊的節(jié)點。所以不會存在環(huán)路。

每個S-屬性定義都是L-屬性定義

4. 語法制導(dǎo)定義（SSD）

????????語法制導(dǎo)定義和屬性文法分不開關(guān)系，就是有屬性文法，我們才能根據(jù)屬性文法和產(chǎn)生式構(gòu)造出分析樹，并根據(jù)分析樹進行語法制導(dǎo)翻譯，完成語義分析。

4.1 根據(jù)屬性文法構(gòu)造分析樹（依賴圖）

4.1.1 S-SDD分析樹

屬性文法如下：

S-SDD分析樹如下：

4.1.2 L-SDD分析樹

????????在上面這個SDD就是一個帶有繼承屬性的SDD。首先根據(jù)產(chǎn)生式(1)對應(yīng)的語義規(guī)則，得到了最上面的L.inh=T.type=real，然后根據(jù)產(chǎn)生式(4)對應(yīng)的語義規(guī)則，得到Lbellow.inh=Lup.inh，然后同樣的道理依據(jù)產(chǎn)生式(4)得到Lbellow.inh=Lup.inh。

4.2 分析樹的計算順序

• 這邊的計算順序也就是語義分析的順序。
• 這里的SDD語義分析順序和語法分析順序沒有關(guān)系。
• S-SDD和L-SDD語義分析順序和語法分析順序相聯(lián)系。

SDD為CFG中的文法符號設(shè)置語義屬性。對于給定的輸入串xx，我們將應(yīng)用語義規(guī)則，計算分析樹中各結(jié)點對應(yīng)的屬性值。SDD聲明了語法分析樹上屬性之間的依賴關(guān)系，按照這種依賴關(guān)系的拓撲排序可以確定他們的求值順序。

依賴圖是一個有向圖，它描述了分析樹中結(jié)點屬性之間的依賴關(guān)系。一個依賴關(guān)系圖有拓撲排序的充要條件是無環(huán)。一個依賴圖的示例如下所示：

????????一般說來，給定一個SDD，很難確定是否存在某棵語法分析樹，但是，**S-屬性定義（S-SDD）和L-屬性定義（L-SDD）**一定存在一個拓撲排序，并且這兩類SDD可以和自頂向下和自底向上的語法分析過程一起實現(xiàn)。?

不同屬性文法語法制導(dǎo)得到的分析樹如何計算：

• L里面所有屬性均是綜合屬性，都是根據(jù)子構(gòu)造的屬性計算出父構(gòu)造的屬性，所以可以自底向上的計算每個屬性。
• 對于L-SDD，所有的分析樹屬性都依賴于左邊或者下邊的節(jié)點。所以不會存在環(huán)路。

5?抽象語法樹

????????適用于翻譯的語法結(jié)構(gòu)不只是語法分析樹，抽象語法樹將操作符和關(guān)鍵字都不作為葉節(jié)點而是把它們當(dāng)作內(nèi)部節(jié)點，使用如下產(chǎn)生規(guī)則構(gòu)造，可以看出它的核心就在于只為id，num，運算符創(chuàng)造節(jié)點（mkleaf（），mknode（）），T到E，F到T的規(guī)約，E到F的規(guī)約只是子樹的轉(zhuǎn)移。

????????最終對a+5*b構(gòu)造抽象語法樹的結(jié)果如下圖所示，畫出如何通過屬性文法邊分析語法結(jié)構(gòu)（綠線）邊構(gòu)造抽象語法樹（紅線）也是一個很重要的考察點。

6. 語法制導(dǎo)翻譯?

將一個S-SDD轉(zhuǎn)換為SDT的方法：將每個語義動作都放在產(chǎn)生式的最后

這就是在做語法歸約時從右往左去進行，除了推導(dǎo)外要加上語義信息?

?將L-SDD轉(zhuǎn)換為SDT：

• 將計算L-SDD某個非終結(jié)符號A的繼承屬性的動作插入到產(chǎn)生式右部中緊靠在A的本次出現(xiàn)之前的位置上。
• 將計算一個產(chǎn)生式左部符號的綜合屬性的動作放置在這個產(chǎn)生式右部的最右端

這就是在做語法推導(dǎo)時，除了推導(dǎo)外要加上語義信息?

??

SDT可以看作是對SDD的一種補充，是SDD的具體實施方案；它明確指明語義規(guī)則的計算順序，說明實現(xiàn)細節(jié)。?

5.1?S屬性文法的自下而上計算（語法制導(dǎo)翻譯的實現(xiàn)）?

????????如果一個SDD的基礎(chǔ)文法是LR文法并且此SDD是S屬性定義的，那么我們可以構(gòu)造這樣一個SDT，其中的每個動作都放在產(chǎn)生式的最后，并且在按照這個產(chǎn)生式將產(chǎn)生式體歸約為產(chǎn)生式頭的時候執(zhí)行這個動作。像這樣所有動作都在產(chǎn)生式體最右端的SDT也稱為后綴翻譯方案（后綴SDT）。

????????將一個S屬性定義的且基礎(chǔ)文法為LR文法的SDD轉(zhuǎn)換為一個SDT的規(guī)則如下：

• 將計算一個產(chǎn)生式頭的綜合屬性的動作放置在這個產(chǎn)生式體的最右端。

????????注意到，由于表1中的SDD是S屬性定義的且其基礎(chǔ)文法G是LR文法，因此可以把它轉(zhuǎn)換成后綴SDT，表3中的SDT就是此SDD的一個轉(zhuǎn)換形式。下面我們進一步改進表3中的SDT，使其能夠在語法分析過程中實現(xiàn)：

????????表4中的stack表示LR語法分析棧，top指向棧頂。為了幫助讀者理解這個SDT中的語義動作，以產(chǎn)生式F→(E)為例，考慮將(E)歸約成F的過程，如圖6所示：

????????圖6顯示了把(E)歸約成F的LR語法分析過程。圖6(a)是即將把(E)歸約成F的語法分析?？煺?#xff0c;此時有stack[top]=")"，stack[top-1]="E"，stack[top-2]="("。執(zhí)行的歸約動作是連續(xù)3次出棧操作（將”)”、”E”、”(“依次彈出棧頂，如圖6(b)）和1次入棧操作（將”F”壓入棧頂，如圖6(c)）。注意到，(c)中的top相當(dāng)于(a)中的top-2，也就是說，F實際上出現(xiàn)在(a)中的stack[top-2]處；另外，由于E.val將被賦值給F.val，并且E出現(xiàn)在(a)中的stack[top-1]處，因此在(a)中有stack[top-2].val=stack[top-1].val；將(a)變成(c)還需要執(zhí)行2次出棧操作（實際上是3次出棧操作和1次入棧操作），因此還需要把top指針向下移動2位。

5.2?從SDT中消除左遞歸

????????在詳細介紹如何在語法分析過程中實現(xiàn)L屬性定義的SDT之前，我們先來介紹如何從SDT中消除左遞歸。在介紹語法分析的時候我們知道了帶有左遞歸的文法不能按照自頂向下的方式進行語法分析，并且我們還知道如何從一個左遞歸的文法中消除左遞歸。當(dāng)文法是SDT的一部分時，我們還需要考慮如何處理其中的語義動作。

情況1

最簡單的情況是，我們只需要關(guān)心一個SDT中動作的執(zhí)行順序。在這種情況下，當(dāng)對文法進行消除左遞歸的轉(zhuǎn)換時，可以簡單地將動作當(dāng)成終結(jié)符號處理。之所以可以這樣做，是因為對文法的轉(zhuǎn)換保持了由文法生成的符號串中終結(jié)符號的順序。舉個例子，對下面的SDT：

    E → E+T { print('+'); }E → T

將動作看作終結(jié)符號，消除左遞歸后得到的SDT為：?

    E → TRR → +T { print('+'); } R | ε

?情況2

另一種比較復(fù)雜的情況是，一個SDT的動作包含了對屬性值的計算。舉個例子，對下面的SDT：

    A → A1Y { A.a = g(A1.a, Y.y); }A → X { A.a = f(X.x); }

現(xiàn)在嘗試在文法中加入語義動作。我們給文法符號R附加上兩個屬性，一個屬性i是繼承屬性，它用來保存函數(shù)f和g的結(jié)果，另一個屬性s是綜合屬性，它會在計算結(jié)束后返回最終的計算結(jié)果。得到的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; }

5.3??S屬性文法的自上而下計算（語法制導(dǎo)翻譯的實現(xiàn)）?

如果一個SDD的基礎(chǔ)文法能夠以自頂向下的方式進行語法分析，并且此SDD是L屬性定義的，那么我們可以把這個SDD轉(zhuǎn)換成一個L屬性定義的SDT。

將一個L屬性定義的SDD轉(zhuǎn)換為一個SDT的規(guī)則如下：

• 將計算某個非終結(jié)符號A的繼承屬性的動作插入到產(chǎn)生式體中緊靠在A的本次出現(xiàn)之前的位置上。如果A的多個繼承屬性以無環(huán)的方式相互依賴，就需要對這些屬性的求值動作進行排序，以便先計算需要的屬性；
• 將計算一個產(chǎn)生式頭的綜合屬性的動作放置在這個產(chǎn)生式體的最右端。

在語法分析過程中實現(xiàn)L屬性定義的SDT的方法包括：

1. 使用一個遞歸下降的語法分析器。它為每個非終結(jié)符號都建立一個函數(shù)，對應(yīng)于非終結(jié)符號A的函數(shù)以參數(shù)的形式接受A的繼承屬性，并返回A的綜合屬性；
2. 使用一個遞歸下降的語法分析器，以邊掃描邊生成的方式生成代碼；
3. 與LL語法分析器結(jié)合實現(xiàn)一個SDT。屬性的值存放在語法分析棧中，各個規(guī)則從棧中的已知位置獲取需要的屬性值；
4. 與LR語法分析器結(jié)合實現(xiàn)一個SDT。如果基礎(chǔ)文法是LL的，我們總是可以按照自底向上的方式來處理語法分析和翻譯過程。

6. 一些習(xí)題

例一：

解答：

例二：

解答：

7. 總結(jié)

本文到這里就結(jié)束啦~~

本系列專欄將專注于【編譯原理】知識。

內(nèi)容包括：知識點講解、習(xí)題練習(xí)、重點知識帶練等~~目前已完成：

【編譯原理】編譯原理知識點匯總·概論與文法-CSDN博客

【編譯原理】編譯原理知識點匯總·詞法分析器（正則式到NFA、NFA到DFA、DFA最小化）-CSDN博客

【編譯原理】編譯原理知識點匯總·語法分析器（消除左遞歸、消除二義性、自頂向下語法分析、自下向上語法分析）-CSDN博客

【編譯原理】詞法分析器設(shè)計（山東大學(xué)實驗一）_山東大學(xué)編譯原理實驗-CSDN博客

【編譯原理】語法、語義分析器設(shè)計（山東大學(xué)實驗二）_語法分析實驗-實現(xiàn)一個簡單語法分析器(自上而下方法)實驗小結(jié)-CSDN博客

【編譯原理】代碼生成器的構(gòu)建與測試（山東大學(xué)實驗三）_編譯原理實驗語義分析代碼-CSDN博客?【編譯原理】一篇搞定正規(guī)式到NFA、NFA到DFA、DFA最小化-CSDN博客

【編譯原理】一篇搞定語法分析器對文法的要求（上下文無法文法、消除二義性文法、消除左遞歸）-CSDN博客

【編譯原理】一篇搞定LR分析法（LR(1)、LR(0)、SLR、LALR）-CSDN博客

期待您的關(guān)注~~🥰🥰?

貓貓陪你永遠在路上💪💪

如果覺得對你有幫助，友友們可以點個贊，收個藏呀~