《編譯原理》課程復(fù)習(xí)五、計(jì)算題：1、考慮下面程序Vara：integer；ProcedureS(X)；VarX：integer；Begina：^a+1；X：=a+XEnd；Begina：=5；S(a)；Print(a)End.試問:若參數(shù)傳遞方式分別采取傳名和傳值時(shí)，程序執(zhí)行后輸出a的值是什么？答：傳名：a=12傳值：a=62、寫出表達(dá)式(a+b*c)/(a+b)—d的逆波蘭表示及三元式序列。逆波蘭表示：abc*+ab+/d—三元式序列：(*,b,c)(+,a,①)(+,a,b)(/,②，③)(一，④，d)3、已知文法G(S)S—a|A|(T)T—T,S|S寫出句子((a,a),a)的規(guī)范歸約過程及每一步的句柄。句型歸約規(guī)則句柄((a,a),a)S—aa((S,a),a)T—SS((T,a),a)S—aa((T,S),a)T—T,ST,S((S),a)T—SS((T),a)S—S(T)(T)(S,a)T—SS(T,a)S—aa4、5、6、(T,S)(T)ST—T,SS-(T)T,S(T)寫一個(gè)文法，使其語(yǔ)言是奇數(shù)集，且每個(gè)奇數(shù)不以0開頭。解：文法G(N)：N—AB|BA—AC|DB—1|3|5|7|9D—B|2|4|6|8C—0|D設(shè)文法G(S)：S—(L)|aS|aL—L，SIS解：S—(L)|aS’S’—S倍L—SL’L’—SL’倍FIRST)S)={(,a}FOLLOW(S)={#,,,FIRST(S’)={,a,s)FOLLOW(S’)={#,,FIRST(L)={(,a}FOLLOW(L)={)}FIRST(L’)={,,￡)FOLLOW(L’)={}}(1)消除左遞歸和回溯；⑵計(jì)算每個(gè)非終結(jié)符的FIRST和FOLLOW；(3)構(gòu)造預(yù)測(cè)分析表。Whilea>0Vb<0doBegin)})}X：=X+1；ifa>0thena：=a—1elseb：=b+1End；翻譯成四元式序列。解：(j>,a,0,5)⑵(j，—，—，3)(j<,b,0,5)(j,—,—,15)⑸(+,x,1,T1)(:=,T1,—,x)(j>,a,0,9)(j,—,—,12)⑼(一，a,1,T2)(10)(：=,T2,—,a)(j,—,—,1)(:=,T3,一,b)(j，-，-，1)(15)7、已知文法G(E)E—T|E+TT—F|T*FF-(E)|i給出句型(T*F+i)的最右推導(dǎo)及畫出語(yǔ)法樹；給出句型(T*F+i)的短語(yǔ)、素短語(yǔ)。解：(1)最右推導(dǎo)：E—T—F—(E)—(E+T)—(E+F)—(E+i)—(T+i)—(T*F+i)(2)短語(yǔ)：(T*F+i),T*F+i,T*F,i素短語(yǔ)：T*F,i8、設(shè)布爾表達(dá)式的文法為E—E(1)VE(2)E—E(1)AE(2)E—i假定它們將用于條件控制語(yǔ)句中，請(qǐng)(1)改寫文法，使之適合進(jìn)行語(yǔ)法制導(dǎo)翻譯和實(shí)現(xiàn)回填；(2)寫出改寫后的短個(gè)產(chǎn)生式的語(yǔ)義動(dòng)作。解：(1)E0—E(1)E—E0E(2)EA—E(1)E—EAE(2)E—i⑵E—E⑴{BACKPATCH(E(1)FC,NXQ)；E0-TC：=E(1)-TC}E—E0E(2){E-FC：=E(2)-FC；E-TC：=MERG(E0-TC,E(2)?TC)}EA—E(1){BACKPATCH(E(1)-TC,NXQ)；E0-FC：=E(1)-FC}E—EAE(2){E-TC：=E(2)-TC；E-FC：=MERG(EA-FC,E(2)?FC}E—i{E?TC：=NXQ；E?FC：=NXQ+1；GEN(jn2,entry(i),-0)；GEN(j,-,-,0)9、設(shè)有基本塊T1：=2T2：=10/TT3：=S-RT4：=S+RA：=T2*T4B：=AT5：=S+RT6：=T3*T5B：=T6假設(shè)基本塊出口時(shí)只有A,B還被引用，請(qǐng)寫出優(yōu)化后的四元序列。解：優(yōu)化后的四元式T3：=S—RT4：=S+RA：=5*T4B：=T3*T410、給定文法G=({S,L},{a,(,)},{S一(L)|aL—L,S|S},S)。給出句型”(S,(a))”的推導(dǎo)和語(yǔ)法樹并指出此句型的所有短語(yǔ)、直接短語(yǔ)、句柄和素短語(yǔ)。解：ST(L)T(L,S)T(L,(L))T(L,(S))T(L,(a))T(S,(a))短語(yǔ)有：“a”,“(a)”,“S”，“S,(a)”，“(S,(a))”。直接短語(yǔ)有：”S”，“a”句柄：“S”素短語(yǔ)：“a“語(yǔ)法樹略。11、設(shè)語(yǔ)言L是由奇數(shù)個(gè)a和偶數(shù)(可以是0)個(gè)b組成的符號(hào)串之集。構(gòu)造識(shí)別L的DFA；給出定義L的正規(guī)文法；解：(1)見圖：(2)S一aA|bBA一aS|bC|eB一bS|aCC一bA|aB12、將文法G[S]：S一[AA一AS|B]B一Bi|i改寫為等價(jià)的LL(1)文法，并給出相應(yīng)的LL(1)分析表。解：B—iCC一iC|eA—B]A’A’一ASA’|eS一[AFirst(ASA’)={i},FOLLOW(A’)={[]FIRST(iC)={i},FOLLOW(C)={}}可知文法滿足LL(1)文法的條件。分析表：

13、化簡(jiǎn)文法G[S]:S一ASe|BCaD|aD|ACA一Cb|DBSC一bC|dB一AcD一aD解：化簡(jiǎn)后：S一ASe|ACA一CbC一bC|d14、設(shè)Li{a,b,c}*是滿足下述條件的符號(hào)串構(gòu)成的語(yǔ)言：若出現(xiàn)a，則其后至少緊跟兩個(gè)c；若出現(xiàn)b，其后至少緊跟一個(gè)c。試構(gòu)造識(shí)別L的最小化的DFA，并給出描述L的正規(guī)表達(dá)式。解：DFA如圖所示。相應(yīng)的正規(guī)式為(c|acc|bc)*。15、已給文法G[S]:S一SaP|Sf|PP一qbP|q將G[S]改造成LL(1)文法，并給出LL(1)分析表。解：改造后的文法：S一PS'S'一aPS'|fS'|eP一qP'P'一bP|e各候選式的FIRST集，各非終結(jié)符的FOLLOW集為產(chǎn)生式FIRST集FOLLOW集S一PS'{q}{#}S'一aPS'{a}{#}一fS'{f}—e{e}P一qP'{q}{a,f,#}P'一bP{a,f,#}—e{e}LL(1)分析表為16、給定文法G[S]:S一Aa|dAb|Bb|dBaA一cB一c，構(gòu)造文法G[S]的LR(1)分析表。解：分析表如下圖所示好AJCTICNGOTOabCdSAB0SiS-12312方泠'St4gid蘋95T>rt6n■7ri8■ffll9Sil10Id.11n12r?17、將下面的條件語(yǔ)句表示成逆波蘭式和四元式序列:ifa>bthenx:=a+b*celsex:=b-a;解：（1）逆波蘭式：(2)四元式：(j>,a,b,(3))(j,,,(7))(*,b,c,T1)⑷(+,a,T1,T2)(:=,T2,,x)(j,,,(9))(-,b,a,T3)(:=,T3,,x)()18、給定基本塊：A:=3*5B:=E+FC:=A+12D:=E+FA:=D+12C:=C+1E:=E+F假定出基本塊后，只有A、C、E是活躍的，給出用DAG圖完成優(yōu)化后的代碼序列。解：化簡(jiǎn)后的的四元式序列為D:=E+FA:=D+12E:=E+FC:=2819、試構(gòu)造生成語(yǔ)言L={anbncilnQ1,iQ0}的文法解：G(Z):Z-ABA—aAblabB—cB|s20、已知語(yǔ)言L={anbbnln31},寫出產(chǎn)生L的文法。[解]:G[S]:S—aAbA—aAblb21、已知文法G=({A,B,C},{a,b,c},A,P)，其中產(chǎn)生式P由以下組成：A—abcA—aBbcBb—bBBc—CbccbC—CbaC—aaBaC—aa問：此文法表式的語(yǔ)言是什么？[解]：由于A為開始符。由于A—aBbc—abBc—abCbcc—aCbbcc—aabbcc語(yǔ)言為：{anbncn,n>0}22、試構(gòu)造語(yǔ)言L={anbnd|n>=1,i>=0}的文法。[解]:G(Z):Z—ABA—aAblabB—cB|s23、試寫一文法，使其描述的語(yǔ)言L(G)是能被5整除的整數(shù)集合。解：G(Z):Z—(+1-)A(0I5)A—0I1I2I3I4I5I6I7I8I9IAA|e24、已知語(yǔ)言L={xIxi{a,b,c}*,且x重復(fù)排列是對(duì)稱的(aabcbaa,aabbaa，等)寫出該語(yǔ)言的文法。解：G(Z)：Z—aZaIbZbIcZcIaIbIc|￡25、寫能被5整除的十進(jìn)制整數(shù)的文法及正則表達(dá)式。解：能被5整除的文法：G[Z]:Z—(+I-)A(0I5)A—0I1I2I3I4I5I6I7I8I9IAA|￡如果要求：除零以外不以0開頭，則文法為：G[Z]:Z—(+I-)A(0I5)A—ABICB—0ICIBBC—0I1I2I3I4I5I6I7I8I9正則表達(dá)式：G[Z]:Z=(+I-)A*(0I5)A￡(0,1,2,3,4,5,6,7,8,9)26、寫一個(gè)文法，使其語(yǔ)言是奇數(shù)集，且每個(gè)奇數(shù)不以0開頭。解：文法G(N)：N—ABIBA—ACIDBf1I3I5I7I9D—BI2I4I6I8C—0ID27、寫出能被3整除十進(jìn)制整數(shù)的文法和正則表達(dá)式:解：能被3整除的文法：G=({0,1,2,3,4,5,6,7,8,9},{S,A,B},S,P,)其中P為:S—(0|3|6|9)S|sS—(1|4|7)A|(2|5|8)BA—(0|3|6|9)A|(1|4|7)B|(2|5|8)SB—(0|3|6|9)B|(2|5|8)A|(1|4|7)S正則表達(dá)式：Z=a*I(bc)*I(cb)*I(aIcibi)*I(ciabi)*(i＞=1)a￡(0,3,6,9)be(1,4,7)c￡(2,5,8)28、寫一文法，使其語(yǔ)言是偶正整數(shù)的集合要求：允許0打頭不允許0打頭解：G[S]=({S,P,D,N},{0,1,2,???，9},P,S)P:S9PD|DP-＞NP|ND90|2|4|6|8N-＞0|1|2|3|4|5|6|7|8|9G[S]=({S,P,R,D,N,Q},{0,1,2,-,9},P,S)P:S9PD|P0|DP-＞NR|NR-＞QR|QD92|4|6|8N-＞1|2|3|4|5|6|7|8|9Q-＞0|1|2|3|4|5|6|7|8|929、已知文法G：〈表達(dá)式＞::二〈項(xiàng)＞|＜表達(dá)式＞+＜項(xiàng)＞|＜表達(dá)式＞-＜項(xiàng)＞〈項(xiàng)＞::=〈因子＞|＜項(xiàng)＞*〈因子＞|＜項(xiàng)＞/〈因子＞〈因子＞::二(＜表達(dá)式＞)|i。試給出下述表達(dá)式的推導(dǎo)及語(yǔ)法樹。(1)i;(2)(i)(3)i*i;(4)i*i+i;(5)i+(i+i);(6)i+i*i。解：(1)v=＜表達(dá)式＞=＞＜項(xiàng)＞=＞＜因子＞=＞i=w

⑵v=＜表達(dá)式＞=＞＜項(xiàng)＞=＞＜因子＞=＞（＜表達(dá)式＞）=＞（＜項(xiàng)＞）=＞（＜因子＞）=＞（i）=w（3）v=＜表達(dá)式＞=＞＜項(xiàng)＞=＞＜項(xiàng)＞*〈因子＞=＞＜因子＞*＜因子＞=＞i*i=w（4）v=＜表達(dá)式＞=＞＜表達(dá)式＞+＜項(xiàng)＞=＞＜項(xiàng)＞+〈項(xiàng)＞=＞＜項(xiàng)＞*〈因子＞+＜項(xiàng)＞=＞＜因子＞*＜因子＞+〈因子＞=＞i*i+i=w（5）v=＜表達(dá)式＞=＞＜表達(dá)式＞+〈項(xiàng)＞=＞＜項(xiàng)＞+〈項(xiàng)＞=＞＜因子＞+〈因子＞=＞i+（＜表達(dá)式＞）=＞i+（＜表達(dá)式＞+＜項(xiàng)＞）=＞i+（＜項(xiàng)＞+〈項(xiàng)＞）=＞i+（＜因子＞+〈因子＞）=＞i+（i+i）=w（6）v=＜表達(dá)式＞=＞＜表達(dá)式＞+〈項(xiàng)＞=＞＜項(xiàng)＞+〈項(xiàng)＞=＞＜因子＞+＜項(xiàng)＞=＞i+＜項(xiàng)＞i+i*i=w=＞i+〈項(xiàng)＞*〈因子＞=＞i+＜因子＞*〈因子＞=＞語(yǔ)法樹見下圖：i+i*i=w(1)i(2)(i)(3)i*i〈表達(dá)式〉〈表達(dá)式〉〈表達(dá)式〉〈項(xiàng)〉〈項(xiàng)〉〈項(xiàng)〉〈因子〉＜因子〉〈項(xiàng)〉*〈因子＞〈表達(dá)式＞()〈因子＞〈項(xiàng)＞〈因子＞(4)i*i+i(5)i+(i+i)(6)i+i*i〈表達(dá)式＞〈項(xiàng)＞〈項(xiàng)＞*〈因子〉〈表達(dá)式〉+〈因子〉i〈項(xiàng)〉〈表達(dá)式〉+〈項(xiàng)〉〈表達(dá)式〉〈因子〉〈項(xiàng)〉〈因子〉〈項(xiàng)〉(4)i*i+i(5)i+(i+i)(6)i+i*i〈表達(dá)式＞〈項(xiàng)＞〈項(xiàng)＞*〈因子〉〈表達(dá)式〉+〈因子〉i〈項(xiàng)〉〈表達(dá)式〉+〈項(xiàng)〉〈表達(dá)式〉〈因子〉〈項(xiàng)〉〈因子〉〈項(xiàng)〉i〈因子〉(1〈表達(dá)式〉）〈因子〉i〈表達(dá)式〉+〈項(xiàng)〉1〈項(xiàng)〉〈因子〉〈因子〉ii〈表達(dá)式＞〈因子〉i〈表達(dá)式＞：：=i|（＜表達(dá)式＞）|＜表達(dá)式＞＜運(yùn)算符＞＜表達(dá)式〉〈運(yùn)算符〉：：=+|-|*|/解：為句子i+i*i構(gòu)造的兩棵語(yǔ)法樹如下：

〈表達(dá)式＞〈表達(dá)式＞+〈表達(dá)式＞〈表達(dá)式＞〈表達(dá)式＞*〈表達(dá)式＞i〈表達(dá)式＞〈表達(dá)式＞〈表達(dá)式＞+〈表達(dá)式＞〈表達(dá)式＞〈表達(dá)式＞*〈表達(dá)式＞iiii所以，該文法是二義的。31、令文法G[E]為:e3t|e+t|e-tt3f|t*f|t/fF9(E)|i證明E+T*F是它的一個(gè)句型，指出這個(gè)句型的所有短語(yǔ)、直接短語(yǔ)和句柄。解：可為E+T*F構(gòu)造一棵語(yǔ)法樹(見下圖)，所以它是句型。E/KE+TT*F從語(yǔ)法樹中容易看出，E+T*F的短語(yǔ)有：T*F是句型E+T*F的相對(duì)于T的短語(yǔ)，也是相對(duì)于規(guī)則T3T*F的直接短語(yǔ)。E+T*F是句型E+T*F的相對(duì)于E的短語(yǔ)。句型E+T*F的句柄(最左直接短語(yǔ))是T*F。32、構(gòu)造下列正規(guī)式相應(yīng)的DFA：1(0|1)*1011(1010*|1(010)*1)*0解：(1)1(0|1)*101對(duì)應(yīng)的NFA為卜表由子集法將NFA轉(zhuǎn)換為DFA：I】0=s-closure(MoveTo(I,0))I1=s-closure(MoveTo(I,1))A[0]B[1]B[1]B[1]C[1,2]C[1,2]D[1,3]C[1,2]D[1,3]B[1]E[1,2，4]E[1,4]B[1]B[1，4]

0,1(2)1(1010*|1(010)*1)*0對(duì)應(yīng)的NFA為卜表由子集法將NFA轉(zhuǎn)換為DFA：I】0=s-closure(MoveTo(I,0))I1=s-closure(MoveTo(I,1))A[0]B[1,6]B[1,6]C[10]D[2,5,7]C[10]D[2,5,7]E[3,8]B[1,6]E[3,8]F[1,4,6,9]F[1,4,6,9]G[1,2,5,6,9,10]D[2,5,7]G[1,2,5,6,9,10]H[1,3,6,9,10]I[1,2,5,6,7]H[1,3,6,9,10]J[1,6,9,10]K[2,4,5,7]I[1,2,5,6,7]L[3,8,10]I[1,2,5,6,7]J[1,6,9,10]J[1,6,9,10]D[2,5,7]K[2,4,5,7]M[2,3,5,8]B[1,6]L[3,8,10]F[1,4,6,9]M[2,3,5,8]N[3]F[1,4,6,9]N[3]O[4]O[4]P[2,5]P[2,5]N[3]B[1,6]

33、已知NFA=({x,y,z},{0,1},虬{x},{z})其中：M(x,0)={z},M(y,0)={x,y},M(z,0)={x,z},M(x,1)={x},M(y,1)=sM(z,1)={y},構(gòu)造相應(yīng)的DFA。解：根據(jù)題意有NFA圖如下卜表由子集法將NFA轉(zhuǎn)換為DFA：IL=s-closure(MoveTo(I,0))I1=s-closure(MoveTo(I,1))A[x]B[z]A[x]B[z]C[x,z]D[y]C[x,z]C[x,z]E[x,y]D[y]E[x,y]E[x,y]F[x,y,z]A[x]F[x,y,z]F[x,y,z]E[x,y]卜面將該DFA最小化：首先將它的狀態(tài)集分成兩個(gè)子集：Pj{A,D,E},P2={B,C,F}區(qū)分P2:由于F(F,1)=F(C,1)=E,F(F,0)=F并且F(C,0)=C,所以F，C等價(jià)。由于

F(B,0)=F(C,0)=C,F(B,1)=D,F(C,1)=E,而D,E不等價(jià)(見下步),從而B與C,F可以區(qū)分。有P2i={c,f},P22=。⑶區(qū)分P1：由于A,E輸入0到終態(tài)，而D輸入0不到終態(tài)，所以D與A,E可以區(qū)分，有pii=(a,e},pi2=wceosk0o由于F(A,0)=B,F(E,0)=F,而B,F不等價(jià)，所以A,E可以區(qū)分。綜上所述，DFA可以區(qū)分為P={{A},{B},{D},{E},{C,F}}。所以最小化的DFA如下:34、將下圖確定化:0,0,1解：下表由子集法將NFA轉(zhuǎn)換為DFA：I【0=s-closure(MoveTo(I,0))I1=s-closure(MoveTo(I,1))A[S]B[Q,V]C[Q,U]B[Q,V]D[V,Z]C[Q,U]C[Q,U]E[V]F[Q,U,Z]D[V,Z]G[Z]G[Z]E[V]G[Z]F[Q,U,Z]D[V,Z]F[Q,U,Z]35、把下圖的(a)和(b)分別確定化和最小化:(a)(a):下表由子集法將NFA轉(zhuǎn);換為DFA：IIa=s-closure(MoveTo(I,a))1=s-closure(MoveTo(I,b))A[0]B[0,1]C[1]B[0,1]B[0,1]C[1]C[1]A[0]解：可得圖(al),由于F(A,b)=F(B,b)=C,并且F(A,a)=F(B,a)=B,所以A,B等價(jià)，可將DFA最小化，即：刪除B,將原來引向B的引線引向與其等價(jià)的狀態(tài)A，有圖(a2)。(DFA的最小化，也可看作將上表中的B全部替換為A，然后刪除B所在的行。)㈡(a2)最小化的DFA(a1)(b):該圖已經(jīng)是首先將它的狀態(tài)集分成兩個(gè)子集：P]={0},P2={1,2,3,4,5}區(qū)分P2：由于F(4,a)=0屬于終態(tài)集，，而其他狀態(tài)輸入a后都是非終態(tài)集，所以區(qū)分P2如下：P21={4},P22={1,2,3,5}。區(qū)分P22:由于F(1,b)=F(5,b)=4屬于*而F(2,b)與F(3,b)不等于4,即不屬于P2「所以區(qū)分P22如下：P22「{1,5},P2/{2,3}。區(qū)分P221：由于F(1,b)=F(5,b)=4,即F(1,a)=1,F(5,a)=5，所以1,5等價(jià)。區(qū)分P222:由于F(2,a)=1屬于P221，而F(3,a)=3屬于P222，所以2,3可區(qū)分。P222區(qū)分為P2221{2廣2"""結(jié)論：狀態(tài)5確定化的DFADFA。下面將該DFA最小化:222，「球⑶。該DFA的狀態(tài)集可分為：P={{0},{1,5},{2},{3},{4}},其中1,5等價(jià)。刪去將原來引向5的引線引向與其等價(jià)的狀態(tài)1，有圖(bl)。(bl)最小化的DFA36、構(gòu)造一個(gè)DFA，它接收Z(yǔ)={0,1}上所有滿足如下條件的字符串：每個(gè)1都有0直接跟在右邊。然后再構(gòu)造該語(yǔ)言的正則文法。解：根據(jù)題意，DFA所對(duì)應(yīng)的正規(guī)式應(yīng)為：(0|(10))*。所以，接收該串的NFA如下：卜表由子集法將NFA轉(zhuǎn)換為DFA：I【0=s-closure(MoveTo(I,0))I1=s-closure(MoveTo(I,1))A[0]B[0,2]C[1]B[0,2]B[0,2]C[1]C[1]B[0,2]顯然，A，B等價(jià)，所以將上述DFA最小化后有:對(duì)應(yīng)的正規(guī)文法為：G[A]：A^1C|0A|sC30A37、給出下述文法所對(duì)應(yīng)的正規(guī)式：S90A|1BA91S|1B90S|0解：把后兩個(gè)產(chǎn)生式代入第一個(gè)產(chǎn)生式有：S=01|01SS=10|10S有:S=01S|10S|01|10=(01|10)S|(01|10)=(01|10)*(01|10)即：(01|10)*(01|10)為所求的正規(guī)式。38、對(duì)文法G[S]S^a|A|(T)T9T,S|S給出(a,(a,a))和(((a,a),A,(a)),a)的最左推導(dǎo)。對(duì)文法G，進(jìn)行改寫，然后對(duì)每個(gè)非終結(jié)符寫出不帶回溯的遞歸子程序。經(jīng)改寫后的文法是否是LL(1)的？給出它的預(yù)測(cè)分析表。給出輸入串(a,a)#的分析過程，并說明該串是否為G的句子。解：(a,(a,a))的最左推導(dǎo)為S9(T)9(T,S)9(S,S)9(a,(T))9(a,(T,S))9(a,(S,a))->(a,(a,a))(((a,a),A,(a)),a)的最左推導(dǎo)為S9(T)9(T,S)9(S,a)9((T),a)9((T,S),a)9((T,S,S),a)9((S,A,(T)),a)9(((T),A,(S)),a)9(((T,S),A,(a)),a)9(((S,a),A,(a)),a)9(((a,a),A,(a)),a)⑵由于有T9T,S的產(chǎn)生式，所以消除該產(chǎn)生式的左遞歸，增中一個(gè)非終結(jié)符U有新的文法G/[S]:S9a|A|(T)T9SUU9,SU|￡分析子程序的構(gòu)造方法對(duì)滿足條件的文法按如下方法構(gòu)造相應(yīng)的語(yǔ)法分析子程序。對(duì)于每個(gè)非終結(jié)號(hào)U,編寫一個(gè)相應(yīng)的子程序P(U)；對(duì)于規(guī)則U::=x1|x2|..|xn,有一個(gè)關(guān)于U的子程序P(U),P(U)按如下方法構(gòu)造：IFCHINFIRST(xl)THENP(x1)ELSEIFCHINFIRST(x2)THENP(x2)ELSE...IFCHINFIRST(xn)THENP(xn)ELSEERROR其中，CH存放當(dāng)前的輸入符號(hào)，是一個(gè)全程變量；ERROR是一段處理出錯(cuò)信息的程序;P(xj)為相應(yīng)的子程序。對(duì)于符號(hào)串x=y1y2...yn;p(x)的含義為：BEGINP(y1);P(y2);...P(yn);END如果yi是非終結(jié)符，則P(yi)代表調(diào)用處理yi的子程序；如果yi是終結(jié)符，則P(yi)為形如下述語(yǔ)句的一段子程序IFCH=yiTHENREAD(CH)ELSEERROR即如果當(dāng)前文法中的符號(hào)與輸入符號(hào)匹配，則繼續(xù)讀入下一個(gè)待輸入符號(hào)到CH中，否則表明出錯(cuò)。如果文法中有空規(guī)則U::=EPSILON,則算法中的語(yǔ)句IFCHINFIRST(xn)THENP(xn)ELSEERROR改寫為：IFCHINFIRST(xn)THENP(xn)ELSEIFCHINFOLLOW(U)THENRETURNERROR要分析一個(gè)OrgStr,應(yīng)在該串的后面加上一個(gè)串括號(hào)'#',并從子程序P(S)(S為文法的開始符號(hào))開始，如果中途沒有產(chǎn)生錯(cuò)誤，并且最后CH='#'，則說明OrgStr串合法，否則該串不合法。對(duì)每個(gè)非終結(jié)符寫出不帶回溯的遞歸子程序如下：charCH;//存放當(dāng)前的輸入符號(hào)voidP_S()//非終結(jié)符S的子程序(if(CH==’a’)READ(CH);//產(chǎn)生式S9aelseif(CH==，A，)READ(CH);//產(chǎn)生式S9^elseif(CH==’(’)//產(chǎn)生式S9(T)(READ(CH);P_T();IF(CH==')')THENREAD(CH)elseERROR}elseERR;}voidP_T()//非終結(jié)符S的子程序(if(IsIn(CH,FIRST_SU))//FIRST_SU為T9SU的右部的FIRST集合(P_S();P_U();}}voidP_U()//非終結(jié)符U的子程序(if(CH==’,’)//產(chǎn)生式U9，SU(READ(CH);P_S();P_U();}else//產(chǎn)生式U9s(if(IsIn(CH,FOLLOW_U))//FOLLOW_U為U的FOLLOW集合return;elseERR;}}⑶判斷文法G/[S]是否為L(zhǎng)L(1)文法。各非終結(jié)符的FIRST集合如下：FIRST(S)={a,A,(}FIRST(T)=FIRST(S)={a,A,(}FIRST(U)={，,s}各非終結(jié)符的FOLLOW集合如下：FOLLOW(S)={#}UFIRST(U)UFOLLOW(T)UFOLLOW(U)={札，，)}FOLLOW(T)={)}FOLLOW(U)=FOLLOW(T)={)}每個(gè)產(chǎn)生式的SELECT集合如下：SELECT(S9a)={a}SELECT(S^A)={A}SELECT(S9(T))={(}SELECT(T9SU)=FIRST(S)={a,A,(}SELECT(U9,SU)={,}SELECT(U9s)=FOLLOW(U)={)}可見，相同左部產(chǎn)生式的SELECT集的交集均為空，所以文法G/[S]是LL(1)文法。文法G/[S]的預(yù)測(cè)分析表如下：aA(),#S9a9A9(T)T9SU9SU9SUU9s9,SU給出輸入串(a,a)#的分析過程步驟分析棧剩余輸入串所用產(chǎn)生式1#S(a,a)#S9(T)2#)T((a,a)#(匹配3#)Ta,a)#T9SU4#)USa,a)#S9a5#)Uaa,a)#a匹配6#)U,a)#U9,SU7#)US,,a)#，匹配8#)USa)#S9a9#)Uaa)#a匹配10#)U)#U9s11#))#)匹配12##接受39、對(duì)下面的文法G：E9TE/E/9+E|￡T9FT/T/9T|￡F9PF/F/9*F/|eP9(E)|a|b「計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的FIRST集和FOLLOW集。證明這個(gè)方法是LL(1)的。構(gòu)造它的預(yù)測(cè)分析表。構(gòu)造它的遞歸下降分析程序。解：(1)計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的FIRST集和FOLLOW集。FIRST集合有：FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,"};FIRST(E/)={+,￡}FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,"};FIRST(T/)=FIRST(T)U{￡}={(,a,b,",￡};FIRST(F)=FIRST(P)={(,a,b,"};FIRST(F/)=FIRST(P)={*,￡};FIRST(P)={(,a,b"};FOLLOW集合有：FOLLOW(E)={),#};FOLLOW(E/)=FOLLOW(E)={),#};FOLLOW(T)=FIRST(E/)UFOLLOW(E)={+,),#};//不包含￡FOLLOW(T/)=FOLLOW(T)=FIRST(E/)UFOLLOW(E)={+,),#};FOLLOW(F)=FIRST(T/)UFOLLOW(T)={(,a,b,"+,),#};//不包含￡FOLLOW(F/)=FOLLOW(F)=FIRST(T/)UFOLLOW(T)={(,a,b,"+,),#};FOLLOW(P)=FIRST(F/)UFOLLOW(F)={*,(,a,b,",+,),#};//不包含￡證明這個(gè)方法是LL(1)的。各產(chǎn)生式的SELECT集合有：SELECT(E9TE/)=FIRST(T)={(,a,b,"};SELECT(E/9+E)={+};SELECT(E/9￡)=FOLLOW(E/)={),#}SELECT(T9FT/)=FIRST(F)={(,a,b,"};SELECT(T/9T)=FIRST(T)={(,a,b,“；SELECT(T/9￡)=FOLLOW(T/)={+,),#};SELECT(F9PF/)=FIRST(P)={(,a,b,"};SELECT(F/9*F/)={*};SELECT(F/9￡)=FOLLOW(F/)={(,a,b,"+,),#};SELECT(P9(E))={(}SELECT(P9a)={a}SELECT(P9b)=SELECT(P9”)=廠}可見，相同左部產(chǎn)生式的SELECT集的交集均為空，所以文法G[E]是LL(1)文法。構(gòu)造它的預(yù)測(cè)分析表。文法G[E]的預(yù)測(cè)分析表如下:+*()ab"#E9TE/9TE/9TE/9TE/E/9+E9eT9FT/9FT/9FT/9FT/T/9T9T9T9T9eF9PF/9PF/9PF/9PF/F/->*F/圣圣9e9e9eP9(E)9a9b9構(gòu)造它的遞歸下降分析程序。對(duì)每個(gè)非終結(jié)符寫出不帶回溯的遞歸子程序如下：charCH;//存放當(dāng)前的輸入符號(hào)voidP_E()//非終結(jié)符E的子程序{if(IsIn(CH,FIRST_TEP))//FIRST_TEP為T9TE/的右部的FIRST集合，產(chǎn)生式E9TE/{P_T();P_EP();}elseERR;}voidP_EP()//非終結(jié)符E/的子程序{if(CH==’+’)//產(chǎn)生式E/9+E{READ(CH);P_E();}else//產(chǎn)生式E/^￡{if(IsIn(CH,FOLLOW_EP))//FOLLOW_EP為E/的FOLLOW集合return;elseERR;}}voidP_T()//非終結(jié)符T的子程序{if(IsIn(CH,FIRST_FTP))//FIRST_TEP為T9FT/的右部的FIRST集合，產(chǎn)生式T9FT/{P_F();P_TP();}elseERR;}voidP_TP()//非終結(jié)符T/的子程序{if(IsIn(CH,FIRST_T))//FIRST_T為產(chǎn)生式T/9T的右部的FIRST集合，產(chǎn)生式T/9T{P_T();}else//產(chǎn)生式T/^￡if(IsIn(CH,FOLLOW_TP))//FOLLOW_TP為T/的FOLLOW集合return;elseERR;}}voidP_F()//非終結(jié)符F的子程序{if(IsIn(CH,FIRST_PFP))//FIRST_PFP為F9PF/的右部的FIRST集合，產(chǎn)生式F9PF/{P_P();P_FP();}elseERR;}voidP_FP()//非終結(jié)符F/的子程序{if(CH==’*’)//產(chǎn)生式F/9*F/{READ(CH);P_FP();}else//產(chǎn)生式F/^￡{if(IsIn(CH,FOLLOW_FP))//FOLLOW_FP為F/的FOLLOW集合return;elseERR;}}voidP_P()//非終結(jié)符P的子程序{if(CH==’(‘){READ(CH);P_E();if(CH==’)’)READCH(CH);elseERR;}elseif(CH==’a’)READ(CH);elseif(CH==’b’)READ(CH);elseif(CH=='"')READ(CH);elseERR;}40、已知文法G[S]：S9MH|aH9LSo|￡K9dML|￡L^eHfM9K|bLM判斷G是否是LL(1)文法，如果是，構(gòu)造LL(1)分析表。解：首先求各非終結(jié)符的FIRST集合：FIRST(S)={a}UFIRST(M)UFIRST(H)={a}U{b,d,￡}U{e,￡}={a,b,d,e,￡};FIRST(H)=FIRST(L)U{￡}={e,￡};FIRST(K)={d,￡};FIRST(L)={e};FIRST(M)=FIRST(K)U={b,d,￡};然后求非終結(jié)符的FOLLOW集合：FOLLOW(S)={o,#}FOLLOW(H)=FOLLOW(S)U{f}={f,o,#}FOLLOW(K)=FOLLOW(M)=FIRST(H)UFOLLOW(S)={e,o,#};//不包含￡FOLLOW(L)=FIRST(S)U{o}UFOLLOW(K)UFIRST(M)UFOLLOW(M)={a,b,d,e,o,#}UFOLLOW(M)={a,b,d,e,o,#};//不包含￡FOLLOW(M)=FIRST(L)UFIRST(H)UFOLLOW(S)={e,o,#}//不包含￡最后求各產(chǎn)生式的SELECT集合：SELECT(S9MH)=(FIRST(MH)-{￡})UFOLLOW(S)={b,d,e}U{o,#}={b,d,e,o,#};SELECT(S9a)={a}SELECT(H9LSo)={e}SELECT(H9￡)=FOLLOW(H)={f,o,#}SELECT(K9dML)=g60w0gaSELECT(K9￡)=FOLLOW(K)={e,o,#}SELECT(L9eHf)={e}SELECT(M9K)=(FIRST(K)-{￡})UFOLLOW(M)={d,e,o,#}SELECT(M9bLM)=可見，相同左部產(chǎn)生式的SELECT集的交集均為空，所以文法G[S]是LL(1)文法。文法G[E]的預(yù)測(cè)分析表如下：aodefb#S9a9MH9MH9MH9MH9MHH9￡9LSo9￡9￡K9￡9dML9￡9￡L9eHfM9K9K9K9bLM9K41、設(shè)有基本塊T1：=2T2：=10/TT3：=S-RT4：=S+RA：=T2*T4B：=AT5：=S+RT6：=T3*T5B：=T6畫出DAG圖；假設(shè)基本塊出口時(shí)只有A,B還被引用，請(qǐng)寫出優(yōu)化后的四元序列。解：(1)DAG：(2)優(yōu)化后的四元式T3：=S-RT4：=S+RA：=5*T4B：=T3+T442、假定有一個(gè)獵人帶著一只狼、一頭山羊和一棵白菜來到一條河的左岸，擬擺渡過河，而岸邊只有一條小船，其大小僅能裝載人和其余三件東西中的一件，也就是說，每一次獵人只能將隨行者中的一件帶到彼岸。若獵人將狼和山羊留在同一岸上而無人照管，那么，狼就會(huì)將羊吃掉；如果獵人把山羊和白菜留在同一岸，山羊也會(huì)把白菜吃掉?，F(xiàn)在，請(qǐng)你用狀態(tài)轉(zhuǎn)換圖作為工具，描述獵人可能采取的種種擺渡方案，并從中找出可將上述三件東西安全地帶到右岸的方案來。解：假設(shè)W:表示載狼過河，G:表示載山羊過河，C:表示載白菜過河用到的狀態(tài)1：狼和山羊在左岸2：狼和白菜載左岸3:羊和白菜在左岸4:狼和山羊在右岸5:狼和白菜在右岸6:山羊和白菜在右岸F:全在右岸43、5.2考慮下面的屬性文法:Z一sXattribution:乙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;上述文法中的屬性哪些是繼承的?哪些是綜合的？上述文法中的屬性依賴是否出現(xiàn)了循環(huán)？解：綜合屬性有：乙aZ.pX.dX.c繼承屬性有：X.b屬性依賴出現(xiàn)了循環(huán)；說明屬性文法與屬性翻譯文法有何異同？屬性文法是文法符號(hào)帶有語(yǔ)義屬性的前后文無關(guān)文法;屬性翻譯文法首先是對(duì)文法的屬性依賴關(guān)系作出限制，不允許出現(xiàn)屬性的直接或間接的循環(huán)定義，即要求屬性文法是良定義的；其次還應(yīng)將屬性定義規(guī)則改造為計(jì)算屬性值的語(yǔ)義程序，即將靜態(tài)的定義規(guī)則改寫為可動(dòng)態(tài)執(zhí)行的語(yǔ)義動(dòng)作；屬性文法是靜態(tài)描述，而屬性翻譯文法是動(dòng)態(tài)描述，有語(yǔ)義動(dòng)作。45.設(shè)有PASCAL程序：PROGRAMex62;VARa,b,c,d,e:real;PROCEDUREa;VARc,e,f,g:real;PROCEDUREb;VARe,d:integer;PROCEDUREc;VARh:real;f:ARRAY\[1-10\]OFinteger;BEGIN???END;BEGINc;?END;BEGIN;?END;BEGINEND.試給出編譯程序?qū)Υ顺绦蚪⑦^程表及符號(hào)表的過程。解：(1)當(dāng)掃描到PROCEDUREa時(shí)，符號(hào)表如圖6-1：LABIBLTOPENT圖6-2^POINTERLASENT|OUTEKN、、_mt1T-SClffiRBLQ514ECOUNT(3)當(dāng)掃描到PROCEDUREc所在行時(shí)，符號(hào)表如圖6-3。POINTERLABTBL圖心’TOFE1TT符號(hào)表ECOUNTLASENTCUEKBLq5142.■2OUTERN(4)當(dāng)掃描到PROCEDUREc的begin語(yǔ)句時(shí)，符號(hào)表如圖6-4。圖5-4+-17-4oirrERNTOINTERTOPENTLASENT符號(hào)表~_斷N-8N-llIT-13CURRBLLABTBLQ1.奴22:32ECOUSToirrERHECOirffTpointerLASEJTT符號(hào)表05I-\j_114y*3i*-L_P-ff-11CUFJLBL■2J32—W-8LABTBL■——*w-4TOPEBTN+l圖W-%」(6)當(dāng)掃描到PROCEDUREA的begin語(yǔ)句時(shí)，符號(hào)表如圖6-6。CIIRRBLLAETBLJO.1422-.■3CIIRRBLLAETBLJO.1422-.■32IABTEL(7)當(dāng)掃描到PROGRAMex62的begin語(yǔ)句時(shí)，符號(hào)表如圖6-7。514矽23.2CUERBL(8)因主程序外層再無其它程序，所以，主程序的變量在符號(hào)表中的位置不必再挪動(dòng)。也就是說，圖6-7即為最終符號(hào)表的狀態(tài)。設(shè)有如下的三地址碼（四元式）序列：readNI：=NJ：=2L1：ifI<JgotoL3L2：I：=I-JifI>JgotoL2ifI=0gotoL4J：=J+1I：=NgotoL1L3：Print'YES'haltL4：Print'NO'halt試將它劃分為基本塊，并作控制流程圖。考慮如下計(jì)算兩矩陣乘積的程序:beginfori：=1tondoforj：=1tondoC\[i,j\]：=0;fori：=1tondoforj：=1tondofork：=1tondoC\[i,j\]:=C\[i,j\]+A\[i,k\]*B\[k,j\]end;假定數(shù)組A,B和C均按靜態(tài)分配其存儲(chǔ)單元，對(duì)上述程序?qū)懗鋈刂?四元式)代碼序列；將所得的三地址碼序列劃分為基本塊，并畫出相應(yīng)的控制流程圖。解：四元式序列為：i:=1gotoCHECKiLOOPi:i:=i+1CHECKi:ifi<=ngotoL1gotoOUTiL1:j:=1gotoCHECKjLOOPj:j:=j+1CHECKj:ifj<=ngotoL2gotoOUTjL2:T1:=i-1t1:=T1*nT1:=T1+jT2:=addr(C)T1[T2]:=0gotoLOOPjOUTj:gotoLOOPiOUTi:i:=1gotoCHKiLPi:i:=i+1CHKi:ifi<=ngotoL3gotoOTiL3:j:=1gotoCHKjLPj:j:=j+1CHKj:ifj<=ngotoL4gotoOTjL4:k:=1gotoCHKkLPk:k:=k+1LLk:ifk<=ngotoL5gotoOTkL5:T1:=i-1T1:=T1*nT1:=T1+jT2:=addr(C)T3:=i-1T3:=T3*nT3:=T3+jT4:=addr(C)TT1:=T3[T4]T5:=i-1T5:=T5*nT5:=T5+kT6:=addr(A)TT2:=T5[T6]T7:=k-1T7:=T7*nT7:=T7+jT8:=addr(B)TT3:=T7[T8]T9:=TT2*TT3T10:=TT1+TT2T1[T2]:=T10gotoLPkOTk:gotoLPjOTj:gotoLPiOTi:halt基本塊劃分與流程圖略考慮如下的基本塊：D：=B*CE：=A+BB：=B*CA：=E+D⑴構(gòu)造相應(yīng)的DAG；(2)對(duì)于所得的DAG，重建基本塊，以得到更有效的四元式序列。解：DAG圖見右，優(yōu)化后的代碼為D:=B*CE:=A+BB:=DA:=E+D49.I：=1readJ,KL:A：=K*IB：=J*IC:=A*BwriteCI：=I+1ifI<100gotoLhalt試對(duì)其中的循環(huán)進(jìn)行可能的優(yōu)化。解：優(yōu)化后的代碼為readJ,KA:=0B:=0I:=100*KL:A:=A+KB:=B+JC:=A*BwriteCifA<IgotoLhalt50.對(duì)于下面程序：Procedurep(x,y,z);beginy:=y+1;z:=z+x;end;{p}begina:=2;b:=3;p(a+b,a,a);