編譯原理4語義2表達式及賦值語句翻譯

1、第 10 講編譯原理 第四章 語義分析和中間代碼生成4.1 語義分析概述4.2 屬性文法4.3 幾種常見的中間語言4.4 表達式及賦值語句的翻譯4.5 控制語句的翻譯4.6 數(shù)組元素的翻譯4.7 過程或函數(shù)調(diào)用語句的翻譯4.8 說明語句的翻譯4.9 遞歸下降語法制導(dǎo)翻譯方法簡介第四章語義分析和中間代碼生成4.4 表達式及賦值語句的翻譯簡單算術(shù)表達式和賦值語句的翻譯布爾表達式的翻譯(難點)重點掌握算術(shù)表達式語義子程序布爾表達式的真假出口布爾表達式的語義子程序根據(jù)翻譯圖得到布爾表達式的四元式本講目標(biāo) 4.4 表達式及賦值語句的翻譯4.4.1 簡單算術(shù)表達式和賦值語句的翻譯簡單變量：普通變量和常數(shù)，

2、不包括數(shù)組、結(jié)構(gòu)體成員等復(fù)合型數(shù)據(jù)結(jié)構(gòu)。簡單算術(shù)表達式：僅含簡單變量的算術(shù)表達式簡單算術(shù)表達式與四元式簡單算術(shù)表達式的計值順序與四元式出現(xiàn)的順序相同，因此很容易將其翻譯成四元式形式。當(dāng)然，這些翻譯方法稍加修改也可用于產(chǎn)生三元式或間接三元式。1.3.3 語義分析和中間代碼生成（續(xù)）簡單算術(shù)表達式的計值順序與四元式出現(xiàn)的順序相同：例如，計算圓柱體表面積的C語言程序：s = 2 * 3.1416 * r *（h + r）;賦值語句的四元式中間代碼：（1）（*，2, 3.1416，T1）（2）（*，T1, r， T2）（3）（+，h, r， T3）（4）（*，T2, T3， T4）（5）（=，T4,

3、_， s ）回顧： 表達式及賦值語句的翻譯考慮以下文法GA: A i=E E E+E | E*E | E | (E) | i4.4 表達式及賦值語句的翻譯顯然，文法GA 是一個二義文法，但通過確定運算符的結(jié)合性及規(guī)定運算符的優(yōu)先級就可避免二義性的發(fā)生。用該文法作為示例的目的：為了更簡要地說明語義子程序的設(shè)計過程以及賦值語句的語法制導(dǎo)翻譯過程。如，對于賦值語句x=-b*(c+d)，已經(jīng)預(yù)先規(guī)定運算順序非終結(jié)符A代表“賦值句”非終結(jié)符E代表“表達式”4.4 表達式及賦值語句的翻譯1.設(shè)計6個產(chǎn)生式的語義子程序(1) A i=E p=lookup(); if(p=NULL) error(

4、); else emit(=,E.place,_,p); 例如，賦值語句 x = b 剛開始讀入到符號棧中，顯示為i = i, 使用E i規(guī)約，得到：i = E（符號棧）_ _ b（語義棧）(a)對非終結(jié)符E定義語義變量E.place，即用E.place表示存放E值的變量名在符號表中的入口地址或臨時變量名的整數(shù)碼所以，E.Place中必須保存b在符號表中的入口地址；x=b 翻譯為( =, b, _ , x)4.4 表達式及賦值語句的翻譯1.設(shè)計6個產(chǎn)生式的語義子程序(1) A i=E p=lookup(); if(p=NULL) error(); else emit(=,E.pla

5、ce,_,p); (b) 定義語義函數(shù)lookup()，其功能是審查終結(jié)符是否出現(xiàn)在符號表中，是則返回在符號表的入口指針，否則返回NULL。(c) 定義語義函數(shù)emit(op,arg1,arg2,result)，emit的功能是產(chǎn)生一個四元式并填入四元式表中。4.4 表達式及賦值語句的翻譯(2) E E(1)+E(2) E.place=newtemp(); emit(+,E(1).place, E(2).place, E.place); (d) 定義語義函數(shù)newtemp()，即每次調(diào)用newtemp()時都將回送一個代表新臨時變量的整數(shù)碼；臨時變量名按產(chǎn)生

