程序設(shè)計(jì)語言-編譯原理(第三版-習(xí)題庫-答案)第五章-語法制導(dǎo)翻譯及中間代碼生成

第五章語法制導(dǎo)翻譯及中間代碼生成5.1說明屬性文法與屬性翻譯文法有何異同?5.2考慮下面的屬性文法：Z→sXattribution:Z.a=X.c;X.b=X.a；Z.p=X.b；Z→tXattribution：X.b=X.d;Z.a=X.b;X→uattribution:X.d=1;X.c=X.d;X→Vattribuion:X.c=2;X.d=X.c;(1)上述文法中的屬性哪些是繼承的?哪些是綜合的?(2)上述文法中的屬性依賴是否出現(xiàn)了循環(huán)?5.3為什么說S屬性文法一定是L屬性文法?反之結(jié)論亦正確嗎?5.4將下列中綴式改寫為逆波蘭式。(1)-A*(B+C)↑(D-E)(2)((a*d+c)/d+e)*f+g(3)a+x≤4∨(C∧d*3)(4)a∨b∧c+d*e↑f(5)s=0;i=1;while(i＜=100){s+=i*i;i++;}5.5將下列后綴式改寫為中綴式。(1)abc*+(2)abc-*cd+e/-(3)abc+≤a0＞∧ab+0≠a0∧∨(4)ab＜p1BZxab-c↑=p2BRgh=↑↑p1p25.6設(shè)已給文法G［E］：E→E+T|-T|TT→T*F|FF→P↑F|PP→(E)|i試設(shè)計(jì)一個(gè)遞歸下降分析器，要求此分析器在語法分析過程中，將所分析的符號(hào)串翻譯成后綴式。5.7設(shè)已給布爾表達(dá)式文法G［Z］：Z→EE→T{∨T}T→F{∧F}F→F|(E)|b試設(shè)計(jì)一個(gè)遞歸下降分析器，它把由G［Z］所描述的布爾表達(dá)式翻譯為四元式序列。5.8(1)利用54節(jié)所給的屬性翻譯文法將賦值語句：X=A*(B+C)+D翻譯成四元式序列，給出語法制導(dǎo)的翻譯過程。(2)利用55節(jié)所給的屬性翻譯文法將布爾表達(dá)式：A∧(B∨(C∨D∧F))翻譯成四元式序列，給出語法制導(dǎo)的翻譯過程。(3)利用56節(jié)所給的屬性翻譯文法將語句：whileA＜C∧B＞0doifA=1thenC∶=C+1elsewhileA＜=DdoA∶=A+2翻譯成四元式序列，給出語法制導(dǎo)的翻譯過程。5.9寫出翻譯下列語句的屬性翻譯文法。(1)foriden∶=E1stepE2untilE3doS其中，E1，E2，E3分別為初值參數(shù)、步長參數(shù)和終值參數(shù)，E2的值可負(fù)，且要求E2，E3僅被計(jì)算一次。(2)repeatSuntilE5.10根據(jù)57節(jié)所給屬性翻譯文法對賦值語句：A［I,J］∶=B［J-1,A［I-J,I+J］,I+1］給出產(chǎn)生四元式序列的過程(假定數(shù)組各維下標(biāo)的下界均為1；A的下標(biāo)上界分別為10和20；B的下標(biāo)上界分別為10，20和30)。5.11設(shè)有下面的FORTRAN程序：N=2M=3CALLSUB(N+M,N,N)WRITE(U,10)N10FORMAT(I2)STOPENDSUBROUTINESUB(I，J，K)J=J+2K=K+IRETURNEND若在編譯上述程序時(shí)，過程調(diào)用的形實(shí)結(jié)合分別采用值調(diào)用、引用調(diào)用，程序執(zhí)行后所輸出的N值各是什么?5.12對下面的PASCAL程序：programex512;vari:integer;b:array［1··4］ofinteger;procedureq(x:integer;vary:integer);begini∶=1;x∶=x+2;b［i］=15;y∶=y+3;b［i］=20end;beginfori∶=1to4dob［i］∶=i;i∶=1;q(b［i］,b［i+1］);fori∶=1to4dowrite(b［i］)end.試指出，當(dāng)執(zhí)行上述程序時(shí)，過程調(diào)用的形實(shí)結(jié)合分別采用值調(diào)用、引用調(diào)用、結(jié)果調(diào)用和值結(jié)果調(diào)用時(shí)，程序執(zhí)行后的輸出結(jié)果。5.13在PASCAL語言中，標(biāo)準(zhǔn)的標(biāo)量類型可用形如：VAR〈變量名〉{，〈變量名〉}：〈類型〉的語法結(jié)構(gòu)說明，其中，〈類型〉是integer，real，boolean或char等類型說明符之一。試寫出上述類型說明的S屬性翻譯文法。5.14試用PASCAL語言寫出一個(gè)實(shí)參為形參過程的程序?qū)嵗?.15若一語言的數(shù)組下標(biāo)的下界只能是0(如C語言)，則數(shù)組內(nèi)情向量應(yīng)有哪些內(nèi)容?試給出相應(yīng)的屬性翻譯文法。5.16在FORTRAN語言中，數(shù)組是按列存放的，且各維的下界為1，試?yán)蒙项}的結(jié)果，給出相應(yīng)的屬性翻譯文法。5.17C語言的條件語句的結(jié)構(gòu)為：Stmt→if(Expr)Stmt;［elseStmt;］試給出相應(yīng)的屬性翻譯文法。上機(jī)實(shí)習(xí)題對第4章上機(jī)實(shí)習(xí)題(一)所給的微PASCAL語言文法，完成下列工作：(1)試編寫用YACC對該文法所定義的語言進(jìn)行語法制導(dǎo)翻譯，生成相應(yīng)的四元式序列的YSP文件；(2)使用YACC將該YSP文件翻譯為C語言程序，再利用C編譯器將其編譯為EXE文件；(3)自行編寫若干個(gè)微PASCAL源程序作為測試用例，對所生成的編譯器進(jìn)行測試。要求：(1)自行完成對文法的“拆分”和語義動(dòng)作的編寫。(2)自行完成相應(yīng)的詞法分析程序的設(shè)計(jì)。(3)該翻譯程序應(yīng)能完成查填變量表工作。(4)程序運(yùn)行結(jié)束前，應(yīng)將四元式序列和變量表輸出到某個(gè)指定文件中。第五章習(xí)題解答5.1解：屬性文法是文法符號(hào)帶有語義屬性的前后文無關(guān)文法；屬性翻譯文法首先是對文法的屬性依賴關(guān)系作出限制，不允許出現(xiàn)屬性的直接或間接的循環(huán)定義，即要求屬性文法是良定義的；其次還應(yīng)將屬性定義規(guī)則改造為計(jì)算屬性值的語義程序，即將靜態(tài)的定義規(guī)則改寫為可動(dòng)態(tài)執(zhí)行的語義動(dòng)作；屬性文法是靜態(tài)描述，而屬性翻譯文法是動(dòng)態(tài)描述，有語義動(dòng)作。5.2解：綜合屬性有：Z.aZ.pX.dX.c繼承屬性有：X.b屬性依賴出現(xiàn)了循環(huán)；5.3解：S屬性文法一定是L屬性文法，因?yàn)榍罢呤窃诤笳呋A(chǔ)上加上限制條件，即非終結(jié)符只有綜合屬性；反之當(dāng)然不正確。5.4解：A-BC+*DE-^ad*c+d/e+f*g+ax+4<=cd3*/\\/de*c+b/\a\/f^s0=;i1=;i100<=BZssii*+=;ii1+=;BRS2’5.5解：a+b*ca*(b-c)-(c+d)/e有誤if(a<b)x=(a-b)^c;elseg=h;5.6略5.7略5.8解：(+,B,C,T1)(*,A,T1,T2)(+,T2,D,T3)(=,T3,0,X)2）如下所示：當(dāng)前句型（方框括起來部分為句柄）A/\(BV(CVD/\?F))用產(chǎn)生式Expr→iden歸約，得(1)Expr.TC→(jnz,A,0,0);(2)Expr.FC→(j,0,0,0);當(dāng)前句型Expr/\(BV(CVD/\?F))用產(chǎn)生式Expr^→Expr’/\’歸約，得(1)(jnz,A,0,3);(2)Expr^.FC→(j,0,0,0);當(dāng)前句型Expr^(BV(CVD/\?F))用產(chǎn)生式Expr→iden歸約，得(1)(jnz,A,0,0);(2)Expr^.FC→(j,0,0,0);(3)Expr.TC→(jnz,B,0,0);(4)Expr.FC→(j,0,0,0);當(dāng)前句型Expr^(ExprV(CVD/\?F))用產(chǎn)生式Exprv→Expr'V'歸約，得(1)(jnz,A,0,3);(2)Expr^.FC→(j,0,0,0);(3)Exprv.TC→(jnz,A,0,0);(4)(j,0,0,5);當(dāng)前句型Expr^(Exprv(CVD/\?F))用產(chǎn)生式Expr→iden歸約，得(1)(jnz,A,0,3);(2)Expr^.FC→(j,0,0,0);(3)Exprv.TC→(jnz,A,0,0);(4)(j,0,0,5);(5)Expr.TC→(jnz,C,0,0);(6)Expr.FC→(j,0,0,0);當(dāng)前句型Expr^(Exprv(ExprVD/\?F)),用產(chǎn)生式Exprv→Expr’V’歸約，得(1)(jnz,A,0,3);(2)Expr^.FC→(j,0,0,0);(3)Exprv.TC→(jnz,A,0,0);(4)(j,0,0,5);(5)Exprv.TC→(jnz,C,0,0);(6)(j,0,0,7);當(dāng)前句型Expr^(Exprv(ExprvD/\?F)),用產(chǎn)生式Expr4→iden歸約，得(1)(jnz,A,0,3);(2)Expr^.FC→(j,0,0,0);(3)Exprv.TC→(jnz,A,0,0);(4)(j,0,0,5);(5)Exprv.TC→(jnz,C,0,0);(6)(j,0,0,7);(7)Expr.TC→(jnz,D,0,0);(8)Expr.FC→(j,0,0,0);當(dāng)前句型Expr^(Exprv(ExprvExpr/\?F)),用產(chǎn)生式Expr^→exrp’/\’歸約，得(1)(jnz,A,0,3);(2)Expr^.FC→(j,0,0,0);(3)Exprv.TC→(jnz,A,0,0);(4)(j,0,0,5);(5)Exprv.TC→(jnz,C,0,0);(6)(j,0,0,7);(7)(jnz,D,0,9);(8)Expr^.FC→(j,0,0,0);當(dāng)前句型Expr^(Exprv(ExprvExpr^?F)),用產(chǎn)生式Expr→iden歸約，得(1)(jnz,A,0,3);(2)Expr^.FC→(j,0,0,0);(3)Exprv.TC→(jnz,A,0,0);(4)(j,0,0,5);(5)Exprv.TC→(jnz,C,0,0);(6)(j,0,0,7);(7)(jnz,D,0,9);(8)Expr^.FC→(j,0,0,0);(9)Expr.TC→(jnz,F,0,0);(10)Expr.FC→(j,0,0,0);當(dāng)前句型Expr^(Exprv(ExprvExpr^?Expr)),用產(chǎn)生式Expr→?Expr歸約，得(1)(jnz,A,0,3);(2)Expr^.FC→(j,0,0,0);(3)Exprv.TC→(jnz,A,0,0);(4)(j,0,0,5);(5)Exprv.TC→(jnz,C,0,0);(6)(j,0,0,7);(7)(jnz,D,0,9);(8)Expr^.FC→(j,0,0,0);(9)Expr.FC→(jnz,F,0,0);(10)Expr.TC→(j,0,0,0);當(dāng)前句型Expr^(Exprv(ExprvExpr^Expr)),用產(chǎn)生式Expr→Expr^Expr歸約，得(1)(jnz,A,0,3);(2)Expr^.FC→(j,0,0,0);(3)Exprv.TC→(jnz,A,0,0);(4)(j,0,0,5);(5)Exprv.TC→(jnz,C,0,0);(6)(j,0,0,7);(7)(jnz,D,0,9);(8)(j,0,0,0);(9)Expr.FC→(jnz,F,0,8);(10)Expr.TC→(j,0,0,0);當(dāng)前句型Expr^(Exprv(ExprvExpr)),用產(chǎn)生式Expr→ExprvExpr歸約，得(1)(jnz,A,0,3);(2)Expr^.FC→(j,0,0,0);(3)Exprv.TC→(jnz,A,0,0);(4)(j,0,0,5);(5)(jnz,C,0,0);(6)(j,0,0,7);(7)(jnz,D,0,9);(8)(j,0,0,0);(9)Expr.FC→(jnz,F,0,8);(10)Expr.TC→(j,0,0,5);當(dāng)前句型Expr^(Exprv(Expr)),用產(chǎn)生式Expr→(Expr)歸約，所得四元式序列不變當(dāng)前句型Expr^(ExprvExpr),用產(chǎn)生式Expr→ExprvExpr歸約,得(1)(jnz,A,0,3);(2)Expr^.FC→(j,0,0,0);(3)(jnz,A,0,0);(4)(j,0,0,5);(5)(jnz,C,0,3);(6)(j,0,0,7);(7)(jnz,D,0,9);(8)(j,0,0,0);(9)Expr.FC→(jnz,F,0,8);(10)Expr.TC→(j,0,0,5);當(dāng)前句型Expr^(Expr),用產(chǎn)生式Expr→(Expr)歸約，所得四元式序列不變當(dāng)前句型Expr^Expr,用產(chǎn)生式Expr→Expr^Expr歸約,得(1)(jnz,A,0,3);(2)(j,0,0,0);(3)(jnz,A,0,0);(4)(j,0,0,5);(5)(jnz,C,0,3);(6)(j,0,0,7);(7)(jnz,D,0,9);(8)(j,0,0,2);(9)Expr.FC→(jnz,F,0,8);(10)Expr.TC→(j,0,0,5);3）假設(shè)所產(chǎn)生的四元式序列編號(hào)從1開始1.當(dāng)前句型為whileA<CùB>0doifA=1thenC:=C+1elsewhileA<=DdoA:=A+2用產(chǎn)生式W1→while歸約，得(1)Wl.loop→2.當(dāng)前句型為WlA<CùB>0doifA=1thenC:=C+1elsewhileA<=DdoA:=A+2用產(chǎn)生式Expr→idenropiden歸約，得(1)Wl.loop→Expr.TC→(j<A,C,0);(2)Expr.FC→(j,0,0,0);3.當(dāng)前句型為WlExprùB>0doifA=1thenC:=C+1elsewhileA<=DdoA:=A+2用產(chǎn)生式Expr^→Expr’ù’歸約，得(1)Wl.loop→(j<A,C,3);(2)Expr^.FC→(j,0,0,0);4.當(dāng)前句型為WlExpr^B>0doifA=1thenC:=C+1elsewhileA<=DdoA:=A+2用產(chǎn)生式Expr→idenropiden歸約，得(1)Wl.loop→(j<A,C,3);(2)Expr^.FC→(j,0,0,0);(3)Expr.TC→(j>,B.0,0)(4)Expr2.FC→(j,0,0,0);5.當(dāng)前句型為WlExpr^ExprdoifA=1thenC:=C+1elsewhileA<=DdoA:=A+2用產(chǎn)生式Expr→Expr^Expr歸約，得(1)Wl.loop→(j<A,C,3);(2)(j,0,0,0);(3)Expr.TC→(j>,B.0,0)(4)Expr.FC→(j,0,0,2);6.當(dāng)前句型為WlExprdoifA=1thenC:=C+1elsewhileA<=DdoA:=A+2用產(chǎn)生式WED→W1Exprdo歸約，得(1)WED.loop→(j<A,C,3);(2)(j,0,0,0);(3)(j>,B.0,5)(4)WED.CH→(j,0,0,2);7.當(dāng)前句型為WEDifA=1thenC:=C+1elsewhileA<=DdoA:=A+2用產(chǎn)生式Expr→idenropiden歸約，得(1)WED.loop→(j<A,C,3);(2)(j,0,0,0);(3)(j>,B.0,5)(4)WED.CH→(j,0,0,2);(5)Expr.TC→(j=,A,1,0)(6)Expr.FC→(j,0,0,0)8.當(dāng)前句型為WEDifExprthenC:=C+1elsewhileA<=DdoA:=A+2用產(chǎn)生式Condition→ifExprthen歸約，得(1)WED.loop→(j<A,C,3);(2)(j,0,0,0);(3)(j>,B.0,5)(4)WED.CH→(j,0,0,2);(5)(j=,A,1,7)(6)Condition.CH→(j,0,0,0)9.當(dāng)前句型為WEDConditionC:=C+1elsewhileA<=DdoA:=A+2將賦值語句C:=C+1歸約為Statement，得(1)WED.loop→(j<A,C,3);(2)(j,0,0,0);(3)(j>,B.0,5)(4)WED.CH→(j,0,0,2);(5)(j=,A,1,7)(6)Condition.CH→(j,0,0,0)(7)(+.,C,1,T1)(8)(=,T1,1,C)10.當(dāng)前句型為WEDConditionStatementelsewhileA<=DdoA:=A+2用產(chǎn)生式CondStElseàConditionStatement歸約，(1)WED.loop→(j<A,C,3);(2)(j,0,0,0);(3)(j>,B.0,5)(4)WED.CH→(j,0,0,2);(5)(j=,A,1,7)(6)(j,0,0,10)(7)(+.,C,1,T1)(8)(=,T1,1,C)(9)CondStElse→(j,0,0,0)11.當(dāng)前句型為WEDCondStElsewhileA<=DdoA:=A+2用產(chǎn)生式W1’→while歸約，得(1)WED.loop→(j<A,C,3);(2)(j,0,0,0);(3)(j>,B.0,5)(4)WED.CH→(j,0,0,2);(5)(j=,A,1,7)(6)(j,0,0,10)(7)(+.,C,1,T1)(8)(=,T1,1,C)(9)CondStElse→(j,0,0,0)(10)Wl.loop→12.當(dāng)前句型為WEDCondStElseWlA<=DdoA:=A+2用產(chǎn)生式Expr→idenropiden歸約，得(1)WED.loop→(j<A,C,3);(2)(j,0,0,0);(3)(j>,B.0,5)(4)WED.CH→(j,0,0,2);(5)(j=,A,1,7)(6)(j,0,0,10)(7)(+.,C,1,T1)(8)(=,T1,1,C)(9)CondStElse→(j,0,0,0)(10)Wl.loop→Expr.TC→(j,A,D,0)(11)Expr.FC→(j,0,0,0)13.當(dāng)前句型為WEDCondStElseWlExprdoA:=A+2用產(chǎn)生式WED→WlExprdo歸約，得(1)WED.loop→(j<A,C,3);(2)(j,0,0,0);(3)(j>,B.0,5)(4)WED.CH→(j,0,0,2);(5)(j=,A,1,7)(6)(j,0,0,10)(7)(+.,C,1,T1)(8)(=,T1,1,C)(9)CondStElse→(j,0,0,0)(10)WED.loop→(j,A,D,12)(11)WED.CH→(j,0,0,0)14.當(dāng)前句型為WEDCondStElseWEDA:=A+2將賦值語句歸約A:=A+2為Statement得(1)WED.loop→(j<A,C,3);(2)(j,0,0,0);(3)(j>,B.0,5)(4)WED.CH→(j,0,0,2);(5)(j=,A,1,7)(6)(j,0,0,10)(7)(+.,C,1,T1)(8)(=,T1,,C)(9)CondStElse→(j,0,0,0)(10)WED.loop→(j,A,D,12)(11)WED.CH→(j,0,0,0)(12)(+,A,2,T2)(13)(=,T2,,A)15.當(dāng)前句型為WEDCondStElseWEDStatement,用產(chǎn)生式Statement→WEDStatement歸約，得(1)WED.loop→(j<A,C,3);(2)(j,0,0,0);(3)(j>,B.0,5)(4)WED.CH→(j,0,0,2);(5)(j=,A,1,7)(6)(j,0,0,10)(7)(+.,C,1,T1)(8)(=,T1,,C)(9)CondStElse→(j,0,0,0)(10)(j,A,D,12)(11)Statement.CH→(j,0,0,0)(12)(+,A,2,T2)(13)(=,T2,,A)(14)(j,0,0,10)16.當(dāng)前句型為WEDCondStElseStatement,用產(chǎn)生式Statement→CondStElseStatement歸約，得(1)WED.loop→(j<A,C,3);(2)(j,0,0,0);(3)(j>,B.0,5)(4)WED.CH→(j,0,0,2);(5)(j=,A,1,7)(6)(j,0,0,10)(7)(+.,C,1,T1)(8)(=,T1,,C)(9)(j,0,0,0)(10)(j,A,D,12)(11)Statement.CH→(j,0,0,9)(12)(+,A,2,T2)(13)(=,T2,,A)(14)(j,0,0,10)17.當(dāng)前句型為WEDStatement,用產(chǎn)生式Statement→WEDStatement歸約，得(1)(j<A,C,3);(2)(j,0,0,0);(3)(j>,B.0,5)(4)Statement.CH→(j,0,0,2);(5)(j=,A,1,7)(6)(j,0,0,10)(7)(+.,C,1,T1)(8)(=,T1,,C)(9)(j,0,0,1)(10)(j,A,D,12)(11).(j,0,0,1)(12)(+,A,2,T2)(13)(=,T2,,A)(14)(j,0,0,10)(15)(j,0,0,1)(16)5.9解：1）First→foriden':='Expr{intT=NewTemp);GEN(=,$4.PLACE,0,ENTRY($2));$$.VAR=ENTRY($2);GEN(=,0,,T);$$.temp=ENTRY(T);$$.loop=NXQ;}Second→FirststepExpr{intU=NewTemp();$$.loop=$1.loop;GEN(j=,$1.temp,0,NXQ+2);GEN(+,$1.VAR,$3.PLACE,$1.VAR);GEN(=,1,,$1.temp);$$.VAR=$1.VAR;$$.DELTA=$3.PLACE;}Third→SeconduntilExpr{intT,T1,q=NXQ;$$.loop=$1.loop;T=NewTemp();GEN(J<,$1.DELTA,0,q+4);GEN(J>,$1.DELTA,0,q+6);GEN(=,0,,T);GEN(J,,,q+7);GEN(=,-1,,T);GEN(J,,,q+7);GEN(=,1,,T);T1=NewTemp();GEN(-,$1.DELTA,$3.PLACE,T1);GEN(*,T,T1,T1);GEN(J<,T1,0,q+11);$$.CH=NXQ;GEN(J,,,0);S→ThirddoS{BackPatch($3.CH,$1.loop);GEN(J,,,$3.loop);$$.CH=$3.CH;}2）R→repeat{$$.loop=NXQ;}Rs→RS{$$.loop=$1.loop;BackPath($2.chain,NXQ);}S→RsuntilExpr{$$.chain=$3.TC;BackPatch($3.FC,$1.loop);}5.10解：1)(*,I,20,T1)(+,J,T1,T1)(-,a,Ca,T2)(=,J,0,T)(+,T,1,T)(=,I,0,P1)(=,J,0,P2)(-,P1,P2,P1’)(=,I,0,T1)(=,J,0,T2)(+,T1,T2,T1’)(*,P1’,20,T3’)(+,T1’,T3’,T3’)(-,a,Ca,T’)(=[],T’[T3’],T3)(*,T,20,T)(+,T3,T,T)(=,I,0,T4)(+,T4,1,T4)(*,T,10,T5)(+,T4,T5,T5)(-,b,Cb,T6)(=[],T6[T5],0,T7)([]=,T7,0,T2[T1])5.11解：采用值調(diào)用:N=2采用引用調(diào)用:N=95.12解：采用值調(diào)用:b[]={1,2,3,4}采用引用調(diào)用:b[]={20,5,3,4}采用結(jié)果調(diào)用:error采用值結(jié)果調(diào)用:b[]={3,5,3,4}5.13解：1)DPart→varD2)D→VarList':'Type{BackChain($1.CH,$2.type);}3)Type→integer{$$.type='i';}4)Type→real{$$.type='r';}5)Type→boolean{$$.type='b';}6)Type→char{$$.type='c';}7)VarList→iden{$$.CH=NewChain();AddToChain($$.CH,ENTRY($1));}8)VarList→VarList','iden{AddToChain($1.CH,ENTRY($1));$$.CH=$1,CH;}5.14解：源程序PROGRAMProcAsPara;USESwincrt;VARputin,result:integer;PROCEDUREchild(VARa:INTEGER,FUNCTIONf,i:INTEGER);BEGINa:=f(i)END;FUNCTIONfunc(x:INTEGER):INTEGER;BEGINfunc=x*x;RETURNEND;BEGINputin:=8;ch