编译原理-第三版-课后答案

编译原理-第三版-课后答案

编译原理课后题答案

第二章

P36-6

(1)

是0~9组成的数字串

(2)

最左推导：

N=ND=NDD=NDDD=DDDD=ODDD=O1DD=012D=0127

N=ND二DD二3D二34

N=ND—NDD=DDD=5DD=56D二568

最右推导：

N二ND二N7二ND7二N27二ND27二N127二D127二0127

N=ND=N4=D4=34

N=ND二N8=ND8二N68二D68二568

P36-7

G(S)

编译原理笫三版课后答案

0>1|3|5|7|9

N>2|4|6|8|0

D、0N

S>0|A0

A>ADIN

P36-8

文法：

ETTE+T|E—T

TtFT*F|T/F

F>(E)|i

最左推导：

E=ET=TT=FT=iT=iT*F=iF*F=ii*F=ii*i

E=T=T*F二F*F=i*F二i*(E)—i*(ET)—i*(TT)—i*(FT)

=i*(iT)二i*(iF)=i*(ii)

最右推导：

E=ET=ET*F=ET*i=EF*i=Ei*i=Ti*i=Fi*i=ii*i

E=T=F*T=F*F=F*(E)=F*(ET)=F*(EF)=F*(Ei)

=F*(Ti)=F*(Fi)=F*(ii)=i*(ii)

编译原理第三版课后答案

i+i+ii-i-i+i*i

P36-9

句子iiiei有两个语法树：

*♦CC"♦C♦-•...•

S^iSeS-iSei*iiSei=mei

S=1S=liSeS=nSei=mei

P36-10

S>TS|T

T>(S)|()

P36-11

编译原理第三版课后答案

P36-11

编译原理第三版课后答案

L1:

S>AC

AraAb|ab

CrcC|;

L2:

S>AB

A?aA|；

BrbBc|be

L3:

S>AB

A-：aAb|；

B=aBb|;

L4:

S>A|B

A—；0A11；

B-1BO|A

第三章习题参考答案

P64-7

⑴

编译原理第三版课后答案

01(01),101*o

⑴

编译原理笫三版课后答案

1101

确定化:

01

(X)0(1,2,3}

00

0

{1,2,31(2.31(2,3,4}

{2,3}⑵3}(2,3,4}

{2.3,4}{2.3,5}(2,3.4}

{2,3,5}⑵3}{2.3,4.Y)

(2,3,4,Y)(2,3,5)(2,3,4,)

10

00110

01

0

1

编译原理笫三版课后答案

11

最小化:

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

{0,123,4,5}。={135}{0,1,2,3,4,5}41,2,4,6}

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

{0,123,4}o={1,3,5}

。1,23,{4},{5},{6}

