《编译原理复习》

1、1已知有限自动机如图0.1(1) 以上状态转换图表示的语言有什么特征(2) 写出其正规式.(3) 构造识别该语言的确定有限自动机DFA.答案(1)至少含有两个连续的1的0，1组合(0 I 1)*11 (0 I 1)*01AAABABAABCABCACABCACACABC重新命名，令 AB为B、ABC为C、AC为D01AABBACCDCDDCDFA:2.试构造与下列文法 GS等价的无左递归文法GS: S Sal Nb I cNSd I Ne I f答案S Sa I Nb I cNNe I Sd I f消除NNe I Sd I f左递归：NSdN I fN N eN I 代入 S Sa I Nb

2、I c：S Sa I SdN b fNb c消除 S Sa I SdN b I fN bl c 左递归:SfN bSl cS S aS dN bS &3考虑下面文法 G1:S a IAI (T)TT, S I S消去 G1 的左递归。然后对每一个终结符，写出不带回溯的递归子程 序。答案SaIAI (T)TSTT,ST I &Void match(token t) if (lookahead=t)lookahead=nexttoken;else error( ); void S( ) if (lookahead=a) match(a);else if (lookahead=A match( el

3、se if (lookahead=() match();T( );if (lookahead=) match();else error( ); else error( ); void T( ) S( );T(); void T() if (lookahead=, ) match( , );S( );T(); 4设有以下文法：GS: S eEfGh | gLFSG | hF SEc|cG |&G Sh | &(1) 求出该文法每一个非终结符的 FOLLOW 集。(2) 它是 LL(1) 文法吗？为什么？答案(1)FIRST(S)=e,gFIRST(E)=h, c,e,g, FIRST(F)=c,

4、e,g, &FIRST(G)=e,g, &FOLLOW(S)=#,e,g,h,c,fFOLLOW(E)=f,cFOLLOW(F)=e,gFOLLOW(G)=h,f,c,e,g(2)efghc#SSt eEfGhSTgEEt fsgEtSGEt fsgErhEr fsgEt sgFFt SEcFt SEcFt cGFtFtGG ShGsA ShGeGeGSGe不是LL(1)文法5.设有文法：GS:St aBc | bABA t aAb | bBt b | 构造其LL(1)分析表，并分析符号串baabbb是否是该文法的句子答案FIRST(S)=a,bFIRST(A)=a, b FOLLOW(S)=

5、# FOLLOW(A)=b,#FIRST(B)=b, &FOLLOW(B)=c,#abc#SSt aBcSt bABAA t aAbA t bBBt bBt Bt 步骤下推栈输入串动作查分析表1#Sbaabbb#pop(S),push(bAB)St bAB2# BAbbaabbb #pop(b), next(ip)匹配b3# BAaabbb#pop(A),push(aAb)A t aAb4# BbAaaabbb #pop(a), next(ip)匹配a5# BbAabbb#pop(A),push(aAb)A t aAb6# BbbAaabbb #pop(a), next(ip)匹配a7# Bb

6、bAbbb#pop(A),push(b)A t b8# Bbbbbbb #pop(b), next(ip)匹配b9# Bbbbb#pop(b), next(ip)匹配b10# Bbb#pop(b), next(ip)匹配b11# B#pop(B)Bt FIRSTVT(D) =iLASTVT(D) =i12#正确结束所以符号串baabbb是该文法的句子6.下面文法是否是LL(1)文法，说明理由(1)S Ab2 a | B| B b |(2) S aSe |BB bBe|CS a Ce | d7.对下列文法G:S SP S | iS D(R)D iR R; P | P求出每个非终结符的 FIRST

7、VT集和LASTVT集，并构造算符优先关系表。FIRSTVT(S ) =(, iFIRSTVT(P) =i,(LASTVT(S ) =)LASTVT(P) =),ii7()#i(#V=ViT=ViF=Vi(=T i(=T+F i(=T+( i(=F+( i(=(+( i(句型F+Fi(的语法树：T F/IX IT + F (IF短语：F, F+F, ( , F+Fi(句柄：F素短语：(，F+F(3) FIRSTVT 禾口 LASTVTFIRSTVTLASTVTSi,+,),(i,+,*,(Vi,+,),(i,+,*,(T+,),(+,(,*F),(,*,(2)算符优先关系i+*()#i+*()

8、#三因为任意两个终结符的优先关系唯一，所以该文法为算符优先文法(3)(+(i(的分析过程步骤下推栈输入串动作1#(+(i (# +归约F (3#F+(i (# +移进4#F+(i(#+ i归约F (6#F+Fi(#+ i归约T T+F7#Ti(# i移进8#Ti(#i #归约F (10#TiF#i #归约V ViT11#V#=#接受9.设文法G(S)SAA aA | b构造识别文法G(S的所有活前缀的DFA.答案10 = closure(Si .A)10 : S. AA. aAA . b11 = closure(goto(IO,A)I1: S A .12 = closure(goto(I0,a

9、)I2: A a . AA . aAA . b13 = closure(goto(I0,b)I3: A b .14 = closure(goto(I2,A) I4: A aA . closure(goto(I2,a)= I2 closure(goto(I2,b)= I310.设文法G,试构造G的LR(0)分析表G:(1)SCC(2) C cC(3) C d答案拓广为：S SS CCC cCC d10 = closure(S S)10 : S SS CCC cC11 = closure(goto(IO,S)I1 : SS I2 = closure(goto(I0,C)I2：SC .CC . cC

10、C . dI3 = closure(goto(I0,c)I3：C c .CC . cCC . d14 = closure(goto(I0,d) I4： C d .15 = closure(goto(I2,C) I5： SCC .closure(goto(I2,c)片 I3 closure(goto(I2,d)= I416 = closure(goto(I3,C) I6： C cC .closure(goto(I3,c)片 I3 closure(goto(I3,d)= I4状态actio ngotocd#SC0S3S4121acc2S3S453S3S464r3r3r35r1r1r16r2r2r2

11、11.对于文法 A - aA | a构造SLR(1)分析表答案(1) A aA(2) A a拓广为：At aA t aAA t a10 = closure(AT. a)I0: At. AAt. aAA t. a11 = closure(goto(IO,A)I1: AtA .12 = closure(goto(I0,a)I2: Ata . AAt. aAA t. aA ta .13 = closure(goto(I2,A)I3: AtaA .closure(goto(I2,a)= I2aFOLLOW(A)=#状态actio ngotoa#A0S211acc2S2r233r112.写出下列各式的逆

12、波兰表示(1) -a-(b*c/(c-d) + (-b)*a)(2) a=cA b=d(3) a d V a+bz e答案关系运算符（,=, ,工）优先级低于算术运算符（+, -, *, /, %）布尔运算符（A ,V厂）优先级低于关系运算符(1) a uminus bc*cd-/b uminus a*+-ac=bd=A(3) abc+w ad A ab+eV13.翻译算术表达式a*(- (b+c)为a)：一棵语法树b) :后缀式c) :三地址代码答案a) 语法树：Aa uminus+/b cb) 后缀式：a b c + uminus *c) 三地址代码：t1 := b + ct2 := -

13、t1 t3 := a * t214.翻译算术表达式-a+b)*(c+d) +(a+b+c)为a) ：四元式b) ：三元式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),-)(2

14、) (+,c,d)(3) (*, (1), (2)(4) (+,a,b)(5) (+, (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)15写出语句的四元式形式WHILE a+b 3 DO a:= a+3*b;b:= a + e -f*e答案100(+,a,b,t1)101(j,t1,3,103)102(j,-,-,109)103(*,

15、3,b,t2)104(+,a,t2,a)105(*,f,e,t3)106(+,a,e,t4)107(-,t4,t3,b)108(j,-,-,100)10916写出条件语句四元式序列IF a0 THEN x:=x+1 ELSE x:=4*( x- 1)答案100(j,a,0,102)101(j,-,-,104)102(+,x,1,x)103(j,-,-,106)104(-,x,1,t1)105(*,4,t1,x)10617写出语句的四元式表示WHILE(AB) DOIF(CD)THEN X:=Y+Z;答案100(j,A,B,102)101(j,-,-,106)102(j,C,D,104)103(

16、j,-,-,105)104(+,Y,Z,X)105(j,-,-,100)10618将下列赋值语句译成三地址代码。A,B是10*20的数组，每个元素占1个字节，C,D是一维数组，每个 元素占 4 个字节Ai,j :=Bi,j + CAk,m + Di+j答案 t1 := i * 20 t1 := t1+j t2 := A-21; t3 := t2t1 t4 := i*20 t4 := t4+j t5 := B-21; t6 := t5t4 t7 := k*20 t7 := t7+m t8 := A-21 t9 := t8t7 t10 := 4*t9 t11 := C-4 t12 := t11t1

17、0 t13 := i+j t13 := 4*t13 t14 := D-4 t15 := t14t13 t16:= t6 +t12 t16:= t16 + t15/Ai,j/Bi,j/Ak,m/CAk,m/Di+jt2t1 := t1619试对以下基本块 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 在基本块后被引用。(1) G:=B*CD:=B/CE:=G+D L:=E*2H:=G*GL:=H

18、*GM:=L(2) A:=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 * T4B: =AB:= T3 * T421. 给出如下4元式序列:(1)J:=0;(2) L1:I:=0;(3) IF I8 goto L3;(4) L2:

19、A:=B+C;(5) B:=D*C;(6) L3:IF B=0 goto L4;(7) Write B;(8) goto L5;(9) L4:I:=I+1;(10) IF I8 goto L2;(11) L5:J:=J+1;(12) IF J2，可知循环为234567。22. 对下面的流图，(1) 求出流图中各结点N的必经结点集D(n),(2) 求出流图中的回边，(3) 求出流图中的循环。答案(1) 流图中各结点N的必经结点集D(n),D(l) = 1, D(2) = 1,2, D(3) = 1,2,3, D(4)=1,2,3,4, D(5) = 1,2,5,D(6) = 1,2,5,6(2) 求出流图中的回边，5-2, 4-3(3) 求出流图中的循环：回边5-2对应的循环：2、5、3、4;回边4-3对应的循环：3、423. A、B是M*N的数组，试写出以下程序