編譯原理語義分析與中間代碼生成

S.PO.P語義分析、生成中間代碼生成目標程序代碼優(yōu)化語法分析程序詞法分析程序錯誤處理符號表管理第8章語義分析與中間代碼生成要求明確語義分析的任務(wù)明確屬性文法和語法制導(dǎo)翻譯的含義明確自底向上和自頂向下語法制導(dǎo)翻譯的區(qū)別和特點明確生成中間代碼的目的，中間代碼的幾種形式

教學目標8.1語義分析的任務(wù)8.2語法制導(dǎo)翻譯8.3中間代碼8.4簡單賦值語句的翻譯8.5布爾表達式的翻譯教學內(nèi)容詞法分析，語法分析：解決單詞和語言成分的識別及詞法和語法結(jié)構(gòu)的檢查。語法結(jié)構(gòu)可形式化地用一組產(chǎn)生式來描述。給定一組產(chǎn)生式，我們能夠很容易地將其分析器構(gòu)造出來。本章要介紹的是語義分析和中間代碼生成技術(shù)。程序語言中間代碼目標代碼翻譯翻譯根據(jù)語義規(guī)則對識別出的各種語法成份分析其含義，進行初步翻譯，生成相應(yīng)的中間代碼或直接生成目標代碼。（1）確定數(shù)據(jù)類型（2）語義檢查動態(tài)語義檢查：在運行時刻進行靜態(tài)語義檢查：在編譯時完成（3）識別含義，進行真正的翻譯8.1語義分析的任務(wù)①類型檢查。②控制流檢查，確?？刂普Z句有合法的轉(zhuǎn)向點。例如，C語言中的break語句使控制跳離包括該語句的最小的switch，while或for語句。如果不存在包括它的這樣的語句，則應(yīng)報錯。靜態(tài)語義檢查靜態(tài)語義檢查③一致性檢查。很多情況下要求對象只能被定義一次。例如，Ｃ語言中規(guī)定一個標識符在同一作用域中只能被說明一次，同一case語句的標號不能相同，枚舉類型的元素不能重復(fù)出現(xiàn)等。④相關(guān)名字檢查。有的語言中有時規(guī)定，同一名字必須出現(xiàn)兩次或多次。例如，Ada語言中，循環(huán)或程序塊可以有一個名字，它出現(xiàn)在這些結(jié)構(gòu)的開頭和結(jié)尾，如同語句括號一般，編譯程序必須檢查它們的配對情況。實際應(yīng)用中比較流行的語義分析方法：基于屬性文法的語法制導(dǎo)翻譯方法

8.2語法制導(dǎo)翻譯屬性文法是Knuth在1968年提出的屬性文法的特點是一種接近形式化的語義描述方法長于描述靜態(tài)語義、短于描述動態(tài)語義每個語法符號有相應(yīng)的屬性符號每個產(chǎn)生式有相應(yīng)計算屬性的規(guī)則屬性變量:=屬性表達式8.2.1屬性文法附加了一組屬性和運算（語義）規(guī)則的文法

文法符號X的屬性t常用X.t來表示語義規(guī)則是根據(jù)產(chǎn)生式所蘊涵的語義操作建立起來的，并與語義分析的目標有關(guān)不同的產(chǎn)生式對應(yīng)不同的語義規(guī)則不同的分析目標也對應(yīng)不同的語義規(guī)則

1.屬性的表示2.語義規(guī)則的表示語義信息屬性之間的關(guān)系靜態(tài)語義檢查、符號表操作、代碼生成及打印各種錯誤信息

非終結(jié)符E、T及F都有一個綜合屬性val,符號i有一個綜合屬性，它的值由詞法分析器提供。某些非終結(jié)符加下標是為了區(qū)分一個產(chǎn)生式中同一非終結(jié)符多次出現(xiàn)語義規(guī)則EE1+TETTT1*FTFF(E)Fi

