編譯原理第七章

編譯原理電子教案第七章語義分析和中間代碼產(chǎn)生謝強(qiáng)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)ieqiang@2本章的主要內(nèi)容中間代碼的表示形式說明語句、賦值語句、控制語句的翻譯3本章要求

知識(shí)點(diǎn)：中間語言，說明語句，賦值語句，布爾表達(dá)式，CASE語句，過程調(diào)用語句，控制流語句的翻譯以及回填技術(shù)。深刻理解：語法樹、有向非循環(huán)圖、三地址代碼、四元式、三元式、逆波蘭式表示；適用于一遍掃描分析的回填技術(shù)。熟練掌握：（1）程序中說明的處理，重要的是在符號(hào)表中維持作用域信息；（2）數(shù)組元素，賦值語句，過程調(diào)用語句的翻譯模式；（3）用回填技術(shù)實(shí)現(xiàn)布爾表達(dá)式和控制流語句的翻譯。4靜態(tài)語義審查（1）類型檢查。根據(jù)類型相容性要求，驗(yàn)證程序中執(zhí)行的每個(gè)操作是否遵守語言的類型系統(tǒng)的過程，編譯程序必須報(bào)告不符合類型系統(tǒng)的信息。（2）控制流檢查?？刂屏髡Z句必須使控制轉(zhuǎn)移到合法的地方。例如，在C語言中break語句使控制跳離包括該語句的最小while、for或switch語句。如果不存在包括它的這樣的語句，則就報(bào)錯(cuò)。（3）一致性檢查。在很多場合要求對象只能被定義一次。例如Pascal語言規(guī)定同一標(biāo)識(shí)符在一個(gè)分程序中只能被說明一次，同一case語句的標(biāo)號(hào)不能相同，枚舉類型的元素不能重復(fù)出現(xiàn)等等。（4）上下文相關(guān)性檢查。比如，變量名字必須先聲明后引用；而有時(shí)，同一名字必須出現(xiàn)兩次或多次。

(5)名字的作用域分析翻譯為中間語言的好處（1）便于進(jìn)行與機(jī)器無關(guān)的代碼優(yōu)化；（2）使編譯程序改變目標(biāo)機(jī)更容易；（3）使編譯程序的結(jié)構(gòu)在邏輯上更為簡單明確，以中間語言為界面，編譯前端和后端的接口更清晰。5本章教學(xué)線索1中間語言1.1后綴式1.2圖表示法1.3三地址代碼2說明語句3賦值語句的翻譯4布爾表達(dá)式的翻譯5控制語句的翻譯6過程調(diào)用的處理61中間語言主要介紹三種類型的中間語言：后綴式、三地址代碼、DAG圖。71.1后綴式后綴式表示法（逆波蘭式）是波蘭邏輯學(xué)家盧卡西維奇發(fā)明的一種表示表達(dá)式的方法。這種表示法是：把運(yùn)算量(操作數(shù))寫在前面，把算符寫在后面（后綴）。例如：a+b寫成ab+。一個(gè)表達(dá)式的后綴式可以如下定義：

1）如果E是一個(gè)變量或常量，則E的后綴式是E自身。

2）如果E是E1opE2形式的表達(dá)式，這里op是任何二元操作符，則E的后綴式為E1’E2’op,這里E1’和E2’分別為E1和E2的后綴式。