6、的順序可設(shè)為T1、T2(3) E E(1)*E(2) E.place=newtemp(); emit(*,E(1).place, E(2).place,E.place); (4) EE(1) E.place=newtemp(); emit(uminus, E(1).place,_, E.place); 4.4 表達式及賦值語句的翻譯(5) E(E(1) E.place= E(1).place ;(6) Ei p=lookup(); if(p!=NULL) E.place=p; else error (); 例4.2 試分析賦值語句X= -B*(C+D)的語法制導(dǎo)翻譯過程。解答 賦值

7、語句X=-B*(C+D)的語法制導(dǎo)翻譯過程如表4.2所示(加工分析過程參考表4.1)。其實，利用帶注釋的語法樹進行規(guī)約的同時，就可以完成相應(yīng)的語義分析（一起看黑板）。表4.2(1) 賦值語句X=B*(C+D)的翻譯過程表4.2(2) 賦值語句X=B*(C+D)的翻譯過程4.4 表達式及賦值語句的翻譯4.4.2 布爾表達式的翻譯 1、布爾表達式的組成布爾表達式：由運算符與運算對象組成。 定義布爾變量 A、B、C、D A = bop1 B bop2 C bop3 D(1)運算符：非（單目）、與 （雙目）、或 （雙目） 注意：1、優(yōu)先級： 2、和服從左結(jié)合 3、運算符的優(yōu)先級：算術(shù) 關(guān)系布爾“=”

8、4.4 表達式及賦值語句的翻譯(2)運算對象(三種)：布爾變量布爾常量（false、true）關(guān)系表達式1、運算符rop ： 、=、2、運算對象：算術(shù)表達式3、返回值類型：bool類型例：bool a,b,c; int x,y,z a = b c true (x+y = z) a = b c true x+y = z思考：運算順序？4.4 表達式及賦值語句的翻譯 2、布爾表達式的計算了解1：對布爾運算、關(guān)系運算、算術(shù)運算的運算對象的類型可不區(qū)分布爾型或算術(shù)型，假定不同類型的變換工作將在需要時強制執(zhí)行。了解2：布爾表達式在程序語言中不僅用作計算布爾值，還作為控制語句(如if-else、while

9、等)的條件表達式，用以確定程序的控制流向。無論布爾表達式的作用如何，按照程序執(zhí)行的順序，都必須先計算出布爾表達式的值。計算布爾表達式的值有兩種方法： 1、按照優(yōu)先級和各變量的值，一步步求出結(jié)果；2、優(yōu)化計算： b = true; a = b c ; (不計算c, a=true) b = false; a = b c ; (不計算c, a=false) 思考：C語言的強制轉(zhuǎn)換？4.4 表達式及賦值語句的翻譯 2、布爾表達式的計算所以，按照優(yōu)化方式計算布爾表達式，需要給出整個表達式的真假出口。(1) 真出口： 若E(1)為真，則E為真； 若E(2)為真，則E為真； 所以E的真出口有兩個： E(1)

10、的真出口和E(2)的真出口。(2) 假出口： E(1)的假出口并不是E的假出口，(1)如果為假，必須計算E(2) ，因此：E(2)的假出口是整個的假出口。(a) E = E(1)E(2)4.4 表達式及賦值語句的翻譯 2、布爾表達式的計算(1) 假出口： 若E(1)為假，則E為假； 若E(2)為假，則E為假； 所以E的假出口有兩個： E(1)的假出口和E(2)的假出口。(2) 真出口： E(1)的真出口并不是E的真出口，(1)如果為真，必須計算E(2) ，因此：E(2)的真出口是整個的真出口。 練習(xí)布爾表達式 abcd 的真假出口。(b) E = E(1) E(2)4.4 表達式及賦值語句的翻

11、譯布爾表達式中，每個布爾分量一般至少對應(yīng)兩個四元式。 例如：E = E(1)E(2) = ab if(a | b) c=1; 對應(yīng): (1)(jnz, a,_,真出口） (2)(j,_,_,3) (3)(jnz, b,_,真出口) (4)(j,_,_,假出口) (5)(=,c,_,1) (6)if語句后面的四元式在這個例子中，真出口和假出口不能在生成四元式的當(dāng)時產(chǎn)生；假如a和b并不是簡單的布爾變量，或者條件語句后執(zhí)行的語句并不是僅僅一句，所有的真假出口都無法給定。4.4 表達式及賦值語句的翻譯 3、布爾表達式的文法：(1) 普通布爾表達式文法：(2) 優(yōu)化的布爾表達式文法： 好處：在句子中，如

12、果出現(xiàn) “ab”或“a b”之類的表達式，當(dāng)掃描到“a”或“a ”之后就立即可以進行規(guī)約，不用去關(guān)系b的取值。 GE: EEE | EE | E | (E) | i | i rop iGE： EEAE | EBE | E | (E) | i | i rop i EAE EBE4.4 表達式及賦值語句的翻譯 4、解決“真”、“假”出口問題的方法：拉鏈和回填(1) 拉鏈：在同一個表達式內(nèi)，每個四元式產(chǎn)生的時候，強制其出口為0，若后面一個四元式和它出口相同，用前面產(chǎn)生式的序號去填充后面產(chǎn)生式的跳轉(zhuǎn)位置（result），從而將不同的四元式鏈接起來，俗稱“拉鏈”。 假如下面三個四元式都是真出口：(i)

13、( _ , _ , _ , 0) (j) ( _ , _ , _ , 0)(k) ( _ , _ , _ , 0)注意：(k)為鏈?zhǔn)祝?i)為鏈尾，鏈尾result=0 (i) (_ , _ , _ , 0) (j) (_ , _ , _ , i)(k) (_ , _ , _ , j)4.4 表達式及賦值語句的翻譯(1) 拉鏈算法： p1 ,p2各自是兩個鏈?zhǔn)祝瑢⑺鼈兒喜⒊梢粋€以p2為鏈?zhǔn)椎男骆?merge(p1 ,p2) if(p2=0) return(p1); else p=p2; while(四元式p的第四區(qū)段內(nèi)容不為0) p=四元式p的第四區(qū)段內(nèi)容； 把p1填進四元式p的第四區(qū)段； r

