編譯原理-第七章

第七章語(yǔ)義分析和中間代碼生成1、編譯程序的任務(wù)是把源語(yǔ)言程序翻譯成目標(biāo)程序，有些編譯程序在編譯過程中，不產(chǎn)生中間語(yǔ)言，而是直接從源語(yǔ)言程序翻譯成目標(biāo)語(yǔ)言程序。源程序編譯程序目標(biāo)代碼

以上編譯過程省略了中間語(yǔ)言，它不利于編譯所產(chǎn)生的目標(biāo)代碼的優(yōu)化.為了產(chǎn)生高質(zhì)量的代碼，可以將源語(yǔ)言程序首先翻譯成一種特殊形式的中間語(yǔ)言代碼形式，并對(duì)其進(jìn)行優(yōu)化，然后再將它翻譯成最終的目標(biāo)代碼。源程序語(yǔ)法分析中間代碼優(yōu)化優(yōu)化后中間代碼目標(biāo)代碼代碼生成中間代碼

中間代碼也叫中間語(yǔ)言（Intermediatecode/language）是：源程序的一種內(nèi)部表示，不依賴目標(biāo)機(jī)的結(jié)構(gòu)，復(fù)雜性介于源語(yǔ)言和機(jī)器語(yǔ)言之間。中間代碼的優(yōu)點(diǎn)1、邏輯結(jié)構(gòu)清楚；2、利于不同目標(biāo)機(jī)上實(shí)現(xiàn)同一種語(yǔ)言；3、利于進(jìn)行與機(jī)器無關(guān)的優(yōu)化；語(yǔ)義分析在詞法分析和語(yǔ)法分析之后，編譯程序要完成語(yǔ)義分析和翻譯工作。由于編譯器完成的分析是靜態(tài)定義的，所以，語(yǔ)義分析也可稱作靜態(tài)語(yǔ)義分析（staticsemanticanalysis）。語(yǔ)義分析的具體工作1、類型檢查；2、控制流檢查；3、一致性檢查；4、相關(guān)名字檢查語(yǔ)法制導(dǎo)翻譯對(duì)文法中的每個(gè)產(chǎn)生式都附加一個(gè)語(yǔ)義動(dòng)作或語(yǔ)義子程序，且在語(yǔ)法分析過程中，每當(dāng)需要使用一個(gè)產(chǎn)生式進(jìn)行推導(dǎo)或規(guī)約時(shí)，語(yǔ)法分析程序除執(zhí)行相應(yīng)的語(yǔ)法分析動(dòng)作之外，還要執(zhí)行相應(yīng)地語(yǔ)義動(dòng)作或語(yǔ)義子程序。每個(gè)語(yǔ)義子程序都指明了相應(yīng)產(chǎn)生式中各個(gè)符號(hào)的具體含義，并規(guī)定了使用該產(chǎn)生式進(jìn)行分析時(shí)所應(yīng)采取的語(yǔ)義動(dòng)作。由此可見：抽象文法符號(hào)的具體語(yǔ)義信息，是在語(yǔ)法分析同步的語(yǔ)義處理過程中獲取和加工的。屬性文法

將語(yǔ)義以“屬性”的形式附加到各文法符號(hào)上，再根據(jù)產(chǎn)生式所蘊(yùn)含的語(yǔ)義，給出每個(gè)文法符號(hào)的屬性的求值規(guī)則，從而形成一種帶有語(yǔ)義屬性的前后文無關(guān)文法，即屬性文法。屬性

一個(gè)文法符號(hào)X的語(yǔ)義信息我們稱之為語(yǔ)義屬性或簡(jiǎn)稱為屬性（Atrributes）X.TYPE表示為X的類型X.VAL表示為X的值例:對(duì)于文法:E

→E+T|TT→digit

例語(yǔ)法制導(dǎo)翻譯的實(shí)質(zhì)

根據(jù)文法中每個(gè)產(chǎn)生式所蘊(yùn)含的語(yǔ)義，為其配備一個(gè)（或多個(gè)）語(yǔ)句或子程序，對(duì)所要完成的功能進(jìn)行描述，在語(yǔ)法分析過程中，當(dāng)分析器使用該產(chǎn)生式進(jìn)行語(yǔ)法分析時(shí)（不論是推導(dǎo)還是規(guī)約），除完成語(yǔ)法分析動(dòng)作之外，還將調(diào)用為其配備的語(yǔ)義子程序，進(jìn)行相應(yīng)地語(yǔ)義處理，完成語(yǔ)義翻譯工作。中間代碼常見的幾種形式1、后綴式2、圖表示法抽象語(yǔ)法樹、DAG圖3、三地址代碼三元式、四元式、間接三元式后綴式

