2024年4月29日发(作者：)

编译原理

_

第三版

_

课后答案

编译原理课后题答案

第二章

P36-6

(1)

是

0~9

组成的数字串

⑵

最左推导

：

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

二

N =

ND = N4= D4= 34

N= ND

二

N8= ND8

二

N68

二

D68

二

568

P36-7

G(S)

0127

编译原理第三版课后答案

O > 1|3|5|7|9

N > 2|4|6|8|0

D

、

0|N

S > 0|A0

A > AD|N

P36-8

文法:

E T T E +T|E —T

T t F T* F|T/ F

F > (E)|i

最左推导

：

E = E

T=

T

T=

F T = i T = i T * F = i F * F = i i * F = i i*i

E = T= T* F

二

F * F = i* F

二

i *( E)

二

i*( E T)

二

i *( T T)

二

=i *( i T)

二

i*(i F)= i*( i i)

最右推导

:

E= E

T=

E T*F= E T*i= E F*i= E i*i= T i*i= F i*i= i i*i

E= T= F*T= F * F= F*( E)= F *( E T)= F *( E F)= F *( E i)

=F*( T i)= F*( F i)= F*( i i)= i*(i i)

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

i *( F T)

编译原理第三版课后答案

i

i+i+i

*****************

P36-9

句子

iiiei

有两个语法树:

S

二

iSeS

二

iSei

二

iiSei = iiiei

S= iS = iiSeS = iiSei = iiiei

P36-10

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

S > TS |T

T > (S)|()

***************

P36-11

i

i+i*i

i-i-

i

编译原理第三版课后答案

***************

P36-11

编译原理第三版课后答案

L1:

S > AC

Ar aAb | ab

C r cC |

；

L2:

S > AB

A

》

aA| ；

B r bBc|bc

L3:

S > AB

A—：

aAb |

；

B = aBb |

；

L4:

S > A| B

A—；

0A1| ；

B-

1B0| A

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

P64

-

7

(1)

第三章习题参考答案

编译原理第三版课后答案

1(01)

*

101

(1)

编译原理第三版课后答案

1101

确定化:

0

{X}

0

{1,2,3}

{2,3}

{2,3,4}

{2,3,5}

1

{1,2,3}

0

0

{2,3}

{2,3}

{2,3,5}

{2,3}

{2,3,5}

0

{2,3,4}

{2,3,4}

{2,3,4}

{2,3,4,Y}

{2,3,4,}

{2,3,4,Y}

10

01

0

1

编译原理第三版课后答案

11

最小化:

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

{0,123,4,5}

。

={135} {0,1,2,3,4,5}^{1,2,4,6}

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

{0,123,4}

。

={1,3,5}

