1.已知有限自動機如圖(1)以上狀態(tài)轉(zhuǎn)換圖表示的語言有什么特征(2)寫出其正規(guī)式.⑶構(gòu)造識別該語言的確定有限自動機DFA.［答案］(1)至少含有兩個連續(xù)的1的0，1組合⑵(0I1)*11(011)*01AAABABAABCABCACABCACACABC重新命名，令A(yù)B為B、ABC為C、AC為D。01AABBACCDCDDCDFA:2.試構(gòu)造與下列文法G[S]等價的無左遞歸文法。G[S]:SfSaINbIcN—SdINeIf［答案］S—SaINbIcNfNeISdIf消除NfNeISdIf左遞歸：N—SdN'IfN’③N‘feN'I8 ④代入S—SaINbIc：SfSaISdN'bIfN’bIc消除SfSaISdN'bIfN’bIc左遞歸:S—fN’bS’IcS’①S‘faS'IdN‘bS'I￡ ②.考慮下面文法G1:SfaIAI(T)LT,SIS消去G1的左遞歸。然后對每一個終結(jié)符，寫出不帶回溯的遞歸子程序。［答案］SfaIAI(T)TTT,T'f,ST'I￡Voidmatch(tokent){if(lookahead==t)lookahead=nexttoken;elseerror();}voidS(){if(lookahead==9a9)match('a));elseif(lookahead=='A')match(iA');elseif(lookahead==’('){match('(');T()；if(lookahead==9)9)match(')’)；elseerror();}elseerror();}voidT(){S();T’()；}voidT’(){if(lookahead==’,)){match(',’)；S()；T'();}}.設(shè)有以下文法：G[S]:S—eEfGh|gEtFSG|hF—SEc|cG|€G—Sh|€(1)求出該文法每一個非終結(jié)符的FOLLOW集。(2)它是LL(1)文法嗎？為什么？［答案］