14、eturn(p2); / else / merge(r1) ( _ , _ , _ , 0) (q1) ( _ , _ , _ , r1)(p1) ( _ , _ , _ , q1)(r2) ( _ , _ , _ , 0) (q2) ( _ , _ , _ , r2)(p2) ( _ , _ , _ , q2)算法執(zhí)行完，其實就是將(r2) 中的result變?yōu)閜1，最終形成一個鏈4.4 表達式及賦值語句的翻譯(2) 回填算法：把鏈?zhǔn)譸所鏈接的每個四元式的第四區(qū)段(result)都改寫為地址t。 (r) (_ , _ , _ , 0) (q) (_ , _ , _ , r)(p) (_ ,

15、_ , _ , q)Backpatch(p, int t) Q=p; while(Q!=0) q=四元式Q的第四區(qū)段內(nèi)容； 把t填進四元式Q的第四區(qū)段； Q=q; / while /Backpatch(r) (_ , _ , _ , t) (q) (_ , _ , _ , t)(p) (_ , _ , _ , t)4.4 表達式及賦值語句的翻譯(3) 其它需要說明的問題： 1、對于每個非終結(jié)符E，我們需要為它賦予兩個語義值 E.tc和E.fc，分別用來記錄E所對應(yīng)的四元式的真鏈和假鏈。 也就是說，為每個非終結(jié)符E添加兩個屬性：tc和fc；因此， 規(guī)約的時候，再次擴充語義棧，添加tc棧和fc棧；