{0,1,23，{4},{ 5},{6}

{0,1,23

°

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

厂

{1,2,4}

{0,1},{2,

0

}{4},{ $,{6

{0,1}

0

<1} {0,1}

厂

{1,2}

{2,3}

厂

{3 {23

厂

{4}

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

0010

01

0

1

P64

-

8

(1)

编译原理第三版课后答案

11

P64

-

(1)

8

编译原理第三版课后答案

(1 |0)

*

01

(2)

⑴2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)

*

(0|5)|(0|5)

(3)

0

*

1(0|10

*

1)

*

|1

*

0(0|10

*

1)

*

P64

-

12

(a)

a,b

a

确定化:

a

{0}

{0,1}

{1}

: {0}

{0,1}

{0,1}

b

{1}

{1}

0

0

0

0

编译原理第三版课后答案

给状态编号:

编译原理第三版课后答案

0

1

2

3

abbb

最小化:

{0,1},{ 2,3}

{0,1}

a

={1} {0,1}

b

二

{2}

{2,3}

a

二

{0,3 {2,3}

b

二

{3}

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

aa

a b

1 2

1 2

0 3

3 3

编译原理第三版课后答案

bb

a

b

(b)

bba

ab

a

ab

ba

aa

已经确定化了

，

进行最小化

最小化:

编译原理第三版课后答案

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

{0,1}

a

={1} {0,1}

b

={2,4}

{2,3,4,5}

b

二

{2,3,4,5} {2,3,4,5}

a

二

{1,3,0,5

{2,4}

a

二

{1,0

{3,5L

二

{3,5

{2,4}

厂{

3,5

{3,5}

厂{

2,4}

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

{0,1}

a

二

{1}

{2,4

人二

{1,0

{3,5L

二

{3,5}

bba

ab a

P64

-

14

(1)0

1

=> :

0

⑵:

{0,1}

b

二

{2,4}

{2,4}

严

{3,5

{3,5}

厂

{2,4}

•

--------------

・ A

编译原理第三版课后答案

(010)

*

确定化:

0

{X,1,Y}

{1，Y}

{2}

r

{1，Y}

{1，Y}

{1，Y}

1

{2}

{2}

0

0

0

0

给状态编号:

0

0

1

2

3

1

2

2

3

3

1

1

1

3

0

编译原理第三版课后答案

10

11

1

0

最小化：

，{2,3

。

={1} {0,1}^ {2}

。

={1,3} {2,3h

二

{3}

，{2},{3}

0

111

0

0

P81

—

1

{0,1}

{0,1}

{2,3}

{0,1}

第四章

编译原理

_

第三版

_

课后答案

(1)

按照

T,S

的顺序消除左递归

G (S)

S > af

|仃)

T > ST

T

>,ST | ;

递归子程序：

procedure S;

beg in

if sym='a' or sym=''

A

the n abva nee

else if sym='('

the n begi n

advance;T;

if sym=')' the n adva nee;

else error;

end

else error

编译原理

_

第三版

_

课后答案

end;

procedure T;

编译原理

_

第三版

_

课后答案

beg in

S;

end;

procedure ;

beg in

if sym

二

','

then begi n

advanee;

S;

end

end;

其中

：

sym:

是输入串指针

IP

所指的符号

advanee:

是把

IP

调至下一个输入符号

error:

是出错诊察程序

编译原理

_

第三版

_

课后答案

FIRST(S)

二

{a,

八

,(}

FIRST(T)

二

{a,

八

,(}

FIRST()={,,}

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

FOLLOW(T)={)}

FOLLOW()={)}

预测分析表

a

S

T

A ( )

J

#

S

T

a

:T

T ST

S

T A

r

S

T

(T)

T

T

ST'

T J s TJ ,ST

是

LL(1)

文法

P81

-

2

文法：

E >TE

E

E p

T > FT

T J T |

；

F > PF

F "―； *F | ；

P > (E)| a |b |

A

编译原理

_

第三版

_

课后答案

(1)

FIRST(E)

二

{(,a,b"}

FIRST(E')

二

{+,

£

}

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

A

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

A

&

}

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

A

FIRST(F')={*,

£

}

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

A

FOLLOW(E)

二

{#,)}

FOLLOW(E')

二

{#,)}

FOLLOW(T)

二

{+,),#}

FOLLOW(T')

二

{+,),#}

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

FOLLOW(F')

二

{(,a,b,"+,),#}

FOLLOW(P)

二

{*,(,a,b,"+,),#}

编译原理

_

第三版

_

课后答案

⑵

考虑下列产生式

E >

E| ;

T > T| ；

F J *F | ；

P > (E)||a|b

A

FIRST(+E)Q FIRST( £ )={+} A{

£

}= ©

FIRST(+E) A FOLLOW(E')

二

{+}Q {#,)}= ©

FIRST(T) A FIRST(

£

)={(,a,b,A} A{

£

}= ©

FIRST(T) A FOLLOW(T')={(,a,b,A} A {+,),#}= ©

FIRST(*F') A FIRST(

£

)={*} A{

£

}= ©

FIRST(*F') A FOLLOW(F')

二

{*} A {(,a,b,A,+,),#}= ©

FIRST((E)) A FIRST(a) A FIRST(b) A FIRST(A)= ©

所以

,

该文法式

LL(1)

文法

.

(3)

+

*

( )

a b A

#

E

E

T

TE'

E

T

TE'

E

T

TE'

E

T

TE '

E'

T

E

E

E J

名

EJ s

T

T

T J T

T

T

F

「

T

T

FT*

T J

「

T

T

FT

T

T

T

T'

T J E

F

F

T

PF'

F J

E

T

T T

F J

名

T

T

T

F

T

PF'

F

T

PF'

F

T

PF'

F J g F J 8 F J E

T

T S

F J 8

F'

F J

E

F

编译原理

_

第三版

_

课后答案

P

P

T

(E)

P

T

a

P

T

b

P

T A

⑷

procedure E;

beg in

if sym='(' or sym='a' or sym='b' or sym=''

A

then begi n T; E' end

else error

end

procedure E：

beg in

if sym='+'

then begi n adva nee; E end

else if sym<>')' and sym<>'#' the n error

end

procedure T;

beg in

编译原理

_

第三版

_

课后答案

if sym='(' or sym='a' or sym='b' or sym='A'

then begi n F; T' end

else error

end

procedure T：

beg in

if sym='(' or sym='a' or sym='b' or sym='

else if sym='*' the n error

end

procedure F;

beg in

if sym='(' or sym='a' or sym='b' or sym='A'

then begi n P; F' end

else error

end

procedure F：

beg in

A

' the n T

编译原理

_

第三版

_

课后答案

if sym

二

'*'

then begi n adva nee; F' end

end

procedure P;

beg in

if sym='a' or sym='b' or sym=''

A

then adva nee

else if sym='(' the n

beg in

advanee; E;

if sym=')' the n adva nee

else error

end

else error

end;

编译原理

_

第三版

_

课后答案

P81

—

3

***************

(1)

是，满足三个条件。

不是，对于

A

不满足条件

3

。

不是，

A

B

均不满足条件

3

。

是，满足三个条件。

⑵

⑶

⑷

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

第五章

P133- 1

E =

E T= E T* F

短语

：E+T*F, T*F,

直接短语

：T*F

句柄

:T*F

P133-2

文法：

(1)

编译原理

_

第三版

_

课后答案

最左推导

：

二

(T)

二

(T,S)= (S,S)

二

(a,S)

二

(a,(T))

二

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

二

(a,(a,S))

二

(a,(a,a)) S

S

二

(T,S)

二

(S,S)

二

((T),S)

二

((T,S),S)

二

((T,S,S),S)

二

((S,S,S),S)

二

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

A

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

=(((a,a),

,S),S)= (((a,a),

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

,(S)), S)= (((a,a),

,(a)), S)

AAA

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

最右推导

：

S

二

(T)

二(「

S)

二(「(

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)

二

(((S,a)“ ,(a)), a)

二

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

(2)

(((a,a),

八

,(a)),a)

(((S,a),

八

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

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

9 #(((T,S

10 #(((T

11 #(((T)

12 #((S

13 #((T

14 #((T,

15 #((T,

A

16 #((T,S

17 #((T

18 #((T,

19 #((T,(

20 #((T,(a

),

A

,(a)),a)#

),A,(a)),a)#

),A,(a)),a)#

,A,(a)),a)#

,A,(a)),a)#

,A,(a)),a)#

A,(a)),a)#

,(a)),a)#

,(a)),a)#

,(a)),a)#

(a)),a)#

a)),a)#

)),a)#

进

归

归

进

归

归

进

归

进

进

进

进

归

编译原理

_

第三版

_

，课后答

案

21

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

归

归

22

#((T,(T )),a)#

23

#((T,(T) ),a)#

进

24

25

26

27

28

29

30

31

32

33

34

P133-3

(1)

#((T,S

#((T

#((T)

#(S

#(T

#(T,

#(T,a

#(T,S

#(T

#(T)

#S

),a)#

),a)#

