編譯原理分知識點習(xí)題語法制導(dǎo)和翻譯

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

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

3、EPLACE:=NEWTEMP;GEN(E】PLACE.EPLACE)(5)E:=(艮)E.PLACE:= EMPLACE(6)E 二=1E.PLACE:= ENTRY(i) 生成的賦值語句X:=B*(C+D)+A的四元式為:什，CQJ4)(*BT1,T2)(+.T2.AJ3)(:=T3,_,X)4. 給出將布爾表達(dá)式翻譯成四元式的語法制導(dǎo)定義。 解答：布爾表達(dá)式的語義子程序為：規(guī)則(1)E:=I語義動作E.TC:=null;E.FC:=NXQ;GEN (Jez , ENTRY(i)，.0) (2) E:= i1 rop i2 E.TC:=null;E.FC:=NXQ;GEN (JmopJEN

4、TRYg), ENTRY(F) E：=Q)(4)E:=-E1ETC=EiTC,ETC=ELTC; E.TC:=NXQ;GEN (J.0): BP (ELFU NXQ);(5) EA:=E!A if EFCnullthen beginE1.TC:=NXQ;GEN (J.,0)End;BPtETCNXQ );EA.TC:=null; EdFC嚴(yán)E】FC (6) E := EAE2if E2.FCiiull then beginBP (EA.FC, NXQ); E.FC:=nuUEndE.TC:=E2.TC; (7) EO:=EXV if E】TC=iiullthen begm E】TC:=NXQ;

5、GEN (I 0)End;EO.TCWTC;BP (E】TC,NXG);(8)E:=E°E2 if E2.TCxnullthenE.TC:=MERG(E°.TC.E2.TC)Else beginBP (EMC ,NXQ);E.FC:=E2.FCEnd;E.FC:=E2.FC其中： NXQ指示器指向下一個將要形成但尚未形成的四元式的地址(編號)，初值為1,每當(dāng) 執(zhí)行GEN次，NXQ自動加U GEN是一個語義過程，該過程把四元式加入四元式表區(qū)中。 E.TC和E.FC分別表示E所對應(yīng)的四元式需回填“真”、“假”出I的四元式地址所構(gòu) 成的鏈。 MERG (P1,P2)為一函數(shù)，把以

6、P1和P2為鏈?zhǔn)椎膬蓚€鏈合二為一作為函數(shù)值，回送 合并后的鏈?zhǔn)住?BP (P, t)為一語義過程，EP是BACKPATCH的縮寫。這是一 “回填”過程，它把以 P為鏈?zhǔn)姿溄拥拿總€四元式的第四區(qū)段都填為to Jrop是根據(jù)關(guān)系運算符rop定義的條件轉(zhuǎn)移。5. 試寫出PASCAL循環(huán)語句foi 1=1 to Ndo S的語義程序，假定該語句的文法為 Ff：= for i:= 1 toNS:= Fi doS1解答：根據(jù)題設(shè)文法，f&語句的語義子程序為：Fi：:= for i:= 1 toNFi.place:=entry (1); GEN(:=, T,Fi.place);Fmal:=nele

7、mp; GEN( :=.N.place,filial);Fi.chain:=NXQ; Fi.quad:=NXQ ;GEN(place .finaLO)S:=Fi doS1BACKPATCH (Scham.NXQ); GEN j+R place, 4Fi.place); GEN (J,_，巧.quad); BACKPATCH (S.chaukNXQ)6.寫出條件賦值語句i :=if B then Ei elseE：的語義子程序。其中E是布爾表達(dá)式，E】和氏是算術(shù)表達(dá)式，1代表與E】、氏類型相同的 左部變量。按寫出的語義子程序生成條件賦值語句Z:=if A>C then x+v else x

8、v+05的四元式序列。解答：按條件賦值語句的語義給出該語句的文法如F:Ai：:=i:=A2:=Ai if B thenA3：:=Az Ei elseS:=A$ Er相應(yīng)的語義子程序為：(1) A】二=1】=Al.place:=entiy (i) (2) A2：:=Ai if B then(3) A3：:=A： Ei elseBP (E.TC, NXQ); A2.chaiii:=B.FC; A：.place :=Ai .place GEN (:=,Ei.place, _ ,A：.place); A3.cham:=NXQ;GEN ( J, _、_,0 );BP(A2.chaiii,NXQ);A3.

