編譯6語法制導(dǎo)翻譯技術(shù)和中間代碼生成

1、編譯原理編譯原理(第三版第三版) 陳火旺等編著22022-5-21 主主 要要 內(nèi)內(nèi) 容容 屬性文法。屬性文法。 語法制導(dǎo)翻譯法的思想語法制導(dǎo)翻譯法的思想 常見中間代碼：逆波蘭表示、四元式表示常見中間代碼：逆波蘭表示、四元式表示和三地址代碼、三元式和樹形表示和三地址代碼、三元式和樹形表示 各種不同語法結(jié)構(gòu)的語法制導(dǎo)翻譯技術(shù)各種不同語法結(jié)構(gòu)的語法制導(dǎo)翻譯技術(shù)語法制導(dǎo)翻譯技術(shù)和中間代碼生成語法制導(dǎo)翻譯技術(shù)和中間代碼生成32022-5-216.1 概述概述一、語義分析的任務(wù)一、語義分析的任務(wù)審查每一個(gè)語法結(jié)構(gòu)的靜態(tài)語義，即驗(yàn)證語法正確的結(jié)構(gòu)是否有意義。如：賦值語句：x=x+y,左邊變量類型與右邊變量

2、類型是否一致。1.在語義正確的基礎(chǔ)上生成一種中間代碼或目標(biāo)代碼。42022-5-21二、語義分析的范圍二、語義分析的范圍1.確定類型：確定標(biāo)識(shí)符所關(guān)聯(lián)的數(shù)據(jù)類型。2.類型檢查：按語言的類型規(guī)則，檢查運(yùn)算的合法性與運(yùn)算分量類型的一致性，必要時(shí)作類型轉(zhuǎn)換。3.識(shí)別含義：根據(jù)語言的語義定義（形式或非形式），識(shí)別程序中各構(gòu)造成分組合到一起的含義，并作相應(yīng)的語義處理（生成中間代碼或目標(biāo)代碼）4.控制流檢查：控制流語句必須轉(zhuǎn)移到合法的地方。如：C中，break語句規(guī)定跳出最內(nèi)層的循環(huán)或switch語句.52022-5-215.一致性檢查：在很多場(chǎng)合要求對(duì)象只能被說明一次(避免重復(fù)定義)。6.相關(guān)名字檢查：

3、如：Ada，循環(huán)或塊可以有一個(gè)名字，它出現(xiàn)在這些結(jié)構(gòu)的開頭或結(jié)尾。編譯程序必須檢查這兩個(gè)地方用的名字是否相同。62022-5-21三、語義描述工具和語義分析方法三、語義描述工具和語義分析方法語義描述工具 目前流行：用屬性文法屬性文法作為描述語義的工具。語義分析方法根據(jù)描述屬性文法的語義規(guī)則的方式不同，語義分析方法分為：n語法制導(dǎo)定義方法1.翻譯方案72022-5-216.2 屬屬 性性 文文 法法一、屬性一、屬性屬性常用來描述事物或人的特征。如：人的姓名，性別等，商品的顏色、重量、單位等。n屬性屬性：在編譯中，對(duì)文法的每一個(gè)符號(hào)，引進(jìn)一些屬性，用這些屬性描述文法符號(hào)相關(guān)的信息，如：類型、值或存

4、儲(chǔ)位置等。如：AX ，在語法推導(dǎo)或歸約時(shí)，有時(shí)結(jié)合X的類型，位置，值，考慮語法分析的正確性，即語法分析中有語義檢查。如:X的屬性：Xtype，Xplace，Xval分別表示X的類型，位置，值等語義。82022-5-21n屬性值：可以在語法分析過程中計(jì)算和傳遞。n屬性的加工過程就是語義的處理過程。二、屬性文法二、屬性文法n語義規(guī)則語義規(guī)則在對(duì)文法符號(hào)屬性處理過程中，必須遵守一定義的規(guī)則語義規(guī)則。為文法的每一產(chǎn)生式定義一組屬性的計(jì)算規(guī)則，稱為語義規(guī)則語義規(guī)則。n屬性文法屬性文法形式定義：一個(gè)屬性文法是一個(gè)三元組A，A=(G,V,F)其中：G為一個(gè)上下文無關(guān)文法； V 表示屬性的有窮集合； F表示屬