归

,a)#

进

,a)#

归

,a)#

归

a)#

进

)#

进

)#

归

)#

归

#

进

#

归

归

编译原理

_

第三版

_

课后答案

FIRSTVT(S)

二

{a,

八

,(}

FIRSTVT(T)={,,a,

八

,(}

LASTVT(S)={a,,)}

A

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

⑵

a

A

( )

5

a

>

>

<

>

>

<

>

>

A

(

)

<

< =

>

<

5

< < >

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

(3)

优先函数

a

f 4

5

A

4

5

(

2

5

)

5

4

2

4

3

g

(4)

栈输入字符串动作

(4)

编译原理第三版课后答案

#

(

a,(a,a)

)

#

预备

#(a, (a,a))#

进

#(a, (a,a))#

进

#(t, (a,a))#

归

#

(

t,(a,a)

)

#

(

t,

(

a,a

) )

#

(

t,

(

a,a

) )

#

(

t,

(

t,a

))

#

(

t,

(

t,a

) )

#

(

t,

(

t,a

) )

#

(

t,

(

t,s

) )

#

(

t,

(

t

) )

#

(

t,

(

t

) )

#

(

t,s

)

#

归

#

(

t

)

#

归

#

进

#

进

#

进

#

归

#

进

#

进

#

归

#

归

#

进

编译原理第三版课后答案

#

(

t

)

#

进

编译原理第三版课后答案

# S#

归

success

P134—5

(1)

0.

4.

5.

8. 9. 10.

SA

AS

1. 2. 3.

6.

7.

11.

编译原理第三版课后答案

确定化:

S

{0,2,5,7,10}

{1,2,5,7,8,10

}

{1,2,5,7,8,10

}

{2,3,5,7,10}

{2,4,5,7,8,10

}

{2,5,7,8,10} {2,5,7,8,10}

{2,5,7,8,10}

A

{2,3,5,7,10}

a

{11}

b

{6}

{2,3,5,7,9,10

}

{2,3,5,7,10}

{11} {6}

{11} {6}

{2,3,5,7,9,10

}

{11} {6}

{2,3,5,7,9,10

}

{2,4,5,7,8,10

}

{11}

{2,4,5,7,8,10

}

{2,5,7,8,10}

{2,3,5,7,10} {11} {6}

{2,3,5,7,9,10

}

{11} {6}

0

0

0

{6}

0

0

0

0

0

AS

编译原理第三版课后答案

Sa AS bSAb

aA

7：

S

》

AS |

— SA

S t A 'S

S

T

4：

AS

S

T

b

A

T

SA

S

》

AS

b

A t a

「

A—

SA

1

A

，

a

aabb

DFA

构造

LR(O)

项目集规范族也可以用

GO

函数来计算得到。所得到

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

：

=｛

，，，，

｝

GO

，

a)=｛

