編譯第七章語(yǔ)法制導(dǎo)翻譯課件

第七章語(yǔ)法制導(dǎo)翻譯和中間代碼生成1精選PPT第七章語(yǔ)法制導(dǎo)翻譯和中間代碼生成1精選PPT第一節(jié)概述語(yǔ)法分析之后，編譯的任務(wù)是由已識(shí)別為正確的源程序生成一組規(guī)格一致，便于計(jì)算機(jī)加工的指令形式。一、中間代碼生成方法語(yǔ)法制導(dǎo)翻譯，屬性文法制導(dǎo)翻譯二、中間代碼●中間代碼：不是機(jī)器語(yǔ)言，便于生成機(jī)器語(yǔ)言，便于代碼優(yōu)化?！裰虚g代碼的形式：-------逆波蘭式-------樹(shù)形表示法-------三元式-------四元式：最常用的形式第七章中間代碼的生成12精選PPT第一節(jié)概述語(yǔ)法分析之后，編譯的任務(wù)是由已識(shí)別為正確的源程第一節(jié)概述二、翻譯方法1、語(yǔ)法制導(dǎo)翻譯----在語(yǔ)法分析的基礎(chǔ)上進(jìn)行邊分析邊翻譯?！褡ⅲ?）語(yǔ)法制導(dǎo)翻譯時(shí)會(huì)根據(jù)文法產(chǎn)生式右部符號(hào)串的含義進(jìn)行翻譯，翻譯的結(jié)果是生成相應(yīng)中間代碼。●2）語(yǔ)法制導(dǎo)翻譯的依據(jù)是語(yǔ)義子程序。●3）具體做法：為每個(gè)產(chǎn)生式配置一個(gè)語(yǔ)義子程序，當(dāng)語(yǔ)法分析進(jìn)行歸約或推導(dǎo)時(shí)，調(diào)用語(yǔ)義子程序，完成一部分翻譯任務(wù)。●4）語(yǔ)法分析完成，翻譯工作也告結(jié)束。第七章中間代碼的生成23精選PPT第一節(jié)概述二、翻譯方法第七章中間代碼的生成23精選PPT第一節(jié)概述二、翻譯方法●1、語(yǔ)法制導(dǎo)翻譯---語(yǔ)法制導(dǎo)翻譯適用于多種語(yǔ)法分析---語(yǔ)法制導(dǎo)翻譯種類●1、自上而下語(yǔ)法制導(dǎo)翻譯：對(duì)每個(gè)文法符號(hào)配以語(yǔ)義動(dòng)作?！?、自下而上語(yǔ)法制導(dǎo)翻譯：我們主要討論LR語(yǔ)法制導(dǎo)翻譯第七章中間代碼的生成34精選PPT第一節(jié)概述二、翻譯方法第七章中間代碼的生成34精選PPT第一節(jié)概述三、語(yǔ)義子程序1、作用●用來(lái)描述一個(gè)產(chǎn)生式所對(duì)應(yīng)的翻譯工作。---如：改進(jìn)某些變量的值；查填各種符號(hào)表；發(fā)現(xiàn)并報(bào)告源程序錯(cuò)誤；產(chǎn)生中間代碼等。●注；這些翻譯工作很大程度上決定了要產(chǎn)生什么形式的中間代碼5精選PPT第一節(jié)概述三、語(yǔ)義子程序5精選PPT三、語(yǔ)義子程序2、寫法●語(yǔ)義子程序?qū)懺谠摦a(chǎn)生式后面的花括號(hào)內(nèi)。Xa{語(yǔ)義子程序}●注：在一個(gè)產(chǎn)生式中同一個(gè)文法符號(hào)可能出現(xiàn)多次，但它們代表的是不同的語(yǔ)義值，要區(qū)分可以加上角標(biāo)。如：EE(1)+E(2)3、語(yǔ)義值●為了描述語(yǔ)義動(dòng)作，需要為每個(gè)文法符號(hào)賦予不同的語(yǔ)義值：類型，地址，代碼值等。第一節(jié)概述6精選PPT三、語(yǔ)義子程序第一節(jié)概述6精選PPT第一節(jié)概述三、語(yǔ)義子程序4、語(yǔ)義棧●各個(gè)符號(hào)的語(yǔ)義值放在語(yǔ)義棧中---當(dāng)產(chǎn)生式進(jìn)行歸約時(shí)，需對(duì)產(chǎn)生式右部符號(hào)的語(yǔ)義值進(jìn)行綜合，其結(jié)果作為左部符號(hào)的語(yǔ)義值保存到語(yǔ)義棧中。●下推棧包含3部分：---狀態(tài)棧、符號(hào)棧和語(yǔ)義棧---注：語(yǔ)義棧與狀態(tài)棧和符號(hào)棧是同步變化的。7精選PPT第一節(jié)概述三、語(yǔ)義子程序7精選PPT第一節(jié)概述三、語(yǔ)義子程序注：1）若把語(yǔ)義子程序改成產(chǎn)生某種中間代碼的動(dòng)作，就能在語(yǔ)法分析制導(dǎo)下，隨著分析的進(jìn)展逐步生成中間代碼。2）若把語(yǔ)義子程序改成產(chǎn)生某種機(jī)器的匯編語(yǔ)言指令，就能隨著分析的進(jìn)展逐步生成某機(jī)器的匯編語(yǔ)言代碼。8精選PPT第一節(jié)概述三、語(yǔ)義子程序8精選PPT第一節(jié)概述例如：產(chǎn)生式語(yǔ)義子程序(0)S’E{PRINTE

●VAL}(1)EE(1)+E(2){E●VAL=E(1)●VAL+E(2)●VAL}(2)EE(1)*

E(2){E●VAL=E(1)●VAL*E(2)●VAL}(3)E(E(1)){E●VAL=E(1)●VAL}(4)Ei{E●VAL=LEXVAL}注：LEXVAL指的是詞法分析送來(lái)的機(jī)內(nèi)二進(jìn)制整數(shù)。9精選PPT第一節(jié)概述例如：9精選PPT下推棧SmE(2)E(2).VALSm-1+E(1)E(1).VAL……….S0#狀態(tài)符號(hào)VAL(語(yǔ)義）10精選PPT下推棧SmE(2)E(2).VALSm-1+E(1)E(1)第一節(jié)概述注：由于語(yǔ)義值是放在語(yǔ)義棧中的，它也可以用棧頂指針TOP指出，語(yǔ)義子程序改寫為：產(chǎn)生式語(yǔ)義子程序(0)S’E{PRINTVAL[TOP]}(1)EE(1)+E(2){VAL[TOP]=VAL[TOP]+VAL[TOP+2]}(2)EE(1)*

E(2){VAL[TOP]=VAL[TOP]*VAL[TOP+2]}(3)E(E(1)){VAL[TOP]=[TOP+1]}(4)Ei{VAL[TOP]=LEXVAL}注：LEXVAL指的是詞法分析送來(lái)的機(jī)內(nèi)二進(jìn)制整數(shù)。11精選PPT第一節(jié)概述注：由于語(yǔ)義值是放在語(yǔ)義棧中的，它也可以用棧頂指第一節(jié)概述例如：分析輸入串(7+9)*5#,并給出它的計(jì)算過(guò)程。分析表如下：12精選PPT第一節(jié)概述例如：分析輸入串(7+9)*5#,并給出它的計(jì)算狀態(tài)ACTIONGOTOi+*()#S0S3S211S4S5acc2S3

S2

63r4r4r4r4

4S3S275S3S2

86S4

S5

S9

7

r1(S4)S5(r1)

r1r1

8r1(S4)r2(S5)r2r2

9

r3