E.val=E1.val+T.valE.val=T.val

T.val=T1.valF.valT.val=F.valF.val=E.valF.val=i.lexval產(chǎn)生式例8.1根據(jù)文法符號的語義，為文法符號設(shè)置屬性，用來表示文法符號的語義終結(jié)符使用單詞的屬性（id.val）保留字：if,begin,function,……常數(shù)：40.12,232,80,“TCP/IP”標識符：sum,tcc,id語法變量根據(jù)實際需要設(shè)定屬性表達式E：E.type，E.val屬性的設(shè)定8.2.2語法制導(dǎo)翻譯的過程語法制導(dǎo)翻譯：將語義規(guī)則與語法規(guī)則相結(jié)合，在語法分析的過程中通過執(zhí)行語義動作，計算語義屬性值，從而完成預(yù)定的翻譯工作。Yacc利用的就是語法制導(dǎo)翻譯方法，它使用符號$$表示產(chǎn)生式左端的屬性，$n表示存取產(chǎn)生式右端第n個文法符號相聯(lián)的屬性expr:expr'+'expr {$$=$1+$3;}自底向上語法制導(dǎo)翻譯自頂向下語法制導(dǎo)翻譯語法制導(dǎo)翻譯的實現(xiàn)語法制導(dǎo)翻譯分為兩種處理方法：（1）語法制導(dǎo)定義（自底向上）：對每個產(chǎn)生式編制一個語義子程序，在進行語法分析的過程中，當一個產(chǎn)生式獲得匹配時，就調(diào)用相應(yīng)的語義子程序?qū)崿F(xiàn)語義檢查與翻譯。這種實現(xiàn)方案隱藏了其中語義規(guī)則的計算次序等實現(xiàn)細節(jié)，不必規(guī)定翻譯順序。（2）翻譯方案（自頂向下）：在產(chǎn)生式右部的適當位置，插入相應(yīng)的語義動作，按照分析的進程，執(zhí)行遇到的語義動作。這是一種動作與分析交錯的實現(xiàn)方案。輸入符號串

分析樹

執(zhí)行語義規(guī)則

翻譯結(jié)果翻譯步驟（２）從分析樹得到描述結(jié)點屬性間依賴關(guān)系的依賴圖，由依賴圖得到語義規(guī)則的計算次序

（1）分析輸入符號串，建立分析語法樹（３）進行語義規(guī)則的計算，得到翻譯結(jié)果

8.2.3語法制導(dǎo)定義對每個產(chǎn)生式編制一個語義子程序在進行語法分析的過程中，當一個產(chǎn)生式獲得匹配時，就調(diào)用相應(yīng)的語義子程序?qū)崿F(xiàn)語義檢查與翻譯綜合屬性繼承屬性自底向上傳遞信息自頂向下（自左向右）傳遞信息1、文法非終結(jié)符既有綜合屬性，也可有繼承屬性；2、開始符號沒有繼承屬性；3、終結(jié)符只有綜合屬性，由詞法分析器提供。幾點說明：

print(E.val)打印由E產(chǎn)生的算術(shù)表達式的值，可認為這條規(guī)則定義了L的一個虛屬性。

LEEE1+TETTT1*FTFF(E)Fiprint(E.val)

E.val=E1.val+T.valE.val=T.val

T.val=T1.valF.val

T.val=F.valF.val=E.valF.val=i.lexval例8.２綜合屬性語義規(guī)則產(chǎn)生式一個結(jié)點的綜合屬性值是其子結(jié)點的某些屬性來決定的２+3*4的注釋分析樹通常使用自底向上的分析方法在每個結(jié)點處使用語義規(guī)則來計算綜合屬性值當一個產(chǎn)生式獲得匹配時，就調(diào)用相應(yīng)的語義子程序從葉結(jié)點到根結(jié)點進行計算只含有綜合屬性的語法制導(dǎo)定義稱為S屬性定義8.2.4S屬性定義與自底向上翻譯LR分析器可以改造為一個翻譯器，在對輸入串進行語法分析的同時對屬性進行計算LR分析器增加屬性值（語義）棧