16、 2、nxq:這是一個int變量，翻譯工作開始之前，初始值 是1，翻譯工作開始之后，每執(zhí)行一次emit()，nxq自增1， 即： nxq = 四元式個數(shù)+1； 4.4 表達式及賦值語句的翻譯 5、布爾表達式的翻譯1、文法：2、語義子程序： 例如 if(a) b;GE： EEAE | EBE | E | (E) | i | i rop i EAE EBEEi （布爾值） E.tc=nxq; E.fc=nxq+1; emit(jnz,entry(i),_,0); emit(j,_,_,0); (2) Ei(1) rop i(2) E.tc=nxq; E.fc=nxq+1; emit(jrop, e

17、ntry(i(1), entry(i(2),0); emit(j,_,_,0); 4.4 表達式及賦值語句的翻譯說明 (5): 如果E(1)為真，表達式的值取決于之后，可以回填 E(1)的tc鏈，跳轉(zhuǎn)到nxq ; 如果E(1)為假，那么不必計算后面， EA直接為假。(3) E(E(1) E.tc = E(1).tc; E.fc = E(1).fc; (4) EE(1) E.tc = E(1).fc; E.fc = E(1).tc; (5) EAE(1) Backpatch( E(1).tc, nxq); EA.fc = E(1) .fc; (6) EEAE(2) E.tc = E(2).tc;

18、 E.fc =merge( EA.fc，E(2).fc); 4.4 表達式及賦值語句的翻譯(7) EBE(1) Backpatch(E(1).fc，nxq); EB.tc = E(1).tc; (8) EEBE(2) E.fc = E(2).fc; E.tc = merge(EB.tc，E(2).tc); 說明 (8): 能使用(8)規(guī)約，說明E(1)為假， E(1)的真出口必須鏈接到E(2)，因此要拉鏈操作；E的真假出口都必須依賴于E(2) ，因此E.fc = E(2).fc; E.tc = E(2).tc; 4.4 表達式及賦值語句的翻譯3、步驟：(1) 首先規(guī)約布爾表達式，如“abcd”

19、，通過語義子程序翻譯出初始的四元式；(2) 添加真假出口的四元式標(biāo)記(3) 回填真假出口，經(jīng)判斷得知， 整個布爾表達式的真出口是106， 假出口是q(回填鏈尾為0的tc、fc) 100 (jnz，a，_，102) 101 (j，_，_，104) 102 (jnz，b，_，0) 103 (j，_，_，104) 104 (j，c，d，102) 105 (j，_，_，0)T: 106 F: qif (abcd) else 4.4 表達式及賦值語句的翻譯例4.3 試給出布爾表達式abcd作為控制條件的四元式中間代碼。解答 設(shè)四元式序號從100開始，則布爾表達式abcd的 分析過程為：規(guī)則：Ei Ebc

20、d初始輸入： abcd語義棧(tc/fc)： E.tc=100E.fc=101四元式： 100 (jnz, a, _ , 0) 101 (j, _ , _ , 0) Ei （布爾值） E.tc=nxq; E.fc=nxq+1; emit(jnz,entry(i),_,0); emit(j,_,_,0); 規(guī)則： EAE(1) EA bcd語義棧(tc/fc)： EA.fc=101四元式： 100 (jnz, a, _ , 102) 101 (j, _ , _ , 0) nxq = 1024.4 表達式及賦值語句的翻譯規(guī)則：Ei EA E(2)cd語義棧(tc/fc)： E.tc=102E.fc

21、=103EA.fc=101四元式： 102 (jnz, b, _ , 0) 103 (j, _ , _ , 0)規(guī)則： EEAE(2) Ecd語義棧(tc/fc)： E.tc=102E.fc=103四元式： 101 (j, _ , _ , 0) 103 (j, _ , _ , 101) 4.4 表達式及賦值語句的翻譯規(guī)則： EBE(1) EB cd語義棧(tc/fc)： EB.tc=102四元式： 101 (j, _ , _ , 104) 103 (j, _ , _ , 104)規(guī)則： Ei rop i EB E語義棧(tc/fc)： 四元式： 104 (j, c , d , 0) 105 (j, _ , _ , 0)E.tc=104E.fc=105EB.tc=102規(guī)則： E EBE(2) E語義棧(tc/fc)： 四元式： 104 (j, c , d , 102) E.tc=102E.fc=1054.4 表達式及賦值語句的翻譯第一步結(jié)束，得到 abcd 的四元式如下： 100 (jnz，a，_，102) 101 (j，_，_，104) 102 (jnz