# 武汉大学计算机学院《编译原理》05-06学年期末考试答案

2005-2006

2003
(1) (2)
ε 3 0 4

0 1

0

11

ε start 0 0 1 ε 2 ε

ε 7 ε 8 1 9 1 10

5

1

6

ε

ε

(3)

0 C 0 start A
{0} {2,3,4,5,6,7,8}

0 0 E 1 1

0

B 1

1 D
1

{1,2,3,5,8}

{2,3,5,6,7,8,9,10}

{2,3,5,6,7,8,9}
1

(4) A → B → D → E → C → D → E (1) r = (0 1)? 101(0 1)? ; (2)

0

1

1

0

0 start 1

1 0 1

1

0

0

1

(3)

0 start 1

1 0

0

(1) First(S) = { a, b, d }; First(A) = { a, b, c, d }; First(B) = { a, b, d, ε }; First(C) = { a, b, d, ε }; (2) Follow(S) = { c, \$ }; Follow(A) = { a, b, c, d, \$ }; Follow(B) = { c, d, \$ }; Follow(C) = { b }; (3) a S S → aAB, S → Bd A A → BcA, A → a B B → Cb C C → Sc C (4) (1) S =? AcB
rm

b S → Bd A → BcA B → Cb → Sc, C → ε

d S → Bd A → BcA A → BcA B→ε B → Cb ε C→ε

c

\$

B→ε

LL(1)

=? AcbcB
rm rm rm rm

=? Acbcb =? acAcbcb =? acacbcb (2) (3) a b c a c, ac ? A }, (4) / (ac)m (bc)n b (m > 0, n ≥ 0); { A → a ? cA, A → a? }, c ∈ Follow(A), A→a c {A → SLR(1)

2

S → AB A → acA ac B → bcB b G(S) (1) S =? S ∨ S
lm

(10

5+5)

S =? S ∧ S
lm

=? a ∨ S
lm

=? S ∨ S ∧ S
lm

=? a ∨ S ∧ S
lm

=? a ∨ S ∧ S
lm

=? a ∨ a ∧ S
lm

=? a ∨ a ∧ S
lm

=? a ∨ a ∧ a
lm

=? a ∨ a ∧ a
lm

(2) S → S∨T T T → T ∧F F F → ?F (S) a (1) First(S) = { a, (, ? }; Follow(S) = { ∨, ∧, ), \$ }; (2) I2 = I7 = (3) state 0 1 2 3 4 5 6 7 8 9 10 11 ? s1 s1 s1 / / s1 / s1 / / / / ( ) s2 / s2 / s2 / / s4 / r4 s2 / / r2 s2 / / r1 / r5 / r3 / /
3

S → (?S), S → ?S ∨ S, S → ?S ∧ S, S → ??S, S → ?(S), S → ?a S → S ∨ ?S, S → ?S ∨ S, S → ?S ∧ S, S → ??S, S → ?(S), S → ?a

action ∧ a ∨ \$ / s9 / / / s9 / / / s9 / / s5 / s7 / r4 / r4 r4 / s9 / / r2 / r2 r2 / s9 / / s5 / r1 r1 r5 / r5 r5 r3 / r3 r3 s5 / s7 acc

goto S 11 10 3 / / 6 / 8 / / / /

(4) stack I0 I0 ?I1 I0 ?I1 aI9 I0 ?I1 SI10 I0 SI11 I0 SI11 ∨ I7 I0 SI11 ∨ I7 aI9 I0 SI11 ∨ I7 SI8 I0 SI11 ∨ I7 SI8 ∧ I5 I0 SI11 ∨ I7 SI8 ∧ I5 aI9 I0 SI11 ∨ I7 SI8 ∧ I5 SI6 I0 SI11 ∨ I7 SI8 I0 SI11 input action ?a ∨ a ∧ a\$ shift a ∨ a ∧ a\$ shift ∨a ∧ a\$ reduce S → a ∨a ∧ a\$ reduce S → ?S ∨a ∧ a\$ shift a ∧ a\$ shift ∧a\$ reduce S → a ∧a\$ shift a\$ shift \$ reduce S → a \$ reduce S → S ∧ S \$ reduce S → S ∨ S \$ accept

(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) (12) (13) (1) (1) (2) (3)

S → S 1 ∨ S2 S → S1 ∧ S2 S → ?S1

(4) (5) (2)

S → (S1 ) S→a

{ S.neg := “(” + S1 .neg + “∧” + S2 .neg + “)” } { S.neg := “(” + S1 .neg + “∨” + S2 .neg + “)” } { S.neg := if if ?rst is neg(S1 .neg) then delete ?rst(S1 .neg) else “?” + S1 .neg } { S.neg := S1 .neg } { S.neg := “?” + a.lexme }

S
S.neg=(P(Λ?QV?R)) S.neg=P

S

V

S.neg=(?QV?R)

S

?

S.neg=?P a.lexme=P

S

S.neg=?Q a.lexme=Q

S a

Λ

S.neg=?R a.lexme=R

S a

a

4

(1) if (a > b + c) x = b - c + b * c; else x = e / f; t0 := b + c if a > t0 goto L1 t1 := e / f x := t1 goto L2 L1: t2 := b * c t3 := b - c t4 := t2 + t3 x := t4 L2: (1) (2) (4) (5) (6) (7) (8) (9) (10) (11) + if> / := jump * + := b a e t1 (11) b b t2 t4 c t0 f / c c t3 / t1 (7) t1 x t2 t3 t4 x

(2) do s = s + 1; i++; while (i < 100); L1: t0 := s + 1 s := t0 t1 := i + 1 i := t1 if i < 100 goto L1 main() i address x x-4 x-8 x-16 x-24 x-28 x-32 x-36 x, f() note ←i of main, a+7 ← of main, a+6 ←of main, a+5 ←i of f, a+4 ←a+3 ←a+2 ←a+1 ←a of f (1) (2) (3) (4) (5) + := + := if< s t0 i t1 i 1 / 1 / 100 t0 s t1 i (1)

memory ...... 1 fp ret add 1 -1 -1 -1 -1 ......

i = 4 a + 4 i, *(a + 4)= -1 0, , , main() i 1 + 2,

f() i 3

while (i) -1, i++ i ; *(a + 7) += 2

5