r3r3r313精選PPTACTIONGOTOi+*()#S0S3S211S4S5步驟狀態(tài)SYMVALINPUTACTION10#-(7+9)*5#20,2#(--7+9)*5#移進(jìn)30,2,3#(7---+9)*5#移進(jìn)40,2,6#(E--7+9)*5#r450,2,6,4#(E+--7-9)*5#移進(jìn)60,2,6,4,3#(E+9--7--)*5#移進(jìn)70,2,6,4,7#(E+E--7-9)*5#r480,2,6#(E--16)*5#r190,2,6,9#(E)--16-*5#移進(jìn)100,1#E--16*5#r3110,1,5#E*-16-5#移進(jìn)14精選PPT步驟狀態(tài)SYMVALINPUTACTION10#-(7+9)第一節(jié)概述四、常見(jiàn)的中間代碼形式1.四元式形式（Operator,Operand1,Operand2,Result)注：1）Operand1,Operand2,Result可能是用戶自定義的變量，也可能是編譯時(shí)引進(jìn)的變量，這里Operator是雙目運(yùn)算符，若只有一個(gè)運(yùn)算量，則是單目運(yùn)算符。2）四元式中變量采用符號(hào)表入口的地址，而不用變良的地址，因?yàn)檎Z(yǔ)義分析不僅需要變量的地址，還需要從符號(hào)表查到的變量的屬性，類型和地址等。15精選PPT第一節(jié)概述四、常見(jiàn)的中間代碼形式15精選PPT第一節(jié)概述四、常見(jiàn)的中間代碼形式2.三元式（Operator,Operand1,Operand2）注：1）這里三元式本身作為存放結(jié)果的單元。2）為了在其它三元式中利用當(dāng)前三元式的結(jié)果，需要對(duì)三元式進(jìn)行遍號(hào)。三元式的編號(hào)就作為相應(yīng)三元式的結(jié)果值。16精選PPT第一節(jié)概述四、常見(jiàn)的中間代碼形式16精選PPT第一節(jié)概述四、常見(jiàn)的中間代碼形式3、后綴表示式（逆波蘭表示式）Operand1Operand2Operator4、樹(shù)型表示法OperatorOperand2Operand1注：常用中間代碼表示法是四元式17精選PPT第一節(jié)概述四、常見(jiàn)的中間代碼形式OperatorOpera第二節(jié)簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句的翻譯一、賦值語(yǔ)句的翻譯----僅含簡(jiǎn)單變量的表達(dá)式和賦值語(yǔ)句的翻譯1、賦值語(yǔ)句的文法Ai=EEE+E|E*E|-E|(E)|i2、需要的語(yǔ)義過(guò)程N(yùn)EWTEMO函數(shù)：每次使用送回一個(gè)代表新臨時(shí)變量的序號(hào)，可認(rèn)為是送回T1,T2這樣的一些臨時(shí)變量；ENTRY(i)函數(shù)：用于查變量i的符號(hào)表入口地址；GEN(OP,ARG1,ARG2,RESULT)過(guò)程：產(chǎn)生一個(gè)四元式，并填入四元式序列表18精選PPT第二節(jié)簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句的翻譯一、賦值語(yǔ)句的翻譯18第二節(jié)簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句的翻譯一、賦值語(yǔ)句的翻譯3、需要的語(yǔ)義變量E●PLACE:與非終結(jié)符E相聯(lián)系的語(yǔ)義變量---值為某變量的符號(hào)表入口地址或臨時(shí)變量序號(hào)。---它與文法的非終結(jié)符相聯(lián)，分析過(guò)程就建立，不需要就消亡。19精選PPT第二節(jié)簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句的翻譯一、賦值語(yǔ)句的翻譯19產(chǎn)生式語(yǔ)義子程序(1)Ai=E{GEN(=,E●PLACE,_,ENTRY(i)}(2)E-E(1){T=NEWTEMP;----GEN(@,E(1)●PLACE,_,T);----E●PLACE=T}(3)EE(1)*E(2){T=NEWTEMP;GEN(*,E(1)●PLACE,E(2)●PLACE,T);E●PLACE=T}(4)EE(1)+E(2){T=NEWTEMP;GEN(+,E(1)●PLACE,E(2)●PLACE,T);E●PLACE=T}(5)E(E(1)){E●PLACE=E(1)●PLACE}(6)Ei{E●PLACE=ENTRY(i)}20精選PPT產(chǎn)生式輸入符號(hào)串SYM棧PLACE棧生成四元式A=-B*(C+D)#=-B*(C+D)#i--B*(C+D)#i=--B*(C+D)#i=----*(C+D)#i=-i----*(C+D)#i=-E---B*(C+D)#i=E--T1(@,B,-,T1)(C+D)#i=E*--T1-C+D)#i=E*(--T1--+D)#i=E*(i--T1--C+D)#i=E*(E--T1--C21精選PPT輸入符號(hào)串SYM棧PLACE棧生成四元式A=-B*(C+D)注：1、符號(hào)棧是為了介紹才列出的，實(shí)際上不存在。2、由于語(yǔ)義分析是在語(yǔ)法分析的過(guò)程中進(jìn)行的，所以狀態(tài)棧實(shí)際上是需要的，這里沒(méi)有寫出來(lái)。3、這個(gè)分析過(guò)程是針對(duì)整型變量做的。實(shí)際上在一個(gè)表達(dá)式中，可能出現(xiàn)各種不同類型的變量或常量，所以，編譯程序要么拒絕接受某種混合運(yùn)算，要么能產(chǎn)生有關(guān)類型轉(zhuǎn)換的指令。22精選PPT注：1、符號(hào)棧是為了介紹才列出的，實(shí)際上不存在。22精選PP第二節(jié)簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句的翻譯類型轉(zhuǎn)換對(duì)于表達(dá)式文法中的i是實(shí)型又可以是整型。對(duì)這種混合運(yùn)算，我們要先把整型量轉(zhuǎn)化為實(shí)型量，就需要為每個(gè)非終結(jié)符的語(yǔ)義值添加類型信息，用E●MODE表示非終結(jié)符E的類型信息。1、定義各非終結(jié)符的類型信息產(chǎn)生式EE(1)opE(2)的語(yǔ)義動(dòng)作中要加入關(guān)于E●MODE的語(yǔ)義規(guī)則的定義；--{IFE(1)●MODE=intANDE(2)●MODE=int--{IFE●MODE=intELSEE●MODE=r}23精選PPT第二節(jié)簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句的翻譯類型轉(zhuǎn)換23精選PPT第二節(jié)簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句的翻譯2、對(duì)運(yùn)算量進(jìn)行類型轉(zhuǎn)換例如：X=Y+I*J,其中X,Y是實(shí)型，I,J是整型。其四元式為：--(*I,I,J,T1)--(itr,T1,_,T2)--(+r,Y,T2,T3)--(=,T3,_,X)24精選PPT第二節(jié)簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句的翻譯2、對(duì)運(yùn)算量進(jìn)行類型轉(zhuǎn)第二節(jié)簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句的翻譯注：1)對(duì)運(yùn)算符也要指出相應(yīng)的類型（運(yùn)算符上加角標(biāo)），說(shuō)明是定點(diǎn)還是浮點(diǎn)遠(yuǎn)算。2)由于非終結(jié)符E的語(yǔ)義值有E●PLACE和E●MODE兩個(gè)，這兩者都要保存在語(yǔ)義棧中。3)在運(yùn)算量的類型較多的情況下，需要仔細(xì)推敲語(yǔ)義規(guī)則，否則語(yǔ)義子程序會(huì)變置累贅不填。25精選PPT第二節(jié)簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句的翻譯注：1)對(duì)運(yùn)算符也要指第三節(jié)布爾表達(dá)式的翻譯一、布爾表達(dá)式在程序設(shè)計(jì)語(yǔ)言中的作用--用作控制語(yǔ)句中的條件表達(dá)式--用于邏輯賦值語(yǔ)句中布爾表達(dá)式演算二、布爾表達(dá)式的組成--由布爾算符作用于布爾變量（或常量）或關(guān)系表達(dá)式而形成的。--布爾算符：∧,∨,--關(guān)系表達(dá)式的形式：E(1)ropE(2),其中rop是關(guān)系運(yùn)算符（如<,<=,=,<>,>=,>),E(1)和E(2)是算術(shù)表達(dá)式。26精選PPT第三節(jié)布爾表達(dá)式的翻譯一、布爾表達(dá)式在程序設(shè)計(jì)語(yǔ)言中的作用第三節(jié)布爾表達(dá)式的翻譯三、布爾表達(dá)式的文法：--G(B):EE∧E|E∨E|E|(E)|i|EaropEa--i為布爾變量或常量；Ea為算術(shù)表達(dá)式。注：1)此文法為二義文法，一般布爾算符的優(yōu)先順序?yàn)椋?∧,∨服從左結(jié)合律；關(guān)系運(yùn)算優(yōu)先級(jí)別高于布爾運(yùn)算。2)由于布爾表達(dá)式有兩種用途，所以有兩種不同的翻譯方法。27精選PPT第三節(jié)布爾表達(dá)式的翻譯三、布爾表達(dá)式的文法：27精選PPT第三節(jié)布爾表達(dá)式的翻譯四、布爾表達(dá)式在邏輯演算中的翻譯1、語(yǔ)義子程序由于布爾表達(dá)式演算與算術(shù)表達(dá)式計(jì)算非常類似，可以仿照算術(shù)表達(dá)式的翻譯方法，為每個(gè)產(chǎn)生式寫出語(yǔ)義子程序。28精選PPT第三節(jié)布爾表達(dá)式的翻譯四、布爾表達(dá)式在邏輯演算中的翻譯28產(chǎn)生式語(yǔ)義子程序(1)EEa(1)ropEa(2){T=NEWTEMP;GEN(rop,Ea(1)●PLACE,Ea(2)●PLACE,T);E●PLACE=T}(2)EEa(1)bopEa(2){T=NEWTEMP;GEN(bop,Ea(1)●PLACE,Ea(2)●PLACE,T);E●PLACE=T}(3)EE(1){T=NEWTEMP;GEN(,E(1)●PLACE,_,T);E●PLACE=T}(4)E(E(1)){E●PLACE=E(1)●PLACE}(5)Ei{E●PLACE=ENTRY(i)}29精選PPT產(chǎn)生式語(yǔ)第三節(jié)布爾表達(dá)式的翻譯四、布爾表達(dá)式在邏輯演算中的翻譯2、實(shí)例：對(duì)布爾式X+Y>Z∨A∧(B∨C)進(jìn)行翻譯：解：語(yǔ)法制導(dǎo)翻譯是在語(yǔ)法分析下的過(guò)程中進(jìn)行的，若利用G(B)文法的LR分析表對(duì)上句進(jìn)行LR分析，在其過(guò)程中進(jìn)行語(yǔ)義分析；則得到對(duì)上句進(jìn)行LR分析，在其過(guò)程中進(jìn)行語(yǔ)義分析；則得到的四元式序列是：--(+,X,Y,T1);E+E進(jìn)行歸約，識(shí)別了算術(shù)運(yùn)算--(>,T1,Z,T2);E>E進(jìn)行歸約，識(shí)別了關(guān)系運(yùn)算--(,B,_,T3);E歸約--(∨,T3,C,T4);E∨E進(jìn)行歸約--(∧,A,T4,T5);