FOLLOW(S)={#,e,g,h,c,f}FOLLOW(S)={#,e,g,h,c,f}FOLLOW(E)={f,c}FOLLOW(F)={e,g}FOLLOW(G)={h,f,c,e,g}FIRST(S)={e,g}FIRST(E)={h,c,e,g,s}FIRST(F)={c,e,g,s}FIRST(G)={e,g,s}efghc#SS—eEfGhS―gEE—FSGE—sSGE—FSGE—hE—FSGE—sSGFF—SEcF—sF—SEcF—sF—cGGG—ShG——sG——sG—ShG——sG——sG——s不是LL(1)文法.設(shè)有文法：G[S]:SfaBc|bABA—aAb|bB—b|s構(gòu)造其LL(1)分析表，并分析符號串baabbb是否是該文法的句子。［答案］FIRST(S)={a,b}FOLLOW(S)={#}FIRST(S)={a,b}FOLLOW(S)={#}FIRST(A)={a,b}FOLLOW(A)={b,#}FIRST(A)={a,b}FOLLOW(A)={b,#}步驟下推棧輸入串動作查分析表1#Sbaabbb#pop(S),push(bAB)S—bAB2#BAbbaabbb#pop(b),next(ip)匹配b3#BAaabbb#pop(A),push(aAb)A—aAb4#BbAaaabbb#pop(a),next(ip)匹配a5#BbAabbb#pop(A),push(aAb)A—aAb6#BbbAaabbb#pop(a),next(ip)匹配a7#BbbAbbb#pop(A),push(b)A—b8#Bbbbbbb#pop(b),next(ip)匹配b9#Bbbbb#pop(b),next(ip)匹配b10#Bbb#pop(b),next(ip)匹配b11#B#pop(B)B—￡

12##正確結(jié)束所以符號串baabbb是該文法的句子,下面文法是否是LL(1)文法，說明理由。S—AbA—a|B|sB—b|￡S—aSe|BB—bBe|CC—aCeId.對下列文法G:S'fSPTIiSfD(R)DfiRfR;PIP求出每個非終結(jié)符的FIRSTVT集和LASTVT集，并構(gòu)造算符優(yōu)先關(guān)系表。FIRSTVT(S,)FIRSTVT(S,)={(,i}FIRSTVT(P)={i,(}FIRSTVT(S)={(,i}LASTVT(S,)={)}LASTVT(P)={),i}LASTVT(S)={)}i:()#i>>>；*>*才(***)>才才#**FIRSTVT(D)={i}FIRSTVT(R)={;,i,(}FIRSTVT(D)={i}FIRSTVT(R)={;,i,(}LASTVT(D)={i}LASTVT(R)={;,),i}.有文法G［S］：S)VV)T|ViTT)F|T+FF))V*|((1)給出(+(i(的規(guī)范推導(dǎo)。(2)指出句型F+Fi(的短語，句柄，素短語。(3)G［S］是否為算符優(yōu)先文法？若是，給出(1)中句子的分析過程。［答案］(1)S=>V=>ViT=>ViF=>Vi(=>Ti(=>T+Fi(=>T+(i(=>F+(i(=>(+(i(⑵句型F+Fi(的語法樹：短語：F,F+F,(,F+Fi(句柄：F素短語：(,F+F(3)FIRSTVT和LASTVTFIRSTVTLASTVTSi,+,),(i,+,*,(Vi,+,),(i,+,*,(T+,),(+,(,*F),(,*,((2)算符優(yōu)先關(guān)系i+*()#i>*>市*>+>>>市*>*>>>>(>>>>)****#****

因為任意兩個終結(jié)符的優(yōu)先關(guān)系唯一，所以該文法為算符優(yōu)先文法。(3)(+(i(的分析過程步驟下推棧輸入串動作1#(+(i(##?(移進2#(+(i(#(>+歸約F今(3#F+(i(##?+移進4#F+(i(#+?(移進5#F+(i(#(4i歸約F)(6#F+Fi(#+4i歸約T今T+F7#Ti(##<i移進8#Ti(#i<(移進9#Ti(#(>#歸約F今(10#TiF#i>#歸約VfViT11#V##=#接受9.設(shè)文法G(S,)S，-AAfaAIb構(gòu)造識別文法G(S,)的所有活前綴的DFA.［答案］I0=closure({S’f.A})I0：S’f.AAf.aAAf.bI1=closure(goto(I0,A))I1：S’fA.I2=closure(goto(I0,a))I2：Afa.AAf.aAAf.bI3=closure(goto(I0,b))I3：Afb.I4=closure(goto(I2,A))I4：AfaA.closure(goto(I2,a))=I2closure(goto(I2,b))=I310.設(shè)文法G,試構(gòu)造G的LR(0)分析表G: (1)S-CC(2)C-cC(3)C-d［答案］拓廣為：S5-SS-CCC-cCC-dI0=closure({S5-.S})I0：S'-.SS-.CCC-.cCI1=closure(goto(I0,S))I1：S"S.I2=closure(goto(I0,C))I2：SY.CCfcCCfdI3=closure(goto(I0,c))I3：Cfc.CCf.cCCf.dI4=closure(goto(I0,d))I4：Cfd.I5=closure(goto(I2,C))I5：SfCC.closure(goto(I2,c))=I3closure(goto(I2,d))=I4I6=closure(goto(I3,C))I6：CfcC.closure(goto(I3,c))=I3closure(goto(I3,d))=I4

狀態(tài)actiongotocd#SC0S3S4121acc2S3S453S3S464r3r3r35r1r1r16r2r2r211.對于文法A-aA|a構(gòu)造SLR(1)分析表［答案］(1)A-aA⑵A-a拓廣為:A」AAfaAAfaI0=closure({A'f.A})A’f.AAf.aAAf.aI1=closure(goto(I0,A))A’fA.I2=closure(goto(I0,a))Afa.AAf.aAAf.aAfa.I3=closure(goto(I2,A))AfaA.closure(goto(I2,a))=I2

12.寫出下列各式的逆波蘭表示(1)-a-(b*c/(c-d)+(-b)*a)a=cAb=da<b+cAa>dVa+bWe［答案］關(guān)系運算符(<,>,=,〈,，,W)優(yōu)先級低于算術(shù)運算符(+,-,*,/,%)布爾運算符(A,V門)優(yōu)先級低于關(guān)系運算符auminusbc*cd-/buminusa*+-⑵ac=bd=A(3)abc+Wad>Aab+erV.翻譯算術(shù)表達式a*（-（b+c））為a）：一棵語法樹b）：后綴式。：三地址代碼［答案］a）語法樹:b）后綴式:abc+uminus*②三地址代碼:t1:=b+ct2:="t1t3:=a*t2.翻譯算術(shù)表達式(a+b)*(c+d)+(a+b+c)為a)：四元式防：三元式c)：間接三元式［答案］先寫出三地址代碼為：t1:=a+bt2:="t1t3:=c+dt4:=t2*t3t5:=a+bt6:=t5+ct7:=t4+t6a)：對應(yīng)的四元式為：(+,a,b,t1)(uminus,t1,-,t2)(+,c,d,t3)(*,t2,t3,t4)(+,a,b,t5)(+,t5,c,t6)(+,t4,t6,t7)b)：對應(yīng)的三元式為：(0)(+,a,b)(1)(uminus,(0),-)⑵(+,c,d)(3)(*,(1),(2))(4)(+,a,b)⑸(十,(4),c)(6)(+,(3),(5))c)：對應(yīng)的間接三元式為：(0)(+,a,b)(1)(uminus,(0),-)(2)(+,c,d)(3)(*,(1),(2))(4)(+,(0),c)(5)(+,(3),(4))間接碼表：(0)(1)(2)(3)(0)(4)(5).寫出語句的四元式形式WHILEa+b>3DO{a:=a+3*b;b:=a+e—*e［答案］100(+,a,b,t1)101(j>,t1,3,103)102(j,-,-,109)103(*,3,b,t2)104(+,a,t2,a)105(*,f,e,t3)106(+,a,e,t4)107(-,t4,t3,b)108(j,-,-,100)109.寫出條件語句四元式序列IFa>0THENx:=x+1ELSEx:=4*(x-1)［答案］100(j>,a,0,102)101(j,-,-,104)102(+,x,1遇)103(j,-,-,106)104(-,x,1,t1)105(*,4,t1,x)106.寫出語句的四元式表示W(wǎng)HILE(A<B)DOIF(C<D)THENX:=Y+Z;[答案]100(j<A,B,102)101(j,?,-,106)102gC,D,104)103(j,-,-,105)104(+,Y,Z,X)105(j,?,-,100)106.將下列賦值語句譯成三地址代碼。A,B是10*20的數(shù)組，每個元素占1個字節(jié)，C,D是一維數(shù)組，每個元素占4個字節(jié)A[ij]:=B[ij]+C[A[k,m]]+D[i+j][答案]t1:=i*20t1:=t1+jt2:=A-21;t3:=t2[t1]t4:=i*20t4:=t4+jt5:=B-21;t6:=t5[t4]t7:=k*20t7:=t7+mt8:=A-21t9:=t8[t7]t10:=4*t9t11:=C-4t12:=t11[t10]t13:=i+jt13:=4*t13t14:=D-4t15:=t14[t13]t16:=t6+t12〃A[ij]//B[ij]//A[k,m]〃C[A[k,m]]//D[i+j]t16:=t16+t15.試對以下基本塊B1應(yīng)用DAG進行優(yōu)化。B1: A:=B*CD:=B/CE:=A+DF:=E*2G:=B*CH:=G*GF:=H*GL:=FM:=L并就以下兩種情況分別寫出優(yōu)化后的四元式序列:(1)假設(shè)G、L、M在基本塊后面被引用；(2)假設(shè)只有L在基本塊后被引用。G:=B*CD:=B/CE:=G+D_L:=E*2H:=G*GL:=H*GM:=LA:=B*CD:=B/CE:=A+D_L:=E*2H:=A*AL:=H*A20.設(shè)有基本塊T1：=2T2：=10/T1T3：=S—RT4：=S+RA：=T2*T4B：=AT5：=S+RT6：=T3*T5B：=T6(1)畫出DAG圖；(2)假設(shè)基本塊出口時只有A,B還被引用，請寫出優(yōu)化后的四元序列T2：=5T3：=S—RT4：=S+RA：=T2*T4—B：=AB：=T3*T421.給出如下4元式序列:(1) J：=0;(2)L1:I:=0;(3)IFI<8gotoL3;(4)L2:A:=B+C;(5) B:=D*C;(6)L3:IFB=0gotoL4;WriteB;gotoL5;(9)L4:I:=I+1;IFI<8gotoL2;(11)L5:J:=J+1;IFJ<=3gotoL1;STOP①畫出上述4元式序列的程序流程圖G②求出G中各結(jié)點N的必經(jīng)結(jié)點集D(n)③求出G中的回邊與循環(huán)［答案］①1，2,3,4,6,7,9,11，13為入口語句,故基本塊為l,2/3,4/5,6,7/8,9/10,11/12,13,故可畫出程序流圖如下圖所示：

②D(l)={1},D(2)={1,2},D(3)={1,2,3},D(4)={1,2,4},D(5)={1,2,4,5},D(6)={1,2,4,6},D(7)={1,2,4,7},D(8)={1,2,4,7,8},即為所求必經(jīng)結(jié)點集。③回邊只有7->2,可知循環(huán)為234567。22.對下面的流圖，(1)求出流圖中各結(jié)點N的必經(jīng)結(jié)點集D(n),⑵求出流圖中的回