编译原理第4章习题答案

1、FIRST()是从推导出的串的起始终结符的集合。FIRST(FIRST( ) = ) = a a | | a a, a a V VT T 特别是， 时，规定FIRST(FIRST( ) ) 例如：A xB|yC，First(xB)=x, First(yC)=y， First(A)=First(xB)First(yC) = x, yFOLLOW(A)是在所有句型中紧跟在A后面的终结符集合。FOLLOW(A) = a|S Aa，a V VT TS AaAa 约定：如果A是某个句型的最右符号（SA），那么$属于FOLLOW(A) 。 因为 S$ A$，可见$在A之后。“句柄”是和某个产生式体匹配的子

2、串，对它的归约代表了相应的最右推导的一个反向步骤。4.5.2 2）对文法 和最右句型SS+a*a+，找出该最右句型的句柄。下面给出最右推导得到最右句型SS+a*a+的过程： aSSSSS|*| * * * aaSSaSaaSSSaSSS4.5.3 对于下面的输入符号串和文法，说明相应的自底向上语法分析过程。1）文法： 输入串：000111自底向上语法分析过程：01| 10SS 2）文法： 输入串：aaa*a+ 自底向上语法分析过程： aSSSSS| *|4.6.2 为文法 构造SLR项集。计算这些项集的GOTO函数。给出这个文法的语法分析表。这个文法是SLR文法吗？aSSSSS|*|010:*

3、:(, )*ISSSSSSSSSaIGOTO ISSSSSSSSSSSSSSSSa2031:(, ):( , )*IGOTO IaSaIGOTO I SSSSSSSSSSSSSSSSSSSSa1243533332( , ):( , ):( ,*)*( , )( , )GOTO I aIIGOTO ISSSIGOTO ISSSGOTO I SIGOTO I aISLR项集0:*ISSSSSSSSSa1:*ISSSSSSSSSSSSSSSa2:ISa3:*ISSSSSSSS SSS SSSSSSSSa4:ISSS5:*ISSSaaS+*SSa状态ACTIONGOTOa + * $ S012345s

4、2 s2 accr4 r4 r4 r4s2 s4 s5r2 r2 r2 r2r3 r3 r3 r3 1 3 3(1)将$加入到Follow(S)中。(2)因为SS+的第一个S，将First(S+)=a添加到Follow(S)中。(3)对SS*同理，求First(S*)=a。(4)因为SS+的第二个S，将First(+)=+添加到Follow(S)中。(5)对SS*同理，求First(*)=*。aSSSSSS )4* )3SSS 2) ) 1语法分析表：是SLR文法，不存在移进-归约和归约-归约冲突。 增广文法增广文法First(S)= First(SS+) First(SS*) First(a

5、) = aFollow(S)a,+,*,$4.6.3 处理输入串aa*a+时的动作：栈符号输入动作(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)00201012013013501012013013401aSSaSSSS*SSaSSSS+Saa*a+$a*a+$a*a+$*a+$*a+$a+$a+$+$+$移入根据(4)归约移入根据(4)归约移入根据(3)归约移入根据(4)归约移入根据(2)归约接受4.6.5 说明下面的文法是LL(1)的，但不是SLR(1)的。FIRST(A)=FIRST(B)= FIRST(AaAb) = a, FIRST(BbBa) = bFIRST

6、(S) = FIRST(AaAb) FIRST(BbBa)=a,bFOLLOW(S)=$， FOLLOW(A)=FOLLOW(B)=a,b语法分析表：是LL(1)文法。A |SAa b BbBaABBABbBaSAaAbSSS )5 )4 ) 3 )2 ) 1aAbASAIGOTOISSSIGOTOIBABbBaSAaAbSSSI),( :),( :02010BBaBbSbIGOTOIAAbAaSaIGOTOIbBaBSBIGOTOI),( :),( :),( :352403BbBaSaIGOTOIAaAbSbIGOTOIaBbBSBIGOTOIbAaASAIGOTOI),( :),( :),

7、( :),( :79685746增广文法增广文法SLR项集族项集族 FOLLOW(A)=FOLLOW(B)=a,b状态ACTIONGOTOa b $ S A B0123456789r4/r5 r4/r5 accs4 s5 r4 r4 r5 r5 s8 s9 r2 r3 1 2 3 6 7语法分析表：不是SLR(1)文法。存在归约-归约冲突。 FOLLOW(A)=FOLLOW(B)=a,b4.6.6 说明下面的文法是SLR(1)，但不是LL(1)的。FIRST(A)=FIRST(a)=aFIRST(S)=FIRST(SA) FIRST(A)=aFOLLOW(S) =a,$FOLLOW(A)=a,

8、$语法分析表：不是LL(1)文法，因为存在重复表项。aAASAS|因为 FIRST(SA)=a FIRST(A)=aaAASSASSS )4 )3 )2 ) 1增广文法增广文法0:ISSSSASAAa1:ISSSSAAa2:ISA3:IAa4:ISSASaAAa状态ACTIONGOTO a $ S A01234s3 s3 accr3 r3r4 r4r2 r2 1 2 4 语法分析表：是SLR(1)文法，不存在移进-归约和归约-归约冲突。 FOLLOW(S) =a,$FOLLOW(A) =a,$4.7.1 为文法 构造：1）规范LR项集族。aSSSSS|*|aSSSSSSSSS*$/,:/*,/

9、*,/*,$/*,$/,$:$/,$/*,$/,$:210aaSIaaSaSSSaSSSaSSSaSSSSSIaaSaSSSaSSSSSI$/,*:$/,:/*,:/*,/*,/*,/*,/*,$/*,$/,:6543aSSSIaSSSIaaSIaaSaSSSaSSSaSSSaSSSaSSSaSSSIaSSSIaSSSIaaSaSSSaSSSaSSSaSSSaSSSaSSSI/*,*:9/*,:8/*,/*,/*,/*,/*,/*,/*,:7增广文法增广文法I2和I4I3和I7I5和I8I6和I9的核心一样。2）LALR项集族。375869:,/*/$*,/*/$,/*/*,/*/,/*/*,

