编译原理课后习题答案

Z→S (1)S→cA (2)S→ccB (3)B→ccB (4)B→b (5)A→cA (6)A→a (7)aS0S1S2S3S4S5S6S7S8S9S10S11s3R7R6s3R3R2s3R5s3R4actionbcs1s5R7R6s8R3R2s10R5s8R4#A4gotoBS2R7R6s9R3R2R5s9R4AccR7R67R3R27R57R411

62. 设有下列文法:

(1) S?SaS | b (2) S?bSb | cSc | b | c (3) S?bSb | bSc | d (4) S?aSb | bSa | ab (5) S?Sab | bR

R?S | a B?b A?aA | B B?? A?? B?dB | ? (6) S?SAB | BA

(7) S?AaAb | BbBa

(8) A?aABe | Ba

说明上述文法是否为SLR(1)文法。若是,请构造SLR(1)分析表;若不是,请说明理由。 答:

(1)

Ch05-2-(1)不是SLR(1)Follow(S)={#,a}0Z→.SS→.SaSS→.bb1S→b.2SZ→S.S→S.aS3S→Sa.SaS→.SaSS→.bbSa4S→SaS.S→S.aS

13

(2)

Ch05-2-(2)不是SLR(1)Follow(S)={#,b,c}01S→b.SbS→b.S→.bSbS→.cScS→.bS→.cZ→.SS→.bSbS→.cScS→.bS→.c

(3)

b

Ch05-2-(3)Z→.SS→.bSbS→.bScS→.dS1Z→S.0是SLR(1)3dS→d.5S→bSb.b4S→bS.bS→bS.cc6S→bSc.d2S→b.SbbS→b.ScS→.bSbbS→.bScS→.dS

Z→.S (1)S→.bSb (2) S→.bSc (3)S→.d (4) S0S1S2S3S4S5S6bs2s2R4s5R2R3actioncds3s3#gotoS1R4s6R2R3AccCh05-2-74R4R2R3

(4)

14

Ch05-2-(4)不是SLR(1)Follow(S)={#,a,b}2S→a.SbS→a.bS→.aSbS→.bSaS→.ab4S→b.SaS→.aSbS→.bSaS→.ab3S→aS.b5S→ab.S→b.SaS→.aSbS→.bSaS→.abb4S→aSb.Sb0Z→.SS→.aSbS→.bSaS→.abS1Z→S.ab

(5)

Ch05-2-(5)不是SLR(1)Follow(R)={#,a}1Z→S.S→S.abS0Z→.SS→.SabS→.bRb4S→b.RR→.SR→.aS→.SabS→.bRRS5S→bR.4R→S.S→S.aba2S→Sa.bb3S→Sab.

(6)

Ch05-2-(6)是SLR(1)20bB→b.Z→.SS→.SABbS→.BA3BS→B.AB→.bA→.aASA→.B1B→.bZ→S.aS→S.ABb2A→.aAA→.BB5B→.bA8S→SA.B9BB→.bS→SAB.ABa4S→BA.A→B.5B6A→a.AA→.aAA→.BB→.b2bAaB7A→aA.b

15

actionaZ→S (1)S→SAB (2)S→BA (3)A→aA (4)A→B (5) B→b (6)S0S1S2S3S4S5S6S7S8S9s6R6s6R3R5s6R4R2bs2s2R6s2R3R5s2R4s2R2#AccR6R3R5gotoAB385Ch05-2-745S17R459R2

(7)

Ch05-2-(7)不是SLR(1)Follow(A)={a,b} Follow(B)={a,b}0Z→.SS→.AaAbS→.BbBaA→.B→.SAB1Z→S.2S→A.aAb3S→B.bBa4S→Aa.AbaA→.b5S→Bb.BaB→.A6S→AaA.b7S→BbB.a8bS→AaAb.9aS→BbBa.B

(8) Ch05-2-(8)不是SLR(1) Follow(B)={a,e}a3A→a.ABeA→.aABeA→.BaB→.dBB→.B4A→B.a5B→d.BB→.dBB→.6A→aA.BeB→.dBB→.7A→aAB.ee8A→aABe.d1Z→A.A0Z→.AA→.aABeA→.BaB→.dBB→.ABaBdadB9A→Ba.d10B→dB.

3. 设有下列文法:

S?aAd | bBd | aBe | bAe A?g B?g

说明该文法是LR(1)文法,但不是LALR(1)文法。 答:

16

联系客服:779662525#qq.com(#替换为@)