步驟狀態(tài)棧符號棧屬性值棧剩余符號串分析動作10#?2+3*4#移進205#2?+3*4#用F→i歸約303#F?2+3*4#用T→F歸約402#T?2+3*4#用E→T歸約501#E?23*4#移進6016#E+?2?*4#移進70165#E+3?2??*4#用F→i歸約80163#E+F?2?3*4#用T→F歸約90169#E+T?2?3*4#移進1001697#E+T*?2?3?4#移進11016975#E+T*4?2?3??#用F→i歸約120169710#E+T*F?2?3?4#用T→T*F歸約130169#E+T?2?(12)#用E→E+T歸約1401#E?(14)#acc產(chǎn)生式語義規(guī)則DTLTintTfloatLL1,idLidL.in=T.typeT.type=intT.type=floatL1.in=L.inenter(id.entry,L.in)enter(id.entry,L.in)例8.3繼承屬性L.inintid1,id2,id3DL.in=intL.in=intL.in=intT.type=intintid2id1id3.，，一個結(jié)點的繼承屬性值是由其父結(jié)點或兄弟結(jié)點的某些屬性決定的DTLintLid2，id1圖示：屬性信息傳遞情況8.2.5L-屬性定義(L-屬性文法)包含綜合屬性和繼承屬性的屬性文法（語法制導(dǎo)定義）如：算術(shù)表達式求值的屬性文法、說明語句的屬性文法翻譯思想將語義動作插入到產(chǎn)生式的某個位置特征規(guī)定在語法分析中使用語義規(guī)則進行計算的次序保證當動作使用某屬性時，該屬性必須是有效的——最左派生表示形式：{……}例8.4：建立說明語句的翻譯方案將語義動作中繼承屬性的計算前移，使它出現(xiàn)在其相應(yīng)文法符號之前D→T{L.in:=T.type}LT→int{T.type:=integer}T→real{T.type:=real}L→{L1.in:=L.in}L1,id{addtype(id.entry,L.in)}L→id{addtype(id.entry,L.in)}realid1,id2的處理過程DT{L.in:=T.type}Lreal{T.type:=real}{L.in:=T.type}Lreal{L.in=real}L

real{L.in=real}{L1.in:=L.in}L1,id2{addtype(id2.entry,L.in)}real{L1.in=real}L1,id2{addtype(id2.entry,L.in)}real{L1.in=real}id1{addtype(id1.entry,L1.in)},id2{addtype(id2.entry,L.in)}realid1{(id1.entry,real)},id2{(id2.entry,real)}D→T{L.in:=T.type}LT→int{T.type:=integer}T→real{T.type:=real}L→{L1.in:=L.in}L1,id{addtype(id.entry,L.in)}L→id{addtype(id.entry,L.in)}生成中間代碼的目的(1)便于優(yōu)化(2)便于移植常見的中間代碼形式：后綴式三地址代碼（四元式、三元式和間接三元式）圖形（抽象語法樹、有向無環(huán)圖）

中間代碼：一種介于源語言和目標語言之間的中間語言形式8.３中間代碼.java

java源程序文件.class

二進制字節(jié)碼文件Java虛擬機（JVM)本地計算機系統(tǒng)編譯Java語言.NET框架

GCC

中綴表示后綴表示

a+bab+

a+b*cabc*+