后綴式是波蘭邏輯學(xué)家盧卡西維奇（J.Lukasiewicz）提出的一種對(duì)表達(dá)式的表示方法：每一運(yùn)算符都置于其運(yùn)算對(duì)象之后，即操作數(shù)寫在前面，算符寫在后面。

它的特點(diǎn)是：表達(dá)式中各個(gè)運(yùn)算是按運(yùn)算符出現(xiàn)的順序進(jìn)行的，故無需用括號(hào)來指示運(yùn)算順序，因而又稱為無括號(hào)式。實(shí)例

表達(dá)式（中綴式）：A+B*（C-D）+E/（C-D）

后綴式：CD-B*A+CD-E/+表達(dá)式(中綴式):（a=0∧b>3）∨（e∧x

>y）后綴式:a0=b3>xy>e∧∨∧

結(jié)論從以上兩個(gè)例子我們可得出：1、在兩種表示中，運(yùn)算對(duì)象出現(xiàn)的順序相同；2、在后綴表示中，運(yùn)算符按實(shí)際計(jì)算順序從左到右排列，且每一運(yùn)算符總是跟在運(yùn)算對(duì)象之后。翻譯成后綴式的語(yǔ)義描述見P167表7.1。后綴式的推廣條件語(yǔ)句的翻譯：IfeTHENS1elseS2圖表示法-抽象語(yǔ)法樹

在語(yǔ)法樹中去掉一些對(duì)翻譯不必要的信息后，獲得的更有效的源程序的中間表示，這種經(jīng)過變換后的語(yǔ)法樹稱為抽象語(yǔ)法樹。在抽象語(yǔ)法樹中，操作符和關(guān)鍵字都不作為葉子節(jié)點(diǎn)出現(xiàn)，而是把它們作為內(nèi)部節(jié)點(diǎn)，即這些葉子節(jié)點(diǎn)的父節(jié)點(diǎn)。

例1

if-then-elseBS1S2S→ifBthenS1elseS2例1

++*a*-da-bcbca+a*（b-c）+（b-c）*d翻譯成抽象語(yǔ)法樹的屬性文法見P169表7.2圖表示法-DAG圖DAG（DirectedAcyclicGraph）有向無循環(huán)圖對(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)（與抽象語(yǔ)法樹中公共子表達(dá)式被表示為重復(fù)的子樹不同）例

++**da-bca+a*（b-c）+（b-c）*d抽象語(yǔ)法樹的表示方法1、每一個(gè)結(jié)點(diǎn)用一個(gè)記錄來表示，該記錄包括一個(gè)運(yùn)算符域和若干個(gè)指向子結(jié)點(diǎn)的指針域。例：a：=b*-c+b*-cassignassigna+a+***b-b-b-ccc

抽象語(yǔ)法樹DAG方法1assign??ida+??*??idbuminus?idc*??idbUminus?idc方法2把所有的結(jié)點(diǎn)安排在一個(gè)記錄的數(shù)組中，結(jié)點(diǎn)的位置或索引作為指向地點(diǎn)的指針。

三地址代碼三地址代碼最基本的用法形式:

x:=yopz其中x、y、z為名字、常數(shù)或編譯時(shí)產(chǎn)生的臨時(shí)變量；op代表運(yùn)算符號(hào)。每個(gè)語(yǔ)句的右邊只能有一個(gè)運(yùn)算符。例如：x+y*z可以翻譯為：

T1：=y*zT2：=x+T1T1、T2位編譯時(shí)產(chǎn)生的臨時(shí)變量三地址代碼可以看成是抽象語(yǔ)法樹一種線性表示assigna+**b-b-cc

抽象語(yǔ)法樹

T1:=-cT2:=b*T1T3:=-cT4:=b*T3T5:=T2+T4a:=T5三地址代碼三地址代碼可以看成是DAG的一種線性表示assigna+*b-c

DAG

T1:=-cT2:=b*T1T3:=T2+T2a:=T3三地址代碼最后看P171，表7.3三地址碼的各種形式：P170x:=yopzx:=opz

x:=yGotoLifxrelopygotoL

ifagotoL

Paramxcallp,n

