陳火旺編譯原理(第三版)課后習(xí)題答案

第二章

P36-6

(1)

〃G)是0~9組成的數(shù)字串

(2)

最左推導(dǎo)：

N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>0\DD=>0nD=>0\21

NnNDnDDn3D=34

NnNDnNDD=DDD=5DD=56D=568

最右推導(dǎo)：

N=NZ)=N7=ND7=N27=ND27=N127=DI27=>0127

NnNOnN4nO4n34

NnNDnN8nND8nN68n068n568

P36-7

G(S)

Of1|3|5|7|9

N12|4|6|8|O

O-0|N

Sf0|A0

A->AD\N

P36-8

文法：

E^T]E+T\E-T

ITb|7"|7/b

…⑻li

最左推導(dǎo)：

EnE+TnT+TnF+T=i+Tni+T*Fni+F*Fni+i*Fni+i*i

E=>T=>T*F=>F*F=>z*F=>/*(￡)=>/*(￡+n=>/*(r+D=>/*(F+T)

=>z*(/+T)=>z*(Z+F)=>/*(/+/)

最右推導(dǎo):

E=>E4-7，=>￡+7'*F=>E+T*/=>F4-F*/=>￡+/*/=>7+/*/=>F+/*z=>/+/*/

E=>7,=>F*T=>F*F=>F*(E)=>F*(E+T)=>r*(E+F)=>F*(E+/)

=>F*(T+z)=>F*(F+i)=>F*(i+i)=>z*(/+/)

語法樹：/********************************

Fi

i

i+i*i

*****************/

P36-9

句子iiiei有兩個(gè)語法樹：

S=>iSeS=iSei=>USei=iiiei

SniSnUSeSnUSei=>iiiei

P36-10

/**************

S->TS\T

3⑸l()

***************/

P36-11

/***************

L1:

S->AC

A->aAb\ab

CcC\s

L2:

S^AB

A一|￡

B—>bBc\be

L3:

S^AB

AtaAb\s

BTaBb|￡

L4:

SfA|3

Af0Al|e

8-160|A

***************/

第三章習(xí)題參考答案

P64-7

⑴

1(011)101

1

確定化:

01

(X)6(1,2.3)

1

11

P64-8

(1)

⑴o)'oi

(2)

(l|2|3|4|5|6|7|8|9X0|l|2|3|4|5|6|7|8|9)*(0|5)|(0|5)

(3)

0^1(0110^1)*11*0(01103lf

P64-12

(a)

a

確定化:

ab

(0}(0.1)(1)

{o.D(0,1){1}

Hl{0}Q

000

給狀態(tài)編號(hào):

ab

012

112

203

333

最小化：

{0,1},{2,3}

{0,1}.={1}{0,1}^=(2)

{2,3},={0,3}{2,3〃=(3}

{0,1},{2},{3}

a

b

(b)

已經(jīng)確定化了，進(jìn)行最小化

最小化：

{{0,1},{2}3,4,5}}

(O,l}fl={l}{0,1}.={2,4}

{2,3,4,5}.={1,3,0,5}{2,3,4,5},={2,3,4,5}

{2,4},={1,0}{2,4}〃={3,5}

{3,5}“={3,5}{3,5}b={2,4}

{{0,1},{2,4},{3,5})

{0」}“二{1}{0,1}產(chǎn){2,4}

{2,4}“={1,0}{2,4}〃={3,5}

{3,5}“={3,5}{3,5}產(chǎn){2,4}

P64-14

o

(2):

(50)

確定化:

01

(X,1,Y)H.Y)(2}

(1.Y){1.Y){2}

12)11,Y)0

00

給狀態(tài)編號(hào):

01

012

112

213

333

0

最小化：

{0,1},{2,3}

{0,1}0={1}(0,1},=(2)

{2,3}。={1,3}{2,3},={3}

{0,1},{2},{3}

八

。V

0

第四章

P81-1

(1)按照T,S的順序消除左遞歸

G<S)

Sf。|八|(7)

TfST'

r-?,sri￡

遞歸子程序：

procedureS;

begin

ifsym='a'orsym='

thenabvance

