編譯原理：第七章 中間語言(2)

1、7.3 中間代碼翻譯算法7.3.1 屬性文法A=(G, V, E); 【定義】 屬性文法是上下文無關(guān)文法在語義上的擴(kuò)展，可定義為如下三元組：其中：G(文法)；V(屬性集)；E(屬性規(guī)則集)。 屬性 代表與文法符號相關(guān)的信息，這里主要指語義信息(類型、種類、值和值地址)；文法產(chǎn)生式中的每個文法符號都附有若干個這樣的屬性。 屬性可以進(jìn)行計算和傳遞，屬性規(guī)則就是在同一產(chǎn)生式中，相互關(guān)聯(lián)的屬性求值規(guī)則。 屬性分兩類（按屬性求值規(guī)則區(qū)分）： 綜合屬性：其值由子女屬性值來計算(自底向上求值)； 繼承屬性：其值由父兄屬性值來計算(自頂向下求值)。說明 屬性文法構(gòu)造示例 ：【例7.7】 算術(shù)表達(dá)式的屬性文法;

2、 設(shè)：X.val 為文法符號 X 的值屬性； 下述屬性文法用于算術(shù)表達(dá)式的求值運(yùn)算：E - E1 + T ; | E.val:= E1.val + T.valT - T1 * F ; | T.val:= T1.val * F.valE - T ; | E.val:= T.valT - F ; | T.val:= F.valF - ( E ) ; | F.val:= E.valF - i ; | F.val:= i.valE - E1 - T ; | E.val:= E1.val - T.valT - T1 / F ; | T.val:= T1.val / F.val【注】可以看出： X.val

3、 屬性是綜合屬性。 屬性計算過程示例 ： 根據(jù)算術(shù)表達(dá)式屬性文法及其相應(yīng)的屬性求值規(guī)則， 2+4*(5-9/3)的屬性語法樹：E.10E1.2 + T.8 T.2 T.4 * F.2 F.2 F.4 ( E.2 ) 2 4 E.5 - T.3 T.5 T.9 / F.3 F.5 F.9 3 5 9按 最左推導(dǎo)或 最左歸約 傳遞規(guī)則： 計算規(guī)則：7.3.2 語法制導(dǎo)翻譯技術(shù) 【定義】語法制導(dǎo)(syntax_directed)是指根據(jù)語言的形式文法對輸入序列進(jìn)行分析、翻譯處理；核心技術(shù)是構(gòu)造 翻譯文法 - 在源文法產(chǎn)生式中插入語義動作符號(翻譯子程序)，借以指明屬性文法中屬性求值時機(jī)和順序。 以算

4、術(shù)表達(dá)式文法為例，探討翻譯文法的構(gòu)造！ 通俗地說，所謂語法制導(dǎo)翻譯技術(shù)，是指： 語法分析技術(shù) 翻譯文法構(gòu)造技術(shù) +注 為敘述簡便起見，除非臨時詳細(xì)指明，標(biāo)識符 X 的屬性一律視為符號表項指針，同時用：X 表示 X.point !逆波蘭式翻譯文法構(gòu)造示例：符號串 a*(b+c)的分析(翻譯)過程(推導(dǎo)法):E=T=T*F* =F*F* =aa*F* =aa*(E)* =aa*(E+T+)* =ai*(T+T+)* 導(dǎo)出序列aa*(bb+cc+)* =+ 分解導(dǎo)出序列：去掉動作符號： a*(b+c) . 源表達(dá)式；去掉文法符號： abc+* . 逆波蘭式；【例7.8】 算術(shù)表達(dá)式逆波蘭式翻譯文法

5、a:動作符號；含義：輸出(a)E - T | E+T+ | E-T-T - F | T*F* | T/F/F - ii | (E) G(E)注 四元式翻譯文法構(gòu)造示例1：. 從逆波蘭式的翻譯到四元式的翻譯： t1 = c / d t2 = t1 - e t3 = b * t2 t4 = a + t3四元式 則 算術(shù)表達(dá)式 a+b*(c/d-e) 的逆波蘭式算符進(jìn)棧之日，也就是四元式生成之時。重要結(jié)論逆波蘭式(生成)計算順序：a 即為 PUSH(a)- 逆波蘭式在棧中！假定：t3at1t2t4(結(jié)果)bcd/e-*+ GEQ() 表達(dá)式四元式生成函數(shù):G(E)：E - T | E+TGEQ(+)