returnyx:=y[i]x[i]:=yx:=&y

x:=*y

*x:=y

賦值語(yǔ)句翻譯為三地址碼的屬性文法P171，表7.3三地址代碼—四元式四元式實(shí)際上是一種“三地址語(yǔ)句”的等價(jià)表示，是一個(gè)帶有四個(gè)域的記錄結(jié)構(gòu)。它的一般形式為：（op，arg1，arg2，result）需要指出的是：每個(gè)四元式只能有一個(gè)運(yùn)算符，所以，一個(gè)復(fù)雜的表達(dá)式只能由多個(gè)四元式構(gòu)成的序列表示。例

a：=b*-c+b*-c三地址代碼-三元式

三元式顧名思義就是帶有三個(gè)域的記錄結(jié)構(gòu)，他的一般形式為（i）（op，arg1，arg2）其中，（i）為三元式的編號(hào)，也代表了該式的運(yùn)算結(jié)果，op，arg1，arg2的含義與四元式類似，區(qū)別在于arg可以是某三元式的序號(hào)，表示用該三元式的結(jié)果作為運(yùn)算對(duì)象。例a：=b*-c+b*-c三元式和四元式的比較1、無論在一個(gè)三元式序列還是四元式序列中，各個(gè)三元式或四元式都是按相應(yīng)表達(dá)式的實(shí)際運(yùn)算順序出現(xiàn)的；相同點(diǎn)：2、對(duì)同一表達(dá)式而言，所需的三元式或四元式的個(gè)數(shù)一般都是相同的。三元式和四元式的比較1、由于三元式?jīng)]有result字段，且不需要臨時(shí)變量，故三元式比四元式占用的存儲(chǔ)空間少；不同點(diǎn)：2、在進(jìn)行代碼優(yōu)化處理時(shí)，常常需要挪動(dòng)一些運(yùn)算的位置，這對(duì)于三元式序列來說是很困難的，但對(duì)于四元式來說，由于四元式之間的相互聯(lián)系是通過臨時(shí)變量來實(shí)現(xiàn)的，所以，更改其中一些四元式給整個(gè)系列帶來的影響就比較小。三地址代碼-間接三元式

建立兩個(gè)與三元式有關(guān)的表格，一個(gè)稱為三元式表，用于存放各三元式本身；另一個(gè)稱為執(zhí)行表，它按照三元式的執(zhí)行順序，依次列出相應(yīng)各三元式在三元式表中的位置，也就是說我們用一個(gè)三元式表連同執(zhí)行表來表示中間代碼。通常我們稱這種表示方法為間接三元式。例x：=（a+b）*cb：=a+by：=c*（a+b）三元式x：=（a+b）*cb：=a+by：=c*（a+b）

（1）（+，a，b）（5）（+，a，b）（2）（*，（1），c）（6）（*，c，（5））（3）（：=，x，（2））（7）（：=，y，（6））（4）（：=，b，（1））

間接三元式x：=（a+b）*c

b：=a+b

y：=c*（a+b）執(zhí)行表三元式表（1）（1）（+，a，b）（2）（2）（*，（1），c）（3）（3）（：=，x，（2））（4）（4）（：=，b，（1））（1）（5）（：=，y，（2））（2）（5）三元式與間接三元式之間的區(qū)別1、由于間接三元式在執(zhí)行表中已經(jīng)依次列出每次要執(zhí)行的那個(gè)三元式，若其中有相同的三元式，則僅需在三元式表中保存其中之一，即三元式的項(xiàng)數(shù)一般比執(zhí)行表的項(xiàng)數(shù)少；2、當(dāng)進(jìn)行代碼優(yōu)化需要挪動(dòng)運(yùn)算順序時(shí)，則只需對(duì)執(zhí)行表進(jìn)行相應(yīng)地調(diào)整，而不必再改動(dòng)三元式本身，這樣，就避免了前面講到的因改變?nèi)降捻樞蛩鸬穆闊?。四元式：一般形?(Op，arg1，arg2，result)arg1、arg2為參加運(yùn)算的兩個(gè)分量result為運(yùn)算結(jié)果若為單目運(yùn)算，arg2為空，用“-”表示舉例說明：1.表達(dá)式的四元式：例1.a*b+c/d(*,a,b,T1)(/,c,d,T2)(+,T1,T2,T)例2.-(a*b-c)(*,a,b,T1)(-,T1,c,T2)(@,T2,-,T)@表示單目運(yùn)算減2.賦值語(yǔ)句的四元式：把賦值看成一種運(yùn)算，arg2為空例1：x:=10(:=,10,-,x)例2：x:=-(a*b-c)(*,a,b,T1)