5、性的斷言或謂詞的有窮集。92022-5-21n在屬性文法中：每個(gè)屬性與文法中某個(gè)符號(hào)相關(guān)聯(lián)，用“符號(hào)屬性”表示。如：Xtype, Xint, Xbool等。每個(gè)斷言與文法的某產(chǎn)生式相關(guān)聯(lián)。 斷言就是產(chǎn)生式上定義的一組語義規(guī)則。例：一個(gè)簡(jiǎn)單表達(dá)式方法：EN1+N2 | N1orN2Nnum|true|false102022-5-21n根據(jù)程序語言中有關(guān)類型的檢驗(yàn)原則，可以得到關(guān)于類型檢驗(yàn)的屬性文法：EN1+N2 N1.type=int and N2.type=intEN1orN2 N1.type=bool and N2.type=boolNnum N.type=intNtrue N.type=b

6、oolNfalse N.type=bool112022-5-21n屬性分類：綜合屬性 繼承屬性綜合屬性：從語法分析角度看，如果一個(gè)結(jié)點(diǎn)的某一屬性，其值由子結(jié)點(diǎn)的屬性的值來計(jì)算，稱該屬性為綜合屬性。繼承屬性：在語法分析樹中，結(jié)點(diǎn)的某個(gè)屬性值由該結(jié)點(diǎn)的兄弟結(jié)點(diǎn)和（或）父結(jié)點(diǎn)的屬性值來計(jì)算，此結(jié)點(diǎn)的屬性稱為繼承屬性。繼承屬性用于“自上而下”傳遞信息、 綜合屬性用于“自下而上”傳遞信息。122022-5-21n注意：注意：終結(jié)符號(hào)只有綜合屬性，他由詞法分析器提供。非終結(jié)符號(hào)既有綜合屬性，也可有繼承屬性。文法識(shí)別符號(hào)（開始符號(hào)）的所有繼承屬性作為屬性計(jì)算前的初始值。根據(jù)處理不同的要求，屬性和斷言可以多種

7、形式出現(xiàn)，如：語義規(guī)則或者程序段等。132022-5-21【例6.1】簡(jiǎn)單表達(dá)式求值的屬性文法。 產(chǎn)生式語義規(guī)則LEprint(E.val)EE1+TE.val=E1.val+T.valETE.val=T.valTT1*FE.val=T1.val*F.valTFT.val=F.valF(E)F.val=E.val1.FdigitF.val= digit.lexval142022-5-21【例6.2】描述說明語句中簡(jiǎn)單變量類型信息的屬性文法產(chǎn)生式產(chǎn)生式語義規(guī)則語義規(guī)則DTLL.in=T.typeTintT.type =integerTrealT.type =real LL1，id L1.in=L

8、.inaddtype(id.entry,L.in)1.Lidaddtype(id.entry,L.in)152022-5-21文法定義了一種說明語句，該說明語句的形式是由關(guān)鍵字int或real開頭，后跟一個(gè)標(biāo)識(shí)符表，每一個(gè)標(biāo)識(shí)符間用逗號(hào)隔開：real id1，id2，idn 或 int id1，id2，idn屬性文法中，非終結(jié)符T有綜合屬性type，其值由關(guān)鍵字int和real決定。n語義規(guī)則L.in=T.type將L的屬性值置為該說明語句指定的類型。 L.in將被沿著語法樹傳遞到下邊的結(jié)點(diǎn)使用，與L產(chǎn)生式相聯(lián)的規(guī)則里使用了它。如：句子int id1，id2語法樹： D T L L int ,

9、 id2 id1 162022-5-21一、基本思想對(duì)文法中的每個(gè)產(chǎn)生式都附加上一個(gè)語義動(dòng)作或語義子程序，伴隨著語法分析，每當(dāng)使用一條產(chǎn)生式進(jìn)行推導(dǎo)或歸約時(shí)，就執(zhí)行相應(yīng)產(chǎn)生式的語義動(dòng)作（包括：查填表格，改變變量的求值，打印信息和生成中間代碼等），從而完成預(yù)定的翻譯工作。即在語法翻譯過程中伴隨部分語義的檢查工作。6.3 語法制導(dǎo)翻譯概述語法制導(dǎo)翻譯概述172022-5-21n語法制導(dǎo)翻譯方法：自底向上的語法制導(dǎo)翻譯方法自頂向下的語法制導(dǎo)翻譯方法二、語法制導(dǎo)翻譯的步驟1、為所給文法每個(gè)產(chǎn)生式設(shè)計(jì)相應(yīng)的語義規(guī)則。例：為一個(gè)簡(jiǎn)單表達(dá)式計(jì)值的文法：EE+E|E*E|(E)|digit設(shè)計(jì)簡(jiǎn)單計(jì)算的語義規(guī)