3）如果E是(E1)形式的表達(dá)式，則E1的后綴式就是E的后綴式。注意以下三點(diǎn)：1）在后綴式中：標(biāo)識(shí)符出現(xiàn)的順序(從左到右)同原來的順序相同；2）在后綴式中：運(yùn)算符是按實(shí)際計(jì)算順序（從左到右）出現(xiàn)的3）在后綴式中：運(yùn)算符跟在運(yùn)算對象的后面出現(xiàn)，且沒有括號(hào)。例子：a＝3*（b+c）表示為：a3bc+*=a*（b+c/d）表示為：abcd/+*81.2圖表示法包括：抽象語法樹和DAG(DirectedAcyclicGraph無循環(huán)有向圖）。DAG：對表達(dá)式中的每個(gè)子表達(dá)式，DAG中都有一個(gè)結(jié)點(diǎn)，一個(gè)內(nèi)部結(jié)點(diǎn)代表一個(gè)操作符。它的孩子代表操作數(shù)。抽象語法樹和DAG區(qū)別：在一個(gè)DAG中代表公共子表達(dá)式的結(jié)點(diǎn)具有多個(gè)父結(jié)點(diǎn)，而在一顆抽象語法樹中公共子表達(dá)式被表示為重復(fù)的子樹。++*-abc*da+a*(b-c)+(b-c)*d的DAG+a*-abc*d+-bca+a*(b-c)+(b-c)*d的抽象語法樹后綴式：aabc-*+bc-d*+9=a+*buminusc*buminusc=a+*buminusca=b*-c+b*-c的抽象語法樹a=b*-c+b*-c的DAG后綴式：abcuminus*bcuminus*+=結(jié)論：后綴式是抽象語法樹的線性表示，對抽象語法樹進(jìn)行深度優(yōu)先從左到右的掃描，就可以得到后綴式。101.3三地址代碼1.3.1

概念

三地址代碼的一般形式：x＝y(tǒng)opz三地址代碼：每條語句通常包括三個(gè)地址，其中兩個(gè)用來表示操作數(shù)，一個(gè)用來存放結(jié)果。如：源語言x+y*z可以翻譯為：T1＝y(tǒng)*zT2=x+T1又如：a=b*-c+b*-c的抽象語法樹對應(yīng)的三地址代碼：t1=-ct2=b*t1t3＝-ct4=b*t3t5＝t2+t4a=t5

a=b*-c+b*-c的DAG對應(yīng)的三地址代碼：t1=-ct2=b*t1t3＝t2+t2a=t3111.3.2三地址語句的種類（1）賦值語句x＝y(tǒng)opz，op為二目算術(shù)算符或邏輯算符；（2）賦值語句x＝opy，op為一目算符，如一目減uminus、邏輯非not、移位算符及轉(zhuǎn)換算符；（3）復(fù)制語句x＝y(tǒng)；（4）無條件轉(zhuǎn)移語句gotoL；（5）條件轉(zhuǎn)移語句ifxrelopygotoL，關(guān)系運(yùn)算符號(hào)relop（<，=，＞=等）；（6）過程調(diào)用語句paramx和callp，n，過程返回語句returny；（7）索引賦值x＝y(tǒng)[i]及x[i]＝y(tǒng)；（8）地址和指針賦值x

:＝＆y，x

:＝*y和*x

:＝y(tǒng)。在設(shè)計(jì)中間代碼形式時(shí)，選擇多少種算符需要權(quán)衡

.三地址語句序列是語法樹的線性表示，用臨時(shí)變量代替語法樹中的結(jié)點(diǎn)。實(shí)際實(shí)現(xiàn)中，三地址語句序列往往被存放到一個(gè)輸出文件中，而不是將三地址語句序列置入code屬性之中。12產(chǎn)生賦值語句三地址代碼的語法制導(dǎo)定義產(chǎn)生式語義規(guī)則S→id:=ES.code:=E.code║gen(id.place':='E.place)E→E1+E2E.place:=newtemp;E.code:=E1.code║E2.code║gen(E.place':='E1.place'+'E2.place)E→E1*E2E.place:=newtemp;E.code:=E1.code║E2.code║gen(E.place':='E1.place'*'E2.place)E→-E1E.place:=newtemp;E.code:=E1.code‖gen(E.place′:=′′uminus′E1.place)E→(E1)E.place:=E1.place;E.code:=E1.codeE→idE.place:=id.place;E.code:=‘’131.3.3三地址代碼的具體實(shí)現(xiàn)1）四元式op，arg1，arg2，result2）三元式op，arg1，arg23）間接三元式間接碼表+三元式表四元式需要利用較多的臨時(shí)單元，四元式之間的聯(lián)系通過臨時(shí)變量實(shí)現(xiàn)。中間代碼優(yōu)化處理時(shí)，四元式比三元式方便得多，間接三元式與四元式同樣方便，兩種實(shí)現(xiàn)方式需要的存儲(chǔ)空間大體相同。例：對于語句a＝b*-c+b*-c的兩種表示方法oparg1arg2resultoparg1arg2（0）uminuscT1（0）uminusc（1）*bT1T2（1）*b(0)（2）uminuscT3（2）uminusc（3）*bT3T4（3）*b(2)（4）+T2T4T5（4）+(1)(3)（5）=T5a（5）assigna(4)三元式四元式14（為什么要計(jì)算一次A+B即間接代碼中要在一次調(diào)用（1），因?yàn)椋?）已經(jīng)被引用一次，存儲(chǔ)臨時(shí)變量的地址已經(jīng)被釋放。）例：X=(A+B)*CY=D↑（A+B）的三元式、間接三元式表示：間接代碼(1)(2)(3)(1)(4)(5)oparg1arg2(1)+AB(2)*(1)C(3)=X(2)(4)↑D(1)(5)=Y(4)15本章教學(xué)線索1中間語言2說明語句2.1過程中的說明語句2.2保留作用域信息2.3記錄中的域名3賦值語句的翻譯4布爾表達(dá)式的翻譯5控制語句的翻譯6過程調(diào)用的處理162說明語句說明語句的翻譯：對每個(gè)局部名字，在符號(hào)表中建立相應(yīng)的表項(xiàng)，填寫有關(guān)的信息如類型、嵌套深度、相對地址等。相對地址：相對靜態(tài)數(shù)據(jù)區(qū)基址或活動(dòng)記錄中局部數(shù)據(jù)區(qū)基址的一個(gè)偏移值。172.1過程中的說明語句