(-,T1,c,T2)

(@,T2,-,T)

(:=,T,-,x)3.轉(zhuǎn)向語(yǔ)句的四元式：有以下三種跳轉(zhuǎn)四元式：(jnz,a,-,p)表示ifagotop；(jrop,x,y,p)表示ifxropygotop；(j,-,-,p)表示gotop；rop為：=，<>，<=<，>=，>

4.條件語(yǔ)句的四元式：例1：ifa<bthenx:=a+belsex:=a-b對(duì)應(yīng)的四元式為：(1)(j<,a,b,

)(2)(j,-,-,

)(3)(+,a,b,T1)(4)(:=,T1,-,x)(5)(j,-,-,

)(6)(-,a,b,T2)(7)(:=,T2,-,x)(8)……685.循環(huán)語(yǔ)句的四元式

待討論循環(huán)語(yǔ)句的翻譯時(shí)介紹。回填回填回填3例2：ifa<bande＞dthenx:=a+belsex:=a-b例3：ifa<bore＞dthenx:=a+belsex:=a-b

語(yǔ)法制導(dǎo)的翻譯方法：

就是對(duì)文法中的每個(gè)產(chǎn)生式都附加一個(gè)語(yǔ)義動(dòng)作或語(yǔ)義子程序，且在語(yǔ)法分析過程中，每當(dāng)需要使用一個(gè)產(chǎn)生式進(jìn)行推導(dǎo)或歸約時(shí)，語(yǔ)法分析程序除執(zhí)行相應(yīng)的語(yǔ)法分析動(dòng)作之外，還要執(zhí)行相應(yīng)地語(yǔ)義動(dòng)作或語(yǔ)義子程序。每個(gè)語(yǔ)義子程序都指明了相應(yīng)產(chǎn)生式中各個(gè)符號(hào)的具體含義，并規(guī)定了使用該產(chǎn)生式進(jìn)行分析時(shí)所應(yīng)采取的語(yǔ)義動(dòng)作。翻譯過程見P171表7。3。這種模式既把語(yǔ)法分析與語(yǔ)義處理分開，又令其平行地進(jìn)行，讓其在同一遍掃描中同時(shí)完成語(yǔ)法分析和語(yǔ)義處理兩項(xiàng)工作。一.過程中的說明語(yǔ)句說明語(yǔ)句的翻譯，主要工作是填符號(hào)表、分配地址說明語(yǔ)句的文法產(chǎn)生式及語(yǔ)義動(dòng)作如下：T→integer {T.type:=integer;T.width:=4}T→real {T.type:=real;T.width:=8}T→array[num]ofT1 {T.type:=array(num.val,T1.type); T.width:=num.val*T1.width}T→↑T1 {T.type:=pointer(T1.type); T.width:=4}D→D;DD→id:T {enter(,T.type,offset);offset:=offset+T.width}P→MD {offset:=0}M→ε{offset:=0}offset為存儲(chǔ)空間分配指針，每個(gè)過程均從0開始。enter為填符號(hào)表過程7.2說明語(yǔ)句的翻譯

例：a:integer;b:real7.3賦值語(yǔ)句的翻譯S→id:=E{p:=lookup();ifp<>nilthenemit(id.place,‘:=’,E.place)elseerror }E→(E1){E.place:=E1.place;}E→-E1{E.place:=newtemp;emit(E.place,‘:=’,‘uminus’,E1.place)}E→E1*E2{E.place:=newtemp; emit(E.place,‘:=’,E1.place‘*’,E2.place)}E→E1+E2{E.place:=newtemp; emit(E.place,‘:=’,E1.place‘+’,E2.place)}7.3.1簡(jiǎn)單算術(shù)表達(dá)式及賦值語(yǔ)句的翻譯簡(jiǎn)單算術(shù)表達(dá)式及賦值語(yǔ)句的產(chǎn)生式及語(yǔ)義動(dòng)作如下：Lookup為查符號(hào)表過程Emit過程用于生成三地址碼指令語(yǔ)句并送往輸出文件E→id{p:=lookup();ifp<>nilthenE.place:=pelseerror}掌握1、2、lookup()3、

