編譯原理分知識(shí)點(diǎn)習(xí)題-語(yǔ)法制導(dǎo)和翻譯

1、精選優(yōu)質(zhì)文檔-傾情為你奉上1. 一般情況下，為什么語(yǔ)義分析部分僅產(chǎn)生中間代碼？解答：一般情況下，語(yǔ)義分析部分僅產(chǎn)生中間代碼，其原因是：可使難點(diǎn)分解，分別解決?？蓪?duì)語(yǔ)義分析產(chǎn)生的中間代碼進(jìn)行優(yōu)化，以產(chǎn)生高效率的目標(biāo)代碼。語(yǔ)義分析通常與機(jī)器無(wú)關(guān)，目標(biāo)代碼往往與機(jī)器有關(guān)。把語(yǔ)義分析與目標(biāo)代碼生成分開(kāi)，可讓一個(gè)語(yǔ)義分析程序適用于多個(gè)目標(biāo)代碼生成程序。2.（湖北省高等教育自學(xué)考試）什么是語(yǔ)法制導(dǎo)翻譯？為什么把這種方法叫語(yǔ)法制導(dǎo)翻譯？解答：所謂語(yǔ)法制導(dǎo)翻譯，是指在語(yǔ)法規(guī)則的制導(dǎo)下，通過(guò)計(jì)算語(yǔ)義規(guī)則，完成對(duì)輸入符號(hào)串的翻譯。由于使用屬性文法時(shí)把語(yǔ)法規(guī)則和語(yǔ)義規(guī)則分開(kāi)，但在使用語(yǔ)法規(guī)則進(jìn)行推導(dǎo)或規(guī)約的同時(shí)又使

2、用這些語(yǔ)義規(guī)則來(lái)知道翻譯與最終產(chǎn)生目標(biāo)代碼，所以稱為語(yǔ)法制導(dǎo)翻譯。3. 給出將附值語(yǔ)句翻譯成四元式的語(yǔ)法制導(dǎo)定義，允許右部表達(dá)式含有加法、乘法、取負(fù)、括號(hào)運(yùn)算。生成賦值語(yǔ)句X:=B*(C+D)+A的四元式。解答：賦值語(yǔ)句的自下而上的語(yǔ)法制導(dǎo)翻譯過(guò)程描述為：規(guī)則 語(yǔ)義動(dòng)作（1）A:=i:=E GEN (:=,E.PLACE,ENTRY(i) ) （2）E:=E1+E2 E.PLACE:=NEWTEMP; GEN(+,E1.PLACE, E2.PLACE,E.PLACE)（3）E:= E1*E2 E.PLACE:=NEWTEMP; GEN(*,E1.PLACE, E2.PLACE,E.PLACE)

3、（4）E:=-E1 E.PLACE:=NEWTEMP; GEN(,E1.PLACE,E.PLACE)(5)E:=(E1) E.PLACE:= E1.PLACE (6)E:=i E.PLACE:= ENTRY(i) 生成的賦值語(yǔ)句X:=B*(C+D)+A的四元式為：(+，C,D,T1)(*,B,T1,T2)(+,T2,A,T3)(:=,T3,X)4. 給出將布爾表達(dá)式翻譯成四元式的語(yǔ)法制導(dǎo)定義。解答：布爾表達(dá)式的語(yǔ)義子程序?yàn)椋阂?guī)則 語(yǔ)義動(dòng)作(1) E:=I E.TC:=null;E.FC:=NXQ; GEN (Jez , ENTRY(i), ,0) (2) E:= i1 rop i2 E.TC:

4、=null;E.FC:=NXQ; GEN (Jnrop,ENTRY(i1), ENTRY(i2),0)(3) E:= (E1) E.TC:=E1.TC, E.TC:=E1.TC; (4) E:= ¬ E1 E.TC:=NXQ; GEN ( J, , , 0); BP (E1.FC, NXQ);(5) EA:=E1 if E1.FC=nullthen begin E1.TC:=NXQ; GEN ( J, , , 0) End;BP ( E1.TC , NXQ );EA.TC:=null; EA.FC:=E1.FC (6) E := EAE2 if E2.FCnullthen begin