一個(gè)過程中的所有說明語句作為一個(gè)類集來處理。用一個(gè)全程變量Offset來記錄下一個(gè)數(shù)據(jù)在活動(dòng)記錄中的位置。P→｛offset：＝0}DD→D；DD→id：T｛enter（，T.type，offset）；

offset＝offset+T.width}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}圖7．4計(jì)算說明語句中名字的類型和相對地址182.2保留作用域信息

問題的提出一般的語言中，標(biāo)識(shí)符的作用在程序正文中有一個(gè)確定的范圍。因此，同一個(gè)標(biāo)識(shí)符在不同的程序正文中可能標(biāo)識(shí)不同的對象，具有不同的性質(zhì)，要求分配不同的存儲(chǔ)空間。于是提出下面的問題：如何組織符號(hào)表，使得同一個(gè)標(biāo)識(shí)符在不同的作用域中得到正確的引用而不產(chǎn)生混亂。編譯程序分析說明語句時(shí)建立符號(hào)表，編譯執(zhí)行語句時(shí)查找符號(hào)表。Lookup(id)返回正確的id.entry。程序結(jié)構(gòu)一組嵌套過程，為每個(gè)過程說明的局部名字建立一個(gè)符號(hào)表，所有正在翻譯過程的符號(hào)表組成整個(gè)源程序的符號(hào)表。翻譯語句部分時(shí)查找符號(hào)表，查找過程的符號(hào)表的路線相當(dāng)于當(dāng)前被翻譯過程的靜態(tài)鏈。翻譯時(shí)，實(shí)際上，為每一個(gè)過程維持一個(gè)符號(hào)表。這種符號(hào)表可用鏈表實(shí)現(xiàn)。當(dāng)碰到過程說明D→procid；D1；S時(shí)，就創(chuàng)建一張新的符號(hào)表，并且把在D1中的所有說明項(xiàng)都填入此符號(hào)表內(nèi)。新表有一個(gè)指針指向剛好包圍該嵌入過程的外圍過程的符號(hào)表，由id表示的過程名字作為該外圍過程的局部名字。19處理嵌套過程中的說明語句P→MD {addwidth(top(tblptr)，top(offset))；

pop(tblptr)；pop(offset)}M→ε {t=mktable（nil）；

push（t，tblptr）；push（0，offset）｝D→D1；D2

D→procid；ND1；S {t＝top（tblptr)；

addwidth（t，top(offset)）；

pop（tblptr）；pop（offset）；

enterproc（top（tblptr），，t）}D→id：T{enter（top（tblptr），，T.type，top(offset)）；top(offset）：=top(offset)＋T.width}N→ε{t＝mktable（top（tblptr））；

push(t，tblptr）；push（0，offset)}

在下面的語義規(guī)則中用到如下操作。(1)mktable(previous)創(chuàng)建一張新符號(hào)表，并返回指向新表的一個(gè)指針。參數(shù)previous指向一張先前創(chuàng)建的符號(hào)表，譬如剛好包圍嵌入過程的外圍過程符號(hào)表。指針previous之值放在新符號(hào)表表頭，表頭中還可存放一些其它信息如過程嵌套深度等等。我們也可以按過程被說明的順序?qū)^程編號(hào)，并把這一編號(hào)填入表頭。(2)enter(table，name，type,offset）在指針table指示的符號(hào)表中為名字name建立一個(gè)新項(xiàng)，并把類型type、相對地址offset填入到該項(xiàng)中。(3)addwidth(table,width)在指針table指示的符號(hào)表表頭中記錄下該表中所有名字占用的總寬度。(4)enterproc(table，name，newtable）在指針table指示的符號(hào)表中為名字為name的過程建立一個(gè)新項(xiàng)。參數(shù)newtable指向過程name的符號(hào)表。20programsortvara,xprocedurereadarryvaribegin…end//readarryprocedureexchangebeginx=a…end//exchangeprocedurequiksortvark,vfunctionpartitionvari,jbegin…a….;….v…exchange(i,j)endpartitionbegin….end//sort嵌套過程的符號(hào)表nilheaderaxreadarryexchangequicksortheaderireadarryheaderpartitionheaderkvpartitionheaderijexchangequicksortexchangereadarrysort212.3記錄中的域名T→recordLDend {T.type=record（top（tblptr））；

T.width=top(offset)；

pop（tblptr)；pop(offset)}L→ε{t=mktable(nil)；

push(t，tblptr)；push(0，offset))}