(a+b)*cab+c*a:=b*c+b*dabc*bd*+:=特點1、運算對象出現(xiàn)的順序和原有順序（從左到右）相同2、運算符按實際計算順序（從左到右）出現(xiàn)3、運算符緊跟在運算對象的后面出現(xiàn)，且沒有括號優(yōu)點：簡明、便于計值8.3.1后綴式分別給出下列表達式的后綴表示1.-a+b*(-c+d)2.X:=-(a+b)/(c-d)-(a+b*c)3.a=c∧b=d4.a≤b+c∧a>d∨a+b≠ea-bc-d+*+Xab+-cd-/abc*+-:=ac=bd=∧abc+≤ad>∧ab+e≠∨8.3.2三地址代碼１．種類（1）x=yopz形式的賦值語句，其中op是二元運算符。（2）x=opy形式的賦值語句，其中op是一元運算符。（3）x=y形式的賦值語句。（4）無條件轉(zhuǎn)移語句gotoL，表示下一個要執(zhí)行的語句是標號為L的語句。（5）條件轉(zhuǎn)移語句ifxropygotoL中，rop為關(guān)系運算符，如果x和y滿足關(guān)系rop，就轉(zhuǎn)而執(zhí)行標號為L的語句，否則順序執(zhí)行下一個語句。2．具體實現(xiàn)四元式操作符操作數(shù)1操作數(shù)2結(jié)果結(jié)果：通常是由編譯引進的臨時變量例:X=(A+B)*(C+D)-E+,A,B,T1+,C,D,T2*,T1,T2,T3-,T3,E,T4=,T4,一,XT1,T2,T3,T4為臨時變量，由四元式優(yōu)化比較方便T1=A+BT2=C+DT3=T1+T2T4=T3-EX=T4操作符左操作符數(shù)右操作數(shù)表達式的三元式：w*x+(y+z)(1)*,w,x(2)+,y,z(3)+,(1),(2)

第三個三元式中的操作數(shù)(1)(2)表示第(1)和第(2)條三元式的計算結(jié)果。三元式例：A=B+C*D/EF=C*D三元式(1)*,C,D(2)/,(1),E(3)+,B,(2)(4)=,A,(3)(5)*,C,D(6)=,F,(1)

不便于代碼優(yōu)化：刪除某些三元式后可能需作一系列的修改

三元式(1)*,C,D(2)/,(1),E(3)+,B,(2)(4)=,A,(3)(5)=,F,(1)間接三元式執(zhí)行順序(1)(2)(3)(4)(1)(5)三元式的執(zhí)行次序用另一張表表示,優(yōu)化時三元式可以不變，僅僅改變其執(zhí)行順序表例：x=y+yz+yz