9、place:=A2.place(4) S:=A3E2GEN (:= Ez.place, ,A3.place);BP(A3.chain.NXQ) 按上述語義子程序,條件賦值語句Z:=if A>C thenx+y else x-y+0.5的四元式序列為:JZ JZ JZ JZ JZ JZ JZ JZ JZ 123456789 ( /(X /lx /(X /(X /(V z(x /(J>,AG )(J , 一 一(6) (+：XTi) v c=g 一z)(人 _，_，(刃) CXXTJ (+,T2,O.5J3) (：=, 一Z)7.寫出編譯PASCAL語言repeat語句repeatSi

10、； S2；Sn until E;的語義子程序其中E是條件表達(dá)式.解答:PASCAL的“peat語句的文法為:Ri- repeatL->S|LsSlT；R：f R1L untilS-R：E于是repeat語句各產(chǎn)生式的語義子程序為:Ri- repeat L SLT;L->LsSlR：-*R1L untilRi.QUAD:=NXQL.CHAIN:=S.CHAINBACKPATCH (L.CHAIN.NXQ)L.CHAIN:=Si.CHAINR2.QUAD-R1.QUAD; BACKPATCH (L.CHAIN,NXQ) Sf R：EBACKPATCH (E.FC, Rz.QUAD);

11、S.CHAIN:=E.TC8為便于填寫被說明的名字的性質(zhì)，試修改下面關(guān)于變量類型說明的文法，并給出相應(yīng)的語義動作。待修改的類型說明文法為：D-namelist integEt namelistnamelist-* i, name 1 i st i解答：(1為便于填寫名字的屬性，將上述文法修改為:Dfnamelist, DIDf i integerD i realnamelist-* name 1 i s 11, i namelist- i于是，相應(yīng)的語義動作為: Df i integerD i realDfnamelist, DInamelist-* inamelist-* name list

12、1, iFILL (ENTRY (1)，mt); D.ATT:=int FILL (ENTRY (i) ,real )； D.ATT:=realfor 隊列 namelist.QUEUE 的每一項 P do FILL (RD】.ATT); DArr=D】ATT 建立一個隊列namelist.QUEUE.它只包含一項ENTRY (i) 把 ENTRY(i)排在 nainelistQUEUE 的末端； namelist.QUEUE: lamelist1 .QUEUE 注意：其中FILL (P, A)是一語義過程，其功能是把屬性A添進(jìn)P所指向的符號表入I I的 有關(guān)區(qū)段。語義變量D.ATT用以記錄說

13、明語句所規(guī)定的屬性。(2)若類型說明的文法為：D-namelis t int egerD-namelis t real namelist-* name list1, inamelisti相應(yīng)的語義動作為：Df namelis t integerfor 隊列 namelist.QUEUE 的每一項 P do FILL (Emt);Df namelis t realfor 隊列 namelist.QUEUE 的每一項 P do FILL (Pjeal);namelisti建立一個隊列namelist.QUEUE它只包 含一項 ENTRY(i) namelist- name list1, i把 EN

14、TRY(i)排在 namelist.QUEUE 的末端；nainelist.QUEUEnainelist1 .QUEUE 9.(中國科學(xué)院計算所1996年)某些語言允許給出名字表的一個屬性表，也允許聲明嵌在另 一個聲明里面，下面文法抽彖這個問題：D>attrlistnamelist|attilist(D)Name list>id,namelist id Attrlist>A attrlist|AA>decinial|fixed|float|realD - attrlist (D)的含義是：在括號中的聲明提到的所有名字有attrlist中給出的屬 性，而不管聲明嵌套多少層

15、。寫一個翻譯方案，它將每個名字的屬性添入符號表。解答：相應(yīng)的翻譯方案為：DJ ->D.num=O; DD attrlistnamelist.num=D.num+attilist.num; namelistD attrlist D).num=D .niun-rattrlist.num; (D JNamelist -ldfaddattrd.entiy aiamelist.num); Namelist -ldnamelisti.nunnamelist.num; namelistiaddatti (list.num); attrlist A attrlisti attr

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

17、反序記錄每個實在參數(shù)的地址。翻譯過程調(diào)用語句的語義子程序為：aiglist Eaiglist aiglist1、E建立一個arglist.STACK棧，它只包含一個項E.PLACE 把 E.PLACE 壓入棧 arglistSTACK;aiglist. STACK:=arghst1. STACK S call i (aiglist)WHILE aighst.STACKnull doBegin把arglist.STACK棧頂上托出去，并放入P元中；GEN (par,一P)End;GEN(call, 一 一ENTRY(i) 11. 仲國科學(xué)院計算所1994)設(shè)有文法GS：S 二=(L)|aL:=L

18、.S|S給此文法配上語義動作子程序(或者說為此文法寫一個語法制導(dǎo)定義)，它輸出配對拾 號的個數(shù),如對于句子(a,(a,)，輸出是2。解答：加入新的開始符號S和規(guī)則S*S,得到增廣文法。語法制導(dǎo)定義如下：print (S.num);S.num:=L.num+l;S.num:=O; L.num:=L i .num+S.num; L.num:=S.num; st=sS 二=(L)S:=aL:=LbSL:=S12. (中國科學(xué)院軟件所1999)文法GS的產(chǎn)生式如2S 二=(L)|aL:= L、S|S 試寫出一個語法制導(dǎo)定義，它輸出配對括號個數(shù)。寫出一個翻譯方案，打印每個a的嵌套深度。如(a,a) ,a

19、)，打印2, 1。 解答：加入新的開始符號S，和規(guī)則S，aS,得到增廣文法：s=sSx(L)S:=AL:=LbSL；：=S1為s； L引入屬性h,語法制導(dǎo)定義為：S=Spnnt (S.h)S 二=(L)S.h:=L.h+lS:= aS.h:=OL：: =Li, SL.h:=Li.h+S.hL：: =SL.h:=S.h2引入屬性d,翻譯方案定義為：S：=S.d:=O; SS :='C L.d:=S.d+l; Li Sd:=Ld; S，L:=S.d=L.d; S13. (中國科學(xué)院軟件所2000年)程序的文法如下：Pf DDD; D|id ; T|proc id ; D ; S(1) 寫一

20、個語法制訂定義，打印該程序一共聲明了多少個id.(2) 寫一個翻譯方案，打印該程序每個變量id的嵌套深度。 解答：(1)引進(jìn)屬性b得到語法制導(dǎo)定義如下：PDprint (D,i); DDi；D?D.i:=Di.i+D2.i；D->id :TD.i:=l; D-proc id :DI ; S引進(jìn)屬性1和得到翻譯方案如卞:D->Di.l:=D.l; DiDz.l-D.l; d2DidTprint （ Ql）； DprocIdDi.l:=D.l+l;D）s14. （中國科學(xué)院計算所1995年）設(shè)有文法GS：S;:=L.L|LL:=LB|BE:=0|l給此文法配上語義動作子程

21、序（或者說為此文法寫一個語法制導(dǎo)定義），它輸出S產(chǎn)生 的二進(jìn)制數(shù)的值，例如101.101時，輸出5.625。解答：加入新的開始符號9和規(guī)則9 : =S,得到增廣文法。s=spimt (S.val); S:=Li.LzS.val:=Li.val+L2.vaV2L2 kngth;S:=LS.val:=L.val; L:=LiBL.val:=Li.val*2+B.val; L.length:=Li.lengths 1;L:=BL.val:=B.val; L.length:=l; B:=0B.val:=0;B:=lB.val:=l; 語法制導(dǎo)定義如下：15. (中國科學(xué)院計算所1993年)請按語法制導(dǎo)

22、的定義將后綴表達(dá)式翻譯成中綴表達(dá)式。注 意：不允許出現(xiàn)冗余拾號，后綴表達(dá)式的文法如下：E：=E1E2+E:=EiE2*E:=id解答：加入新的餓開始符號S和規(guī)則S:=E,得到增廣文法。語法制導(dǎo)定義如下：S:=Eprint (E.code) E：=EiE2+E.code:=Ei.code|p |Ez.code; E.op=>+> E:=E1E2*if Ei.op= + and E：.op=ThenEi.code:= X c |Ei.code| 0 ' * MP Cll Ei.code| 4 ) c;ElseIf El .op=,+JThen E.codeh C | Ei.co

23、de| ')' |4 * 'HEz.code; ElseIf E2.op=5+,Then E.code:=Ei.code|c c |p (4 |E2.code| y ； ElseE.code:=Ei.code|c* ' |E2.code;E.oph *；E:=idE.code:=id.lexval; E.op='$，;16.某程序設(shè)計語言說明部分的語法制導(dǎo)定義如下所示：D:=TL T:=mt T:=real L:=LijdL:=id給出其語法制導(dǎo)定義及自底向上分析的翻譯方案，并比較兩者的不同解答：語法制導(dǎo)定義為：D:=TLL.in:=T.typeT:=i

24、iitT.type:=iiitegerT:=realT.type:=realL:=LljdL.m:=L.m addtvpe (id.entryX.iii) L:=idaddtype (id.entiy, L.m) 自底向上分析的翻譯方案為：D:=TL T:=mtL.iii:=T.typeT.type:=integerT:=realT.type:=realL:=L.in:=L.inLbidaddtvpe (id.entiy. L.m) L:=idaddtype (id.entry, L.iii)從上述定義可見，兩者的區(qū)別僅在于翻譯方案中，把語義操作插入在規(guī)則右部的任意位置。17. 給出PASCAL語言常量定義的翻譯方案。解答：PASCAL語言常量定義的翻譯方案為：CONSTDP:=CONST CDTCDT:=CDT: CDCD:=id=num num.ord: =lookCT (num.lexval);id.ord:=num.oid;ld.type :=iiiteger ;id .kind :=CONSTANT;add (id.entry; 1d.kind4d.typejd.01d) CD:=id=id i id .kind :=CONSTANT; ld.type:=id 1 .typelid.ord:=idi.ord;add (id.