emit(…)的含義7.3.2數(shù)組元素的引用一、數(shù)組元素的地址計(jì)算1、一維數(shù)組設(shè)數(shù)組A[low..n],每個(gè)元素占w個(gè)單元，則LOC(A[i])=base+(i-low)*w

=i*w+(base-low*w)其中varpart=i*wC=low*wconspart=base-C即地址D=varpart+conspart7.3.2數(shù)組元素的引用一、數(shù)組元素的地址計(jì)算2、二維數(shù)組(按行存放）設(shè)i1,i2的下界為low1,low2,數(shù)組是n1×n2,每個(gè)元素占w個(gè)單元，則LOC(A[i1,i2])=base+((i1-low1)*n2+i2-low2)*w

=((i1*n2)+i2)*w+(base-((low1*n2)+low2)*w)其中varpart=((i1*n2)+i2)*w

C=((low1*n2)+low2)*w)conspart=base-C即地址D=varpart+conspart推廣到k維數(shù)組(按行存放）LOC(A[i1,i2，…,ik])=(…(i1*n2+i2)n3+i3)…)nk+ik)*w+base-(…(low1*n2+low2)n3+low3)…)nk+lowk)*w對(duì)C或varpart的計(jì)算，可用遞歸公式e1=i1em=em-1*nm+im當(dāng)m=k時(shí)，ek*w7.3.2數(shù)組元素的引用一、數(shù)組元素的地址計(jì)算例：A[x]

地址可變部分為x*W,應(yīng)生成指令：

(T’:=X*W)A[x,y]地址可變部分為(x*n2+y)*W,應(yīng)生成指令：

(T1:=X*n2)

(T1:=T1+y)

(T’:=T1*W)A[x,y,z]地址可變部分為((x*n2+y)*n3+z)*W,應(yīng)生成指令：(T1:=X*n2)

(T1:=T1+y)(T2:=T1*n3)

(T3:=T2+z)

(T’:=T3*W)地址不變部分的指令為:

(T=A-C)地址結(jié)果指令為:

(T’’=T[T’])二、賦值語(yǔ)句中數(shù)組元素的翻譯賦值語(yǔ)句的文法：S→id:=EE→E1+E2E→E1*E2E→-E1E→(E1)E→id

增加L→id[Elist]|idElist→Elist,E|E為便于語(yǔ)義處理，再改為L(zhǎng)→Elist]|idElist→Elist,E|id[ELL含數(shù)組元素的賦值語(yǔ)句的文法p181-183(1)S→L:=E(2)E→E+E(3)E→(E)(4)E→L(5)L→Elist](6)L→id(7)Elist→Elist,E(8)Elist→id[E引進(jìn)如下語(yǔ)義變量和過程：1.Elist.array2.Elist.ndim3.limit(array,j)4.Elist.place5.L.place,L.offset

含有數(shù)組的賦值語(yǔ)句文法產(chǎn)生式如下： (1)S→L:=E

(2)E→E+E

(3)E→(E)

(4)E→L

(5)L→id

(6)Elist→id[E

(7)Elist→Elist,E

(8)L→Elist]例：x:=A[y,z]的語(yǔ)法樹如右圖：xSL:=ELE]ElistEElist,Lz[LAy（3）L→Elist]

{L.place:=newtemp;emit(L.place‘:=’Elist.array‘-’C);

L.offset:=neswtemp;

emit(L.offset‘:=’w‘﹡’Elist.place)}（1）Elist