10、則如下：1. EE(1)+E(2)Eval=E(1)val + E(2)val 2. EE(1)*E(2)Eval=E(1)val * E(2)val 3. E(E(1)Eval=E(1)val4. EdigitEval=lexdigit為文法產(chǎn)生式寫語義規(guī)則或語義子程序?yàn)槲姆óa(chǎn)生式寫語義規(guī)則或語義子程序是難點(diǎn).182022-5-212.采用LR分析方法，則構(gòu)造LR分析表192022-5-213. 將原LR語法分析棧擴(kuò)充，增加語義值棧。4. 根據(jù)語義分析棧的工作過程設(shè)計(jì)總控程序，使語法分析與語義分析工作同時(shí)完成。例例：計(jì)算表達(dá)式7+8*5的語法樹，以及用LR語法制導(dǎo)翻譯法得到該表達(dá)式的計(jì)值過程

11、：202022-5-21 7 + Eval=47 Eval=7 Eval=40 + Eval=8 Eval=5 8 5 注：自底向上語法制導(dǎo)翻譯的特點(diǎn)：當(dāng)棧頂形成句柄執(zhí)當(dāng)棧頂形成句柄執(zhí)行歸約時(shí)，調(diào)用相行歸約時(shí)，調(diào)用相應(yīng)的語義動(dòng)作應(yīng)的語義動(dòng)作。語法分析與語義分語法分析與語義分析同步操作。析同步操作。*212022-5-211 中間語言n中間語言：它介于源程序到目標(biāo)語言程序中間程序的語言n中間語言程序：用中間語言表示的程序。n作用：用于編譯程序，將源程序翻譯成等價(jià)的中間語言程序，再將中間語言程序轉(zhuǎn)化成目標(biāo)程序（即將語義分析和目標(biāo)代碼生成分開處理）n源程序 中間語言程序目標(biāo)程序n中間語言是表示語法制

12、導(dǎo)翻譯的結(jié)果。等價(jià)變換轉(zhuǎn)化6.4 6.4 中中 間間 語語 言言222022-5-21好處：n中間語言與機(jī)器無關(guān)，使采用中間語言進(jìn)行翻譯的編譯程序系統(tǒng)易于移植。n易于優(yōu)化翻譯后的代碼。n使編譯程序的結(jié)構(gòu)在邏輯上更簡(jiǎn)單明確。2 中間語言的表示常見：逆波蘭表示 四元式表示和三地址代碼 三元式和樹形表示232022-5-216.4.1 逆波蘭表示逆波蘭表示 由波蘭邏輯學(xué)家J.Lukasiewicz(盧卡西維茲)首先提出用來表示表達(dá)式的方法，后來推廣到表示程序設(shè)計(jì)語言中的其它語法成分。n表達(dá)式的逆波蘭表示表達(dá)式的逆波蘭表示表達(dá)式的表示：n中綴表示：運(yùn)算符居中，運(yùn)算對(duì)象在左右兩邊:a+bn波蘭表示：前綴

13、表示：運(yùn)算符在前，運(yùn)算對(duì)象在后：+ab后綴表示：運(yùn)算對(duì)象在前，運(yùn)算符在后：ab+(逆波蘭表示)242022-5-21n例：逆波蘭表示的例子252022-5-21(1)表達(dá)式逆波蘭表示的定義： 設(shè)E是一般表達(dá)式，則： 一般表達(dá)式一般表達(dá)式逆波蘭表達(dá)式逆波蘭表達(dá)式n若E為變量或常量En（E）E的逆波蘭式nE(1)opE(2)(二目運(yùn)算)E(1)的逆波蘭式E(2)的逆波蘭式opnopE(單目運(yùn)算)E的逆波蘭式op262022-5-21 在編譯過程中，生成逆波蘭表示的語義規(guī)則描述： 產(chǎn)生式 語義規(guī)則 EE(1)opE(2) E.code=E(1).code|E(2) .code|op E(E(1) )

