編譯原理與實踐第五章答案

TheExercisesofTheChapterFive

5.1

a.DFAofLR(0)items[Seep.202,p.208,LR(0)def.p.207]

Grammar:

E(L)|a

LL,E|E

LR(0)items:(withaugmentedgrammarruleE’E)

1.E’.E

2.E’E.

3.E.(L)

4.E(.L)

5.E(L.)

6.E(L).

7.E.a

8.Ea.

9.L.L,E

10.LL.,E

11.LL,.E

12.LL,E.

13.L.E

14.LE.

b.SLR(1)parsingtable:[Seepp.210-211]

c.SLR(1)parsingstackforinputstring“((a),a,(a,a))”:[Seep.212]

d.[Seep.207fordef.ofLR(0),p.209forLR(0)parsingtable]

ThegrammarisLR(0)astherearenoambiguities(shift-reduceconflicts)accordingtotherulesonp.207(definitionofLR(0)).

ThedifferencebetweenSLR(1)andLR(0)isthatSLR(1)detectsanerrorbeforeareductionbecauseofthelook-ahead,whereasLR(0)detectsanerrorinaparsestringafterareduction.

5.2Considerthefollowinggrammar:

E→(L)|a

L→L,E|E

a.ConstructtheDFAofLR(1)itemsforthisgrammar.

b.ConstructthegeneralLR(1)parsingtable.

c.ConstructtheDFAofLALR(1)itemsforthisgrammar.

d.ConstructtheLALR(1)parsingtable.

e.DescribeanydifferencethatmightoccurbetweentheactionsofageneralLR(1)parserandanLALR(1)parser.

[Solution]

Augmentthegrammarbyaddingtheproduction:E’→E

a.

State0:[E’→.E,$] State1: [E’→E.,$]

[E→.(L),$]

[E→.a,$]

State2: [E→(.L),$] State3: [E→a.,$]

[L→.L,E,()]

[L→.E,()]

[L→.L,E,,] State4:[E→(L.),$]

[L→.E,,] [L→L.,E,()]

[E→.(L),()] [L→L.,E,,]

[E→.a,()]

[E→.(L),,] State5: [L→E.,()]

[E→.a,,] [L→E.,,]

State6: [E→(.L),()] State7: [E→a.,()]

[E→(.L),,] [E→a.,,]

[L→.L,E,()]

[L→.E,()] State8: [E→(L).,$]

[L→.L,E,,]

[L→.E,,] State9: [L→L,.E,()]

[E→.(L),()] [E→.(L),()]

[E→.a,()] [E→.a,()]

[E→.(L),,] [L→L,.E,,]

[E→.a,,][E→.(L),,]

[E→.a,,]

State10: [E→(L.),()] State11:[L→L,E.,()]

[E→(L.),,] [L→L,E.,,]

[L→L.,E,()]

[L→L.,E,,] State12:[E→(L).,()]

[E→(L).,,]

a

a

(

,

(

)

E

L

,

)

a

(

E

L

(

a

S0

S1

S3

S2

S4

S5

S6

S7

S8

S9

S10

S11

S12

E

E

b. r1:E→(L) r2:E→a r3:L→L,Er4:L→E

State

Input

Goto

(

a

)

,

$

L

E

0

S2

S3

1

1

Accept

2

S6

S7

4

5

3

r2

4

S8

S9

5

r4

r4

6

S6

S7

10

5

7

r2

r2

8

r1

9

S6

S7

11

10

S12

S9

11

r3

r3

12

r1

r1

c.

State0:[E’→.E,$] State1: [E’→E.,$]

[E→.(L),$]

[E→.a,$]

State2/6: [E→(.L),$/()/,] State3/7:[E→a.,$/()/,]

[L→.L,E,()]

[L→.E,()]

[L→.L,E,,] State4/10:[E→(L.),$/()/,]

[L→.E,,] [L→L.,E,()]

[E→.(L),()] [L→L.,E,,]

[E→.a,()]

[E→.(L),,] State5: [L→E.,()]

[E→.a,,] [L→E.,,]

State8/12:[E→(L).,$/()/,]

State9: [L→L,.E,()] State11:[L→L,E.,()]

[E→.(L),()] [L→L,E.,,]

[E→.a,()]

[L→L,.E,,]

[E→.(L),,]

[E→.a,,]

E

a

(

E

,

)

a

E

L

(

a

S0

S1

S3/7

S2/6

S4/10

S5

S8/12

S9

S11

d. r1:E→(L) r2:E→a r3:L→L,Er4:L→E

State

Input

Goto

(

a

)

,

$

L

E

0

S2/6

S3/7

1

1

Accept

2/6

S2/6

S3/7

4/10

5

3/7

r2

r2

r2

4/10

S8/12

S9

5

r4

r4

8/12

r1

r1

r1

9

S2/6

S3/7

11

10

S8/12

S9

11

r3

r3

e.TheconsequenceofusingLALR(1)parsingovergeneralLR(1)parsingisthat,inthepresenceoferrors,somespuriousreducationmaybemadebeforeerrorisdeclared.(Page225)

5.11

a.AugmentgrammarwithruleE’E:

A’A

AaAa

A

Thereareshift-reduceconflictsinstate2andstate5accordingtocondition1onp.221.I.e.thegiven

grammarisnotLR(1).

b.Thegrammarisnotambiguousbecausethereisonlyonepossibleparsetreeforanygiveninputstring.

5.12ShowthatthefollowinggrammarisLR(1)butnotLALR(1):

S→aAd|bBd|aBe|bAe

A→c

B→c

[Solution]

r1:S→aAdr2:S→bBdr3:S→aBer4:S→bAer5:A→cr6:B→c

ThereisnoconflictsinthefollowinggeneralLR(1)parsing:

state

Input

Goto

a

b

c

d

e

$

S

A

B

0

S2

S3

1

1

Accept

2

S6

4

5

3

S11

10

9

4

S7

5

S8

6

r5

R6

7

r1

8

r3

9

S12

10

S13

11

r6

r5

12

r2

13

r4

Whilethereisareduce-reduceconflictintheLALR(1)parsingtable:

state

Input

Goto

a

b