E∧E進(jìn)行歸約--(∨,T2,T5,T6);

E∨E進(jìn)行歸約30精選PPT第三節(jié)布爾表達(dá)式的翻譯四、布爾表達(dá)式在邏輯演算中的翻譯30第三節(jié)布爾表達(dá)式的翻譯注：上面的翻譯質(zhì)量并不高，可以采取某種優(yōu)化措施：例如：對(duì)A∨B.若已知A的值是1.那么B的值就不需要知道就能得出A∨B=1；---可以表示為：IFATHENTRUEELSEB對(duì)A∧B若已知A的值是0，那么B的值就不需要知道就錯(cuò)得出A∧B=0；---可以表示為：IFATHENFALSEELSETRUE31精選PPT第三節(jié)布爾表達(dá)式的翻譯注：上面的翻譯質(zhì)量并不高，可以采取某第三節(jié)布爾表達(dá)式的翻譯五、控制語(yǔ)句中布爾式的翻譯1、控制語(yǔ)句中布爾式并不需要計(jì)算表達(dá)式的值，只用if-then-else來(lái)解釋∧,∨,,以來(lái)控制程序流向。IfEthenS1elseS2

E的代碼序列S1的代碼序列S2的代碼序列假真32精選PPT第三節(jié)布爾表達(dá)式的翻譯五、控制語(yǔ)句中布爾式的翻譯E的代碼序第三節(jié)布爾表達(dá)式的翻譯五、控制語(yǔ)句中的布爾式的翻譯2、控制語(yǔ)句中的布爾式的翻譯的四元式為以下三種：(juz,A1,_,P-ifA1thengotoP(jQ,A1,A2,-ifA1QA2thengotoP(j,_,_,P)-GotoP注：這些四元式都是轉(zhuǎn)移四元式，其中P為出口的四元式序號(hào)，與E的真假值相對(duì)應(yīng)的分別為真出口和假出口兩類四元式。33精選PPT第三節(jié)布爾表達(dá)式的翻譯五、控制語(yǔ)句中的布爾式的翻譯33精選例如：把語(yǔ)句ifA∨B<DthenS1elseS2翻譯成四元式解:(1)(jnz,A,_,(5));真出口;若A為真,執(zhí)行S1代碼(2)(j,_,(3));若A為假，看∨右邊的表達(dá)式值(3)(j<,B,D,(5));真出口,∨右邊的表達(dá)式值為真(4)(j,_,_,(p+1));假出口,∨右邊的表達(dá)式值為假(5)S1語(yǔ)句的第一個(gè)四元式……..(p)(j,_,_,(q));執(zhí)行完S1代碼后跳過(guò)S2代碼段(p+1)S2語(yǔ)句的第一個(gè)四元式…….(q)此語(yǔ)句的后繼語(yǔ)句34精選PPT例如：把語(yǔ)句ifA∨B<DthenS1elseS2第三節(jié)布爾表達(dá)式的翻譯五、控制語(yǔ)句中布爾式的翻譯4、增加語(yǔ)義值E●TC、E●FC的值也可以放在語(yǔ)義棧中，即下推棧又增加了兩欄.∧E(1)…..S0#___SSYMPLACETCFC分析棧語(yǔ)義棧35精選PPT第三節(jié)布爾表達(dá)式的翻譯五、控制語(yǔ)句中布爾式的翻譯∧E(1)第三節(jié)布爾表達(dá)式的翻譯五、控制語(yǔ)句中布爾式的翻譯5、文法G(B)各產(chǎn)生式的語(yǔ)義子程序----文法：EEAE|E0E|E|(E)|i|EaropEaEAE∧E0E∨語(yǔ)義子程序：--(1)Ei{E●TC=NXQ;E●FC=NXQ+1;--GEN(jnz,ENTRY(i),_,O);--GEN(j,_,_,O)--注：將布爾型操作數(shù)進(jìn)行歸約，產(chǎn)生兩個(gè)四元式；無(wú)論真假都不知該轉(zhuǎn)到哪個(gè)四元式上去，故轉(zhuǎn)向036精選PPT第三節(jié)布爾表達(dá)式的翻譯五、控制語(yǔ)句中布爾式的翻譯36精選P例如：將控制語(yǔ)句中的A∨B<D翻譯成四元式解:(1)(jnz,A,_,0);真出口；(2)(j,_,_,0);若A為假,看∨右邊的表達(dá)式的值TC:1;FC:2;37精選PPT例如：將控制語(yǔ)句中的A∨B<D37精選PPT第三節(jié)布爾表達(dá)式的翻譯五、控制語(yǔ)句中布爾式的翻譯5、文法G(B)各產(chǎn)生式的語(yǔ)義子程序(7)E0E(1)∨---{BACKPATCH(E(1)●FC,NXQ);---E0●TC=E(1)●TC;}注：對(duì)∨進(jìn)行歸約之后，若E(1)=0,則∨運(yùn)算的結(jié)果就要看∨右邊式子的值了，所以表示E(1)=0的四元式應(yīng)轉(zhuǎn)移到∨歸約后的下一個(gè)四元式，即判斷∨右邊式子的值的第一個(gè)四元式。38精選PPT第三節(jié)布爾表達(dá)式的翻譯五、控制語(yǔ)句中布爾式的翻譯38精選P第三節(jié)布爾表達(dá)式的翻譯五、控制語(yǔ)句中布爾式的翻譯5、文法G(B)各產(chǎn)生式的語(yǔ)義子程序PROCEDUREBACKPATCH(p,t){Q=P;WHILE(Q<>0){q=四元式Q第四段的內(nèi)容；把t填入四元式Q的第四段；Q=q;}}注：其算法思想是：從鏈頭算起，邊找邊讀，直到鏈尾為止。39精選PPT第三節(jié)布爾表達(dá)式的翻譯五、控制語(yǔ)句中布爾式的翻譯39精選P例如：將控制語(yǔ)句中的A∨B<D翻譯成四元式解:(1)(jnz,A,_,0);真出口；(2)(j,_,_,(3));若A為假，看∨右邊的表達(dá)式的值E0●TC:1;FC已回填40精選PPT例如：將控制語(yǔ)句中的A∨B<D40精選PPT第三節(jié)布爾表達(dá)式的翻譯五、控制語(yǔ)句中布爾式的翻譯5、文法G(B)各產(chǎn)生式的語(yǔ)義子程序(2)EEaropEa--{E●TC=NXQ;E●FC=NXQ+1;--GEN(jrop,Ea(1)●PLACE,Ea(2)●PLACE,0);--GEN(j,_,_,0)}41精選PPT第三節(jié)布爾表達(dá)式的翻譯五、控制語(yǔ)句中布爾式的翻譯41精選P例如：將控制語(yǔ)句中的A∨B<D翻譯成四元式解:(1)(jnz,A,_,0);真出口(2)(j,_,_,(3));若A為假,看∨右邊的表達(dá)式值(3)(j<,B,D,0);真出口,∨右邊的表達(dá)式值為真(4)(j,_,_,0);假出口,∨右邊的表達(dá)式值為假E●TC:3;E●FC:4;42精選PPT例如：將控制語(yǔ)句中的A∨B<D42精選PPT第三節(jié)布爾表達(dá)式的翻譯五、控制語(yǔ)句中布爾式的翻譯5、文法G(B)各產(chǎn)生式的語(yǔ)義子程序(8)EE0E(2)--{E●FC=E(2)●FC;--E●TC=MERG(E0●TC,E(2)●TC}注：由于E的真假?zèng)Q定于E(2)為假時(shí)它們的轉(zhuǎn)移相同；由于E(1)或E(2)為真時(shí)都導(dǎo)致問(wèn)真，所以它們?yōu)檎娴那闆r要合并起來(lái)。43精選PPT第三節(jié)布爾表達(dá)式的翻譯五、控制語(yǔ)句中布爾式的翻譯43精選P例如：將控制語(yǔ)句中的A∨B<D翻譯成四元式解:(1)(jnz,A,_,0);真出口(2)(j,_,_,(3));若A為假,看∨右邊的表達(dá)式值(3)(j<,B,D,0);真出口,∨右邊的表達(dá)式值為真(4)(j,_,_,0);假出口,∨右邊的表達(dá)式值為假E●TC:3，1;E●FC:4;44精選PPT例如：將控制語(yǔ)句中的A∨B<D44精選PPTFUNCTIONMERG(P1,P2);{IFP2=0MERG=P1WHILE四元式P的第4段內(nèi)容不為0{P=四元式P的第4段內(nèi)容；把P1填進(jìn)四元式P的第四段；MERG=P2;}}}注：算法思想：找到P2的鏈尾，然后將P1連接到P2的鏈尾。45精選PPTFUNCTIONMERG(P1,P2);45精選PPT第三節(jié)布爾表達(dá)式的翻譯(3)E(E(1)){E●TC=E(1)●TC;E●FC=E(1)●FC}(4)EE(1){E●TC=E(1)●FC;E●FC=E(1)●FC}(5)EAE(1)∧--{BACKPATCH(E●TC,NXQ);--EA●FC=E(1)●FC;}(6)EEAE(2)--{E●TC=E(1)●TC;--E●FC=MERG(EA●FC,E(2)●FC}46精選PPT第三節(jié)布爾表達(dá)式的翻譯(3)E(E(1)){E第三節(jié)布爾表達(dá)式的翻譯五、控制語(yǔ)句中布爾式的翻譯例如：將布爾式A∧B∨C在語(yǔ)法制導(dǎo)下翻譯成四元式。INPUTSYMTCFC四元式A∧B∨C##--∧B∨C##i----∧B∨C##E-1-21.(jnz,a,_,(3))B∨C##E∧-1--2-2.(j,_,_.(5))B∨C##EA---2∨C##EAi----2-47精選PPT第三節(jié)布爾表達(dá)式的翻譯五、控制語(yǔ)句中布爾式的翻譯INPUTINPUTSYMTCFC四元式∨C##EAE--3-243.(jnz,B,_,0)∨C##E-3-44.(j,_,_,(5))C##E∨-3--4-

C##E0-3--

C##E0-3----##E0i-3------##E0E-3-5----65.(jnz,C,_,0)##E0E-36--55.(j,_,_,(3))##E-6-5成功48精選PPTINPUTSYMTCFC四元式∨C##EAE--3-24第四節(jié)控制語(yǔ)句的翻譯一、控制語(yǔ)句的種類：無(wú)條件轉(zhuǎn)換語(yǔ)句條件語(yǔ)句迭代語(yǔ)句循環(huán)語(yǔ)句分支語(yǔ)句49精選PPT第四節(jié)控制語(yǔ)句的翻譯一、控制語(yǔ)句的種類：49精選PPT第四節(jié)控制語(yǔ)句的翻譯二、標(biāo)號(hào)和轉(zhuǎn)移語(yǔ)句(GOTO)1、標(biāo)號(hào)和轉(zhuǎn)移語(yǔ)句(GOTO)(1)標(biāo)號(hào)語(yǔ)句---GOTO語(yǔ)句實(shí)現(xiàn)無(wú)條件轉(zhuǎn)移，要確定轉(zhuǎn)移的目的語(yǔ)句，需要給語(yǔ)句加標(biāo)號(hào)。---帶標(biāo)號(hào)的語(yǔ)句形式：L:SL是標(biāo)號(hào)(2)標(biāo)號(hào)的定義和使用：---先定義后使用L:S……..GOTOL---先使用后定義GOTOL……L:S50精選PPT第四節(jié)控制語(yǔ)句的翻譯二、標(biāo)號(hào)和轉(zhuǎn)移語(yǔ)句(GOTO)50第四節(jié)控制語(yǔ)句的翻譯2、先定義后使用(1)形式：L:S---…….---GOTOL---…….(2)定義和使用表號(hào)的文法---SgotoL---Labeli:(3)翻譯過(guò)程：---當(dāng)遇到定義性的標(biāo)號(hào)語(yǔ)句時(shí)，將L歸約為L(zhǎng)abel，再將L填入符號(hào)表，如下：51精選PPT第四節(jié)控制語(yǔ)句的翻譯2、先定義后使用51精選PPTNAMEINFORMATIONCAT……..定義否地址…………..L標(biāo)號(hào)已S.QUAD……..S.QUAD:即S對(duì)應(yīng)的入口四元式序號(hào)。當(dāng)后面遇到GOTOL語(yǔ)句時(shí)，便產(chǎn)生四元式：(j,_,_,P),其中P=S.QUAD52精選PPTNAMEINFORMATIONCAT……..定義否地址………2、先使用后定義(1)形式：GOTOL’------……------GOTOL’------…….------GOTOL’------…….------L’:S(2)翻譯過(guò)程：----由于這里是先使用，所以當(dāng)遇到標(biāo)號(hào)L’時(shí)，它還未定義，故而填入符號(hào)表時(shí)情況與上不同，表如下：53精選PPT2、先使用后定義53精選PPTNAMEINFORMATIONCAT……..定義否地址…………..L‘標(biāo)號(hào)未P……..(2)翻譯過(guò)程：(a)填符號(hào)表：將定義否欄填“未”，地址檔暫填即將生成的四元式序號(hào)P,CAT欄填“標(biāo)號(hào)”；(b)生成四元式(P)(j,_,_,0),等待回填；54精選PPTNAMEINFORMATIONCAT……..定義否地址………NAMEINFORMATIONCAT……..定義否地址…………..L’標(biāo)號(hào)未q……..(c)當(dāng)遇到第2個(gè)使用性標(biāo)號(hào)L‘時(shí)，修改符號(hào)表，僅將L’這一行的地址欄內(nèi)容修改為即將生成的四元式序號(hào)q;(b)生成四元式(q)(j,_,_,P),其中第四段的P取自符號(hào)表的地址欄在修改前的內(nèi)容，即形成一個(gè)需要回填的鏈，不斷重復(fù)(c)(d).55精選PPTNAMEINFORMATIONCAT……..定義否地址………NAMEINFORMATIONCAT……..定義否地址…………..L’標(biāo)號(hào)未r……..(p)(j,_,_,0)(q)(j,_,_,p)(r)(j,_,_,q)56精選PPTNAMEINFORMATIONCAT……..定義否地址………第四節(jié)控制語(yǔ)句的翻譯二、標(biāo)號(hào)和轉(zhuǎn)移語(yǔ)句(GOTO)2、先使用后定義(2)翻譯過(guò)程：---e)當(dāng)定義性語(yǔ)句L’:S出現(xiàn)時(shí)，用S語(yǔ)句所對(duì)應(yīng)的第一個(gè)四元式序號(hào)回填這個(gè)鏈，即使用BACKPATCH過(guò)程。---注：此鏈表的鏈?zhǔn)自诜?hào)表的相應(yīng)行的地址欄內(nèi)。(3)形式化的語(yǔ)義子程序：---產(chǎn)生式語(yǔ)義子程序---SgotoL程序1---labeli:程序257精選PPT第四節(jié)控制語(yǔ)句的翻譯二、標(biāo)號(hào)和轉(zhuǎn)移語(yǔ)句(GOTO)57----{查符號(hào)表：----若L不在表中，在表中建L這行，CAT欄置標(biāo)號(hào)，定義否填“未”，地址為NXQ;GEN(j,_,_,0);----若L在表中，但未定義，則;P=L地址；L.地址為NXQ;GEN(j,_,_,p);----若L在表中，已定義，則:P=L.地址；GEN(j,_,_,p);----}58精選PPT----{查符號(hào)表：58精選PPT----{查符號(hào)表：----若L不在表中，在表中建L這行，CAT欄置標(biāo)號(hào)，定義否填“已”，地址為NXQ;----若L已在表中，但定義否填“已”或CAT<>標(biāo)號(hào)，則出錯(cuò)；----否則，{將定義否改為“已”；----q=L.地址；----BACKPATCH(q.NXQ);----L.地址=NXQ;}----}59精選PPT----{查符號(hào)表：59精選PPT第四節(jié)控制語(yǔ)句的翻譯三、IF語(yǔ)句的翻譯1、描述IF語(yǔ)句的文法----SifEthenS(1)----SifEthenS(1)elseS(2)2、IF語(yǔ)句的翻譯---(1)完成對(duì)布爾式E的翻譯，獲得一元四元式，并留下兩個(gè)待續(xù)的語(yǔ)義值E●EC，E●FC;---(2)掃描完then之后，就得到了E的真出口，用BACKPATCH(E●EC,NXQ)過(guò)程或填；---(3)翻譯S(1)，它可能會(huì)是任何一種語(yǔ)句，總可以遞歸地調(diào)用語(yǔ)句翻譯過(guò)程來(lái)完成，得到一組四元式序列；60精選PPT第四節(jié)控制語(yǔ)句的翻譯三、IF語(yǔ)句的翻譯60精選PPT第四節(jié)控制語(yǔ)句的翻譯三、IF語(yǔ)句的翻譯2、IF語(yǔ)句的翻譯---(4)若遇到else，表示S(1)已翻譯完，應(yīng)無(wú)條件生成一條GOTO四元式(j,_,_,0)轉(zhuǎn)到S(2)語(yǔ)句后面，以示這個(gè)IF語(yǔ)句已執(zhí)行結(jié)束。但這個(gè)無(wú)條件轉(zhuǎn)移語(yǔ)句究竟轉(zhuǎn)到什么地方去,是不確定的.甚至在翻譯完S(2)語(yǔ)句之后也不一定確定下來(lái)。遇到else還表示已獲得E的假出口。例如：語(yǔ)句---ifE1thenifE2thenS1elseS2elseS3注：由于轉(zhuǎn)移指令的轉(zhuǎn)移目標(biāo)只能等到出口明朗了才能回填。此時(shí)應(yīng)把該待填的四元式序號(hào)并鏈后存在與代表整個(gè)語(yǔ)句的非終結(jié)符S相聯(lián)系的語(yǔ)義棧S●CHAIN中。61精選PPT第四節(jié)控制語(yǔ)句的翻譯三、IF語(yǔ)句的翻譯61精選PPT第四節(jié)控制語(yǔ)句的翻譯三、IF語(yǔ)句的翻譯2、IF語(yǔ)句的翻譯(4)若不遇到else，那么布爾式的假出口與S(1)的結(jié)束出口都表示IF語(yǔ)句的結(jié)束。(5)翻譯S(2)語(yǔ)句成四元式序列。它執(zhí)行過(guò)后也表示IF語(yǔ)句應(yīng)該結(jié)束了，它的結(jié)束出口和S(1)是一樣的，可將它們出口并鏈，鏈?zhǔn)字糜赟●CHAIN.姑，條件語(yǔ)句翻譯之后，除了生成相應(yīng)E,S(1),S(2)的四元式之外，還剩下一個(gè)待填語(yǔ)句鏈，鏈?zhǔn)自赟●CHAIN中，出口明確后接此回填。62精選PPT第四節(jié)控制語(yǔ)句的翻譯三、IF語(yǔ)句的翻譯62精選PPT第四節(jié)控制語(yǔ)句的翻譯三、IF語(yǔ)句的翻譯3、改寫產(chǎn)生式SifEthenS(1)elseS(2)改寫為：---CifEthen---TCS(1)else---STS(2)

SifEthenS(1)改寫為：--CifEthen---SCS(1)63精選PPT第四節(jié)控制語(yǔ)句的翻譯三、IF語(yǔ)句的翻譯63精選PPT第四節(jié)控制語(yǔ)句的翻譯三、IF語(yǔ)句的翻譯4、語(yǔ)義子程序CifEthen{BACKPATCH(E●EC,NXQ);C●CHAIN=E●FC;}TCS(1)else{q=NXQ;GEN(j,_,_,0);BACKPATCH(C●CHAIN,NXQ);T●CHAIN=MERG(S(1)●CHAIN,q)}STS(2){S●CHAIN=MERG(T●CHAIN,S(2)●CHAIN)}SCS(1){S●CHAIN=MERG(T●CHAIN,S(2)●CHAIN)}64精選PPT第四節(jié)控制語(yǔ)句的翻譯三、IF語(yǔ)句的翻譯64精選PPT第四節(jié)控制語(yǔ)句的翻譯例如：翻譯無(wú)條件嵌套語(yǔ)句：ifathenifbthenA:=2elseA:=3ELSEifcthenA:=4ElseA:=5翻譯成四元式為：(1)(jnz,a,_,0)(2)(j,_,_,0)(3)(jnz,b,_,0)(4)(j,_,_,0)(5)(:=,2,_,A)(6)(j,_,_,0)(7)(:=,3,_,A)(8)(j,_,_,0)65精選PPT第四節(jié)控制語(yǔ)句的翻譯例如：翻譯無(wú)條件嵌套語(yǔ)句：(1)(第四節(jié)控制語(yǔ)句的翻譯(1)(jnz,a,_,0)(2)(j,_,_,0)(3)(jnz,b,_,0)(4)(j,_,_,0)(5)(:=,2,_,A)(6)(j,_,_,0)(7)(:=,3,_,A)(8)(j,_,_,0)(8)(j,_,_,6)(9)(jnz,c,_,11)(10)(j,_,_,13)(11)(:=,4,_,A)(12)(j,_,_,8)(13)(:=,5,_.A)66精選PPT第四節(jié)控制語(yǔ)句的翻譯(1)(jnz,a,_,0)(8)aS4(A:=5)bS1(A:=2)S2(A:=3)cS3(A:=4)1,23,49,101113751286TRUEFALSEifathenifbthenA:=2elseA:=3ELSEifcthenA:=4ElseA:=567精選PPTaS4(A:=5)bS1(A:=2)S2(A:=3)cS3(第四節(jié)控制語(yǔ)句的翻譯四、WHILE語(yǔ)句的翻譯1、WHILE語(yǔ)句的文法SwhileEdoS(1)2、WHILE語(yǔ)句的翻譯思想(1)翻譯E代碼段，并留兩個(gè)待填的E●TC,E●TC鏈(2)掃描過(guò)do之后，就可以回填E●TC(3)翻譯S(1)成代碼段,S(1)翻譯之后，應(yīng)無(wú)條件轉(zhuǎn)到E代碼段的第一條四元式。：1)因此,開(kāi)始翻譯while語(yǔ)句時(shí)，應(yīng)留下第一條四元式序號(hào)，以備S(1)翻譯之后用。2)E為假時(shí)需回填，此時(shí)E●TC作為S●CHAIN一部分，以便回填。68精選PPT第四節(jié)控制語(yǔ)句的翻譯四、WHILE語(yǔ)句的翻譯68精選P第四節(jié)控制語(yǔ)句的翻譯四、WHILE語(yǔ)句的翻譯3、改寫產(chǎn)生式SwhileEdoS(1)改寫為：---Wwhile---WdWEdo---SWdS(1)69精選PPT第四節(jié)控制語(yǔ)句的翻譯四、WHILE語(yǔ)句的翻譯69精選P第四節(jié)控制語(yǔ)句的翻譯4、語(yǔ)義子程序Wwhile{W●QUAD=NXQ}WdWEdo{BACKPATCH(E●FC,NXQ);---Wd●CHAIN=E●FC;---Wd●QUAD=W●QUAD;}SWdS(1)BACKPATCH(S(1)●CHAIN,Wd●QUAD);---GEN(j,_,_,Wd●QUAD);---S●CHAIN=Wd●CHAIN}70精選PPT第四節(jié)控制語(yǔ)句的翻譯4、語(yǔ)義子程序70精選PPT第四節(jié)控制語(yǔ)句的翻譯例如：翻譯While(A<B)doIf(C<D)thenX:=Y+Z;翻譯為:(100)(j<,A,B,0)(101)(j,_,_,0)(102)(j<,C,D,0)(103)(j,_,_,(100))(104)(+,Y,Z,T1)(105)(:=,T1,_,X)(106)(j,_,_,(100))71精選PPT第四節(jié)控制語(yǔ)句的翻譯例如：翻譯71精選PPT第四節(jié)控制語(yǔ)句的翻譯七、復(fù)合語(yǔ)句的翻譯1、文法SbeginLendLSLLSSLSL72精選PPT第四節(jié)控制語(yǔ)句的翻譯七、復(fù)合語(yǔ)句的翻譯72精選PPT第四節(jié)控制語(yǔ)句的翻譯七、復(fù)合語(yǔ)句的翻譯2、語(yǔ)義子程序(1)LS{L●CHAIN=S●CHAIN;}(2)LSL{BACKPATCH(L●CHAIN,NXQ);}(3)LLSS{L●CHAIN=S●CHAIN;}(4)SbeginLend---{BACKPATCH(L●CHAIN,NXQ);---S●CHAIN=0;}73精選PPT第四節(jié)控制語(yǔ)句的翻譯七、復(fù)合語(yǔ)句的翻譯73精選PPT第五節(jié)數(shù)組元素及其在賦值語(yǔ)句中的翻譯一、數(shù)組及其下標(biāo)變量地址的計(jì)算1、數(shù)組分類：---一維數(shù)組，二維數(shù)組，多維數(shù)組---確定數(shù)組，可變數(shù)組：根據(jù)數(shù)組所需存儲(chǔ)空間是否在編譯時(shí)就已知道2、多維數(shù)組的存放---按行存放---按列存放（FORTRAN)---只要知道數(shù)組的首地址，及每個(gè)數(shù)組元素占多少內(nèi)存單元，就可計(jì)算出任一數(shù)組元素的地址。74精選PPT第五節(jié)數(shù)組元素及其在賦值語(yǔ)句中的翻譯一、數(shù)組及其下標(biāo)變量地例如：2維數(shù)組定義為：---Array[L1:u1,L2:u2]---令di=ui-Li+1,i=1,2,稱為每一維尺寸---D=a+((i1-L1)d2+(i2-L2))*/*m為每個(gè)元素所占尺寸*/改寫為D=CONSPART+VARPART---CONSPART=a-CC=(L1d2+L2)*m---VARPART=(i1d2+i2)*m75精選PPT例如：2維數(shù)組定義為：75精選PPT:CONSPART稱作不變部分，它和數(shù)組下標(biāo)無(wú)關(guān)，只和各維尺寸和下界有關(guān)；只需計(jì)算一次，其中C在編譯時(shí)就可算出。VARPART稱作可變部分，它和數(shù)組下標(biāo)有關(guān)，必須根據(jù)下標(biāo)值，轉(zhuǎn)換成相應(yīng)代碼，待運(yùn)行時(shí)計(jì)算出。76精選PPT:CONSPART稱作不變部分，它和數(shù)組下標(biāo)無(wú)關(guān)，只和各維尺第五節(jié)數(shù)組元素及其在賦值語(yǔ)句中的翻譯一、數(shù)組及其下標(biāo)變量地址的計(jì)算3、編譯程序?qū)?shù)組說(shuō)明的處理當(dāng)遇到數(shù)組說(shuō)明時(shí)，必須把數(shù)組的有關(guān)信息記錄在一張“內(nèi)情向量”表中，以便以后計(jì)算數(shù)組下標(biāo)變量地址時(shí)引用這些信息。內(nèi)情向量表的結(jié)構(gòu)：一維數(shù)，各維上下界，首地址，類型L1u1d1L2u2d2….…..….LnundnnCtypea77精選PPT第五節(jié)數(shù)組元素及其在賦值語(yǔ)句中的翻譯一、數(shù)組及其下標(biāo)變量地第五節(jié)數(shù)組元素及其在賦值語(yǔ)句中的翻譯一、數(shù)組及其下標(biāo)變量地址的計(jì)算3、編譯程序?qū)?shù)組說(shuō)明的處理1)對(duì)于確定的數(shù)組來(lái)說(shuō)：內(nèi)情向量可登記在編譯時(shí)的符號(hào)表中；2)對(duì)于可變數(shù)組來(lái)說(shuō)：(1)內(nèi)情向量在編譯時(shí)無(wú)法知道，只有在運(yùn)行時(shí)才能算出來(lái)；因此，編譯程序必須為可變數(shù)組設(shè)置一個(gè)存儲(chǔ)空間，以便運(yùn)行對(duì)建立相應(yīng)的內(nèi)情向量表。(2)這樣,就必須在編譯時(shí)為運(yùn)行程序準(zhǔn)備好調(diào)用的運(yùn)行子程序，我們不作討論。78精選PPT第五節(jié)數(shù)組元素及其在賦值語(yǔ)句中的翻譯一、數(shù)組及其下標(biāo)變量地第五節(jié)數(shù)組元素及其在賦值語(yǔ)句中的翻譯二、確定數(shù)組的數(shù)組元素引用的中間代碼形式1、訪問(wèn)數(shù)組元素可設(shè)想為：把它的VARPART計(jì)算在某一變址單元T中，用CONSPART作為“基礎(chǔ)”。然后以變址方式訪問(wèn)存儲(chǔ)單元---CONPART[T],靜態(tài)數(shù)組CONSPART=a-C,C可以從內(nèi)情向量表中查到，而a在運(yùn)行時(shí)一定可確定下來(lái)，所以可以生成a-C代碼，待運(yùn)行時(shí)再確定。假定T1是用于存放CONSPART的臨時(shí)單元，T1=a-C那么用T1[T]表示數(shù)組元素的地址79精選PPT第五節(jié)數(shù)組元素及其在賦值語(yǔ)句中的翻譯二、確定數(shù)組的數(shù)組元素第五節(jié)數(shù)組元素及其在賦值語(yǔ)句中的翻譯三、按行存放的賦值語(yǔ)句中的數(shù)組元素的翻譯2、訪問(wèn)數(shù)組元素引用數(shù)組元素：----（=[]，T1,[T],_,X):這是一個(gè)變址取數(shù)組四元式。含義相當(dāng)于X=T1[T].對(duì)數(shù)組元素賦值：----（[]=,X,_,T1[T]):這是一個(gè)變址存數(shù)四元式。含義相當(dāng)于：T1[J]=X80精選PPT第五節(jié)數(shù)組元素及其在賦值語(yǔ)句中的翻譯三、按行存放的賦值語(yǔ)句第五節(jié)數(shù)組元素及其在賦值語(yǔ)句中的翻譯三、按行存放的賦值語(yǔ)句中的數(shù)組元素的翻譯1、文法----AV:=E----Vi[Elist]|i----ElistElist,E|E----EEopE|(E)|V/*op表示各種算術(shù)運(yùn)算*/：V可以是簡(jiǎn)單變量也可以是下標(biāo)變量.這個(gè)遞歸定義可形成數(shù)組嵌套數(shù)組結(jié)構(gòu).81精選PPT第五節(jié)數(shù)組元素及其在賦值語(yǔ)句中的翻譯三、按行存放的賦值語(yǔ)句第五節(jié)數(shù)組元素及其在賦值語(yǔ)句中的翻譯三、按行存放的賦值語(yǔ)句中的數(shù)組元素的翻譯2、文法改寫---AV:=E---VElist]|I---ElistElist(1),E|i[E---EEopE|(E)|V注：把數(shù)組名i和最左下標(biāo)表達(dá)式寫在一起就表示為數(shù)組i開(kāi)始計(jì)算第一個(gè)下標(biāo)，同時(shí)使我們?cè)谡麄€(gè)下標(biāo)串Elist的翻譯過(guò)程中隨時(shí)都能知道數(shù)組i的符號(hào)表入口地址及表中相應(yīng)信息。82精選PPT第五節(jié)數(shù)組元素及其在賦值語(yǔ)句中的翻譯三、按行存放的賦值語(yǔ)句第五節(jié)數(shù)組元素及其在賦值語(yǔ)句中的翻譯三、按行存放的賦值語(yǔ)句中的數(shù)組元素的翻譯3、相關(guān)語(yǔ)義變量和函數(shù)過(guò)程語(yǔ)義變量：----ARRAY:數(shù)組名在符號(hào)表的入口地址----DIM：數(shù)組下標(biāo)維數(shù)計(jì)數(shù)器----PLACE:語(yǔ)義變量，在符號(hào)表入口地址或臨時(shí)變量的序號(hào)----OFFSET:簡(jiǎn)單變量：OFFSET=null下標(biāo)變量：OFFSET保存已計(jì)算出的VARPART83精選PPT第五節(jié)數(shù)組元素及其在賦值語(yǔ)句中的翻譯三、按行存放的賦值語(yǔ)句第五節(jié)數(shù)組元素及其在賦值語(yǔ)句中的翻譯三、按行存放的賦值語(yǔ)句中的數(shù)組元素的翻譯3、相關(guān)語(yǔ)義變量和函數(shù)過(guò)程函數(shù)過(guò)程：---LIMIT[ARRAY,K]:通過(guò)符號(hào)表查內(nèi)情向量表，返回第k維的尺寸dk---HEAD[ARRAY]:取得數(shù)組首地址a,或查內(nèi)情向量表，或等運(yùn)行時(shí)分配得到---CONS[ARRAY]:查內(nèi)情向量表,得C值---TYPE[ARRAY]:查內(nèi)情向量表TYPE項(xiàng)，返回一個(gè)數(shù)組元素，占有的字單元數(shù)m值。84精選PPT第五節(jié)數(shù)組元素及其在賦值語(yǔ)句中的翻譯三、按行存放的賦值語(yǔ)句第五節(jié)數(shù)組元素及其在賦值語(yǔ)句中的翻譯三、按行存放的賦值語(yǔ)句中的數(shù)組元素的翻譯4、語(yǔ)義子程序---(1)AV:=E---{IF(V●OFFSET=null()GEN(=,E●PLACe,_,V●PLACE);---ELSE---GEN([]=,E●PLACE,_,V●PLACE[V●OFFSET])}85精選PPT第五節(jié)數(shù)組元素及其在賦值語(yǔ)句中的翻譯三、按行存放的賦值語(yǔ)句第五節(jié)數(shù)組元素及其在賦值語(yǔ)句中的翻譯三、按行存放的賦值語(yǔ)句中的數(shù)組元素的翻譯4、語(yǔ)義子程序(2)EE(1)opE(2){T=NEWTEMP;GEN(op,E(1)●PLACE,E(2)●PLACE,T);E●PLACE=T}(3)E(E(1)){E●PLACE=E(1)●PLACE}(4)EV{IF(V●OFFSET=null)---E●PLACE=V●PLACE;---ELSE---{T=NEWTEMP;---GEN(=[],E●PLACE[V●OFFSET],_,T);---E●PLACE=T;}}86精選PPT第五節(jié)數(shù)組元素及其在賦值語(yǔ)句中的翻譯三、按行存放的賦值語(yǔ)句第五節(jié)數(shù)組元素及其在賦值語(yǔ)句中的翻譯(5)VElist]{IF(TYPE[ARRAY]<>1)---{T=NEWTEMP;---GEN(*,EList●PLACE,TYPE[ARRAY],T);---Elist●PLACE=T;}---V●OFFSET=Elist●PLACE;---T=NEWTEMP;---GEN(_,HEAD[ARRAY],CONS[ARRAY],T);---V●PLACE=T}(6)Vi{V●PLACE=ENTRY[i];---V●OFFSET=null}87精選PPT第五節(jié)數(shù)組元素及其在賦值語(yǔ)句中的翻譯(5)VE第五節(jié)數(shù)組元素及其在賦值語(yǔ)句中的翻譯4、語(yǔ)義子程序(7)ElistElist(1),E{T=NEWTEMP;----K=Elist(1)●DIMT1;----dk=LIMIT(Elist(1)●ARRAY,k);----GEN(*,Elist(1)●PLACE,dk,T);----T1=NEWTEMP;----GEN(+,T,E●PLACE,T1);----Elist●ARRAY=Elist(1)●ARRAY;----Elist●PLACE=T1;----Elist●DIM=K;88精選PPT第五節(jié)數(shù)組元素及其在賦值語(yǔ)句中的翻譯4、語(yǔ)義子程序88精選第五節(jié)數(shù)組元素及其在賦值語(yǔ)句中的翻譯4、語(yǔ)義子程序(8)Elisti[E-----{Elist●PLACE=E●PLACE;-----Elist●DIM=1;-----Elist●ARRAY=ENTRY(i)}89精選PPT第五節(jié)數(shù)組元素及其在賦值語(yǔ)句中的翻譯4、語(yǔ)義子程序89精選第五節(jié)數(shù)組元素及其在賦值語(yǔ)句中的翻譯例如：數(shù)組說(shuō)明為：ARRAY[1:10,1:20];且從內(nèi)情向量表查得數(shù)組首地址為a,C=21,d2=20,m=1為X:=A[I,J]生成四元式序列：解：四元式序列為：----(1)(*,I,20,T1)----(2)(+,T1,J,T2)----(3)(-,a,21,T3)----(4)(=[],T3[T2],_,T4)----(5)(:=,T4,_,X)90精選PPT第五節(jié)數(shù)組元素及其在賦值語(yǔ)句中的翻譯例如：數(shù)組說(shuō)明為：AR第六節(jié)過(guò)程調(diào)用語(yǔ)句一、過(guò)程調(diào)用1、過(guò)程---定義和調(diào)用過(guò)程是程序語(yǔ)言的主要特征之一，過(guò)程是模塊化程序設(shè)計(jì)的主要手段，同時(shí)也是節(jié)省程序代碼和擴(kuò)充語(yǔ)言能力的主要途徑。2、過(guò)程調(diào)用---實(shí)質(zhì)是把程序控制轉(zhuǎn)到子程序.3、過(guò)程調(diào)用中遇到的問(wèn)題：---子程序完成后如何回到主調(diào)程序；---子程序回到主調(diào)程序時(shí)，運(yùn)行環(huán)境的恢復(fù)；---如何進(jìn)行參數(shù)傳遞；91精選PPT第六節(jié)過(guò)程調(diào)用語(yǔ)句一、過(guò)程調(diào)用91精選PPT第六節(jié)過(guò)程調(diào)用語(yǔ)句二、參數(shù)傳遞1、參數(shù)---實(shí)在參數(shù)---形式參數(shù)2、傳遞方式1)傳地址（callbyreference);把實(shí)在參數(shù)的地址傳遞給相應(yīng)的形式參數(shù)。2)傳值(callbyvalue):把實(shí)在參數(shù)的值計(jì)算出來(lái)傳遞給相應(yīng)的形式參數(shù)。3)傳名（callbyname):ALGOL60所定義的一種特殊的形—實(shí)參結(jié)合方式。92精選PPT第六節(jié)過(guò)程調(diào)用語(yǔ)句二、參數(shù)傳遞92精選PPT第六節(jié)過(guò)程調(diào)用語(yǔ)句二、參數(shù)傳遞3、傳地址1)基本方式A)若實(shí)參是一個(gè)變量（包括下標(biāo)變量），則直接傳遞它的地址；B)若實(shí)參是一個(gè)常數(shù)或其他表達(dá)式，就把值計(jì)算出來(lái)并存放在某臨時(shí)單元，然后傳遞這個(gè)臨時(shí)單元的地址。93精選PPT第六節(jié)過(guò)程調(diào)用語(yǔ)句二、參數(shù)傳遞93精選PPT第六節(jié)過(guò)程調(diào)用語(yǔ)句二、參數(shù)傳遞3、傳地址2)傳址過(guò)程A)當(dāng)程序控制轉(zhuǎn)入被調(diào)用過(guò)程之后，被調(diào)用段首先把實(shí)地址從連接數(shù)據(jù)區(qū)中讀入形參單元中。---注：若已直接傳至形參單元，不做此步。B)在過(guò)程體內(nèi)，對(duì)形參的任何引用或賦值都被看作對(duì)新參單元的間接訪問(wèn)，這間接賦值將直接修改實(shí)參單元的內(nèi)容。94精選PPT第六節(jié)過(guò)程調(diào)用語(yǔ)句二、參數(shù)傳遞94精選PPT第六節(jié)過(guò)程調(diào)用語(yǔ)句二、參數(shù)傳遞4、傳值調(diào)用時(shí)把實(shí)在參數(shù)的值計(jì)算出來(lái)，把值直接傳遞給形式單元中，在過(guò)程體內(nèi)應(yīng)用這些單元不會(huì)修改實(shí)質(zhì)單元的值。5、傳名過(guò)程調(diào)用相當(dāng)于把調(diào)用段的過(guò)程代替調(diào)用語(yǔ)句，并且過(guò)程體內(nèi)形參名皆用相應(yīng)的實(shí)參名代替。95精選PPT第六節(jié)過(guò)程調(diào)用語(yǔ)句二、參數(shù)傳遞95精選PPT第六節(jié)過(guò)程調(diào)用語(yǔ)句三、過(guò)程調(diào)用語(yǔ)句的翻譯（傳址）1、文法---Scalli(Arglist)---ArglistArglist,E---ArglistE2、相關(guān)四元式1)(par,_,_,T)---含義是：將參數(shù)T傳遞到一個(gè)公共的區(qū)域或直接傳遞到過(guò)程的形參單元2)(jsr,_,n,S)---含義是：轉(zhuǎn)移指令，轉(zhuǎn)移到S過(guò)程的四元式入口序號(hào)。96精選PPT第六節(jié)過(guò)程調(diào)用語(yǔ)句三、過(guò)程調(diào)用語(yǔ)句的翻譯（傳址）96精選P第六節(jié)過(guò)程調(diào)用語(yǔ)句三、過(guò)程調(diào)用語(yǔ)句的翻譯（傳址）(1)Scalli(Arglist)----{n=0;----for(隊(duì)列Arglist●QUEUE中的每個(gè)P)----GEN(par,_,_,P);----n=n+1;----GEN(jsr,_,n,ENTRY(i))}(2)ArglistArglist(1)E----{把E●PLACE添加入Arglist(1)●QUEUE末端；----Arglist●QUEUE=Arglist(1)●QUEUE}97精選PPT第六節(jié)過(guò)程調(diào)用語(yǔ)句三、過(guò)程調(diào)用語(yǔ)句的翻譯（傳址）97精選P第六節(jié)過(guò)程調(diào)用語(yǔ)句例如：過(guò)程調(diào)用：CALLS(A+B,Z)譯為：-----K(+,A,B,T)-----K+1(par,_,_,T)-----K+2(par,_,_,Z)-----K+3(jsr,_,2,S)98精選PPT第六節(jié)過(guò)程調(diào)用語(yǔ)句例如：過(guò)程調(diào)用：CALLS(A+B,Z第九節(jié)自上而下分析的制導(dǎo)的翻譯一、自上而下分析的制導(dǎo)的翻譯通過(guò)推導(dǎo)自左而右地產(chǎn)生句子的各終結(jié)符號(hào)，再按產(chǎn)生式推導(dǎo)的過(guò)程添加語(yǔ)義子程序，無(wú)需得到侯選式匹配完后，即不必改寫文法。注：1)在按產(chǎn)生式推導(dǎo)的中間任何一步都可以添加語(yǔ)義子程序，所以不必改寫文法。2)實(shí)際上，程序設(shè)計(jì)語(yǔ)言絕大部分均可使用自上而下分析并生成相應(yīng)中間代碼。二、自上而下分析制導(dǎo)翻譯種類1、遞歸下降分析制導(dǎo)翻譯2、LL(1)分析制導(dǎo)翻譯99精選PPT第九節(jié)自上而下分析的制導(dǎo)的翻譯一、自上而下分析的制導(dǎo)的翻譯第十節(jié)中間代碼的其它形式一、后綴表示法（逆波蘭表示法）1、后綴表示法的文法----<后綴式>::=<標(biāo)識(shí)符>|<后綴式><單目算符>|<后綴式><后綴式><雙目算符>----<單目算符>::=@----<雙目算符>::=+|-|*|/----注：這種表示法不帶括號(hào)，根據(jù)運(yùn)算量和運(yùn)算符出現(xiàn)的先后位置，以及每個(gè)運(yùn)算符的目數(shù)，就完全決定了一個(gè)表達(dá)式的計(jì)算程序。100精選PPT第十節(jié)中間代碼的其它形式一、后綴表示法（逆波蘭表示法）10第十節(jié)中間代碼的其它形式后綴表示法的特點(diǎn)：---(1)運(yùn)算量的排列順序與中綴表示法相同；---(2)遠(yuǎn)算量是按運(yùn)算的順序排列的；---(3)運(yùn)算符緊跟在被云酸的對(duì)象之后出現(xiàn)。---注：它顯然不符合人的習(xí)灌，但隊(duì)計(jì)算機(jī)來(lái)說(shuō)，很容易使用一個(gè)棧來(lái)計(jì)算它的值，或轉(zhuǎn)換成另一種代碼。101精選PPT第十節(jié)中間代碼的其它形式后綴表示法的特點(diǎn)：101精選PPT第十節(jié)中間代碼的其它形式二、語(yǔ)法制導(dǎo)產(chǎn)生后綴式首先，除了堆棧外，為分析過(guò)程設(shè)置一個(gè)一維數(shù)組POST來(lái)存放后綴式；初始時(shí)，其下標(biāo)K為1。然后，利用算符優(yōu)先分析法102精選PPT第十節(jié)中間代碼的其它形式二、語(yǔ)法制導(dǎo)產(chǎn)生后綴式102精選P第十節(jié)中間代碼的其它形式二、語(yǔ)法制導(dǎo)產(chǎn)生后綴式1、利用算符優(yōu)先分析法進(jìn)行語(yǔ)法分析語(yǔ)義子程序產(chǎn)生式語(yǔ)義子程序(1)EE(1)opE(2){POST[K]=op;k=k+1;}(2)E(E(1)){}(3)Ei{POST[K]=ENTRY(i);k=k+1;}例如：假定算符優(yōu)先分析表已選好，對(duì)表達(dá)式A*(B+C)#翻譯成后綴式103精選PPT第十節(jié)中間代碼的其它形式二、語(yǔ)法制導(dǎo)產(chǎn)生后綴式103精選P步驟下推棧輸入串后綴式0#A*(B+C)#1#E*(B+C)#A2#E*(B+C)#A3#E*(B+C)#A4#E*(E+C)#AB5#E*(E+C)#AB6#E*(E+E)#ABC+7#E*(E)#ABC+8#E*(E)#ABC+9#E*E#ABC+10#E#ABC+*104精選PPT步驟下推棧輸入串后綴式0#A*(B+C)#1#E*(B+C)第十節(jié)中間代碼的其它形式二、語(yǔ)法制導(dǎo)產(chǎn)生后綴式2、后綴表示法的計(jì)值和產(chǎn)生中間代碼1)計(jì)值過(guò)程：至左至右掃描后綴式，沒(méi)碰到運(yùn)算量就將其入棧，每遇到K目運(yùn)算符就將它作用于棧頂?shù)膋項(xiàng)，并將運(yùn)算結(jié)果來(lái)代替這k項(xiàng)。--例如：ab+c*2)產(chǎn)生四元式過(guò)程：自左至右掃描后綴式，每碰到運(yùn)算量就將其入棧，每遇到k目運(yùn)算符就將它作用于棧頂?shù)腒項(xiàng)，并生成相應(yīng)的中間代碼，以結(jié)果的臨時(shí)變量序號(hào)代替該棧頂?shù)膋項(xiàng)。105精選PPT第十節(jié)中間代碼的其它形式二、語(yǔ)法制導(dǎo)產(chǎn)生后綴式105精選P第十節(jié)中間代碼的其它形式二、語(yǔ)法制導(dǎo)產(chǎn)生后綴式3、后綴式的推廣方法：遵守運(yùn)算符緊跟在被作用的運(yùn)算量之后。例如:(1)賦值語(yǔ)句A:=E,后綴式為：AE:=(2)轉(zhuǎn)向語(yǔ)句GOTOL,后綴式為：L’jmp---其中L’是指示器，用POST中的下標(biāo)值表示。(3)條件語(yǔ)句ifx>ythenm:=xelsem:=y;其后綴值為：1234567891011121314xy>11jezmx:=14jmy:=….106精選PPT第十節(jié)中間代碼的其它形式二、語(yǔ)法制導(dǎo)產(chǎn)生后綴式123456Begink:=100;L:ifk>i+j;gotoLendelsek:=i∧2-j∧2i:=0;End.1234567891011121314151617k100:=kij+>20jezkkl-:=4j18192021222324252627282930313229jki2∧j2∧-:=i0:=…注：翻譯成后綴式時(shí)也存在拉鏈回填的問(wèn)題107精選PPTBegin1234567891011121314151617小結(jié)1、算術(shù)表達(dá)式及賦值語(yǔ)句翻譯2、控制語(yǔ)句中布爾表達(dá)式翻譯---留有真、假出口---回填過(guò)程與并鏈函數(shù)3、標(biāo)號(hào)和轉(zhuǎn)移語(yǔ)句翻譯4、IF語(yǔ)句的翻譯5、WHILE語(yǔ)句的翻譯6、語(yǔ)法制導(dǎo)生成后綴式（逆波蘭表達(dá)式）108精選PPT小結(jié)1、算術(shù)表達(dá)式及賦值語(yǔ)句翻譯108精選PPT此課件下載可自行編輯修改，供參考！感謝您的支持，我們努力做得更好！此課件下載可自行編輯修改，供參考！第七章語(yǔ)法制導(dǎo)翻譯和中間代碼生成110精選PPT第七章語(yǔ)法制導(dǎo)翻譯和中間代碼生成1精選PPT第一節(jié)概述語(yǔ)法分析之后，編譯的任務(wù)是由已識(shí)別為正確的源程序生成一組規(guī)格一致，便于計(jì)算機(jī)加工的指令形式。一、中間代碼生成方法語(yǔ)法制導(dǎo)翻譯，屬性文法制導(dǎo)翻譯二、中間代碼●中間代碼：不是機(jī)器語(yǔ)言，便于生成機(jī)器語(yǔ)言，便于代碼優(yōu)化。●中間代碼的形式：-------逆波蘭式-------樹(shù)形表示法-------三元式-------四元式：最常用的形式第七章中間代碼的生成1111精選PPT第一節(jié)概述語(yǔ)法分析之后，編譯的任務(wù)是由已識(shí)別為正確的源程第一節(jié)概述二、翻譯方法1、語(yǔ)法制導(dǎo)翻譯----在語(yǔ)法分析的基礎(chǔ)上進(jìn)行邊分析邊翻譯?！褡ⅲ?）語(yǔ)法制導(dǎo)翻譯時(shí)會(huì)根據(jù)文法產(chǎn)生式右部符號(hào)串的含義進(jìn)行翻譯，翻譯的結(jié)果是生成相應(yīng)中間代碼?！?）語(yǔ)法制導(dǎo)翻譯的依據(jù)是語(yǔ)義子程序?！?）具體做法：為每個(gè)產(chǎn)生式配置一個(gè)語(yǔ)義子程序，當(dāng)語(yǔ)法分析進(jìn)行歸約或推導(dǎo)時(shí)，調(diào)用語(yǔ)義子程序，完成一部分翻譯任務(wù)?！?）語(yǔ)法分析完成，翻譯工作也告結(jié)束。第七章中間代碼的生成2112精選PPT第一節(jié)概述二、翻譯方法第七章中間代碼的生成23精選PPT第一節(jié)概述二、翻譯方法●1、語(yǔ)法制導(dǎo)翻譯---語(yǔ)法制導(dǎo)翻譯適用于多種語(yǔ)法分析---語(yǔ)法制導(dǎo)翻譯種類●1、自上而下語(yǔ)法制導(dǎo)翻譯：對(duì)每個(gè)文法符號(hào)配以語(yǔ)義動(dòng)作?！?、自下而上語(yǔ)法制導(dǎo)翻譯：我們主要討論LR語(yǔ)法制導(dǎo)翻譯第七章中間代碼的生成3113精選PPT第一節(jié)概述二、翻譯方法第七章中間代碼的生成34精選PPT第一節(jié)概述三、語(yǔ)義子程序1、作用●用來(lái)描述一個(gè)產(chǎn)生式所對(duì)應(yīng)的翻譯工作。---如：改進(jìn)某些變量的值；查填各種符號(hào)表；發(fā)現(xiàn)并報(bào)告源程序錯(cuò)誤；產(chǎn)生中間代碼等?！褡ⅲ贿@些翻譯工作很大程度上決定了要產(chǎn)生什么形式的中間代碼114精選PPT第一節(jié)概述三、語(yǔ)義子程序5精選PPT三、語(yǔ)義子程序2、寫法●語(yǔ)義子程序?qū)懺谠摦a(chǎn)生式后面的花括號(hào)內(nèi)。Xa{語(yǔ)義子程序}●注：在一個(gè)產(chǎn)生式中同一個(gè)文法符號(hào)可能出