14、 E.code=E(1) .code Ei E.code= i 其中：E.code表示E的逆波蘭式；|表示逆波蘭式的連接。272022-5-21 (2)逆波蘭表示的特點(diǎn)a.標(biāo)識(shí)符(運(yùn)算對(duì)象)出現(xiàn)的順序（從左到右）和原有順序相同。b. 運(yùn)算符是按實(shí)際計(jì)算順序（從左到右）出現(xiàn)的。c. 運(yùn)算符緊跟在運(yùn)算對(duì)象的后面出現(xiàn)，并且沒有括號(hào)。282022-5-21(3) 好處：易于對(duì)表達(dá)式的計(jì)算處理n對(duì)于一般表達(dá)式的計(jì)算，系統(tǒng)需要用兩個(gè)工作棧分別處理運(yùn)算對(duì)象和運(yùn)算符。n對(duì)于逆波蘭表示的表達(dá)式計(jì)算處理只用一個(gè)工作棧。例：逆波蘭式ab+c*的計(jì)算處理過程遇運(yùn)算對(duì)象a,b入棧掃描ab+c*棧遇運(yùn)算符+取出a,b，運(yùn)

15、算結(jié)果T入棧c*遇運(yùn)算對(duì)象c入棧取出c,T作運(yùn)算，設(shè)結(jié)果T1遇運(yùn)算符*292022-5-212. 形成逆波蘭表示怎樣將一般表達(dá)式轉(zhuǎn)換成逆波蘭表示？基本思想基本思想:從左到右掃描表達(dá)式，每遇到：1o 表達(dá)式中的運(yùn)算對(duì)象則往左去。2o 表達(dá)式中的運(yùn)算符，則與運(yùn)算符棧頂元素比較優(yōu)先數(shù)：302022-5-21逆波蘭表示表達(dá)式運(yùn)算對(duì)象運(yùn)算符進(jìn)棧出棧運(yùn)算符棧 如果運(yùn)算符棧頂元素的優(yōu)先數(shù)大于或等于表達(dá)式中當(dāng)前的運(yùn)算符優(yōu)先數(shù)，則棧頂元素退棧向左去。然后當(dāng)前運(yùn)算符繼續(xù)與棧頂?shù)男略乇容^優(yōu)先數(shù)。直到棧頂元素的優(yōu)先數(shù)小于表達(dá)式中當(dāng)前運(yùn)算符為止。此時(shí)，才將表達(dá)式中當(dāng)前運(yùn)算符進(jìn)棧。312022-5-21例：畫出形成表達(dá)

16、式a*(b+c/d)的逆波蘭表示過程a*(b+c/d)#步驟a(b+c/d)#*#步驟ab+c/d)#(*#步驟ab+c/d)#(*#步驟abc/d)#+(*#步驟abc/d)#+(*#步驟322022-5-21abcd)#/+(*#步驟abcd)#/+(*#步驟/+(*#abcd/)#步驟+(*#abcd/+)#步驟 *#abcd/+*#步驟332022-5-21形成逆波蘭表示的過程，實(shí)質(zhì)上是表達(dá)式的翻譯過程。（算法不難寫出）例：a/b/c+d = ab/c/d+(a+b)*(c-d/e) = ab+cde/-*342022-5-216.4.2 三元式和樹形表示三元式和樹形表示1. 三元式一