抽象語法樹8.3.3圖形表示有向無環(huán)圖8.4表達式及賦值語句的翻譯簡單表達式的文法如下：Ai=EEE+E|E*E|-E|(E)|i非終結(jié)符A代表“賦值語句”，語義子程序所涉及到語義變量、語義過程及函數(shù)說明如下：（1）對非終結(jié)符的E定義語義變量E.place，即E.place表示存放Ｅ值的變量名在符號表中的入口地址或臨時變量名的整數(shù)碼。（２）定義語義函數(shù)newtemp()，即每次調(diào)用newtemp()時都要回送一個代表新臨時變量的整數(shù)碼。臨時變量按產(chǎn)生的次序為Ｔ１，Ｔ２，。（３）定義語義過程emit(op,arg1,arg2,result)，其中的emit是產(chǎn)生一個四元式并填入四元式的表中。arg1、arg2是操作數(shù)，result是運算結(jié)果。（4）定義語義函數(shù)lookup(),其功能是審查是否出現(xiàn)在符號表中，是則返回在符號表中的入口指針，否則返回空。使用上述的語義變量、過程和函數(shù)，可以寫出文法每個產(chǎn)生式的語義子程序。（1）Ai=E{p=lookup() if(p==NULL)error(); elseemit(=,E.place,_,P);}（2）EE(1)+E(2){E.place=newtemp(); Emit(+,E(1).place,E(2).place,E.place)}（3）EE(1)*E(2){E.place=newtemp(); emit(*,E(1).place,E(2).place,E.place)}（4）E-E(1) {E.place=newtemp();} emit(uminus,E(1).place,_,E.place)}（5）E(E(1)) {E.place=E(1).place}（6）Ei {p=lookup() if(p!=NULL)E.place=p; elseerror();}在上面的語義分析過程中，沒有考慮到靜態(tài)語義檢查。在實際應(yīng)用中，要全面考慮語句的翻譯。例如：EE(1)*E(2)該語句的語義子程序的翻譯可以寫成：EE(1)*E(2){E.place=newtemp(); ifE(1).type=intANDE(2).type=intthen begin emit(E.place,=,E(1).place,*i,E(2).place); E.type=int end elseifE(1).type=realANDE(2).type=realthen begin emit(E.place,=,E(1).place,*r,E(2).place); E.type=real end elseifE(1).type=int/*andE(2).type=real*/then begint=newtemp; emit(t,=,itr,E(1).place); emit(E.place,=,t,*r,E(2).place);E.type=realendelse/*E(1).type=realANDE(2).type=int*/ begint=newtemp; emit(t,=,itr,,E(2).place); emit(E.place,=,E(1).place,*r,t); E.type=real end; } 例題8.7試分析賦值語句X=-B*(C+D)的語法制導(dǎo)翻譯解答：賦值語句X=-B*(C+D)#的語法制導(dǎo)翻譯過程如表8-2所示。輸入串歸約產(chǎn)生式符號棧語義棧（place）四元式X=-B*(C+D)##_=-B*(C+D)#（6）#i_X-B*(C+D)##i=_X_B*(C+D)##i=_X__*(C+D)#（6）#i=i_X__B*(C+D)#（4）#i=E_X__B(uminus,B,_,T1)*(C+D)##i=E_X_T1(C+D)##i=E*_X_T1__C+D)##i=E*（_X_T1_______+D)#（6）#i=E*（i_X_T1___

C+D)##i=E*（E_X_T1__

_CD)##i=E*（E+_X_T1__C_)#（6）#i=E*E+i_X_T1__C_D)#（2）#i=E*(E+E_X_T1__C_D(+,C,D,T2))##i=E*（E_X_T1__T2#（5）#i=E*(E)_X_T1__T2_#（3）#i=E*E_X_T1_T2(*,T1,T2,T3)#（1）#i=E_X_T3(=,T3,_,X)##A_X8.4.2布爾表達式的翻譯布爾表達式的文法為：EE∧E|E∨E|E|(E)|i|iropi其中的rop為，<，==，!=，>=，運算符。1．布爾表達式值的計算計算布爾表達式的值通常有兩種方法。第一種方法和算術(shù)表達式的計算方法一樣，根據(jù)順序和優(yōu)先級一步步計算出來。例如：1∨（0∧0）∨0=1∨（1∧0）∨0=1∨0∨0=1∨0=1另一種方法就是根據(jù)布爾表達式的特點實施某種優(yōu)化。即不必一步一步地計算布爾表達式中所有運算對象的值，而是省略不影響結(jié)果的運算。例如：在計算A∨B時，若計算出A的值為1，則B的值就無須再計算；在計算A∧B時，若A的值為0，則B的值無須要再計算，因為A∧B的值一定為02．布爾表達式的翻譯方法給出布爾表達式ifa<bthen1else0，根據(jù)布爾表達式的第一種計算方法，寫出該表達式的四元式為：（1)ifa<bgoto(4)（2）t=0（3）goto(5)（4）t=1（5）…翻譯方法如下：E(1)∨E(2)：E(1)為TRUE，則整個表達式為TRUE，轉(zhuǎn)向條件為“真”的出口。E(1)為FALSE，則轉(zhuǎn)向E(2)的判斷，若E(2)為TRUE，則整個表達式為TRUE，轉(zhuǎn)向條件為“真”的出口，用E.true指針代表真的出口；若E(1)為FALSE，則轉(zhuǎn)向E(2)的判斷，若E(2)為FALSE，則整個表達式為 FALSE，則轉(zhuǎn)向條件為“假”的出口，用E.false代表假的出口。E(1)∧E(2)：E(1)為FALSE，則整個表達式為FALSE，轉(zhuǎn)向條件為“假”的出口。E(1)為TRUE，則轉(zhuǎn)向E(2)的判斷，若E(2)為TRUE，則整個表達式為TRUE，轉(zhuǎn)向條件為“真”的出口；若E(1)為TRUE，則轉(zhuǎn)向E(2)的判斷。若E(2)為FALSE，則整個表達式為FALSE，轉(zhuǎn)向條件為“假”的出口。根據(jù)上述的思想將布爾表達式翻譯成四元式的描述，其中nextstat給出輸出序列中下一個四元式序號，emit過程每被調(diào)用一次，nextstat增加1。EE(1)∨E(2) {E.place=newtemp; emit(E.place=E(1).place∨E(2).place) }EE(1)∧E(2) {E.place=newtemp; emit(E.place=E(1).Place∧E(2).place) }EE(1){E.place=newtemp; emit(E.place=

