编译原理复习

1.已知有限自动机如图(1)以上状态转换图表示的语言有什么特征(2)写出其正规式.⑶构造识别该语言的确定有限自动机DFA.［答案］(1)至少含有两个连续的1的0，1组合⑵(0I1)*11(011)*01AAABABAABCABCACABCACACABC重新命名，令AB为B、ABC为C、AC为D。01AABBACCDCDDCDFA:2.试构造与下列文法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的左递归。然后对每一个终结符，写出不带回溯的递归子程序。［答案］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'();}}.设有以下文法：G[S]:S—eEfGh|gEtFSG|hF—SEc|cG|€G—Sh|€(1)求出该文法每一个非终结符的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)文法.设有文法：G[S]:SfaBc|bABA—aAb|bB—b|s构造其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##正确结束所以符号串baabbb是该文法的句子,下面文法是否是LL(1)文法，说明理由。S—AbA—a|B|sB—b|£S—aSe|BB—bBe|CC—aCeId.对下列文法G:S'fSPTIiSfD(R)DfiRfR;PIP求出每个非终结符的FIRSTVT集和LASTVT集，并构造算符优先关系表。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(的规范推导。(2)指出句型F+Fi(的短语，句柄，素短语。(3)G［S］是否为算符优先文法？若是，给出(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)算符优先关系i+*()#i>*>市*>+>>>市*>*>>>>(>>>>)****#****

因为任意两个终结符的优先关系唯一，所以该文法为算符优先文法。(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.设文法G(S,)S，-AAfaAIb构造识别文法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.设文法G,试构造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

状态actiongotocd#SC0S3S4121acc2S3S453S3S464r3r3r35r1r1r16r2r2r211.对于文法A-aA|a构造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［答案］关系运算符(<,>,=,〈,，,W)优先级低于算术运算符(+,-,*,/,%)布尔运算符(A,V门)优先级低于关系运算符auminusbc*cd-/buminusa*+-⑵ac=bd=A(3)abc+Wad>Aab+erV.翻译算术表达式a*（-（b+c））为a）：一棵语法树b）：后缀式。：三地址代码［答案］a）语法树:b）后缀式:abc+uminus*②三地址代码:t1:=b+ct2:="t1t3:=a*t2.翻译算术表达式(a+b)*(c+d)+(a+b+c)为a)：四元式防：三元式c)：间接三元式［答案］先写出三地址代码为：t1:=a+bt2:="t1t3:=c+dt4:=t2*t3t5:=a+bt6:=t5+ct7:=t4+t6a)：对应的四元式为：(+,a,b,t1)(uminus,t1,-,t2)(+,c,d,t3)(*,t2,t3,t4)(+,a,b,t5)(+,t5,c,t6)(+,t4,t6,t7)b)：对应的三元式为：(0)(+,a,b)(1)(uminus,(0),-)⑵(+,c,d)(3)(*,(1),(2))(4)(+,a,b)⑸(十,(4),c)(6)(+,(3),(5))c)：对应的间接三元式为：(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.写出语句的四元式表示WHILE(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的数组，每个元素占1个字节，C,D是一维数组，每个元素占4个字节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应用DAG进行优化。B1: A:=B*CD:=B/CE:=A+DF:=E*2G:=B*CH:=G*GF:=H*GL:=FM:=L并就以下两种情况分别写出优化后的四元式序列:(1)假设G、L、M在基本块后面被引用；(2)假设只有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.设有基本块T1：=2T2：=10/T1T3：=S—RT4：=S+RA：=T2*T4B：=AT5：=S+RT6：=T3*T5B：=T6(1)画出DAG图；(2)假设基本块出口时只有A,B还被引用，请写出优化后的四元序列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中各结点N的必经结点集D(n)③求出G中的回边与循环［答案］①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},即为所求必经结点集。③回边只有7->2,可知循环为234567。22.对下面的流图，(1)求出流图中各结点N的必经结点集D(n),⑵求出流图中的回