【文章內(nèi)容簡介】 actor (val = 31) ) term (val = 31*42=1302) factor (val = 42) exp (val = 343=31) ( number (val = 42) the parse tree (343)*42 exp (val = 1302) * exp (val = 34) term (val = 34) factor (val = 34) term (val = 3) factor (val =3) number (val = 3) number (val = 34) 第 5章 語法制導翻譯技術(shù)和中間代碼生成 2021/6/15 信息學院 孫麗云 23 ■ 語法制導翻譯舉例 有一屬性文法為： （ 1） P ? bQb {print:”1”} （ 2） Q ? cR {print:”2”} （ 3） Q ? a {print:”3”} （ 4） R ? Qad {print:”4”} 輸入串為 bccaadadb，且采用自底向上語法分析方法時，則輸出序列是？ 試給出下列文法的適合自下而上翻譯的語義動作，使得當輸入串是 aacbb時，其輸出串是 12020。 （ 1） A ? aB { } （ 2） A ? c { } （ 3） B ? Ab { } 342421 print:”1” print:”2” print:”0” 第 5章 語法制導翻譯技術(shù)和中間代碼生成 2021/6/15 信息學院 孫麗云 24 詞法規(guī)則的描述工具： 語法規(guī)則的描述工具： 語義規(guī)則的常用描述工具： 屬性文法 正規(guī)文法或正規(guī)式 上下文無關(guān)文法 ■ 小結(jié) 屬性文法是在上下文無關(guān)文法的基礎(chǔ)上，允許每個文法符號 X(終結(jié)符或非終結(jié)符 )根據(jù)處理的需要，定義與 X相關(guān)聯(lián)的屬性。 一般地，將屬性文法寫成表格形式，每個文法規(guī)則用屬性等式的集合或相應(yīng)規(guī)則的語義規(guī)則列出。 第 5章 語法制導翻譯技術(shù)和中間代碼生成 2021/6/15 信息學院 孫麗云 25 例： 簡單表達式文法 ： E ? E + E | E – E | E * E | (E) | number 語法規(guī)則 語義規(guī)則 E1?E2+E3 =+ E1?E2E3 = E1?E2*E3 =* E1?(E2) = E?number = 該文法對應(yīng)的屬性文法為： 第 5章 語法制導翻譯技術(shù)和中間代碼生成 2021/6/15 信息學院 孫麗云 26 ■ 小結(jié) 屬性分為兩類： 1. 合成屬性（或稱綜合屬性） 2. 繼承屬性 目前常用過的語義分析方法 ——語法制導翻譯法：在語法分析過程中，隨著分析的逐步進展，根據(jù)相應(yīng)文法的每一規(guī)則所對應(yīng)的語義子程序進行翻譯的方法。 第 5章 語法制導翻譯技術(shù)和中間代碼生成 2021/6/15 信息學院 孫麗云 27 ■ 語法制導翻譯舉例 有一屬性文法為： （ 1） P ? bQb {print:”1”} （ 2） Q ? cR {print:”2”} （ 3） Q ? a {print:”3”} （ 4） R ? Qad {print:”4”} 輸入串為 bab，且采用自底向上語法分析方法時，則輸出序列是？ 31 第 5章 語法制導翻譯技術(shù)和中間代碼生成 2021/6/15 信息學院 孫麗云 28 例： 利用下列屬性文法對 (3+6)*9 進行語義分析。 語法規(guī)則 語義規(guī)則 E1?E2+E3 =+ E1?E2E3 = E1?E2*E3 =* E1?(E2) = E?number = number?0 =0 ………… ………… number?9 =9 ■ 語法制導翻譯舉例 第 5章 語法制導翻譯技術(shù)和中間代碼生成 2021/6/15 信息學院 孫麗云 29 ■ 綜合練習 給出文法 G[S]： S ? SaA|A A ? AbB|B B ? cSd|e （ 1）試證實 AacAd是文法 G[S]的一個句型； （ 2）請寫出該句型的所有短語、直接短語以及句柄； （ 3）為文法 G[S]的相應(yīng)產(chǎn)生式寫出語義動作，使句型 AacAd經(jīng)該翻譯方案后，輸出為 11435 第 5章 語法制導翻譯技術(shù)和中間代碼生成 2021/6/15 信息學院 孫麗云 30 中間語言 所謂中間代碼形式是指用來描述源程序并與之等效的一種編碼方式，可根據(jù)具體情況將它設(shè)計成各種形式。 一般來說，對于一個多遍掃描的編譯程序，越到后面的階段，所產(chǎn)生的中間代碼越接近于機器代碼。 常用的中間代碼有逆波蘭式表示（后綴式）、三元式、樹形（抽象的語法樹）、四元式、三地址碼表示等。 第 5章 語法制導翻譯技術(shù)和中間代碼生成 2021/6/15 信息學院 孫麗云 31 ■ 逆波蘭式 逆波蘭表示法 是把運算量（操作數(shù)）寫在前面，把運算符寫在后面，又稱為 后綴表示法 。 特征 ：操作符在前，操作數(shù)緊隨其后，無需用括號限制運算的優(yōu)先級和結(jié)合性，且求表達式值較中綴表達式方便。 例 ：將 ((a+b)*(ac)d)*(x+y)翻譯成逆波蘭表示，并求出當 a=3,b=7,c=1,d=2,x=4,y=6時該表達式的值。 程序語句也可用逆波蘭式表示。 練習：求 (b+c)*e+(b+c)/f的逆波蘭式？ 第 5章 語法制導翻譯技術(shù)和中間代碼生成 2021/6/15 信息學院 孫麗云 32 三元式由 3個域和一個序號組成： （ i） (op， arg1， arg2) 其中 op為運算符， arg1,arg2是 2個運算對象。 例： 算術(shù)表達式的三地址碼 x=y op z 的三元式為： (1) (op， y， z) (2) (=， x， (1)) ■ 三元式 三元式的運算結(jié)果由每一個三元式前的序號指示。 第 5章 語法制導翻譯技術(shù)和中間代碼生成 2021/6/15 信息學院 孫麗云 33 例：賦值語句 a=(c+d)*(c+d)相應(yīng)的三元式代碼為 (1) (+， c， d) (2) (+， c， d) (3) (*， (1)， (2)) (3) (=， a， (3)) ■ 三元式舉例 三元式出現(xiàn)的先后順序和表達式各部分的計值順序是一致的。 第 5章 語法制導翻譯技術(shù)和中間代碼生成 2021/6/15 信息學院 孫麗云 34 在三元式代碼表的基礎(chǔ)上另設(shè)一張表，該表按運算的次序列出相應(yīng)三元式在表中的位置，這張表稱為間接碼表。三元式表只記錄不同的三元式語句，間接碼表表示由這些語句組成的運算次序。 ■ 間接三元式 例：賦值語句 a=(c+d)*(c+d) 三元式 代碼為 相應(yīng)的 間接三元式 代碼由三元式表和間接碼表組成： 三元式表： (1) (+， c， d) (2) (*， (1)， (1)) (3) (=， a， (2)) 間接碼表： (1)(1)(2)(3) (1) (+， c， d) (2) (+， c， d) (3) (*， (1)， (