17、個(gè)三元式由三個(gè)主要部分和一個(gè)序號(hào)組成：(i)(op,arg1,arg2)其中：op是運(yùn)算符，arg1和arg2是運(yùn)算對(duì)象。當(dāng)op為一目運(yùn)算符時(shí)，只有一個(gè)運(yùn)算對(duì)象。(i)表示三元式的序號(hào)，三元式的運(yùn)算結(jié)果由每個(gè)三元式前序號(hào)(i)指示。序號(hào)(i)指向三元式所處的表格位置，因此引用一個(gè)三元式的計(jì)算結(jié)果是通過引用該三元式的序號(hào)實(shí)現(xiàn)的。三元式出現(xiàn)的先后順序與表達(dá)式的計(jì)值順序一致。352022-5-21例：a=A+(-B)*C 的三元式：(1)(,B,-)(2)(*,(1),C)(3)(+,A,(2)362022-5-212. 間接三元式由于三元式的先后順序決定了值的順序，因此在產(chǎn)生三元式形式的中間代碼后

18、，對(duì)其進(jìn)行代碼的優(yōu)化時(shí)難免涉及到改變?nèi)降捻樞?這就要修改三元式表。為了最少改動(dòng)三元式表，可以另設(shè)一張間接碼表來表示有關(guān)三元式在三元式表的計(jì)值順序，用這種辦法處理的中間代碼稱為間接三元式。例：表達(dá)式x=A+B*Cy=D-B*C372022-5-21其間接三元式表示如下：由于間接碼表的作用，編譯程序每產(chǎn)生一個(gè)三元式時(shí)，先查看三元式表中是否存在當(dāng)前三元式，若存在就不需要重復(fù)填寫三元式表，如上例中的三元式(1) (*,B,C)在間接碼表中出現(xiàn)了兩次，但三元式表中實(shí)際只有一個(gè)三元式。注：間接三元式表示的中間代碼有利于中間代碼的優(yōu)化。382022-5-213.樹形表示樹形表示n樹形結(jié)構(gòu)是三元式的另一種

19、表示形式例如：a=-b*c+b*d的樹形表示(由三元式的下至上畫出) = + a b * * c - d b 392022-5-21v一個(gè)表達(dá)式中簡(jiǎn)單變量或常數(shù)的樹形表示就是它們的本身。v如果表達(dá)式e1和e2的樹分別為T1和T2,則： e1+e2, e1* e2, -e1 的樹分別： + T2 T1 e1+e2 * T2 T1 e1*e2 - T1 -e1 樹形表示法很容易表示一個(gè)表達(dá)式或語句。402022-5-21注注：二目運(yùn)算對(duì)應(yīng)二叉樹三目運(yùn)算對(duì)應(yīng)三叉樹： 如條件語句if u then S1 else S2 可看作三目運(yùn)算。 其三目運(yùn)算符定義為:if then else 則樹表示： S2

20、u S1 注：多叉樹不便于存儲(chǔ)，可以化為二叉樹： S1 S2 u new 412022-5-21四、四元式和三地址代碼四、四元式和三地址代碼四元式是一種比較普遍采用的中間代碼形式。n四元式由四個(gè)部分組成：(i) (op, arg1, arg2, result)其中：op為運(yùn)算符;arg1,arg2為運(yùn)算對(duì)象。result存放結(jié)果的變量。四元式之間的聯(lián)系通過變量來聯(lián)系(而不是三元式中的序號(hào)聯(lián)系)例：a=b*c+b/d 的四元式表示：(1) (*, b, c, t1)(2) (/, b, d, t2)(3) (+, t1, t2, t3)(4) (=, t3, _, a)422022-5-21注：

21、四元式和三元式的主要不同在于：四元式之間的聯(lián)系通過中間引用的變量名實(shí)現(xiàn)，而三元式之間的聯(lián)系通過三元式序號(hào)實(shí)現(xiàn)。 這說明要更改一張三元式表比較困難，它需要改變一系列的三元式的序號(hào)。四元式表的修改比較方便，調(diào)整四元式之間位置，不改變其中的參數(shù)。 因此：四元式和三地址代碼表示的中間代碼便于中間代碼的優(yōu)化。而三元式和樹不便于優(yōu)化。432022-5-21有時(shí)將四元式表示成更直觀的形式：三地址代碼v三地址代碼形式：x = a op b (賦值形式)與賦值語句的區(qū)別：其右邊最多只能有一個(gè)運(yùn)算符。 例：上例的四元式寫成三地址代碼：(1) t1=b*c(2) t2=b/d (3) t3= t1+ t2(4) a= t3n三地址代碼表示的好處：表示中間代碼更直觀，有利于中間代碼的優(yōu)化和目標(biāo)代碼的生成。442022-5-21n四元式的生成算法與逆波蘭式生成算法基本相同。n擴(kuò)充四元式可表示程