编译作业及答案

1、7-2 给定文法 G：S?Aa|Ab|cA?Ad|Se|f请消除文法的左递归，并提取公共左因子。解：（ 1）消除文法G 的产生式直接左递归。 TOC o 1-5 h z A SeA | fAAdA| ?（ 2 ）消除间接左递归：按排序（按算法 i=2,j=1 时）将 S 的产生式代入有A AaeA | AbeA | ceA | fA（3）消除的直接左递归有A ceAA | fAAAaeAA” | beAA | ?（ 4）对S 的产生式提公因子有AAB|cB |a|b（5）最后，文法G提取公因子，消除左递归后的产生式由, ，和组成，无多余的产生式。（ 6）若按排序，得到的产生式组合是另外的形式，

2、但它们是等价的文法。7-3 给定文法G：S?（L）|aL?L， S|S消除文法G 的左递归，并写出递归下降分析的相应递归过程。解：消除左递归后，得文法G:(L) | aL SLL f, SL | ?递归下降过程：procedure advance( )beginsym =getchar( )endprocedure S;beginif sym =a thenadvance( )else ifsym =( thenbeginadvance( )elseL( );if sym =) then advance( ) error()endelseerror()endprocudure L;begin

3、S;L;endprocudure L;beginif sym =, then beginadvance( )S;Lendend7-5 解:G (S) : S ASS-AS | ?ABAA +BA|?BbS* | aFIRST集和 FOLLOW!FIRST FOLLOWS SAABb, a ：?) b, a + , ? b, a#, *#, *#,*,：#, *,:#,*,:,十预测分析表a:SS ASSSfASAABA BAB a0+BAbS ASK BAB bS*Sf?(3)因为预测分析表无多重定义入口，所以G是LL (1)文法7-6 解: 对习题7-3的文法G消除左递归后，得文法 G:S

4、-(L) | aL SLL 7 ,SL|FIRST 集和 FOLLOW!FIRSTFOLLOWS(,a),#L(,a)L,?)预测分析表()a,#SS- (L)Sf aLL-SLL-SLLL-)L一,SL因为预测分析表无多重定义入口，所以文法G是LL (1)文法。8-1已知文法G:S?ABA?Ab|bBB?a|Sb(1)写出bBABb的规范推导。(2)画出bBABb的语法树。(3)求bBABb的短语、直接短语、句柄和最左素短语。解：(1)规范规范推导(最右推导)最右推导S?AB?ASb?AABb?bBABb(2)语法树(推导树)(3)短语 bB, AB, ABb, bBABb直接短语bB, A

5、B句柄bB最左素短语bB8-2已知文法G:S?SbF|FF?FaP|PP?c（1）试证明FaPbc是文法G的一个句型。（2）画出FaPbc 的语法树。（3）求出FaPbc 的短语、直接短语、句柄和最左素短语。解：（ 1）因为存在推导S?SbF?FbF?FaPbF?FaPbP?FaPbc所以FaPbc是文法G的一个句型。（ 2）语法树（ 3）短语FaP, c, FaPbc直接短语 FaP, c句柄 FaP最左素短语FaP8-3已知文法G：S?AS|bA?SA|a（ 1）列出 G 的 LR（ 0 ）项目集规范族。（ 2）这个文法是LR（ 0）文法吗？是SLR（ 1 ）文法吗？若是，请构造出相应的分

6、析表。解：拓广文法7S7ASf b7 SA7aLR( 0)项目集规范族I o=closureSS I1=GO(Io,S)I 2=GO(Io,A)I 3=GO(I o,b)I o：S f SS -S-S - A- SS - b -A - ASA-S - AS f ASA - bAf SAS f bZ - SAAaA f SAZ aS f ASA f aSf bI4=GO(Io,a)I5=GO(I1,A)I6=GO(I1,S)I7=GO(I2,S)A- a ASA-AfS-AS - AS-S -A- SA f SAA - S AS f ASA f bA f SASf bS f ASA f aAf

7、SAS f bS f ASAf aS f GO(I1,b)=I3GO(I2,a)=I4 GO(I1,a)=I4 GO(I2,A)=I2 GO(I2,b)=I3FOLLOW(S)=a, b, #FOLLOW(A)=a, b状态5在输入a时有&和入的移进归约矛盾。状态 5 在输入 b 时有S3 和 r 3 的移进归约矛盾。状态7在输入a时有S4和ri的移进归约矛盾。状态7在输入b时有S3和ri的移进归约矛盾。 文法G既不是LR (0)文法，也不是 SLR (1)文法。8-7设有文法G：S?AB B?cBd|cd A?aAb|ab它是否为SLR (1)文法？若是，请构造相应的 SLR (1)分析表

