【正文】 第七章 語(yǔ)義分析和中間代碼產(chǎn)生 ? 靜態(tài)語(yǔ)義檢查 ?類型檢查 ?控制流檢查 ?一致性檢查 ?相關(guān)名字檢查 ?名字的作用域分析 語(yǔ)法分 析器 中間代碼 產(chǎn)生器 靜態(tài)檢 查器 中間代碼 優(yōu)化器 ? 中間語(yǔ)言 (復(fù)雜性界于源語(yǔ)言和目標(biāo)語(yǔ)言之間 )的好處： ?便于進(jìn)行與機(jī)器無(wú)關(guān)的代碼優(yōu)化工作 ?易于移植 ?使編譯程序的結(jié)構(gòu)在邏輯上更為簡(jiǎn)單明確 源語(yǔ)言 程序 目標(biāo)語(yǔ) 言程序 中間語(yǔ) 言程序 Compiler Front End Compiler Back End ? 常用的中間語(yǔ)言： ?后綴式，逆波蘭表示 ?三地址代碼 ?三元式 ?四元式 ?間接三元式 ?DAG圖表示 中間語(yǔ)言 后綴式 ? 后綴式 表示法： Lukasiewicz發(fā)明的一種表示 表達(dá)式 的方法 ， 又稱 逆波蘭 表示法 。 ? 一個(gè)表達(dá)式 E的后綴形式可以如下定義： 1. 如果 E是一個(gè)變量或常量，則 E的后綴式是 E自身。 2. 如果 E是 E1 op E2形式的表達(dá)式，其中 op是任何二元操作符，則 E的后綴式為 E1? E2? op，其中 E1? 和 E2? 分別為 E1 和 E2的后綴式。 3. 如果 E是 (E1)形式的表達(dá)式，則 E1 的后綴式就是 E的后綴式。 ? 逆波蘭表示法不用括號(hào) 。 只要知道每個(gè)算符的目數(shù) ， 對(duì)于后綴式 ， 不論從哪一端進(jìn)行掃描 ， 都能對(duì)它進(jìn)行唯一分解 。 ? 后綴式的計(jì)算 ?用一個(gè)棧實(shí)現(xiàn) 。 ?一般的計(jì)算過(guò)程是：自左至右掃描后綴式 ，每碰到運(yùn)算量就把它推進(jìn)棧 。 每碰到 k目運(yùn)算符就把它作用于棧頂?shù)?k個(gè)項(xiàng) ， 并用運(yùn)算結(jié)果代替這 k個(gè)項(xiàng) 。 ?把表達(dá)式翻譯成后綴式的語(yǔ)義規(guī)則描述 產(chǎn)生式 E→E (1)op E(2) E→ (E (1)) E→id 語(yǔ)義動(dòng)作 := E(1).code || E(2).code ||op := E(1).code :=id ? E后綴形式 ? op表示任意二元操作符 ? “ ||”表示后綴形式的連接 。 ? 數(shù)組 POST存放后綴式： k為下標(biāo)，初值為 1 ? 上述語(yǔ)義動(dòng)作可實(shí)現(xiàn)為： 產(chǎn)生式 程序段 E→E(1)op E(2) {POST[k]:=op。k:=k+1} E→ (E(1)) {} E→i {POST[k]:=i。k:=k+1} ? 例：輸入串 a+b+c的分析和翻譯 POST： 1 2 3 4 5 a b + c + ? 圖表示法 ?圖表示法 ?DAG ?抽象語(yǔ)法樹 圖表示法 ? 無(wú)循環(huán)有向圖 (Directed Acyclic Graph， 簡(jiǎn)稱 DAG) ?對(duì)表達(dá)式中的每個(gè)子表達(dá)式， DAG中都有一個(gè)結(jié)點(diǎn) ?一個(gè)內(nèi)部結(jié)點(diǎn)代表一個(gè)操作符，它的孩子代表操作數(shù) ?在一個(gè) DAG中代表公共子表達(dá)式的結(jié)點(diǎn)具有多個(gè)父結(jié)點(diǎn) a:=b*(c)+b*(c)的圖表示法 assign a + * b uminus c DAG assign a + * b uminus c 抽象語(yǔ)法樹 * b uminus c 產(chǎn)生賦值語(yǔ)句抽象語(yǔ)法樹的屬性文法 產(chǎn) 生 式 語(yǔ)義規(guī)則 S→id:=E :=mknode(‘a(chǎn)ssign’, mkleaf(id,),) E→E 1+E2 :=mknode(‘+’,) E→E 1*E2 :=mknode(‘*’,) E→ E1 :=mknode(‘uminus’,) E→ (E 1) := E→id :=mkleaf(id,) 三地址代碼 ? 三地址代碼 x:=y op z ? 表達(dá)式 x + y ? z翻譯成的三地址語(yǔ)句序列是 t1 := y ? z t2 := x + t1 出于語(yǔ)句的右邊只有一個(gè)算符的考慮 ? 三地址代碼可以看成是抽象語(yǔ)法樹或 DAG的一種線性表示 三地址代碼是語(yǔ)法樹或 dag的一種線性表示 a := (?b + c?d ) + c?d 語(yǔ)法樹的代碼 dag的代碼 t1 := ?b t2 := c ? d t3 := t1 + t2 t4 := c ? d t5 := t3 + t4 a := t5 新增加的名字對(duì)應(yīng)樹 /圖中的內(nèi)部結(jié)點(diǎn) assign a + + ? ? b c d c d uminus 語(yǔ)法樹 三地址代碼是語(yǔ)法樹或 dag的一種線性表示 a := (?b + c?d ) + c?d 語(yǔ)法樹的代碼 dag的代碼 t1 := ?b t2 := c ? d t3 := t1 + t2 t4 := t3 + t2 a := t4 新增加的名字對(duì)應(yīng)樹 /圖中的內(nèi)部結(jié)點(diǎn) assign a + + ? b c d uminus (b) dag 三地址語(yǔ)句的種類 本書常用的三地址語(yǔ)句 ? 賦值語(yǔ)句 x:=y op z。 x:=op y。 x:= y ? 無(wú)條件轉(zhuǎn)移 goto L ? 條件轉(zhuǎn)移 if x relop y goto L ? 過(guò)程調(diào)用 param x 和 call p , n ? 過(guò)程返回 return y ? 索引賦值 x := y[i]和 x[i] := y ? 地址和指針賦值 x := amp。y， x := ?y和 ?x := y ? 生成三地址代碼時(shí)， 臨時(shí)變量 的名字對(duì)應(yīng)抽象語(yǔ)法樹的 內(nèi)部結(jié)點(diǎn) ? id:=E ?對(duì)表達(dá)式 E求值并置于變量 T中值 ?:=T 從賦值語(yǔ)句生成三地址代碼的 S屬性文法 ? 非終結(jié)符號(hào) S有綜合屬性 ， 它代表賦值語(yǔ)句 S的三地址代碼。 ? 非終結(jié)符號(hào) E有如下兩個(gè)屬性： ? E值的名字 。 ? E求值的三地址語(yǔ)句序列 。 ?函數(shù) newtemp的功能是 ， 每次調(diào)用它時(shí) ， 將返回一個(gè)不同臨時(shí)變量名字 ,如 T1,T2,…。 為賦值語(yǔ)句生成三地址代碼的 S屬性文法定義 產(chǎn)生式 語(yǔ)義規(guī)則 S→id:=E := || gen( ‘:=’ ) E→E 1+E2 :=newtemp。 := || || gen( ‘:=’ ‘+’ ) E→E 1*E2 :=newtemp。 := || || gen( ‘:=’ ‘*’ ) E→ E1 :=newtemp。 := || gen( ‘:=’ ‘uminus’ ) E→ (E 1) :=。 := E→id :=。 =‘ ’ 三地址語(yǔ)句 三地址語(yǔ)句可看成中間代碼的一種抽象形式 .編譯程序中 ,三地址代碼語(yǔ)句的具體實(shí)現(xiàn)可用記錄表示 .通常有三種表示方法 :四元式、三元式、間接三元式 。 ? 四元式 ?一個(gè)帶有四個(gè)域的記錄結(jié)構(gòu)，這四個(gè)域分別稱為 op, arg1, arg2及 result op arg1 arg2 result (0) uminus c T1 (1) * b T1 T2 (2) uminus c T3 (3) * b T3 T4 (4) + T2 T4 T5 (5) := T5 a 三地址語(yǔ)句 ? 三元式 ?通過(guò)計(jì)算臨時(shí)變量值的語(yǔ)句的位置來(lái)引用這個(gè)臨時(shí)變量 ?三個(gè)域： op、 arg1和 arg2 op arg1 arg2 (0) uminus c (1) * b (0) (2) uminus c (3) * b (2) (4) + (1) (3) (5) assign a (4) 三地址語(yǔ)句 ? x[i]:=y op arg1 arg2 (0) [ ] = x i (1) assign （ 0） y ? x:=y[i] op arg1 arg2 (0) = [ ] y i (1) assign x (0) 三地址語(yǔ)句 ? 間接三元式 ?為了便于優(yōu)化 ， 用 三元式表 +間接碼表 表示中間代碼 ?間接碼表