6、 | E-TGEQ(-) T - F | T*FGEQ(*) | T/FGEQ(/) F - iPUSH(i) | ( E ) 四元式翻譯文法構(gòu)造示例2：. 算術(shù)表達(dá)式四元式翻譯文法設(shè)計假定：SEM(m)- 語義棧(屬性傳遞、賦值場所)； PUSH(i) 壓棧函數(shù)(把當(dāng)前 i 壓入語義棧)；則：其中：QTq 四元式區(qū)； t := NEWT; 申請臨時變量函數(shù)； SEND( SEMm-1,SEMm,t) POP;POP;PUSH(t)生成一個四元式送QTq語義棧次棧頂、棧頂 動作函數(shù)(序列)執(zhí)行過程示例 ：G(E)：E - T | E+TGEQ(+) | E-TGEQ(-) T - F | T*

7、FGEQ(*) | T/FGEQ(/) F - iPUSH(i) | ( E ) 對比 算術(shù)表達(dá)式 a*(b/c-d) 的逆波蘭式動作序列：abc/d-* ；可得四元式動作序列： QTq SEMm 動作序列 a b c t2 PUSH(d) GEQ(-) GEQ(/) GEQ(*) PUSH(c) PUSH(b) PUSH(a)執(zhí)行過程 a a b a t1 d a b c a t1 d ( * a t2 t3 )( - t1 d t2 )( / b c t1 ) t3 a7.3.3 四元式翻譯文法設(shè)計擴(kuò)展1. 賦值語句四元式翻譯文法： S - vPUSH(v)=EASSI(=) ; ASSI

8、(=) - 賦值函數(shù)； SEND(:= SEMm,_ ,SEMm-1 ); POP;POP; . 標(biāo)號、轉(zhuǎn)向語句四元式翻譯文法： S - i PUSH(i) :LABER(i) S ; S - goto iGOTO(i); LABER(i) - 標(biāo)號函數(shù)； SEND( lb _ ,_ ,SEMm ); POP; GOTO(i) - 轉(zhuǎn)向函數(shù)； SEND( gt _ ,_ ,i ); 7.3.3 四元式翻譯文法設(shè)計擴(kuò)展2. 條件語句四元式翻譯文法： S - if(R)IF(if)S;elseEL(el)SIE(ie) IF(if) - if 函數(shù)； SEND( if SEMm, _ , _ );

9、 POP; IE(i) - ifend 函數(shù)； SEND( ie _ ,_ ,_ ); EL(el) - else 函數(shù)； SEND( el _ ,_ ,_ ); R - E E GEQ() GEQ() - 表達(dá)式四元式生成函數(shù)； 其中的 為當(dāng)前匹配的關(guān)系算符。7.3.3 四元式翻譯文法設(shè)計擴(kuò)展3. 循環(huán)語句四元式翻譯文法： S - whileWH()(R)DO(do)SWE(we); WH(wh) - 循環(huán)頭 函數(shù)； SEND( wh _ , _ , _ ); WE(we) - 循環(huán)尾 函數(shù)； SEND( we _ ,_ ,_ ); 【注】文法中的 R 為 關(guān)系表達(dá)式（見條件語句四元式翻譯文

10、法）。 DO(el) - DO 函數(shù)； SEND( do SEMm ,_ ,_ ); POP ; 7.3.3 四元式翻譯文法設(shè)計擴(kuò)展4 . 說明語句四元式翻譯文法： 說明語句的翻譯目標(biāo)：填寫符號表 （1）原文法： D - id:T;D | id:TT - integer | real | array num of T | T（2）文法變換： D - id:TDD - ;id:TD | T - integer | real | array num of T | T（3）翻譯文法： D -INI()idNAME():TENT()DD -;idNAME():TENT()D | T -integerT

11、YP(i) -realTYP(r) -array numNUM() of TTYP(a) -TTYP()INI()-初始化 函數(shù)； offset := 0 ; NAME()-標(biāo)識符 名字處理 函數(shù)； := entry(id) ; ENT()-填寫符號表 函數(shù)； enter( , T.type, offset );(2)offset := offset + T.width; TYP(x)-標(biāo)識符類型處理 函數(shù)； T.type := x; T.width := x.width; NUM()-標(biāo)識符類型處理 函數(shù)； num.val := val(num); 翻譯文法應(yīng)用

12、驗(yàn)證示例【例7.9】 已知條件語句 if(a if( R )IF(if) S ; IE(ie)E EGEQ()apush(a)aPUSH(a) = EASSI(=)E + TGEQ(+)TFapush(a)TFF1push(1)TFbpush(b) if(a0)a=a+1 四元式翻譯的動作序列：push(a),push(a),push(b),GEQ(),IF(if),PUSH(a) push(1),GEQ(+),ASSI(=),IE(ie) 根據(jù)上述條件語句四元式翻譯的動作序列，if(a0)a=a+1 的四元式生成過程：IF(if) push(a) push(b)push(a)push(1)GEQ(+)ASSI(=)IE(ie)PUSH(a)GEQ() QTq SEMm 動作序列 a