eIseifsym=,('

thenbegin

advance;!;

ifsym=')'thenadvance;

eIseerror;

end

eIseerro-

end;

procedureT;

begin

s；r

end;

procedureT';

begin

ifsym=",

thenbegin

advance;

s；r

end

end;

其中：

sym:是輸入串指針I(yè)P所指的符號(hào)

advance:是把IP調(diào)至下一個(gè)輸入符號(hào)

error:是出錯(cuò)診察程序

(2)

FIRST(S)={a<,(}

FIRST(T)={a,",()

FIRST(F)={,,

FOLLOW(S)={),,,#)

FOLLOW(T)={))

FOLLOW(T,)={))

預(yù)測(cè)分析表

A

a()f#

sStaS—As-⑺

TTfSTTfSTTfST

VTTfST

是LL⑴文法

P81-2

文法：

ETTE，

E'->+E|￡

TtFT'

T'fT|￡

FTPF'

F'f*F'|E

Pf(E)|〃|bE

(D

FIRST(E)={(,a,b/)

FIRST(E')={+,E}

FIRST(T)={(,a,b/}

FIRST(T')={Ca,b/,E)

FIRST(F)={(,a,b/J

FIRST(F')={*E}

FIRST(P)={(,a,b/)

FOLLOW(E)={#,)}

FOLLOW(E')={#,)}

FOLLOW(T)=[+,),#)

FOLLOW(T')={+,),#)

FOLLOW(F)=1(,arb,\+,),#)

FOLLOW(F')={Ca,b,z',+.),#)

FOLLOW(P)={*(,a,b「，+,),#)

(2)

考慮下列產(chǎn)生式：

V^T\￡

尸->*尸]￡

PF(E)I人mg

FIRST(+E)HFIRST(8)={+}A{E}=0

FIRST(+E)DFOLLOW(E')=[?)A[#,))=0

FIRST(T)AFIRSTCt)={(,a,b<}n(E}=0

FIRST(T)AFOLLOW(T')={(,a,b/)F{+,),#}=0

FIRST(*F')AFIRSTC￡)={*}F{E)=0

FIRST(*F')PIFOLLOW(F')={*}Cl{(,a,b/，+,).#}二Q

FIRST((E))nFIRST(a)CIFIRST(b)AFIRSK)=Q

所以,該文法式LL⑴文法.

(3)

人

+*()ab#

EEfTE'ETTE'ETTE'ETTE'

E'￡一+￡E'T￡E'f￡

TTfFTTTFVTTFTTfFT

T'TT￡TITTTTTTTTTfTT

FFTPPFTPF'FTPF'FTPF'

F'F'T￡FFFF'FT2F'f￡

PP-3)PfaPTbP->A

(4)

procedureE;

begin

ifsym='('orsym='a'orsym='b'orsym=

thenbeginT;E'end

eIseerror

end

procedureE';

begin

ifsym=,+

thenbeginadvance;匚end

elseifsym<>')'andsym<>'#'thenerror

end

procedureT;

begin

ifsym=,('orsym="a'orsym="b'orsym=

thenbeginF;T'end

eIseerror

end

procedureT';

begin

ifsym='('orsym='a'orsym='b'orsym=

thenT

eIseifsym=,*'thenerror

end

procedureF;

begin

ifsym="('orsym='a'orsym='b'orsym二

thenbeginP;F'end

eIseerror

end

procedureF';

begin

ifsym='*'

thenbeginadvance;F'end

end

procedureP;

begin

ifsym='a'orsym='b'orsym=

thenadvance

eIseifsym='('then

begin

advance;E;

ifsym=')'thenadvance

eIseerror

end

elseerror

end;

P81-3

/***************

(D是，滿足三個(gè)條件。

(2)不是，對(duì)于A不滿足條件3。

(3)不是，A、B均不滿足條件3。

(4)是，滿足三個(gè)條件。

***************/

第五章

P133-1

石=石+7=七+7*尸

短語：E+T*F,T*F,

直接短語：T*F

句柄：T*F

P133-2

文法：

Sf。|八|⑺

TfT,S|S

(1)

最左推導(dǎo)：

S=>(T)=>(T,S)=(S,S)=>(a,S)=>(。，⑺)=(a,(T,S))=>(a,(S,S))=(a,(a,S))=(a,(a,a))

sn(「s)=(s,s)=((r).s)=((7；s),s)=((T,s,s),s)=((s,s,s),s)n(((r),s,s),s)

n(((7；S),S,S)),S)=(((S.S),S,S),S)n(((a,S),S,S),S)n(((a,a),S,S),S)

=>(((a,a),A,S),S)=(((&“)/,⑺),S)=(((a,a)A(S)),S)=>(((，M)J,(a)),S)

=(((a,a),人,(a)),a)

最右推導(dǎo)：

S=>(7)=(T,S)=>(7,⑺)=>(T,(T,S))=>(T,(7?)n(7;(SM))=>(T,(a,a))

n(S,(a,a))n(a,(a,a))

Sn(T,S)=>(T,a)=>(S,a)=>((T),a)=>((T,S),a)=>((T,⑺),a)=>((7,(S)),a)

=>((r,(a))M)=((T,S,(a)),a)=>((T,3(a)),a)=>((SJ,(〃)),〃)=((⑺,人，⑷),a)

=(((r,S),A,(a)),4)n(((TM),A,(a)),4)n(((SM),A,(a))M)=>(((a,4)J,(〃))M)

(2)

(((a.a)/,(a)),a)

(((S,a)：(a)),a)

(((T,a),\(a)),a)

(((LS)/,(a)),a)

((02<,(a)),a)

((§/，(a)),a)

((T.\(a)),a)

((LS.(a)),a)

((T,(a)),a)

((T,(S)),a)

((T,(T)),a)

((LS).a)

(CD.a)

(S.a)

(L_S)

(T)

S

“移進(jìn)-歸約”過程:

步要1棧輸入串動(dòng)作

0#(((a,a),*,(a)),a)#預(yù)備

1#(((a,a),",(a)),a)#進(jìn)

2#(((a.a)/,(a)),a)#進(jìn)

3#(((a.a),(a)),a)#進(jìn)

4#(((a.a),",(a)),a)#進(jìn)

5#(((S,aX,(a)),a)#歸

6#(((T,a)/,(a)),a)#歸

7#(((T,a),",(a)),a)#進(jìn)

8#(((T,a),\(a)),a)#進(jìn)

9#(((T,S)/,(a)),a)#歸

10#(((T(a)),a)#歸

11#(((T)—，(a)),a)#進(jìn)

12#((S(a)),a)#歸

13#((T:(a)),a)#歸

14#((T,工(a))a)#進(jìn)

15#((T/.(a)),a)#進(jìn)

16#((T.S,(a)),a)#歸

17#((T,(a)),a)#歸

18#((T.(a)),a)#進(jìn)

19#((T,(a)),a)#進(jìn)

20#((T.(a)),a)#進(jìn)

21#((T.(S)),a)#歸

22#((T,(T)),a)#歸

23#((T.(T)),a)#進(jìn)

24#((T,S),a)#歸

25#((T),a)#歸

26#((T),a)#進(jìn)

27#(S,a)#歸

28#(T,a)#歸

29#(T.a)#進(jìn)

30#(T,a)#進(jìn)

31#(T,S)#歸

32#(T)#歸

33#(T)#進(jìn)

34#S#歸

P133-3

(1)

FIRSTVT(S)={a,()

FIRSTVT(T)={,,a/，(}

LASTVT(S)={a,\)}

LASTVT(T)={,,a/,))

(2)

a/V()

a>>

人

>>

(<<<=<

)>>

?<<<>>

Ge是算符文法，并且是算符優(yōu)先文法

⑶優(yōu)先函數(shù)

A

a()t

f44244

g55523

(4)

棧輸入字符串動(dòng)作

#(a,(a,a))#預(yù)備

#(a,(a,a))#進(jìn)

#(a,(a,a))#進(jìn)

#(t,(a,a))#歸

#(t.(a.a))#進(jìn)

#(t,(a,a))#進(jìn)

#(t,(a,a))#進(jìn)

#(t,(t,a))#歸

#(t.(t,a))#進(jìn)

#(t,(t.a))#進(jìn)

#(t,(t,s))#歸

#(t,(t))#歸

#(t,(t))#進(jìn)

#(t,s)#歸

#(t)#歸

#(t)#進(jìn)

#s#歸

success

P134-5

(1)

OS'—SLS'fS-2.AS3.S->AS

4.S^AS-5.ST?b6.Sfb-7.AfSA

8.A-^S-A9.A—>S4-10.A^-a11.A-^a-

⑵

確定化:

SAab

[0,2,5,7,10)(1,2,5,7,8,10{2,3,5,7,10}{11}{6)

1

(1,2,5,7,8,10(2,5,7,8,10){2,3.5,7,9,10{11}(6)

}J

{2,3,5,7.10)(2.4.5,7.8,1012,3,5,7,101{11}{6J

1

{2,5,7,8,10)(2,5,7,8,101[2,3,5,7,9,10{11}(6}

)

{2,3,5,7,9,10(2,4,5,7.8,10{2,3,5,7,10)(11)(6)

}1

{2,4,5,7,8,10(2,5,7,8,10)(2,3,5,7,9,10(111(6)

))

{11}04)QQ

(6)0QQQ

A

3S-S?5:AfSA6:A^SA

AfS->ASSfAS

A^SAS，bS—AS

AfaA^SAS-b

S—>,ASA—>aAfSA

-S_T，b------Afa

sA

DFA

構(gòu)造LR(O)項(xiàng)目集規(guī)范族也可以用GO函數(shù)來計(jì)算得到。所得到的項(xiàng)目集規(guī)范族與上圖中的

項(xiàng)目集一樣:

IQ-[S'―>,S—>?AS,S->,b,A—>,SA,A—>}

GO(/yja)={A—>ci?}—

GO(/0,b)={S一>Z7-}=/2

=

GO(/0,S){S'-S?,A―>S,A,A―>,A―>,S—>,AS,S―>,/?!-/3

GO(70,A)={S—>AS,S—>?AS,STb,A—>S4,A—>??}=/4

=

GO(73,a){yA—>67?}=/[

G0(/3,b)=(SZ?-}=/2

=

GO(73,S){A―>S,A,S—>?AS,S->,b,A—>,SA,A—=

=

GO(Z3,A)={A—>5A,,S—>A,S,S—>-AStS—>7?,A—>'SA,A―>}/6

GO(/4,a)={A—>6Z-J=/j

G0(Z4,b)={S—>Z?-l=/2

G0(/4,S)={S—AS?，AfS?A,Sf-AS,Sfb,A^-a]=I1

==

GO(/4,A){S—>A*S,S—>,AS,S—>,byA―A—>,tz}/4

GO(/j,a)={A—>a?}-/)

GO(75,b)={S—>-}=I2

GO(I,S)={A—>S-A,S—>'AS,S―>,b,A.—>'SA,A.—>}=/,

G0(/5,A)={4-SA?，STAS,SfAS,Sib,AfSA,A^-a]=I(J

==

GO(/6,a){yV—>Cl?}/1

G0(/6,b)={SZ?-)=/2

==

GO(/6,S){S—>AS?,A—>S,A,S―>?AS,S->'b,A—A—>,6Z1^7

=

GO(/6,A)-{S―>A,S,S—>,AS,S—》，b,A—>,SA,A->,tz)/4

GO(Z7,a)={—>a?}=/1

GO([7,b)={S—>Z??}二，2

=

G0(，7，S){A—>S*A,S—>,S—>'byA―A―><z}—15

==

GO(/7,A){A—>SA?,S—>A，S,S—>,AS,S—>,/?,A―>,iSA,A->}/6

項(xiàng)目集規(guī)范族為c={/1,I2,Z3,74,/5,/6,/7)

(3)不是SLR文法

狀態(tài)3,6,7有移進(jìn)歸約沖突

狀態(tài)3：FOLLOW(S5)=[#)不包含a,b

狀態(tài)6：F0LL0W(S)={#,a,b}包含a,b,；移進(jìn)歸約沖突無法消解

狀態(tài)7：FOLLOW(A)={a,b}包含a,b；移進(jìn)歸約沖突消解

所以不是SLR文法。

(4)構(gòu)造例如LR⑴項(xiàng)目集規(guī)范族

見下圖：

對(duì)于狀態(tài)5,因?yàn)榘?xiàng)目[A->AS-所以遇到搜索符號(hào)a或b時(shí),應(yīng)該用ATAS

歸約。又因?yàn)闋顟B(tài)5包含項(xiàng)目[4f?〃a/b],所以遇到搜索符號(hào)a時(shí)，應(yīng)該移進(jìn)。因此

存在“移進(jìn)-歸約”矛盾，所以這個(gè)文法不是LR⑴文法。

b/

A

S

A

6：9：

AfSAa/bSTAS?a/b

A->SAa/bASAa/b

A―>,Cia/bAtSAa/b

A—>4a/b

STASa/b

STASa/b

S3ba/b

Ab

2：7：

S—>A,S#，a/bSfAS,#,"

S->?AS擢a/bA->S?Aa/b

ST?b#/a/bA->SAa/b

A—>'SAci/bA^-aa/b

10：

sb

Sib，a/b

A

5：

第六章

P164-5

(1)

EfE1+T{if=int)and=int)

then:=int

eIse:=reaI)

EfT{:=1

—>(:=reaI)

T—>num[:=int)

(2)

P164-7

SfL1|L2{:=+2￡27^)l

S->L{:=)

LfLIB{:=2*+;

：=+1)

L->B{:=;

：=1)

B70l：=O}

Bf1{:=1}

***********************/

第七章

P217-1

a*(_b+c)ab@c+*

a+h*(c+d/e)ahcdft/+*+

-a+b*(-c+d)a回bc@d+*+

—iAv―i(Cv—I。)A―CD~~?v—iv

(AABUCVO)/\BAC@￡)Vv

(Av8)A(Cv-i￡)AE)ABVCD@^AVA

if(x+y)*z=0then(a+b)TceIseaTbTcxy+z*O=ab+cTabcTT￥

或xy+z*O=P1jezab+cTP2jumpabcTT

P217-3

-(a+b)*(c+d)-(a+b+c)的

三元式序列：

(1)+,a,b

(2)(1),-

(3)+,c,d

(4)*.(2),(3)

(5)+,a,b

(6)+,(5),c

⑺(4),(6)

間接三元式序列：

三元式表；

(1)+,a,b

(2)(1),-

(3)+,c,d

(4)*,(2),(3)

(5)+,(1),c

(6)(4).⑸

間接碼表：

(1)

(2)

(3)

(4)

(1)

(5)

(6)

四元式序列：

+

(1),a,b,Tx

(2)@,幾T2

(3)+,c,d,

(4)*,T2,T、,TA

(5)+,a,b,T5

(6)+,T5,c,T6

⑺-1T4,r6,T7

P218-4

自下而上分析過程中把賦值句翻譯成四元式的步驟:A:=B*(-C+D)

步驟輸入串棧PLACE四元式

(1)A:=B*(-C+D)

(2):=B*(-C+D)iA

(3)B*(-C+D)i:=A-

(4)*(-C+D)i:=iA-B

(5)*(-C+D)i:=EA-B

(6)*(-C+D)i:=EA-B

(7)(-C+D)i:二E*A-B-

(8)-C+D)i:=E*(A-B—

(9)C+D)i:=E*(-A-B---

(10)+D)i:=E*(-iA-B——C

(11)+D)i:=E*(-EA-B——C(@,C,-T)

(12)+D)i:=E*(EA-B-T]

(13)D)i:=E*(E+A-B—乙-

(14))i:=E*(E+iA-B—1-D

(15))i:=E*(E+EA-B—-DT(,D,T))

(16))i:=E(EA-B—T

2

(17)i:=E*(E)A-B-T-

2

(18)i:=E+EA-B-7^(*B,T.71)

23

(19)i:=EA，（：=.r「A）

(20)A

產(chǎn)生的四元式：

便,c,一y

D,T2)

(*B,T、,T)

(：=,Ty~,A)

P218-5

/****************

設(shè)A：10*20,B、C、D：20,寬度為w=4則

T1:=i*20

T1:=T1+j

T2:=A-84

T3:=4*T1

Tn:=T2[T3]〃這一步是多余的

T4:=i+j

T5:=B-4

T6:=4*T4

T7:=T5[T6]

T8:=i*20

T8:=T8+j

T9:=A-84

T10:=4*T8

T11:=T9[T10]

T12:=i+j

T13:=D-4

T14:=4*T12

T15:=T13[T14]

T16:=T11+T15

T17:=C-4

T18:=4*T16

T19:=T17[T18]

T20:=T7+T19

Tn:=T20

******************/

P218-6

100.(jnz,A,0)

101.(j,一，102)

102.(jnz,B.104)

103.(j,0)

104.(jnz,C,103)

105.(j,106)

106.(jnz,D,104)一假鏈鏈?zhǔn)?/p>

107.(j,一，100)一真鏈鏈?zhǔn)?/p>

假鏈：(106,104,103}

真鏈：(107,100}

P218-7

100.(j<A,C,102)

101.(j,-，0)

102.(j<,B.D,104)

103.(j,101)

104.(j=A,T,106)

105.(j,109)

106.(+.C,T,T1)

107.(:=T1,C)

108.(j,100)

109.(jW,A.D,111)

110.(j,100)

111.(+,A,2,T2)

112.(:=T2,A)

113.(j,109)

114.(j,-100)

P219-12

/********************

⑴

MAXINT-5

MAXINT-4

MAXINT-3

MAXINT-2

MAXINT1

MAXINT

⑵翻譯模式

方法1:

forE1:=E2toE3doS

S->FdoMS)

FfFor/:=toE2

I—>id

MT￡

S—>FdoMS1{backpatch,nextquad);

backpatch,;

emit'+'1);

emit(*]</7；

??

,t

)

F—>ForI:=EjtoE2(:=makeIist(nextquad);

emit(UX'*.0*);

emit二'；

:=makeIist(nextquad);

emit('J,-,-,-')；

一?

?1

,一

?9?

)

I—>id{p:=lookup;

ifp<>niIthen

:二P

elseerror}

MT￡{:=nextquad)

方法2：

STforid:=E1toE2doS1

STFS1

FTforid:=E1toE2d