｝

=

GO

，

b)=｛ ｝=

GO

，

S

)=｛

，，，，，

｝

=

GO

，

A)=｛

，，，，

｝

=

GO

,

a)={ }=

的项

编译原理第三版课后答案

GO

,

b)={ }=

GO

，

S)={

, ,,,

=

}

GO

，

A)={

, ,,,,

=

}

GO

，

a){ }

==

GO

,

b)={ }=

GO

，

S)={

, ,,,,

=

}

}

GO

,

A)={

, ,,,

=

GO

，

a){ }

==

GO

,

b)={ }=

GO

，

S)={

, ,,,

=

}

GO

,

)={

, ,,,,

=

A}

GO

,

a){ }

==

GO

,

b)={ }=

GO

,

S)={

, , , , ,

=

}

}

GO

,

A)={

, , , ,

=

GO

,

a){ }

==

GO

,

b)={ }=

GO

,

S)={

, , , ,

=

}

编译原理第三版课后答案

GO

,

)={

, , , , ,

=

A}

项目集规范族为

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

文法。

(4)

构造例如

LR(1)

项目集规范族

见下图：

对于状态

5

,因为包含项目

［］

，所以遇到搜索符号

a

或

b

时，应

该用归约。又因为状态

5

包含项目

［］

，所以遇到搜索符号

a

时，应该

移进。因此存在“移进

-

归约”矛盾，所以这个文法不是

LR(1)

文法。

编译原理第三版课后答案

bbb

1:

5:

8:

S J S #

A

T

SA

S T

A S

a/b

a/b

a/b

a/b

a/b

a/b

S

T

S

T

AS

AS

a/b

A

A

T

S

A

A

T

SA

A

T

a

S

T

AS

S

T

b

a/b

a/b

a/b

S T

AS

S T b

AA

a/b

a/b

a/b

A

T

SA

A

T

a

S

T

b

A

T

SA

A

T

a

a/b

a/b

a/b

aS

3:

SaS

o：

S

aaAa

S >