→id[E

{Elist.place:=E.place;Elist.ndim:=1;

Elist.array:=id.place}（2）Elist→Elist1，E

{t:=newtemp; m:=Elist1.ndim+1;

emit(t‘:=’Elist1.place‘﹡’limit(Elist1.array，m));

emit(t‘:=’t‘+’E.place);

Elist.array:=Elist1.array;

Elist.place:=t; Elist.ndim:=m}（4）L→id

{L.place:=id.place;L.offset:=null}其相應(yīng)的語(yǔ)義動(dòng)作如下：計(jì)算：Em=Em-1*nm+im賦初值：(E1=i1)例見P183（7）E

→E1+E2

{E.place:=newtemp;

emit(E.place‘:=’E1.place‘+’E2.place)}（6）E

→(E1)

{E.place:=E1.place}（5）E→L

{ifL.offset=nullthenE.place:=L.place

elsebeginE.place:=newtemp;

emit(E.place‘:=’L.place‘[’L.offset‘]’)

end}（8）S→L:=E

{ifL.offset=nullthen/*L是簡(jiǎn)單變量*/

emit(L.place‘:=’E.place)

elseemit(L.place‘[’L.offset‘]’‘:=’E.place)}7.4布爾表達(dá)式的翻譯文法：E→EorE|EandE|notE|(E)|idrelopid|id

布爾表達(dá)式是由布爾運(yùn)算符作用于布爾變量或關(guān)系表達(dá)式組成。布爾運(yùn)算符：notandor關(guān)系表達(dá)式：E1ropE27.4布爾表達(dá)式的翻譯布爾表達(dá)式的計(jì)算通常有兩種方法：

1.嚴(yán)格按計(jì)算規(guī)則進(jìn)行：例：1or(not0and0)or0=1or(1and0)or0=1or0or0=1or0=12.采取優(yōu)化措施，省略計(jì)算步驟：即：AorB→ifAthen1elseBAandB→ifAthenBelse0notA→ifAthen0else1在程序中布爾表達(dá)式的作用有兩個(gè)方面：計(jì)算邏輯值；控制程序流程；因此討論布爾表達(dá)式的兩種翻譯方式：邏輯值計(jì)算：Ex1.aorbandnotc翻譯為：T1:=notcT2:=bandT1T3:=aorT2Ex2.a<b翻譯為:100:ifa<bgoto103101:T:=0102:goto104103:T:=1104:Ex3.a<borc<dande<f的三地址代碼100)ifa<bgoto103105)T2:=0110)goto112101)T1:=0106)goto108111)T3:=1102)goto104107)T2:=1112)T4:=T2andT3103)T1:=1108)ife<fgoto111113)T5:=T1orT4104)ifc>dgoto107109)T3:=0則計(jì)算邏輯值的布爾表達(dá)式的語(yǔ)義動(dòng)作為：P186E→id{E.place:=id.place}E→id1relopid2{E.place:=newtemp;emit(‘if’id1.placerelop.Opid2.Place‘goto’nextstat+3); emit(E.place‘:=’‘0’); emit(‘goto’nextstat+2);emit(E.place‘:=’‘1’)}E→(E1) {E.place:=E1.place}E→notE1 {E.place:=newtemp;emit(E.place‘:=’‘not’E1.place)}E→E1andE2 {E.place:=newtemp; emit(E.place‘:=’E1.place‘a(chǎn)nd’E2.place)}E→E1orE2 {E.place:=newtemp; emit(E.place‘:=’E1.place‘or’E2.place)}二、作為條件控制的布爾式翻譯

由于條件語(yǔ)句：if

E

thenS1elseS2中

E的作用僅在于控制對(duì)

S1或S2

的選擇，而E的值無須保留,因此賦予E兩個(gè)新的語(yǔ)義值:

E.true(真出口,出向S1)

E.false(假出口,出向S2)其含義及作用見圖：E.codeS1.codeGotos.nextS2.code…

E.true

E.falseE.true：E.false：

S.next:ifEthenS1elseS2Ex1:ifa>corb<dthens1elses2翻譯：ifa>cgotoL2gotoL1L1:ifb<dgotoL2gotoL3L2:S1的代碼

gotoSnextL3:S2的代碼Snext:二、作為條件控制的布爾式翻譯思路對(duì)布爾表達(dá)式E,引入標(biāo)號(hào)E.ture和E.falseE形如a<bE形如E1orE2E形如E1andE2E形如notE1seeP188table7.7Ex2.a<borc<dande<f的三地址代碼設(shè)整個(gè)表達(dá)式的真假出口為Etrue和Efalse,則代碼：Ifa<bgotoEturegotoL1L1:ifc<dgotoL2gotoEfalseL2:ife<fgotoEturegotoEfalse

seeP188table7.71、四元式形式表示三地址碼（jnz,a,,p)(jrop,x,y,p)(j,,,p)2、關(guān)于拉鏈回填問題寫出以下語(yǔ)句的四元式形式：Ex1:a<borc<dande<fEx2:Aor(Bandnot(CorD))seeP190二.作為條件控制的布爾表達(dá)式的翻譯（一遍掃描）

對(duì)于條件語(yǔ)句：if

E

thenS1elseS2翻譯分析到

E

時(shí)，S1、S2并未進(jìn)行翻譯，既使計(jì)算出E的結(jié)果也不知跳轉(zhuǎn)到何處，因此賦予E兩個(gè)新的語(yǔ)義值:

E.true

(真出口,記錄跳往S1的語(yǔ)句號(hào),待回填)

E.false(假出口,記錄跳往S2的語(yǔ)句號(hào),待回填)其含義及作用見圖：E.codeS1.codeGotos.nextS2.code…

E.true

E.false[E.true][E.false]

S.next

另外：當(dāng)E自身較復(fù)雜時(shí)，跳往S1、S2的語(yǔ)句可能為多條，為記錄這多條語(yǔ)句，可以將這些語(yǔ)句建一鏈表:并改：E.true為

E.truelist(記錄跳往S1的語(yǔ)句鏈表表頭)

E.false為E.falselist(記錄跳往S2的語(yǔ)句鏈表表頭)

(※,※,※,0)0為鏈尾標(biāo)識(shí)

……(q)(※,※,※,P)……(r)(※,※,※,q)←鏈表表頭為r此外：為記錄下一條即將產(chǎn)生的四元式號(hào)，以便及時(shí)回填跳往該四元式的語(yǔ)句，我們?cè)谖姆ㄖ胁迦敕墙K結(jié)符M，用于在翻譯分析時(shí)遇見M即記錄四元式號(hào)，則布爾表達(dá)式文法修改為：

(1)M→ε

(2)E→E1orME2|E1and

ME2|notE1|(E1)|id1relopid2|id上述文法的語(yǔ)義動(dòng)作如下：(1)M→ε

{M.quad:=nextquad}(7)E→id {E.truelist:=makelist(nextquad);E.falselist:=makelist(nextquad+1);emit(‘jnz’‘,’id.place‘,’‘-‘‘,’‘0’);emit(‘j,-,-,0’)}(6)E→id1relopid2{E.truelist:=makelist(nextquad);E.falselist:=makelist(nextquad+1);emit(‘j’relop.op‘,’id1.place‘,’id2.place‘,’‘0’);emit(‘j,-,-,0’)(5)E→(E1)

{E.truelist:=E1.truelist;E.falselist:=E1.falselist}

(4)E→notE1{E.truelist:=E1.falselist;E.falselist:=E1.truelist}(2)

E→E1orME2{backpatch(E1.falselist,M.quad);E.truelist:=merge(E1.truelist,E2.truelist);E.falselist:=E2.falselist}(3)

E→E1andME2{backpatch(E1.truelist,M.quad);E.truelist:=E2.truelist;E.falselist:=merge(E1.falselist,E2.falselist)}即將產(chǎn)生的四元式號(hào)（地址）將M.quad回填至E1.truelist為表頭的鏈表上各四元式中將E1.falselist和E2.falselist為表頭的兩條鏈合并創(chuàng)建一條新鏈表nextquad為該鏈中唯一一個(gè)四元式的地址寫出以下語(yǔ)句的四元式形式：Ex1:a<borc<dande<f7.5控制語(yǔ)句的翻譯一.控制流語(yǔ)句S→ifEthenS1|ifEthenS1elseS2|whileEdoS1上述的紅色跳轉(zhuǎn)語(yǔ)句相當(dāng)于S的出口，在對(duì)S語(yǔ)句進(jìn)行翻譯分析時(shí)，其跳轉(zhuǎn)目標(biāo)并不確定，因此賦予S語(yǔ)義值:S.next。E.falselistE.codeS1.code…E.truelist[E.truelist][E.falselist]E.codeS1.codeGotos.nextS2.code…E.truelistE.falselist[E.truelist][E.falselist]S.nextE.codeS1.codegotoS.begin…E.truelistE.falselist[E.truelist][E.falselist]S.begin此外，考慮到語(yǔ)句可以嵌套等因素，S的出口語(yǔ)句可能有多條，也需要建立鏈表，因此將S.next改為S.nextlist。S.nextlist：記錄S的出口語(yǔ)句鏈表表頭,待回填。S.next：S的出口,記錄跳出S的語(yǔ)句號(hào),待回填。例：

ifE1then

{ifE2thenS1}

elseS2E1.codeE2.codeS1.codeGotoS.nextlistS2.code…E2.truelistE2.falselist[E2.truelist]S.nextlist

[E2.falselist]E1.truelistE1.falselist[E1.truelist][E1.falselist]更為完整的控制語(yǔ)句文法產(chǎn)生式如下：

(1)S→ifEthenS(6)L→L;S(2)|ifEthenSelseS(7)

|S(3)