圖7.7為－個(gè)記錄中的域名建立一張符號(hào)表p178該翻譯模式強(qiáng)調(diào)了作為一個(gè)語言結(jié)構(gòu)的記錄的設(shè)計(jì)與活動(dòng)記錄之間的相似處。22關(guān)于符號(hào)表的一些討論：1.符號(hào)表的數(shù)椐結(jié)構(gòu)（a）線性表；（b）散列表；

（c）樹結(jié)構(gòu)。2.符號(hào)表上的運(yùn)算：（a）插入（insert）；（b）查找（lookup）；（c）刪除(delete)；（d）更新（update）。3.符號(hào)表必須維持源程序中的作用域信息，源程序中的作用域規(guī)則因語言而異，對一種語言，根椐符號(hào)表采用的數(shù)據(jù)結(jié)構(gòu)，維持源程序中的作用域信息方法不同。４.符號(hào)表中名字的屬性信息由兩方面組成：（a）名字在源程序中的屬性信息，例如，名字在源程序中的表示，種類，類型等；（b）經(jīng)分析加工得到的有用信息，例如，對于變量來說，嵌套深度，在活動(dòng)記錄中的偏移量等。23本章教學(xué)線索1中間語言2說明語句3賦值語句的翻譯3.1符號(hào)表中的名字3.2數(shù)組元素地址分配3.3訪問數(shù)組元素的翻譯模式3.4訪問記錄中的域4布爾表達(dá)式的翻譯5控制語句的翻譯6過程調(diào)用的處理243賦值語句的翻譯賦值語句的翻譯表達(dá)式的類型可以是整型、實(shí)型、數(shù)組和記錄253.1符號(hào)表中的名字名字可以理解為指向符號(hào)表中相應(yīng)該名字表項(xiàng)的指針，如何根據(jù)名字查找符號(hào)表的表項(xiàng)？過程lookup()檢查是否在符號(hào)表中存在相應(yīng)此名字的表項(xiàng)。采用最近嵌套作用域規(guī)則查找非局部名字時(shí)，lookup過程先通過top(tblptr）指針在當(dāng)前符號(hào)表中查找名字為name的表項(xiàng)。 若找到，返回有關(guān)信息。若未找到，lookup就利用當(dāng)前符號(hào)表表頭的指針（指向正好包圍該過程的外圍過程）找到該符號(hào)表的外圍符號(hào)表，然后在那里查找名字為name的表項(xiàng)，直到所有外圍過程的符號(hào)表中均無此name表項(xiàng)，則lookup返回nil，表明查找失敗。26產(chǎn)生賦值語句三地址代碼的翻譯模式p179：S→id：=E{p：=lookup()；

ifp≠nilthenemit（p'：='E.place）elseerror}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')}E→-E1{E.place：=newtemp；

emit(E.place′：=′′uminus′E1.place}E→（E1）{E.place：=E1.place}E→id {p：=lookup（）；

ifp≠nilthenE.place：=pelseerror}lookup()=id.entry/nil（查詢符號(hào)表，如果查到則返回id在符號(hào)表中的入口，否則返回空）emit：它將生成的三地址代碼送到輸出文件。

語義動(dòng)作還應(yīng)包括類型分析，文法符號(hào)應(yīng)有類型屬性，在類型分析的基礎(chǔ)上，進(jìn)行相容和賦值相容檢查，生成類型轉(zhuǎn)換的三地址代碼。

273.2數(shù)組元素地址分配

數(shù)組元素的三地址代碼是什么？如何生成數(shù)組元素的三地址代碼。28數(shù)組元素地址的計(jì)算公式一維數(shù)組A的下標(biāo)為i的元素的開始地址

VARa：ARRAY[low…h(huán)igh]OFreal；求a[i]的地址。base＋（i-low）*w=i*w+(base-low*w)

其中，base是數(shù)組元素a[low]的地址。對于C＝(base-low*w)是一個(gè)常量，可以在處理數(shù)組說明的時(shí)候確定。對于一個(gè)二維數(shù)組，可以按行或按列存放若按行存放，則可用如下公式計(jì)算A[i1,i2]的相對地址：

base+（（i1-low1）*n2+i2-low2）*w=base-（low1*n2+low2）*w

+（i1*n2+i2)*w