{0,1,23°={1,3}{0,1,2,3}T{1,2,4)

{0,1},{2,0}{4},{$,{6

[0,

1}0<1}{0,1}厂{1,2}

{2,3}广{3{23厂⑷

⑻,⑴，⑵3},{4},{5},{6}

0010

01

0

1

P6418

⑴

编译原理笫三版课后答案

P64-8

⑴

编译原理第三版课后答案

(10)*01

(2)

⑴2⑶4⑸6|7|8⑼(0|1⑵3⑷5⑹7⑻9)*(0|5)|(0|5)

(3)

0*1(0仪D*11*0(0110*1)*

P64-12

(a)

a,b

确定化:

ab

{0}{0,1)⑴

(0.1){0,1}(1)

{1}0

:{0}

00

0

编译原理笫三版课后答案

给状态编号：

编译原理第三版课后答案

ab

012

112

203

333

{0,1},{2,3}

{0,1}={1}{0,1}二⑵

{2,3}'—{0,3{2,3}b二⑶

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

aa

编译原理笫三版课后答案

bb

a

b

(b)

bba

ab

a

ab

ba

aa

已经确定化了，进行最小化

最小化:

编译原理第三版课后答案

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

{0,也=⑴{0,1口42,4}

{2,3,4,5},二{1,3,0,5{2,3,4,5}b—⑵3,4,5)

{2,4}a—{1,0{2,4}厂匕,5

{3,5L二{3,5{3,5}厂{2,4}

{{0,1},{2,4},{315})

{0,l}a—{1}{0,1儿二⑵4}

{2,4人二{1,0{2,4}严⑶5

{3,5L—{3,5}{3,5}厂⑵4}

bba

aba

P64-14

(1)0

1

=>：

0

(2)：

编译原理第三版课后答案

(010).

确定化:

1

0

{X,1,Y)(hY)(2)

(1.Y)(bY)⑵

⑵r{1,Y}0

00

0

给状态编号:

01

012

i12

3

21

333

0

R6

0

编译原理笫三版课后答案

10

11

1

0

最小化：

{0,1},{2}3

{0,1}o=⑴{0,1「⑵

{2,3}。={1,3}⑵3h二⑶

{0,1},⑵，⑶

0

111

0

0

第四章

P81—1

编译原理一第三版-课后答案

⑴按照T,S的顺序消除左递归

G(S)

S>afl仃)

T>ST

T>,ST|;

递归子程序：

procedureS;

begin

ifsym='a'orsym='A'

thenabvanee

elseifsym二‘(‘

thenbegin

advance;7;

ifsym=')'thenadvanee;

elseerror;

end

elseerror

编译原理一第三版-课后答案

end;

procedureT;

编译原理一第三版-课后答案

begin

S;

end;

procedure;

begin

ifsym一

thenbegin

advanee;

S;

end

end;

其中：

sym:是输入串指针IP所指的符号

advanee:是把IP调至下一个输入符号

error:是出错诊察程序

编译原理一第三版-课后答案

FIRST(S)―'{a,，1,(}

FIRST(T)—{a,八,(}

FIRST()={,,}

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

FOLLOW(T)={)}

FOLLOW()={)}

预测分析表

aA()

s狗aSTAM(T)

T：1'TSTTTST)

TJsTJ,ST

是LL⑴文法

P81一2

文法：

E>TE

EEp

T>FT

TJT|；

F>PF

F〃一：*F|；

A

P>(E)|a|b

编译原理一第三版-课后答案

(1)

FIRST(E)一{(,a,b”}

FIRST(E')一{+,}

£

FIRST(T)={(,a,b,A)

FIRST(T')={(,a,b,»,&}

FIRST(F)={(,a,b,»}

FIRST(F，)={*,}

£

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

FOLLOW(E)—"{#,)}

FOLLOW®)一{#,)}

FOLLOW(T)一{+,),#}

FOLLOW〕')一{+,),#}

FOLLOW(F)={(,a,b,"+,),#}

FOLLOWe')一{(,a,b,"+,),#}

FOLLOW(P)—*{*.(,a,b,"+,),#}

编译原理一第三版-课后答案

(2)

考虑下列产生式

E>E|;

T>T|；

FJ*F|；

P>(E)用alb

FIRST(+E)QFIRST(£)={+}A{}=©

£

FIRST(+E)AFOLLOW(E')一{+}Q{#,)}=©

FIRST(T)AFIRST()={(,a,b,A}A{}=©

££

FIRST(T)AFOLLOW(T，)={(,a,b,A}A{+,),#}=©

FIRST(*F')AFIRST()={*}A{}=©

££

FIRST(*F')AFOLLOW(F')一{*}A{(,a,b,A,+,),#}=©

FIRST((E))AFIRST(a)AFIRST(b)AFIRST(A)=©所以，该文法式LL⑴文法.

(3)

+*()abA

t'fTE'

EETTE'ETTE,ETTE'

EEEJ名EJs

E'

TITF1ITFT*ITFT

TJETJTTJ「TTTTT

rTTTTTTS

F卜TPF'PF'hrPF'hrPF'

FJEFFJEFjgFJ名FJ8FJEFJ8

F，

编译原理一第三版-课后答案

TEaTb

pP()PTPPTA

(4)

procedureE;

begin

ifsym='('orsym=，a'orsym='b'orsym='A'

thenbeginT;E'end

elseerror

end

procedureE：

begin

ifsym='+'

thenbeginadvanee;Eend

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

end

procedureT;

begin

编译原理一第三版-课后答案

ifsym=，('orsym='aorsym=，b'orsym=，A'

thenbeginF;T'end

elseerror

end

procedureT：

begin

ifsym='('orsym='a'orsym='b'orsym='「thenT

elseifsym=，*'thenerror

end

procedureF;

begin

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

thenbeginP;F'end

elseerror

end

procedureF：

begin

编译原理一第三版-课后答案

ifsym-，*，

thenbeginadvanee;F'end

end

procedureP;

begin

ifsym=，aorsym='b'orsym='A'

thenadvanee

elseifsym='('then

begin

advanee;E;

ifsym=')'thenadvanee

elseerror

end

elseerror

end;

编译原理一第三版-课后答案

P81—3

⑴是，满足三个条件。

⑵不是，对于A不满足条件3

(3)不是，AB均不满足条件3。

⑷是，满足三个条件。

第五章

P133-1

E=ET=ET*F

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

直接短语：T*F

句柄:T*F

P133-2

文法：

⑴

编译原理一第三版-课后答案

最左推导：

S一(T)一(T,S)=(S,S)一(a,S)一(a,(T))一(a,(T,S))=(a,(S,S))一(a,(a,S))—(a,(a,a))

S一(T,S)一⑸S)一(CF),S)一((T,S),S)一«T,S,S),6)一((S,S,S),S)一(((T),S,S),S)

=(((T,S),S,S))»S)=«(S,S),S,S),S)=(((a,S),S,S),S)=(((a,a),S,S),S)

=(((a,a),A,S),S)=(((a.a)/,(T)),S)=(((a,a),A,(S»,S)=(((a,a),A,(a)),S)

=(((a,a)f,(a)),a)

最右推导：

S-(T)-(Fs)-(r(T))-(T,(T,S))-(T,(T,a))-(T,(S,a))-(T,(a,a))

-■(S,(a,a))二(a,(a,a))

S二(T,S);(「a)二(S,a)二((T),a)二((T,S),a)二((T,(T)),a)二((T,(S)),a)

-((T,(a)),a)=((T,S,(a)),a)=((T,\(a)),a)=((S,\(a)),a)=(((T)“，(a)),a)二

(((T,S)“，(a)),a):(((T,a)“，(a)),a)二((($,a)“，(a)),a)二(((a,a)“，(a)),a)

(2)

(((a,a),(a)),a)

(((S,a),1l,(a)),a)

(((T,a),八,(a)),a)

(((T,S),八,(a)),a)

(((T),A,(a)),a)

((S,A,(a)),a)

((T,A,(a)),a)

((T,S,(a)),a)

编用原理第三版课后告案

((T,(a)),a)

((T,(S)),a)

((T,(T)),a)

((T,S),a)

((T),a)

(S,a)

(T.S)

(T)

S

“移进一归约”过程：

步骤栈输入串动作

0#(((a,a),八，(a)),a)#预备

1#(((a,a),"(a)),a)#进

(a,a),*IT

2#((八进

(a)),a)#

,a,a),、并

3#(((八，、、、进

八，(a)),a)#

4#(((a,a),A,(a)),a)#进

编译原理一第•:版—课后答案

5#(((S,a),(a)),a)#归

6#(((T,a),八,(a)),a)#归

7#(((T,a),A,(a)),a)#进

8#(((T,a),A,(a)),a)#进

9#(((T,S),A,(a)),a)#归

10#(((T),A,(a)),a)#归

11#((⑴,A,(a)),a)#进

12#((S,A,(a)),a)#归

13#((T,A,(a)),a)#归

14#((T,A,(a)),a)#进

15#((T,A,(a)),a)#进

16#((T,S,(a)),a)#归

17#((T,(a)),a)#归

18#((T,(a)),a)#进

19#((T,(a)),a)#进

20#((T,(a)),a)#进

编译原理一第三版—，课后答

一案

21#((T,(S)),a)#归

22#((T,(T)),a)#归

23#((T,(T)),a)#进

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

25#((T),a)#归

#«T)a)tt进

26f

#(S,a)#归

27

#(T,a)#归

28

#(T,a)#进

29

#(T,a)#进

30

#(T,S)#归

31

#(T)#归

32

#(T)#进

33

ns#归

34

P133-3

(1)

编译原理-第三版■-课后答案

FIRSTVT(S)—{a,八,(}

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

LASTVT(S)={a,A,)}

LASTVT(T)={,,a,")}

⑵

是算符文法，并且是算符优先文法

⑶优先函数

(4)

栈输入字符申动作

(4)

编译原理第三版课后答案

#(a,(a,a))#预备

#(a,(a,a))#进

#(a,(a,a))#进

#(t,(a,a))#归

#(t,(a,a))#进

#（t,（a,a））#进

#3（（a,a））#进

#（t,（t,a））#归

#（t,（t,a））诞

#（t,（t,a））#进

#（t,（t,s））#归

#（t,（t））#归

#t（.（t））#进

#（t,s）#归

#(t)#归

编译原理第二版课后答案

#(t)#进

编译原理第三版课后答案

#S#归

success

Pl34—5

⑴

0.1.2.3.

4.5.6.7.

8.9.10.11.

AS

编译原理第三版课后答案

确定化:

SAab

(0,2,5,7.10}(1,2,5,7,8,10(2,3,5,7,10){11}⑹

|

{1,2,5,7,8,10(2,5,7,8,10){2,3,5,7,9,10(in⑹

))

[2,3,5,7,10)24,5,7,8,10(2,3,5,7,10){in

}

(2,5,7,8,10}{2,5,7,8,10){2,3,5,7,9,10{⑴⑹

)

(2,3,5,7,9,10<2,4.5,7,8,10(2,3,5,7,10){in{6}

)

(2,4,5,7,8,10(2,5,7,8,10){2,3,5,7,9,10(in⑹

))

(11)000

0

000

{6}

0

AS

编译原理第三版课后答案

SaASbSAb

aA

DFA

构造LR(O)项目集规范族也可以用GO函数来计算得到。所得到的项

目集规范族与上图中的项目集一样：

GO，a)={i=

GO，b)={}=

GO，s)={，，，，，)=

GO，A)={，9'，)=

GO，a)={}=

编译原理第三版课后答案

GO,b)={}=

GO，S)={，，，，1=

GO*A)={，，，，，)=

GO'a)=l}=

GO，b)={}=

GO，S)={>，，，，?=

GO，A)={>，，，：=

GO，a)=(1=

GO,b)={}=

GO，S)={，，，，)=

GO,A)={，，，,,：•=

GO，a)={)=

GO,b)={}=

GO,S)={，，，，，)=

GO，A)={>，，，i=

GO，a)=(}=

GO，b)={}=

GO，S)={，尸

编译原理第三版课后答案

GO,0={尸

项目集规范族为C=｛，，，，，，｝

⑶不是SLR文法

状态3，6，7有移进归约冲突

状态3:FOLLOW(S)=｛#｝不包含a,b状态6:FOLLOW(S)=｛#,a,b｝包含a,b,；

移进归约冲突无法消解状态7：FOLLOW(A)"(a,b｝包含a,b；移进归约冲

突消解所以不是SLR文法。

⑷构造例如LR⑴项目集规范族

见下图：

对于状态5,因为包含项目口，所以遇到搜索符号a或b时，应

该用归约。又因为状态5包含项目口，所以遇到搜索符号a时，应该

移进。因此存在“移进一归约”矛盾，所以这个文法不是LR⑴文法。

编译原理第三版课后答案

bbb

8:

1:5:

ATSA

sJs#a/bSTASa/b

AATSAa/bSTASa/bSTASa/b

AT

SAa/bSTASa/bSTba/b

ATaa/bSTba/bATSAa/b

AA

STASa/bATSAa/bATaa/b

STba/bATaa/b

aS

3:

SaS

o：3:

Taa/b

saaAa#A

S>AS#/a/b

S>b#/a/b

A

A>SAa/b

A>aa/b

6:9:

AySTAS■a/b

sAa/b

ATSAa/b

T

ASAa/b

ATSAa/b

AT

aa/bATaa/b

STAS

a/bSTASa/b

STba/bSTba/b

编译原理第三版课后答案

Ab

aaSbb

7:

2:

S》AS#/a/bs

STAS#/a/bAT

STAS#/a/bAa/b

A、SAa/bA一；a

STb#/a/b10：

a/b

bATSAa/bS》ba/b

ATaa/bS》ASa/bS》b

a/b

5:

编译原理第三版课后答案

/********************第^^章

P164-5第六章会有点难

(1)

EE1+T(if(El.type=int)and,「type=int)

thenE.type:=int

elseE.type:=real}

ET(E.type:=T.type}

Tnum.num{T.type:=real)

Tnum{T.type:=int}

⑵

P164-7

SL11L2{S.val:=L1.val+(L2.val/2)}

SL{S.val:=L.val)

LL1B{L.val:=2*Ll.val+B.val;

L.Iength:LI.Iength+1)

编译原理第三版课后答案

LB{L.val:=B.c;

L.Iength:=1)

BO{B.c:=0}

Bl{B,c:=l}

第七章

P217—1

a*(-b+c)

a+b*(c+d/e)abcde/+*+

-a+b*(-c+d)-A—(C—D)

(AB)(—CD)

A_CD_

(AB)(CPE)

ABC@D

或xy+z*0=Pljezab+cfABCD©E

if(x+y)*z=0then(a+b)fcelseafbfcxy+z*0=

ab+cfabcff¥

P2jumpabcff

编译原理一第三版-课后答案

PlP2

P217-3

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

三元式序列：

(1)+,a,b

⑵@,(1),-

(3)+,c,d

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

(5)+,a,b

(6)+,(5),c

⑺(4),(6)

间接三元式序列：

三兀式表：

⑴+,a,b

(2)(1),-

编译原理一第三版一课后答案

(3)+,c,d

⑷*,(2),(3)

⑸+,(1),c

(6)(4),(5)

间接码表：

(1)

(2)

(3)

(4)

(1)

(5)

(6)

四元式序列:

(1)+,a,b,

⑵

⑶+,c,d,

⑷*,,,

(5)+,a,b,

编译原理一第三版-课后答案

(6)+,,c,

⑺一,，，

P218-4

自下而上分析过程中把赋值句翻译成四元式的步

骤:A:二B*(-C+D)

步骤输入串栈PLACE四元式

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

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

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

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

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

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

⑺(-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,)

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

编译原理第三版课后答案

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

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

(15))i:=E*(E+EA-B--D

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

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

A-B-

(18)i:=E+E*,B,,)

(-

(19)i:=EAA)

(,,

(20)A

产生的四元式：

(@,C,)

(+,Q,)

(*,B,,)

，，，

(：=A)

P218-5

设A:10*20，B、CD:20,宽度为…

Tl:=i*20

Tl:=Tl+j

T2:二A-84

T3:=4*T1

n这一步是多余的

编译原理第二版课后答案

T4:=i+j

T5:=B-4

T6:=4*T4

T7:=T5[T6]

T8:=i*20

T8:=T8+j

T9:二A-84

T10:二4*T8

Tll:=T9[T10]

T12:=i+j

T13:=D-4

T14:=4*T12

T15:=T13ET14]

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)—假链链首

107.(j,100)—真链链首

假链：{106,104，103}

真链：{107,100}

P218-7

编译原理第二版课后答案

(j<,A,C,102)

101.(j,0)

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

103.(j,-101)

104.(j=,A,\106)

105.(j,109)

106.(+,C,Tl)

107.(:=,T1,C)

108.(j,100)

109.(j<,A,D,111)

110.(j,100)

Hl.(+,A,T2)

112.(:=,T2,A)

113.(j,109)

114.(j,-100)

P219-12

编译原理—第三版—课后答案

(1)

MAXINT-5

MAXINT-4

MAXINT-3

MAXINT_2

MAXINT_1

MAXINT

⑵翻译模式

方法1：

forEl:=E2toE3doS

SrFdoMS

!

F=ForI:=E.toE

J2

I>id

Mr：

{backpatch(Sl.nextlist,nextquad);

backpatch(F.truelist,M.quad);

编译原理—第三版—课后答案

+11);

emit(F.place:=F.place

emit(j,F.place,F.endM.quad);

S.nextlist:=F.falsellst;

(F.falselist:"makelist(nextquad);

emit(j>,El.place,E2.place,);

emit(I.Place:=El.place);

F.truelist:=makelist(nextquad);

emit(j,;

F.place:=I.place;

F.end:=E2.place;

{p:=looku);

ifp<>nilthen

I.place:=p

编译原理—第三版—课后答案

elseerror)

{M.quad:=nextquad)

编译原理第三版课后答案

方法2：

Sforid:=E1toE2doSI

S-FSI

Fforid:=EltoE2do

do

INITIAL—*NEWTEMP;

emit(----'>El.PLACE，-，INITIAL);

FINAL-NEWTEMP;

emit('：―■，'E2.PLACE'-，'FINAL);

p:=nextquad+2;

巳血t(\i,、INITIA