AS

S >

b

A

A >

SA

a

A >

3:

#

#/a/b

#/a/b

a/b

a/b

A

T

a a/b

6:

9:

A

T

S

A

A

T

SA

A

T

a

S

T

AS

S

T

b

S

T

a/b

a/b

a/b

a/b

a/b

AS

■

a/b

A

T

S

A

A

T

SA

a/b

a/b

a/b

a/b

a/b

A

T

a

S

T

AS

S

T

b

编译原理第三版课后答案

Ab

aaSbb

2:

S T A S #/a/b

S T

AS #/a/b

S T

b #/a/b

b

A

T

SA a/b

A

T

a a/b

7:

S

》

AS #/a/b

A

T

S

A a/b

A、

SA a/b

A—；

a

a/b

S

》

AS a/b S

》

b

a/b

10:

S

》

b a/b

5:

编译原理第三版课后答案

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

第六章

第六章会有点难

P164-5

(1)

EE1+ T {if ( = int) and

(「

type = int )

the n := int

else := real}

ET { := }

{ := real}

Tnum { := int}

⑵

P164-7

SL1|L2 {:=+(/2)}

SL {:=}

LL1B {:=2* + ;

ngth:

二

ngth+1}

编译原理第三版课后答案

LB {:=B.c;

ngth :=1}

BO {B.c:=0}

B1 {B.c:=1}

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

P217— 1

a*(-b+c)

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

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

(A B) (—C D)

(A B) (C P E)

或

xy+z*0= P1 jez ab+c f

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

ab+cf abcff ¥

P2 jump abc ff

第七章

A_CD_ _

AB C @ D

AB CD @ E

f c else a f b fc xy+z*0=

编译原理

_

第三版

_

课后答案

P1 P2

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

(7) -, (4), (6)

间接三元式序列

：

三兀式表：

(1)+, a, b

(2) @, (1),-

编译原理

_

第三版

_

课后答案

(3) +, c, d

⑷*, (2), (3)