8、解： fSFOLLOW(S)=$fABFOLLOW(A尸b,cfcBdFOLLOW(B)=d,$Sf cd faAb fab I o=closureS10 sf SI 4=GO(I2,B)I9=GO(I5,d)S ABS -AB-B f cd A aAbI 5 = GO(I 2,c)I 10=GO(I6,b)A abB fc BdA faAbI 1=GO(I0,S)B f cBdIn=GO(I8,d)SfS-B f cBdB fcBdI2=GO(0,A)B - c dSA-BI 6=GO(I3,A)B cBdAfaA bB cdGO(I 3,a)=I 3l3=GO(l0,a)I 7=GO(I3

9、,b)Aa AbAfab Aa bI 8=GO(I5,B)A aAbBfcB dA abGO(I 5,c)=I 5上述状态集没有移进一归约冲突，(a)是SLR文法，分析表如下:0S312S53S3 S7acc4567891011r 1S5 SoS105 r 5S11334422SAB1 24688-9设有文法GP?P (F) |FF?abFda|a(1)试求每个非终结符的FIRSTVT集和 LASTVTSo(2)试构造文法G的优先关系表。解：( 1) FIRSTVT(P)=a,(LASTVT(P)=a,)FIRSTVT(F)=aLASTVT(F)=a( 2)优先关系表：9-4对下列翻译方案：S

10、?PSprint “ 1”S?PQprint “ 2”P?a print “ 3”Q?bR print “ 4”Q?dQ print “5”R?c print “ 6”当输入串为“aaadb ”时，翻译结果是什么？解：结果为。9-5试写出语句if CB do x:=y+2*z 解：Ei-CwhileE-ABEi-E*EG-E+EZi:=E 2Sf AS- WSS- if E i thenSi9-69-7 试写出语句for i:=i to N do Si其语义为i:=i;again : if i?N then beginS i;i:=i+i;goto againend原文法Sf for i:=i

11、 to N do S改写为的翻译过程。Ei - F=10iW - code=102E - F=103Ei - VAL=TE2 - VAL=TA - chain=0S i - chain=0Si - chain=i03S - chain=i0i(i00)(,A,B,i04)(i03)(j,-,-,0)(i04)(*,2,(i05)(+,y,T i,T2)(i06)(:=,T 2,-,x)(i07)(j,-,-,i02)的语义子程序。Ff for i:=i to N doSf F SiFf for i:=1 to N do := entry(i);emit(:=, 1,-);:=ip;: if B

12、 goto 0:goto again原文法Sf repeat Si until B改写为S f R BRf P Si untilP frepeat翻译方案：P frepeat:=ipRf P Si untilbackpatch,ip);：二Sf R B backpatch,;：二10-1有如下三地址代码序列：回边(1)read x(10)B:=y+j7-4(2)read y(11)if A=B goto9-1(6)(3)if xB goto(16)(5)read j(14)write B(6)if ij goto(9)(15)goto (9)A:=i+1(16)A:=x*j(8)goto (1

13、0)(17)goto(10)(9)A:=x*j(a)请划分基本块，构造程序流图。(b)根据必经结点找出回边及由回边组成的循环。解：(a)基本块程序流图B (1)(3)及(4)R (5)B4 (6)住(7)(8)R (9)B (10)(11)R (12)(13)B9 (14)(15)Bio(16)(17)(b)必经结点D(1)=1 D(4)=1,3,4D(7)=1,3,4,7 D(10)=1,3,4,7,8,10D(2)=1,2D(5)=1,3,4,5D(8)=1,3,4,7,8D(3)=1,3D(6)=1,3,4,6D(9)=1,3,4,7,8,9由回边7 - 4组成的循环7,4,5,6,8,1010-2试将下面的程序段划分为基本块，构造其程序流图，并进行优化(1) C:=100 (2) A:=0 (3) B:=10 (4) A:=A+B (5) if B C then goto ( 8) (6) B:=B+10 goto (4) (8) write A 解： (1)基本块(2)程序流图B 1 (1)(3) B 2 (4)(5) B 3 (6)B 4 (8) 10-7 对下列中间代码：(3)优化结果 B:=10 A:=A+8if B 100 then goto (8)B