令c=（low1*n2+low2）*w則常量部分=a[low1，low2]-c=base-c29計(jì)算元素A[i1，i2，...，ik]相對地址的推廣公式：((...((i1*n2+i2)*n3+i3...)*nk+ik)*w+base-((...((low1*n2+low2)*n3+low3...)*nk+lowk)*wc=((...((low1*n2+low2)*n3+low3)...)*nk+lowk)*w變量部分=((...((i1*n2+i2)*n3+i3...)*nk+ik)*wa[i1，i2，…，in]的地址=base-c+變量部分

x：=a[i1，i2

，…，ik]三地址代碼結(jié)構(gòu)：

t1：=變量部分t2：=base-ct3：=t2[t1]x：=t3計(jì)算動(dòng)態(tài)數(shù)組元素地址的公式與在固定長度數(shù)組情況下是同樣的，只是上、下界在編譯時(shí)是未知的。30數(shù)組的類型信息：VARa：ARRAY[1..10，1..20]OFreal；符號(hào)表中的信息可組織如下：（w=4）a嵌套深度偏移量類型名字表C=84low1=1high1=10n1=10low2=1high2=20n2=20基類型Real標(biāo)準(zhǔn)類型4內(nèi)情向量31數(shù)組元素引用的文法L→id[Elist]|id//*****數(shù)組名在形成L時(shí)與Elist聯(lián)系Elist→Elist，E|E為了在分析下標(biāo)表達(dá)式中始終知道有關(guān)數(shù)組名的信息，改寫為：

L→Elist]|idElist→Elist，E|id[E//****數(shù)組名與數(shù)組最左下標(biāo)表達(dá)式聯(lián)系Elist可以產(chǎn)生k維數(shù)組引用的前m維下標(biāo)，并生成：（…（（i1n2+i2）n3+i3）…）nm+im則有遞歸公式：e1=i1

，em=em-1*nm+im對于m=k時(shí)，ek*w即為計(jì)算數(shù)組元素相對地址的變量部分。有關(guān)變量與函數(shù)的說明Elist.ndim：記錄Elist中的下標(biāo)表達(dá)式的個(gè)數(shù)，即維數(shù)；limit（array，j）：返回nj，即由array所指示的數(shù)組的第j維長度；Elist.place：用來臨時(shí)存放由Elist中的下標(biāo)表達(dá)式計(jì)算出來的值；em=em-1*nm+imElist引進(jìn)綜合屬性array，指向符號(hào)表中相應(yīng)數(shù)組名字表項(xiàng)的指針。323.3訪問數(shù)組元素的翻譯模式給定文法：（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相應(yīng)語義動(dòng)作S→L：＝E

｛ifL.offset＝nullthenemit(L.place'：＝'E.place)elseemit（L.place'['L.offset']'：='E.Place）}//如果L為簡單變量，則生成一般賦值語句，否則若L為數(shù)組元素引用，則生成對L所指示地址的索引賦值。332．E→E1＋E2

｛E.place：＝newtemp；

emit（E.place'：＝'E1.place'＋'E2.place）｝3．E→（E1）

{E.place：＝E1.place}當(dāng)一個(gè)數(shù)組引用L歸約到E時(shí)，我們需要L的右值，因此使用索引來獲得地址L.place[L.offset]的內(nèi)容：4.E→L

｛ifL.offset＝nullthenE.place:＝L.place／*Lisasimpleid*/elsebeginE.place：=newtemp；

emit（E.place'：='L.place'['L.offset']')end}（L.place：常量部分，L.offset：變量部分）345.L→Elist]

｛L.place：=newtemp；

emit（L.place‘：=’Elist.array‘－’c）//-----Elist.array：base

L.offset：=newtemp；

emit（L.offset‘：=’w‘*’Elist.place）}

//------Elist.place：下標(biāo)表達(dá)式計(jì)算出來的值em

//------L.offset：數(shù)組元素相對地址的變量部分一個(gè)空的offset表示一個(gè)簡單的名字：6.L→id{L.place：=id.place；L.offset：=null}35應(yīng)用遞歸公式掃描下一個(gè)下標(biāo)表達(dá)式：7.Elist→Elist1，E//**（Elist1.place：em-1）{t：＝newtemp；

//**（limit（Elist1.array，m）：nm；E.place：im）

m：＝Elist1.ndim＋1；

emit（t'：='Elist1.place'*'limit（Elist1.array，m））；

emit（t'：='t'+'E.place）；

Elist.array：＝Elist1.array；（em=em-1*nm+im）Elist.place：=t；