5、 BP (EA.FC, NXQ); E.FC:=nullEndE.TC:=E2.TC; (7) E0:=E1 if E1.TC:=nullthen begin E1.TC:=NXQ; GEN ( J, , , 0)End;E0.TC:=E1.TC;BP (E1.TC,NXG);(8) E:=E0E2 if E2.TCnullthen E.TC:=MERG(E0.TC,E2.TC)Else begin BP (E0.TC ,NXQ); E.FC:=E2.FCEnd;E.FC:=E2.FC其中：l NXQ指示器指向下一個(gè)將要形成但尚未形成的四元式的地址（編號(hào)），初值為1，每當(dāng)執(zhí)行GEN一次，NXQ

6、自動(dòng)加1。l GEN是一個(gè)語(yǔ)義過(guò)程，該過(guò)程把四元式加入四元式表區(qū)中。l E.TC和E.FC分別表示E所對(duì)應(yīng)的四元式需回填“真”、“假”出口的四元式地址所構(gòu)成的鏈。l MERG（P1,P2）為一函數(shù)，把以P1和P2為鏈?zhǔn)椎膬蓚€(gè)鏈合二為一作為函數(shù)值，回送合并后的鏈?zhǔn)住 BP（P，t）為一語(yǔ)義過(guò)程，BP是BACKPATCH的縮寫(xiě)。這是一“回填”過(guò)程，它把以P為鏈?zhǔn)姿溄拥拿總€(gè)四元式的第四區(qū)段都填為t。l Jrop是根據(jù)關(guān)系運(yùn)算符rop定義的條件轉(zhuǎn)移。5. 試寫(xiě)出PASCAL循環(huán)語(yǔ)句for I:=1 to N do S 的語(yǔ)義程序，假定該語(yǔ)句的文法為F1:= for i:= 1 to NS:= F1

7、 do S1解答：根據(jù)題設(shè)文法，for語(yǔ)句的語(yǔ)義子程序?yàn)椋篎1:= for i:= 1 to N F1.place:=entry (i); GEN(:=, 1 , ,F1.place); Final:=newtemp; GEN( :=,N.place, ,final); F1.chain:=NXQ; F1.quad:=NXQ ;GEN( J>,F1.place ,final,0)S:= F1 do S1 BACKPATCH (S1.chain,NXQ); GEN (+,F1.place, 1,F1.place); GEN (J, , ,F1.quad); BACKPATCH (S.cha

8、in,NXQ)6. 寫(xiě)出條件賦值語(yǔ)句i :=if B then E1 else E2的語(yǔ)義子程序。其中B是布爾表達(dá)式，E1和E2是算術(shù)表達(dá)式，i代表與E1、E2類(lèi)型相同的左部變量。按寫(xiě)出的語(yǔ)義子程序生成條件賦值語(yǔ)句Z:=if A>C then x+y else x-y+0.5的四元式序列。解答：按條件賦值語(yǔ)句的語(yǔ)義給出該語(yǔ)句的文法如下：A1:=i:=A2:=A1 if B then A3:=A2 E1 elseS:=A3 E2相應(yīng)的語(yǔ)義子程序?yàn)?(1) A1:=i:= A1.place:=entry (i) (2) A2:=A1 if B then BP (B.TC, NXQ); A2.