E(1).place) }E(E(1)){E.place=E(1).place}Eid1ropid2{E.place=newtemp; emit(ifid1.placeropid2.placegotonextstat+3) emit(E.Place=0) emit(gotonextstat+2) emit(E.place=1) }Etrue {E.place=newtemp; emit(E.place=

1) }Etrue {E.place=newtemp; emit(E.place=

0)}8.4.3在控制語句中布爾表達式的翻譯E的代碼S1的代碼（a）ifEthenS1代碼結(jié)構(gòu)TFE的代碼S1的代碼（b）ifEthenS1elseS2

代碼結(jié)構(gòu)jumpoutS2的代碼TFout:E的代碼S1的代碼（c）whileEdoS1

代碼結(jié)構(gòu)jumpbeginTFbegin:圖8-5控制語句的代碼結(jié)構(gòu)56S→ifEthenS1

的翻譯代碼結(jié)構(gòu)S1.beginE.trueS.nextE.codeS1.codeE.false57例：ifa>bthena=a+a

ifa>bgotoC.true (S1.begin) gotoC.false (S.next)S1.begin: t1:=a+a a:=t1S.next:（1）EE(1)VE(2){backpatch(E(1).false,E(2).codebegin)；

E.codebegin=E(1).codebegin E.true=merge(E(1).true,E(2).true) E.false=E(2).false }

（2）EE(1)∧E(2){backpatch(E(1).true,E(2).codebegin); E.codebegin=E(1).codebegin E.true=E(2).true E.false=merge(E(1).false,E(2).false) }

（3）EE(1) {E.true=E(1).False; E.codebegin=E(1).Codebegin E.false=E(1).true }（4）E(E(1)) { E.true=E(1).true; E.false=E(1).false E.codebegin=E(1).codebegin }

（5）Eid1ropid2 {E.true=nextstat; E.codebegin=nextstat; E.false=nextstat+1; emit(ifid1.placeropid2.placegoto—); emit(goto—); }（6）Etrue {E.true=nextstat; E.codebegin=nextstat;

emit(goto—) }（7）Efalse{E.false=nextstat; E.codebegin=nextstat;

emit(goto—)}代碼結(jié)構(gòu)E.codeS1.beginE.trueS.nextS1.codeE.falsegotoS.nextS2.codeS2.beginS2.nextS1.nextS→ifEthenS1elseS2

的翻譯例題8.8給出布爾表達式ifa<b∨c<d∧e>fthenS1elseS2，它翻譯成四元式序列為：（1)ifa<bgotoE.true（2）goto（3）（3）ifc<dgoto(5)（4）gotoE.false （5）ife<fgotoE.true（6）gotoE.falseE.true為S1語句目標代碼的首地址，E.false為S2語句目標代碼的首地址。E為a<b∨c<d∧e>f例題8.8給出布爾表達式ifa<b∨c<d∧e>fthenS1elseS2，它翻譯成四元式序列為：（1）ifa<bgotoE.true（2）goto（3）（3）ifc<dgoto(5)（4）gotoE.false