Elist.ndim：＝m｝第一維情況，最先掃描到：8.Elist→id[E

｛Elist.place：=E.place；（E.place：i1）

Elist.ndim：=1；

Elist.array：＝id.place}36例設(shè)A為一個(gè)10*20的數(shù)組，即n1=10，n2=20。并設(shè)w＝4，數(shù)組第一個(gè)元素為A[1，1]。則有：((low1*n2)＋low2)*w=(1*20＋1)*4＝84。賦值語句x:=A[y,z]在由底向上的分析中被翻譯成如下三地址語句序列：t1：=y*20t1：=t1＋zt2：=A-84t3：=4*t1t4：=t2[t3]x：=t4SL.place=xL.offset=nullx:=E.place=T4L.place=T2L.offset=T3Elist.place=T1Elist.ndim=2Elist.array=A]Elist.place=yElist.ndim=1Elist.array=AA[E.place=yL.place=yL.offset=null,E.place=zL.place=zL.offset=nullzy373.4訪問記錄中的域

編譯器將記錄的域的類型和相對地址保存在相應(yīng)域名的符號(hào)表表項(xiàng)之中，可以把用在符號(hào)表中查找名字的程序同樣用來查找域名。例如：表達(dá)式：p↑．info＋1變量P是一個(gè)指向某個(gè)記錄類型的指針，info為其中一個(gè)算術(shù)型類型的域名。編譯程序內(nèi)部把p表示為：pointer（record（t）），域名info將可以在t所指向的符號(hào)表中查找。PinfonextTYPElink=↑node；

node=RECORDinfo：integer；

next：linkEND；VARp：link；38本章教學(xué)線索1中間語言2說明語句3賦值語句的翻譯4布爾表達(dá)式的翻譯4.1翻譯布爾表達(dá)式的方法4.2數(shù)值表示法4.3用作控制流語句的布爾表達(dá)式的翻譯5控制語句的翻譯6過程調(diào)用的處理394布爾表達(dá)式的翻譯布爾表達(dá)式：用布爾運(yùn)算符號(hào)（and，or，not）作用到布爾變量或關(guān)系表達(dá)式上而組成；布爾表達(dá)式的作用：1）用作計(jì)算邏輯值；

2）用作控制流語句如if-then，if-then-else和while-do等之中的條件表達(dá)式。本節(jié)考慮由如下文法生成的布爾表達(dá)式：

E→EorE|EandE|notE|（E）|idrelopid|true|false404.1翻譯布爾表達(dá)式的方法表示一個(gè)布爾表達(dá)式的值：方法一：用數(shù)值1、0表示真、假，從而對布爾表達(dá)式的求值可以象對算術(shù)表達(dá)式的求值那樣一步一步地來計(jì)算；方法二：通過程序的控制流，即用程序中控制轉(zhuǎn)移到達(dá)的位置來表示布爾表達(dá)式的值。方法二用于翻譯控制流語句中的布爾表達(dá)式尤其方便。414.2數(shù)值表示法用1表示真，0表示假來實(shí)現(xiàn)布爾表達(dá)式的翻譯布爾表達(dá)式：aorbandnotc

翻譯成三地址代碼序列：

100：t1：=notc 101：t2：=bandt1 102：t3：=aort1關(guān)系表達(dá)式：a<b等價(jià)于ifa<bthen1else0翻譯成三地址代碼序列：

100：ifa＜bgotol03 101：t：=0 102：gotol04103：t：=1 104：（注意：運(yùn)算優(yōu)先級(jí)：not、and、or）42關(guān)于布爾表達(dá)式的數(shù)值表示法的翻譯模式E→E1orE2｛E.place：=newtemp；

emit（E.place'：='E1.place'or'E2.place）}E→E1andE2｛E.place：=newtemp；

emit(E.place'：='E1.place'and'E2.place)}E→notE1 ｛E.place：=newtemp；

emit(E.place'：=''not'E1.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→true｛E.place：=newtemp；

emit(E.place'：=''1')}E→false｛E.place：=newtemp；

emit(E.place'：=''0')}43例：根據(jù)上面的翻譯模式，將布爾表達(dá)式:

a<borc<dande<f翻譯成三地址代碼100：ifa<bgoto103107：T2:=1101：T1:=0108：ife<fgoto111102：goto104109：T3:=0103：T1:=1110：goto112104：ifc<dgoto107111：T3:=1105：T2:=0112：T4:=T2andT3106：goto108113：T5:=T1orT4444.3用作控制流語句的布爾表達(dá)式的翻譯布爾表達(dá)式在控制流語句中的作用：用于對語句的選擇，其中間值無須保留。如：ifEthenS1elseS2：如果E為真，轉(zhuǎn)向S1，否則轉(zhuǎn)向S2。因此需要給出E的“真”出口和“假”出口。E.codeS1.codegotoS.nextS2.code…toE.truetoE.falseE.true:E.false:S.next:作為轉(zhuǎn)移條件布爾表達(dá)式可以翻譯成一串跳轉(zhuǎn)語句如：ifa>corb<dthenS1elseS2代碼：ifa>cgotoL2gotoL1L1：ifb<dgotoL2gotoL3L2：S1.codegotoL.nextL3：S2.codeL.next：45產(chǎn)生布爾表達(dá)式三地址代碼的語義規(guī)則產(chǎn)生式語義規(guī)則E→E1orE2E1.true=E.trueE1.false=newlabelE2.true=E.trueE2.false=E.falseE.Code=E1.code||gen(E1.false’:’)||E2.codeE→E1andE2E1.true=newlabelE1.false=E.falseE2.true=E.trueE2.false=E.falseE.Code=E1.code||gen(E.true’:’)||E2.codeE→notE1E1.true=E.falseE1.false=E.trueE.code=E1.code46產(chǎn)生布爾表達(dá)式三地址代碼的語義規(guī)則(續(xù))產(chǎn)生式語義規(guī)則E→（E1）E1.true=E.trueE1.false=E.falseE.code=E1.codeE→id1relopid2E.code=gen（’if’id1.placerelop.opid2.place‘goto’E.true)||gen(‘goto’E.false)E→trueE.code=gen(‘goto’E.true）E→falseE.code=gen(‘goto’E.false）47例：a<borc<dande<f翻譯為：ifa<bgotoLtruegotoL1L1:ifc<dgotoL2gotoLfalseL2:ife<fgotoLtruegotoLfalseEEEorEEandab<cd<ef<48使用翻譯模式，實(shí)現(xiàn)一遍掃描完成布爾表達(dá)式作為條件轉(zhuǎn)移的翻譯基本思路：由于在生成某些跳轉(zhuǎn)語句時(shí)，語句標(biāo)號(hào)可能還是未知，因此需要采用回填技術(shù)來解決這個(gè)問題。在生成跳轉(zhuǎn)指令時(shí)，對于未知的目標(biāo)，可以先建立一個(gè)鏈表，將這些具有相同的跳轉(zhuǎn)目標(biāo)的語句串起來，然后在確定了目標(biāo)后，再進(jìn)行回填。跳轉(zhuǎn)指令的三地址代碼：(jnz，a，-，p）：ifagotop(jrop，x，y，p）：ifxropygotoprop:>、=、<、<>…(j，-，-，p)：gotop49布爾表達(dá)式的文法：（1）E→E1orME2（2）|E1andME2（3）|notE1（4）|(E1)（5）|id1relopid2（6）|id（7）M→ε//M用來產(chǎn)生下一條語句的標(biāo)號(hào)翻譯模式用到如下三個(gè)函數(shù)：

1．makelist(i)：創(chuàng)建一個(gè)僅包含i的新表，i是四元式數(shù)組的一個(gè)下標(biāo)（標(biāo)號(hào)）。

2．merge(p1，p2)：將由指針p1和p2指向的兩個(gè)表合并，且返回一個(gè)指向連接后的表的指針。

3．backpatch（p，i）：把i作為目標(biāo)標(biāo)號(hào)回填到p所指向的表中的每一個(gè)轉(zhuǎn)移指令中的第四區(qū)段。此處的“表”都是為“反填”所拉的鏈50使用一遍掃描的布爾表達(dá)式的翻譯模式EE1orME2

{backpatch(E1.falselist,M.quad);E.truelist:=merge(E1.truelist,E2.truelist);E.falselist:=E2.falselist}EE1andME2{backpatch(E1.truelist,M.quad);E.truelist:=E2.truelist;E.falselist:=merge(E1.falselist,E2.falselist);}EnotE1{E.truelist:=E1.falselist;E.falselist:=E1.truelist}E(E1){E.truelist:=E1.truelist;E.falselist:=E1.falselist}51Eid1relopid2{E.truelist:=makelist(nextquad);E.falselist:=makelist(nextquad+1);emit(′j′relop.op‘，’id1.place‘，’id2.place′，′′0′);emit(′j，-，-，0′);}Eid{E.truelist:=makelist(nextquad);E.falselist:=makelist(nextquad+1);emit(‘jnz’‘，’id.place‘，’‘-’‘，’‘0’）

emit(‘j,-,-,0’)}M{M.quad:=nextquad}52E.t={100,104}E.f={103,105}E.t={100}E.f={101}E.t={104}E.f={103,105}orM.q=102a<bE.t={102}E.f={103}E.t={104}E.f={105}andM.q=104c<edf<例:表達(dá)式a＜borc＜dande＜f一棵作了注釋的分析樹a<b歸約為E產(chǎn)生：100（j<，a，b，0）101（j，-，-，0）c<b歸約為E產(chǎn)生：102（j<，c，d，0）103（j，-，-，0）e<f歸約為E產(chǎn)生：104（j<，e，f，0）105（j，-，-，0）E1andME2歸約為E，對102回填104：102（j<，c，d，104）E1orME2歸約為E，對101回填102：101（j，-，-，102）53本章教學(xué)線索1中間語言2說明語句3賦值語句的翻譯4布爾表達(dá)式的翻譯5控制語句的翻譯5.1

控制流語句5.2

控制流語句的屬性文法5.3使用回填技術(shù)實(shí)現(xiàn)控制流語句的翻譯5.4標(biāo)號(hào)與GOTO語句5.5CASE語句的翻譯6過程調(diào)用的處理545.1控制流語句控制流語句的種類：S→ifEthenS1|ifEthenS1elseS2|whileEdoS1下圖為代碼結(jié)構(gòu)：E.codeS1.codeGotoS.begin…E.codes1.code…E.true:E.falseE.trueE.false:E.codes1.codegotoS.nextS2.code…E.true:E.falseE.trueE.false:S.next:E.true:E.falseE.trueE.false:S.begin:（a）建立新的標(biāo)號(hào)，E.true，代表S1的代碼的第一條指令，如果布爾表達(dá)式E的值為真則執(zhí)行S1的代碼，否則直接執(zhí)行S1之后的代碼；代碼：

IFETHENGOTOE.trueGOTOE.falseE.true：S1.codeE.false：……55（b）建立新的標(biāo)號(hào)E.true和E.false，因?yàn)椴紶柋磉_(dá)式E的值為真則執(zhí)行S1的代碼，否則執(zhí)行S2的代碼，E.true為S1的代碼的第一條指令，E.false為S2的代碼的第一條指令，在S1的代碼執(zhí)行后，應(yīng)該有一條無條件跳轉(zhuǎn)指令跳轉(zhuǎn)到S2的代碼之后：代碼結(jié)構(gòu)：IFEGOTOE.trueGOTOE.falseE.true：S1的代碼

GOTOS.nextE.false：S2的代碼

S.next：（c）建立新的標(biāo)號(hào)E.true和E.false，根據(jù)while的含義，E為真則執(zhí)行S1的代碼，執(zhí)行完后跳轉(zhuǎn)到E的代碼的開始位置，繼續(xù)檢查E的值，所以在S1的代碼后有一條語句GOTOS.begin，如果E的值為假則執(zhí)行E.false開始的代碼，即：代碼結(jié)構(gòu)：S.begin：IFETHENGOTOE.trueGOTOE.falseE.true：S1的代碼

GOTOS.beginE.false：565.2控制流語句的屬性文法產(chǎn)生式語義規(guī)則S→ifEthenS1E.True=newlabelE.false=S.nextS1.next=S.nextS.code=E.code||gen(E.true’:’)||S1.codeS→ifEthenS1elseS2E.True=newlabelE.false=newlabelS1.next=S.nextS2.next=S.nextS.code=E.code||gen(E.true’:’)||S1.code||

gen(‘goto’S.next)||gen(E.false’:’)||S2.codeS→whileEdoS1S.begin=newlabelE.true=newlabelE.false=S.nextS1.next=S.beginS.code=gen(S.begin’:’)||E.code||gen(E.true’:’)||S1.code||gen(‘goto’S.begin)57例：whilea<bdoifc<dthenx=y+zelsex=y-z根據(jù)屬性文法生成的代碼：L1：ifa<bgotoL2gotoLnextL2：ifc<dgotoL3gotoL4L3：T1=y+zx=T1gotoL1L4：T2=y-zx=T2gotoL1Lnext：585.3使用回填技術(shù)實(shí)現(xiàn)控制流語句的翻譯考慮的文法：S→ifEthenS|ifEthenSelseS|whileEdoS|beginLend|AL→L；S翻譯模式：S→ifEthenM1S1NelseM2S2{backpatch(E.truelist，M1.quad)；

backpatch(E.falselist,M2.quad)；

S.nextlist=merge(S1.nextlist，N.nextlist，S2.nextlist)}N→ε{N.nextlist=makelist(nextquad)emit(‘j，-，-，-’)}M→ε{M.quad=nextquad}59S→ifEthenMS1{backpatch(E.truelist，M.quad)S.nextlist=merge(E.faselist，S1.nextlist)}S→whileM1EdoM2S1{backpatch(S1.nextlist，M1.quad)；

backpatch(E.truelist，M2.quad)S.nextlist=E.falselistemit(‘j，-，-，M1.quad’)}S→beginLend{S.nextlist=L.nextlist}S→A{S.nextlist=makelist()}L→L1；MS{backpatch(L1.nextlist，M.quad)；L.nextlist=S.nextlist}L→S{L.nextlist=S.nextlist}60L1.nextlist=S.nextlist={101}例：將下列語句翻譯成四元式：while(a<b)doif(c<d)thenx=y+z;LL1;MSS.nextlist=E.falselist={101}whileM1doM2S1.nextlist={103,-}Ea<bifEc<dthenM3S2Ax=EE1+E2y