9、chain:=B.FC; A2.place:=A1.place(3) A3:=A2 E1 else GEN (:=,E1.place, ,A2.place); A3.chain:=NXQ; GEN ( J, , ,0 );BP(A2.chain,NXQ);A3.place:=A2.place(4) S:=A3E2 GEN (:=,E2.place, ,A3.place);BP(A3.chain,NXQ) 按上述語(yǔ)義子程序,條件賦值語(yǔ)句Z:=if A>C then x+y else x-y+0.5的四元式序列為:(1) ( J>,A,C, (3)(2) ( J , , ,(6)(3)

10、 (+,X,Y,T1)(4) (:=,T1, ,Z)(5) ( J, , ,(9)(6) (-,X,Y,T2)(7) (+,T2,0.5,T3)(8) (:=,T3, ,Z)(9)7. 寫(xiě)出編譯PASCAL語(yǔ)言repeat語(yǔ)句 repeat S1; S2; ; Sn until E;的語(yǔ)義子程序.其中E是條件表達(dá)式.解答:PASCAL的repeat語(yǔ)句的文法為:R1repeatLS|LsSLsL;R2R1L untilSR2E于是repeat語(yǔ)句各產(chǎn)生式的語(yǔ)義子程序?yàn)?R1repeat R1.QUAD:=NXQLS L.CHAIN:=S.CHAINLsL; BACKPATCH (L.CHAIN

11、,NXQ)LLsS1 L.CHAIN:=S1.CHAINR2R1L until R2.QUAD:=R1.QUAD; BACKPATCH (L.CHAIN,NXQ) SR2E BACKPATCH (E.FC, R2.QUAD); S.CHAIN:=E.TC8. 為便于填寫(xiě)被說(shuō)明的名字的性質(zhì),試修改下面關(guān)于變量類(lèi)型說(shuō)明的文法,并給出相應(yīng)的語(yǔ)義動(dòng)作。待修改的類(lèi)型說(shuō)明文法為：Dnamelist integer|namelistnamelisti,namelist|i解答：(1) 為便于填寫(xiě)名字的屬性，將上述文法修改為：Dnamelist，D1Di integerDi realnamelistnamel

12、ist1,inamelisti于是，相應(yīng)的語(yǔ)義動(dòng)作為：Di integer FILL (ENTRY (i) , int ); D.ATT:=int Di real FILL (ENTRY (i) ,real ); D.ATT:=real Dnamelist，D1 for 隊(duì)列 namelist.QUEUE 的每一項(xiàng) P do FILL (P,D1.ATT);D.ATT:=D1.ATT namelisti 建立一個(gè)隊(duì)列namelist.QUEUE, 它只包含一項(xiàng)ENTRY（i） namelistnamelist1,i 把ENTRY(i)排在namelist1.QUEUE的末端； namelist

13、.QUEUE:=namelist1.QUEUE 注意：其中FILL（P，A）是一語(yǔ)義過(guò)程，其功能是把屬性A添進(jìn)P所指向的符號(hào)表入口的有關(guān)區(qū)段。語(yǔ)義變量D.ATT用以記錄說(shuō)明語(yǔ)句所規(guī)定的屬性。（2）若類(lèi)型說(shuō)明的文法為：Dnamelist integerDnamelist realnamelistnamelist1,inamelisti相應(yīng)的語(yǔ)義動(dòng)作為：Dnamelist integer for 隊(duì)列 namelist.QUEUE的每一項(xiàng)P do FILL (P,int);Dnamelist real for 隊(duì)列 namelist.QUEUE的每一項(xiàng)P do FILL (P,real);name

14、listi 建立一個(gè)隊(duì)列namelist.QUEUE它只包含一項(xiàng)ENTRY(i) namelistnamelist1,i 把ENTRY(i)排在namelist.QUEUE的末端；namelist.QUEUE:=namelist1.QUEUE 9. (中國(guó)科學(xué)院計(jì)算所1996年)某些語(yǔ)言允許給出名字表的一個(gè)屬性表，也允許聲明嵌在另一個(gè)聲明里面，下面文法抽象這個(gè)問(wèn)題：D attrlist namelist|attrlist(D) Namelistid,namelist|id AttrlistA attrlist|AA decimal|fixed|float|realD attrlist (D)

15、的含義是：在括號(hào)中的聲明提到的所有名字有attrlist中給出的屬性，而不管聲明嵌套多少層。寫(xiě)一個(gè)翻譯方案，它將每個(gè)名字的屬性添入符號(hào)表。解答：相應(yīng)的翻譯方案為：D D.num=0; DD attrlistnamelist.num=D.num+attrlist.num; namelistD attrlistD1.num=D.num+attrlist.num; (D1)Namelist idaddattr(id.entry ,namelist.num); Namelist id,namelist1.num=namelist.num; namelist1addattr (id.entry,name

16、list.num); attrlist A attrlist1 attrlist.num=attrlist1.num +1; attrlist A attrlist.num=1; 10. 寫(xiě)出翻譯過(guò)程調(diào)用語(yǔ)句的語(yǔ)義子程序。要求生成的四元式序列在轉(zhuǎn)子指令之前的參數(shù)四元式par按反序出現(xiàn)（即和實(shí)在參數(shù)的順序相反），在此情況下翻譯過(guò)程調(diào)用語(yǔ)句時(shí)是否需要語(yǔ)義變量（隊(duì)列）QUEUE呢？解答：為使過(guò)程調(diào)用語(yǔ)句的語(yǔ)義子程序產(chǎn)生的參數(shù)四元式par按反序出現(xiàn)，過(guò)程調(diào)用語(yǔ)句的文法為：S call i (arglist)Arglist EArglist arglist1,E按照該文法，語(yǔ)法制導(dǎo)翻譯程序?qū)⒉恍枰Z(yǔ)義變

17、量隊(duì)列QUEUE，但需要一個(gè)語(yǔ)義變量棧STACK，用以實(shí)現(xiàn)按反序記錄每個(gè)實(shí)在參數(shù)的地址。翻譯過(guò)程調(diào)用語(yǔ)句的語(yǔ)義子程序?yàn)椋篴rglist E 建立一個(gè)arglist.STACK棧，它只包含一個(gè)項(xiàng)E.PLACE arglist arglist1,E 把E.PLACE壓入棧arglist1.STACK; arglist.STACK:=arglist1.STACK S call i (arglist) WHILE arglist.STACKnull doBegin 把a(bǔ)rglist.STACK棧頂上托出去，并放入P元中；GEN（par, , ,P）End;GEN(call, , ,ENTRY(i) 1

18、1. (中國(guó)科學(xué)院計(jì)算所1994)設(shè)有文法GS：S:=(L)|aL:=L,S|S給此文法配上語(yǔ)義動(dòng)作子程序（或者說(shuō)為此文法寫(xiě)一個(gè)語(yǔ)法制導(dǎo)定義），它輸出配對(duì)括號(hào)的個(gè)數(shù)，如對(duì)于句子（a,(a,)）,輸出是2。解答：加入新的開(kāi)始符號(hào)S和規(guī)則S:=S,得到增廣文法。語(yǔ)法制導(dǎo)定義如下：S:=S print (S.num); S:=(L) S.num:=L.num+1; S:=a S.num:=0; L:=L1,S L.num:=L1.num+S.num; L:=S L.num:=S.num; 12. (中國(guó)科學(xué)院軟件所1999)文法GS的產(chǎn)生式如下：S:= (L)|aL:= L,S|S試寫(xiě)出一個(gè)語(yǔ)法制導(dǎo)

19、定義，它輸出配對(duì)括號(hào)個(gè)數(shù)。寫(xiě)出一個(gè)翻譯方案，打印每個(gè)a的嵌套深度。如（a,a）,a）,打印2，1。解答：加入新的開(kāi)始符號(hào)S和規(guī)則S :=S,得到增廣文法：S :=SS:= (L)S:= AL:=L1,SL:=S1 為S，L引入屬性h，語(yǔ)法制導(dǎo)定義為： S :=S print (S.h) S:= (L) S.h:=L.h+1 S:= a S.h:=0 L：=L1，S L.h:=L1.h+S.h L：=S L.h:=S.h2 引入屬性d，翻譯方案定義為： S :=S.d:=0; S S := ( L.d:=S.d +1; L1 , S.d:=L.d; SL:=S.d=L.d; S13. (中國(guó)科學(xué)

20、院軟件所2000年)程序的文法如下：PDDD; D|id ; T|proc id ; D ; S(1) 寫(xiě)一個(gè)語(yǔ)法制訂定義，打印該程序一共聲明了多少個(gè)id.(2) 寫(xiě)一個(gè)翻譯方案，打印該程序每個(gè)變量id的嵌套深度。解答：（1） 引進(jìn)屬性i,得到語(yǔ)法制導(dǎo)定義如下：PD print (D,i); DD1;D2 D.i:=D1.i+D2.i;Did : T D.i:=1; Dproc id ;D1 ; S D.i:=D1.i+1; (3) 引進(jìn)屬性l和name,得到翻譯方案如下：PD.l:=1; DDD1.l:=D.l; D1 ; D2.l:=D.l; D2Did : T print (id.nam

21、e ,D.l); Dproc Id : D1.l:=D.l+1; D1 : S14. (中國(guó)科學(xué)院計(jì)算所1995年) 設(shè)有文法GS：S;:=L.L|LL:=LB|BB:=0|1給此文法配上語(yǔ)義動(dòng)作子程序（或者說(shuō)為此文法寫(xiě)一個(gè)語(yǔ)法制導(dǎo)定義），它輸出S產(chǎn)生的二進(jìn)制數(shù)的值，例如101.101時(shí)，輸出5.625。解答： 加入新的開(kāi)始符號(hào)S和規(guī)則S ：=S，得到增廣文法。語(yǔ)法制導(dǎo)定義如下：S :=S print (S.val); S:=L1.L2 S.val:=L1.val+L2.val/2L2.length; S:=L S.val:=L.val; L:=L1B L.val:=L1.val*2+B.va

22、l; L.length:=L1.length+1; L:=B L.val:=B.val; L.length:=1; B:=0 B.val:=0; B:=1 B.val:=1; 15. (中國(guó)科學(xué)院計(jì)算所1993年) 請(qǐng)按語(yǔ)法制導(dǎo)的定義將后綴表達(dá)式翻譯成中綴表達(dá)式。注意：不允許出現(xiàn)冗余括號(hào)，后綴表達(dá)式的文法如下： E:=E1E2+ E:=E1E2* E:=id解答：加入新的餓開(kāi)始符號(hào)S和規(guī)則S:=E, 得到增廣文法。語(yǔ)法制導(dǎo)定義如下：S:=E print (E.code) E:=E1E2+ E.code:=E1.code| + |E2.code; E.op=+ ; E:=E1E2* if E1.

23、op= + and E2.op= + Then E1.code:= ( |E1.code| ) * | ( | E1.code| ) ; Else If E1.op=+ Then E.code:= ( | E1.code| ) | * |E2.code; Else If E2.op=+ Then E.code:=E1.code| * | ( |E2.code| ); Else E.code:=E1.code| * |E2.code; E.op:= * ; E:=id E.code:=id.lexval; E.op:=$ ; 16. 某程序設(shè)計(jì)語(yǔ)言說(shuō)明部分的語(yǔ)法制導(dǎo)定義如下所示：D:=TLT:=

24、intT:=realL:=L1,idL:=id給出其語(yǔ)法制導(dǎo)定義及自底向上分析的翻譯方案，并比較兩者的不同。解答： 語(yǔ)法制導(dǎo)定義為： D:=TL L.in:=T.typeT:=int T.type:=integerT:=real T.type:=realL:=L1,id L.in:=L.in addtype (id.entry,L.in) L:=id addtype (id.entry, L.in ) 自底向上分析的翻譯方案為：D:=T L.in:=T.typeLT:=int T.type:=integerT:=real T.type:=realL:= L.in:=L.inL1,id addt

25、ype (id.entry, L.in ) L:=id addtype (id.entry, L.in ) 從上述定義可見(jiàn)，兩者的區(qū)別僅在于翻譯方案中，把語(yǔ)義操作插入在規(guī)則右部的任意位置。17. 給出PASCAL語(yǔ)言常量定義的翻譯方案。解答： PASCAL語(yǔ)言常量定義的翻譯方案為： CONSTDP:=CONST CDT CDT:=CDT: CD CD:=id=num num.ord:=lookCT (num.lexval); id.ord:=num.ord; id.type:=integer ; id.kind:=CONSTANT; add (id.entry, id.kind,id.type,id.ord) CD:=id=id1 id.kind:=CONSTANT; id.type:=id1.typel id.ord:=id1.ord; add (id.entry ,id,kind,id.type,id,ord) 函數(shù)lookCT（c）將在常量表中查找常量c。若查不到，則把該常量值錄入常量表。不論查到與否，最終將回送常量c之值在常量表中的序號(hào)。CONSTANT是表示標(biāo)識(shí)符種類(lèi)為常量的一個(gè)枚舉值。過(guò)程add是對(duì)過(guò)程addtype的擴(kuò)充，它把種類(lèi)、類(lèi)型與序號(hào)三者填入符號(hào)表相應(yīng)條目中。18. 將 PASCAL語(yǔ)言的餓變量說(shuō)明簡(jiǎn)化為：變量說(shuō)