（5）ife<fgotoE.true（6）gotoE.false（7）S1的四元式（p）goto(q)（p+1）關(guān)于S2的的四元式（q）（7）（p+1）（7）（p+1）通過上面的例子可以看出:（7）是該條件語句的真出口，(p+1)是該條件語句的假出口。而E.true和E.false必須是在翻譯到S1或S2時才能確定它的語句編號是什么，所以需要回填。并且需要回填的語句很多，如四元式（1）和（5）需要回填E.true的值，（4）和（6）需要回填E.false的值。這些要回填的四元式標號需要記住。因此就采用“拉鏈”的技術(shù)，如果不能記住，則無法回填了。把需要回填E.true的值作為真鏈，把需要回填E.false的值作為“假“鏈。65拉鏈回填一遍掃描先產(chǎn)生暫時沒有填寫目標標號的轉(zhuǎn)移指令；對于每一條這樣的指令作適當?shù)挠涗洠灰坏┺D(zhuǎn)移的目標“標號”被確定下來，再將它“回填”到相應(yīng)的指令中布爾表達式E設(shè)屬性E.turelist和E.falselistE.truelist——對應(yīng)真出口EtrueE.falselist——對應(yīng)假出口Efalse兩遍掃描n1(j,,,0)……n2(j<,a,b,n1)……n3(j=,c,d,n2)E.Turelistn366拉鏈回填翻譯模式用到如下兩個函數(shù)：

1．merge(p1，p2)：將由p2指向的表接在p1所指向的鏈表后，返回p1

2．backpatch（p，i）：把i作為目標標號回填到p所指向的鏈表中的每一個轉(zhuǎn)移指令中去。此處的“鏈表”都是為“回填”作準備的67拉鏈回填舉例——拉鏈n1(j,,,0)……n2(j<,a,b,n1)……n3(j=,c,d,n2)P2:n3P1:n4(j,,,0)……n5(j<,a,b,n4)……n6(j=,c,d,n5)n5n6n42023/1/3168拉鏈回填舉例——并鏈n1(j,,,0)……n2(j<,a,b,n1)……n3(j=,c,d,n2)P2:n3n4(j,,,)……n5(j<,a,b,n4)……n6(j=,c,d,n5)P1:n60n32023/1/3169n4n2n3n5n6拉鏈回填——回填n1(j,,,)……n2(j<,a,b,)……n3(j=,c,d,

)n4(j,,,)……n5(j<,a,b,)……n6(j=,c,d,)P1:backpatch（p，i）n5n4n3n2n1i0iiiiin10拉鏈的技術(shù)如下：（100）…gotoE.true …(200)…gotoE.true …(300)…gotoE.true …則鏈成：（100）…goto（0）

…（200)…goto（100）

…（300)…goto（200）

…把地址300作為鏈首，地址（100）為鏈尾，0為鏈尾標志。根據(jù)上面的翻譯思想，我們給出將布爾表達式翻譯成四元式的描述，其中（1）nextstat為給出序列中的下一個四元式的序號。emit過程每調(diào)用一次，nextstat的值就增加1。（2）merge(p1,p2)：把以p1和p2為鏈首的兩條鏈合并為一條以p2為鏈首的鏈。（3）backpatch(p,t)：把鏈首p所鏈接的每個四元式的第四區(qū)段（即result）都改寫為地址t。（4）語義值E.codebegin與非終結(jié)符E相連，表示表達式E的第一個四元式語句的序號。merge()函數(shù)如下：merge(p1,p2){if(p2==0)return（p1）；else{p=p2;while(四元式p的第四區(qū)段內(nèi)容不為0)