陈火旺编译原理(第三版)课后习题答案

∣

7

∣

8

∣

9)(0

∣

1

∣

2

∣

< br>3

∣

4

∣

5

∣

6

∣

7

∣

8

∣

9)< /p>

*

(0

∣

5)< /p>

∣

(0

∣

5

)

⑶

0

*

1(0

∣

10

*

1)

*

∣

1

*

0(0

∣

10

*

1)

*

P64- 12

⑻

a

{0}

b

{1}

{0,1}

{0,1}

{1}

{0,1}

{0}

{1}

φ

φ

φ

φ

给状态编号

:

0

1

2

3

a

0

a

b

b

b

2

a

最小化：

{0,1},{ 2,3}

{0,1}

a

={1} {0,1}

b

={2}

{2,3}

{2,3}

b

={3}

a

={0,3}

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

a

1

1

0

3

b

2

2

3

3

已经确定化了

，

进行最小化

最小化

:

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

{0,1}

a

={1}

叽

={2,4}

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

{2,3,4,5}

a

={1, 3,0,5}

{2,4}

a

={1,0}

{3,5}

a

={3,5}

{2,4}

b

={3,5}

{3,5}

b

={2,4}

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

{0,1}

b

={2,4}

{0,1}

a

H1}

{2,4}

a

={1,0}

{3,5}

a

={3,5}

{2,4

打

={3,5

{3,5}

b

={2,4}

0

0

1

{2}

确定化

:

{X,1,Y}

{1,Y}

{1,Y}

{2}

{1,Y}

{1,Y}

{2}

φ

φ

给状态编号

:

φ

φ

1

2

2

3

3

0

0

1

2

3

1

1

1

3

最小化：

{0,1},{2,3

{0,1}

o

√1}

{0,1}

ι

={2}

{2,3}o={1,3}

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

{2,3}^{3}

P81

-

1

(1)

按照

τ,s

< br>的顺序消除左递归

G(S)

S > a

∣

^

∣

仃

)

T > ST

TrST |

；

递归子程序：

ProCedUre S;

begin

if sym='a' or sym=' ^'

the n abva nce

else if sym='('

the n begi n

advance;T;

if sym=')' the n adva nce; else error;

end

else error

en d;

PrOCedUre T;

begin

S;

T

en d;

PrOCedUre

T

;

begin

if sym=','

the n begi n

advance;

S;

T

end

en d;

其中

：

Sym:

是输入串指针

IP

advance:

是把

IP

调至下一个输入符号

error:

是出错诊察程序

⑵

FlRST(S)={a,^,(}

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

FIRST(T )={,, J

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

FoLLoW(T)={)}

FOLLOW

T

)={)}

预测分析表

a

S

T

T

是

LL(1)

文法

H

^

(

)

#

S

T

a

Sτ^

:

TT ST

H

:

TT ST

ST (T)

TT ST

TJ

名

T

'T

,ST

P81

-

2

文法

:

E > TE

E^

E |

T > FT

T

》

T I

F

-

PF

F

> *F I

；

P > (E)

∣

a

∣

b

∣

^

(1)

FIRST(E)={(,a,b,^}

FIRST(E')={+,

ε

}

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

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

ε

}

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

FIRST(F')={*,

ε

}

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