(5) +, (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-

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

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

(6) *(-C+D) i:=E A-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*(-i A-B---C

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

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

(@,C,-,)

编译原理第三版课后答案

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

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

(15) ) i:=E*(E+E

(16) ) i:=E(E

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

(18)i:=E+E

A-B-

(

(19)i:=E

-

A

(20)

(,,

产生的四元式:

(@,c,-,)

(+,Q,)

(*,B,,)

,,-,

(：=A)

P218-5

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

设

A

:

10*20

,

B

、

C D: 20

,宽度为

T1:= i * 20

T1:=T1+j

T2:=A

—

84

T3:=4*T1

A-B---D (+,,D,)

A-B--

*,B,,)

-,A)

A

w= 4

Tn :=T2[T3]

II

这一步是多余的

编译原理第三版课后答案

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)--

107. (j, -, -, 100)--

假链：

{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,

‘

, 106)

105. (j, -, -, 109)

106.

(+, C,

‘

, T1)

107. (:=,T1, -, C)

108. (j, -, -, 100)

109.

(j

<

, A, D, 111)

110. (j, -, -, 100)

111.

(+, 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

(2)

翻译模式

方法

1

：

for E1 := E2 to E3 do S

S r F do MS

1

F = For I : = E

j

to E

2

I > id

M

「

；

{backpatch(S1. nextlist ,n extquad);

backpatch(st,);

编译原理

_

第三版

_

课后答案

emit(

‘

:=

'

‘

+

'

1);

emit(

‘

j,

'

‘

,

'

‘

,

'

);

S.n extlist := ist;

}

{ist:

二

makelist (n extquad);

emit(

‘

j>,

'

emit(

‘

:=

'

);

st := makelist( nextquad);

emit(

‘

j,-,-,-

'

);

:= ;

F.e nd := ;

}

{p:=looku);

if p <> nil the n

:= p

,

'

,);

‘‘

编译原理

_

第三版

_

课后答案

else error}

{ := n extquad}

编译原理第三版课后答案

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

方法

2

:

S

—

for id:=E1 to E2 do S1

S

—

F S1

F

—

for id:=E1 to E2 do

do

{

INITIAL

二

NEWTEMP;

emit(

‘

:二

,'

，

-

, '

INITIAL);

FINAL

二

NEWTEMP;

emit(

‘

:二

,'

，

-

, '

FINAL);

p:= n extquad+2;

巳血

t( i , IMTIAL ； 1'INAL j?);

??T

?

F.n extlist:

二

makelist( nextquad);

emit(

‘

j,

———'

,,);

:=looku);

编译原理

_

第三版

_

课后答案

if 1

1

place nil then

emit(

‘

:二

'

INITIAL)

:

二

n extquad;

nal:=FINAL;

}

S > FS1

{

backpatch(S1. nextlist, n extquad)

p:=n extquad+2;

emit. ( J

‘

,

'

nal

'

,

merge(st, makelist(nextquad));

emit(

‘

j,

—

,

—

,

—'

)；

emit(

‘

succ

，‘

' ,

emit(

‘

j,

—

,

—

,

'

);

p ); st :=

-

，‘

);

'

编译原理

_

第三版

_

课后答案

第九章

P270-9

(1)

传名

即当过程调用时，其作用相当于把被调用段的过程体抄到调用出

现处，但必须将其中出现的任一形式参数都代之以相应的实在参数。

A:=2;

B:=3;

A:=A+1;

A:=A+(A+B);

print A;

••• A=9

(2)

传地址

即当程序控制转入被调用段后，被调用段首先把实在参数抄进相 应

的形式参数的形式单元中，过程体对形参的任何引用或赋值都被处 理成

对形式单元的间接访问。当被调用段工作完毕返回时，形式单元

(都是指示器)所指的实参单元就持有所希望的值。

①

A:=2;B:=3;T:=A+B

编译原理

_

第三版

_

课后答案

② 把

T,A,A

的地址抄进已知单元

J1,J2,J3

③

x:

=

J1;y:=J2;z:=J3

〃 把实参地址抄进形式单元，且

J2=J3

④

Yf :=y f +1

Zf :=z f +xf // Y f:

对

y

的间接访问

Zf:

对

z

的间接访问

⑤

print A

A=8

(3)

得结果

每个形参均对应两个单元，第一个存放实参地址，第二个存放实 参

值，在过程体中对形参的任何引用或赋值都看成是对它的第二个单 元的

直接访问，但在过程工作完毕返回前必须把第二个单元的内容放 到第一

个单元所指的那个实参单元中

①

A:=2;B:=3;T:=A+B

② 把

T,A,A

的地址抄进已知单元

J1,J2,J3

③

x1:=J1;x2:=T;

y1:=J2;y2:= A;

编译原理第三版课后答案

z1:=J3;z2:=A;

〃 将实参的地址和值分别放进两个形式单元中

④

y2:=y2+1; z2:=z2+x2;

〃 对形参第二个单元的直接访问

⑤

x1 f:= x2; y1 f

:二

y2; z1 f :=z2 //

返回前把第二个单元的内

容存放到第一个单元所

指的实参地址中

⑥

print A

A=7

⑷传值

即被调用段开始工作时，首先把实参的值写进相应的形参单元中,

然后就好像使用局部变量一样使用这些形式单元

A:=2;

B:=3;

x:=A+B

y:=A

z:=A

y:=y+1

编译原理第三版课后答案

z:=z+x

print A

A=2

编译原理第三版课后答案

过程调用不改变

A

的值

第十章

P306-1

P306-2 read A,B

F:=1

C:=A*A

D:=B*B

if C

Bi

Bi

B

3

B

4

编译原理第三版课后答案

E:=A*A

F:=F+1 E:=E+F write E halt

:E:=B*B

F:=F+2

E:=E+F

write E

if E>100 goto

halt

F:=F-1

编译原理第三版课后答案

goto

基本块为、、、、

P307-4

B2

有回路，所以

｛B2｝

是循环，

B2

既是

xx

节点，又是出口节点

代码外提：不存在不变运算，故无代码外提

强度削弱：

A:=K*I B:=J*I *

—+

(1)

(2)

编译原理第三版课后答案

(3

)删除基本归纳变量：

1<100

可以用

A<100*K

或

B<100*J

代替

编译原理第三版课后答案

P307-5