10、/*/,/*/:,/*/$:* ,/*/$ISSSaSSSaSSSaSSSaSSSaSSSaSaaISSSaISSSa 0124:,$, /$*, /$, /$:,$, /$*, /$,/*/*,/*/,/*/:,/*/$ISSSSSaSSSaSa aISSSSSaSSSaSSSaSSSaSaaISaa 4.7.4下面的文法下面的文法 S Aa | bAc | dc | bda A d是是 LALR(1)，但不是，但不是SLR(1). 1) SS 2) S Aa 3) S bAc 4) S dc 5) S bda 6) A dI0: S S, $S Aa , $S bAc , $S dc ,

11、$S bda , $A d , aI4: S d c , $ A d , aI1: S S ,$I2: S A a , $I3: S b Ac , $S b da , $A d ,c构造LR（1）项目集：I5: S A a , $I6: S bA c , $I7: S bd a , $ A d ,cI8: S d c , $I9: S bAc , $I10: S bd a , $SAdbcadAac文法：1) SS 2) S Aa 3) S bAc 4) S dc 5) S bda 6) A d状态ACTIONGOTOa b c d $ S A012345678910 s3 s4 accs5

12、s7r6 s8 r2 s9s10 r6 r4 r3 r5 1 2 6 语法分析表：是LALR(1)文法，不存在移进-归约和归约-归约冲突。 构造LR（0）项目集：I0: S SS Aa S bAcS dc S bdaA d I1: S S I2: S A aI3: S b AcS b da A d I4: S d c A d I5: S A a I6: S bA c I7: S bd a A d I8: S d c I9: S bAc I10: S bd a Follow(A) = a, c移进/归约冲突不是SLR(1)。状态ACTIONGOTOa b c d $ S A4 s8/r6 文法：

13、1) SS 2) S Aa 3) S bAc 4) S dc 5) S bda 6) A d4.7.5下面的文法S Aa | bAc | Bc | bBaA dB d是LR(1)，但不是LALR(1).构造LR（1）项目集：I0: S S, $S Aa , $S bAc , $S Bc , $S bBa , $A d ,aB d ,cI1: S S , $I2: S A a , $I3: S b Ac , $S bBa , $A d ,cB d ,aI4: S B c , $ I5: A d , a B d , cI6: S A a , $I7: S bA c , $I8: S bBa , $

14、I9: A d , c B d , a I10: S B c , $I11: S bAc , $I12: S bB a , $状态ACTIONGOTOa b c d $ S A B0123456789101112 s3 s5 accs6 s9 s10r6 r7 r2 s11s12r7 r6 r4 r3 r5 1 2 4 7 8 语法分析表：是LR(1)文法，不存在移进-归约和归约-归约冲突。 构造LALR（1）项目集：I0: S S, $S Aa , $S bAc , $S Bc , $S bBa , $A d ,aB d ,cI1: S S , $I2: S A a , $I3: S b A

15、c , $S bBa , $A d ,cB d ,aI4: S B c , $ I5: A d , a B d , cI6: S A a , $I7: S bA c , $I8: S bBa , $I9: A d , c B d , a I10: S B c , $I11: S bAc , $I12: S bB a , $I59: A d , a/c B d , a/c归约-归约冲突。不是LALR(1)。4.8.2 为下面的文法构造LR语法分析表stmt if e then stmt | if e then stmt else stmt | while e do stmt | begin li

16、st end | slist list; stmt | stmt令 i = if e then;j = else; w = while e do; b = begin; d = end; L = list; S = stmt.则文法可表示如下：1） S S2)S iS3)S iSjS4)S wS5)S bLd6)S s7)L L;S8)L S构造其LR(0)项目集：I0:S S S iS S iSjS S Ws S bLd S sI1:S SI2:S iS S iSjS S iS S iSjS S Ws S bLd S sI3:S WS S iS S iSjS S Ws S bLd S sI4:S bLd L L;S L S S iS S iSjS S Ws S bLd S sI5:S sI6:S iS S iSjSI7:S wSI8:S bLd L L;SI9:S iSjS S iS S iSjS S Ws S bLd S sI10:S bLdI11:L L;S S iS S iSjS S Ws S bLd S sI12:S iSjS I13:L L;SI14:L SFOLLOW(S)=j, d, ;, $FOLLOW(L)= d, ; 对于I6状态中可能