FoLLoW(E)={#,)}

FoLLoW(E')={#,)}

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

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

FOLLOW(F)={(,a,b,^,+,),*}

FOLLOW(F')={(,a,b,^,+,),*}

FOLLOW(P)={*,(,a,b,^,+,),*}

⑵

考虑下列产生式

：

E

，

E|

；

T

J

T| :

F

J

*F | :

P > (E)|

A

|a|b

FIRST(+E)

∩

FIRST(

ε

)={+}

∩

{

ε

}=

φ

FIRST(+E)

∩

FOLLOW(E')={+}

∩

{#,)}=

φ

FIRST(T)

∩

FIRST(

ε

)={(,a,b,^}

∩

{

ε

}=

φ

FIRST(T)

∩

FOLLOW(T')={(,a,b,^}

∩

{+,),#}=

φ

FIRST(*F')

∩

FIRST(

ε

)={*}

∩

{

ε

}=

φ

FIRST(*F')

∩

FOLLOW(F')={*}

∩

{(,a,b,^,+,),*}=

φ

FIRST((E))

∩

FIRST(a)

∩

FIRST(b)

∩

FIRST(^)=

φ

所以

,

该文法式

LL(1)

文法

.

⑶

+

*

(

)

a

b

^

#

E

Eτ TE'

E

τ

TE'

Eτ TE'

Eτ TE '

E'

T

E

J+

E

EJ

S

EJ

8

T

T

FT

H

T

T

FT

T

JE

H

TT FT

T

J

T

H

T

T

FT

T

J

T

H

T'

T

JE

T

J

T

T

J

T

TJ

J

F

FT Pi

FTPL

FTPL

FT PF*

F'

F

'τ

*F

'

:

F

JE

FJ

S

F

Jg

P

PT (E)

PT a

⑷

ProCedUre E;

begin

if sym='(' or sym='a' or sym='b' or sym=' ^' the n beg in T; E' end else error

end

PrOCedUre E';

begin

if sym='+'

the n beg in adva nce; E end

else if sym<>')' and sym<>'#' then error end

PrOCedUre T;

begin

if sym='(' or sym='a' or sym='b' or sym=' ^' the n beg in F; T' end else error

end

PrOCedUre T';

begin

if sym='(' or sym='a' or sym='b' or sym=' ^' the n T

else if sym='*' then error

end

PrOCedUre F;

begin

if sym='(' or sym='a' or sym='b' or sym=' ^' the n beg in P; F' end else error

end

PrOCedUre F';

begin

if sym='*'

the n beg in adva nce; F' end

end

PrOCedUre P;

begin

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

the n adva nce

else if sym='(' the n

FJ

S

PT b

FJ

名

FJ

S

P

T

^

begin

advance; E;

if sym=')' the n adva nce

else error

end

else error

en d;

P81

-

3

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

(1)

是，满足三个条件。

(2)

不是，对于

A

不满足条件

3

。

(3)

不是，

A

、

B

均不满足条件

3

。

(4)

是，满足三个条件。

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

第五章

P133- 1

E= E T=E T* F

短语

：

E+T*F, T*F,

直接短语

：

T*F

句柄

:T*F

P133-2

文法：

S > a

< br>∣

^

∣

(T)

< br>

T > T,S|S

(1)

最左推导

:

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,S) = ((T), S)= ((T ,S), S)= ((T, S, S), S) = ((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),^ ,S),S)= (((a,a),^ ,(T)), S)= (((a,a),^ ,(S)), S)= (((a,a),^ ,(a)), S)

=(((a,a),^ ,(a)), a)

最右推导

:

S= (T)= (T,S)

二

(

T,(T))

二

(T

l

(T

l

S)^ (T

l

(T

l

a)^ (T

l

(S

l

a)^ (T,(a,a))

=

(SI(aI a)

^

= (a,( aIa))

S= (TIS)= (TIa)= (SIa)= ((T)Ia)= ((TIS)Ia)= ((TI(T))Ia)= ((TI(S)), a)

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

二

(

(T,^ ,(a)), a)

二

(

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

(((T),^ ,(a)),a) =(((T,S)l^ ,(a)),a)= (((T,a),^ ,(a)),a)= ((( S,a),^ ,(a)),

a)= (((a,a),^ ,(a)), a)

⑵

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

(((Sm),^,(a)),a)

(((T, a),^,(a)),a)

(((TS),^,(a)),a)

(((TL,^,(a)),a)

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

((TS,(a)),a)

((T,( a)),a)

((T,( S)),a)

((T,( T)),a)

((TS),a)

((ILa)

(S,a)

(LS)

(TL

S

步

栈

输入串

动作

骤

0

#

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

1

#(

#

((a,a),^,(a)),a)#

2

#((

(a,a),^,(a)),a)#

3

#(((

a,a),^,

4

#(((a

(a)),a)#

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

5

#(((S

)#

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

6

#(((T

)#

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

7

#(((T,

)#

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

8

#(((T,a

#

),^,(a)),a)#

9

#(((T,S

),^,(a)),a)#

10

#(((T

),^,(a)),a)#

11

#(((T)

,^,(a)),a)#

进

12

#((S

,^,(a)),a)#

归

13

#((T

,^,(a)),a)#

归

14

#((T,

^,(a)),a)#

15

#((T,^

,(a)),a)#

16

#((T,S

,(a)),a)#

17

#((T

,(a)),a)#

18

#((T,

(a)),a)#

19

#((T,(

a)),a)#

进

预备

进

进

进

进

归

归

进

进

归

归

进

进

归

归

进

-

归约”过程

:

“ 移进

20

#((T,(a

21

#((T,(S

22

#((T,(T

23

#((T,(T)

24

#((T,S

25

#((T

)),a)#

)),a)#

)),a)#

),a)#

),a)#

),a)#

进

归

归

进

归

归

26

#((T)

,a)#

进

27

#(S

,a)#

归

28

#(T

,a)#

归

29

#(T,

a)#

进

30

#(T,a

)#

进

31

#(T,S

)#

归

32

#(T

)#

归

33

#(T)

#

进

34

#S

#

归

P133-3

(1)

FlRSTVT(S)={a,^,(} FlRSTVT(T)={,,a,^,(} LASTVT(S)={a,^,)} LASTVT(T)={,,a,^,)}

a

^

(

)

5

a

>

>

^

>

>

(

V

V

V

=

V

)

>

>

5

V

V

V

>

>

G

6

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

(3)

优先函数

a

^

(

)

5

f

4

4

2

4

4

g

5

5

5

2

3

(4)

栈

输入字符串

动作

#

(a,(a,a) ) #

预备

#(

a, (a,a))#

进

#(a

,(a,a))#

进

#(t

,(a,a))#

归

⑵

# (t,

# (t,(

# ( t, ( a

# ( t, ( t

# ( t, ( t,

# (t, (t,a

# (t, (t,s

# ( t, ( t

# ( t, ( t )

# (t,s

# (t

# (t

# S

SUCCeSS

)

(a,a) ) #

a,a )) #

,a )) #

,a )) #

a)) #

))#

))#

))#

)#

)#

)#

#

#

进

进

进

归

进

进

归

归

进

归

归

进

归

P134-5

(1)

O.

S

r

S

1.

S

r

S ■

4. Sr

AS

' 5. Sr

b

8.

A-

?

2.

S ' AS

3. Sr

A S

6. S

r

b ■

7. Ar

SA

?

S A

9. Ar

SA ■

10. Ar

a

11. Ar

a ■

⑵

确定化

:

{0,2,5,7,10}

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

S

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

}

A

{2,3,5,7,10}

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

a

{11}

{11}

b

{6}

{2,5,7,8,10}

⑹