編譯原理第4章習(xí)題答案.pptx

1、編譯原理習(xí)題答案-第4章,作業(yè)7： P119 4.2.1 P120 4.2.2(3) 4.2.3 作業(yè)8： P126 4.3.1 4.3.2(1) 作業(yè)9： P136 4.4.3 作業(yè)10： P136 4.4.1（3） P142 4.5.2(3) 4.5.3(2),4.2.1 考慮上下文無關(guān)文法： 以及串 1）給出這個(gè)串的一個(gè)最左推導(dǎo)。 2）給出這個(gè)串的一個(gè)最右推導(dǎo)。,第四章 語法分析,3）給出這個(gè)串的一棵語法分析樹。 4）這個(gè)文法是否為二義性的？證明你的回答。 該文法不是二義性的。因?yàn)閷τ谖姆óa(chǎn)生的每一個(gè)符號串，不存在兩棵不同的分析樹（或兩種不同的最左或最右推導(dǎo)）。 5）描述這個(gè)文法生成的語

2、言。 以a為變量，+和*為二元操作符的后綴表達(dá)式的集合,4.2.2 3）考慮上下文無關(guān)文法： 以及串()()。 ）給出這個(gè)串的一個(gè)最左推導(dǎo)。 ）給出這個(gè)串的一個(gè)最右推導(dǎo),）給出這個(gè)串的一棵語法分析樹。,4）這個(gè)文法是否為二義性的？證明你的回答。 該文法是二義性的文法。 如串 ()() 對應(yīng)著兩棵不同的語法分析樹。 5）描述這個(gè)文法生成的語言。 括號的匹配，包括空串。,4.2.3 為下面的語言設(shè)計(jì)文法： 1）所有由0和1組成的并且每個(gè)0之后都至少跟著一個(gè)1的串的集合。 2）所有由0和1組成的回文的集合，也就是從前面和從后面讀結(jié)果都相同的串的集合。 3）所有由0和1組成的具有相同多個(gè)0和1的串的集

3、合。,4）所有由0和1組成的并且0的個(gè)數(shù)和1的個(gè)數(shù)不同的串的集合。 S A| B A AA | E0E （A是0比1多的串） B BB | E1E （B是1比0多的串） E 0E1E | 1E0E | （E是0和1的個(gè)數(shù)相等的串） 5）所有由0和1組成的且其中不包含子串011的串的集合。 6）所有由0和1組成的形如xy的串的集合，其中 且x和y等長。 S AB | BA A XAX | 0 （A是奇數(shù)長度，中間為0的串） B XBX | 1 （B是奇數(shù)長度，中間為1的串） X 0 | 1,4.3.1 下面是一個(gè)只包含符號a和b的正則表達(dá)式的文法。它使用+替代表示并運(yùn)算的字符“”，以避免和文法中

4、作為元符號使用的豎線相混淆： 1）對這個(gè)文法提取左公因子。,）提取左公因子的變換能使這個(gè)文法適用于自頂向下的語法分析技術(shù)嗎？ 不可以。文法中依然存在左遞歸。 ）提取左公因子之后，從原文法中消除左遞歸。 ）得到的文法適用于自頂向下的語法分析嗎？ 適用。因?yàn)槲姆ㄖ胁淮嬖谧蠊蜃?，也不存在左遞歸。,4.3.2 1) S- SS+|SS*|a a.提取左公因子：S-SSA|a A-+|* b.提取左公因子的變換能使這個(gè)文法適用于自頂向下的語法分析技術(shù)嗎？ 不可以。文法中依然存在左遞歸。 c.消除左遞歸：S-aS S-SAS| A-+|* d.得到的文法適用于自頂向下的語法分析嗎？ 適用。因?yàn)槲姆ㄖ胁淮?/p>

5、在左公因子，也不存在左遞歸,S-aS S-aSAS| A-+|*,代入,A A | 改寫為 A A A A | ,4.4.3 S-SS+|SS*|a FIRST(S)=a 因?yàn)镾是起始符號，把$加入到Follow(S)中。 對于S-SS+的第一個(gè)S，把First(S+) = a加入到Follow(S)中。 對于S-SS*的第一個(gè)S，把First(S*) = a加入到Follow(S)中。 對于S-SS+的第二個(gè)S，把First(+) = +加入到Follow(S)中。 對于S-SS*的第二個(gè)S，把First(*) = *加入到Follow(S)中。 所以，F(xiàn)OLLOW(S)=a,+,*,$ 僅

6、消除左遞歸后的文法： FIRST(S)=a ，F(xiàn)IRST(S)=a, FOLLOW(S)=FOLLOW(S)=+,*,$,題目中并沒有要求我們消除左遞歸，所以第一個(gè)答案才是符合要求的。,下頁還有內(nèi)容。,S-aS S-aSAS| A-+|*,4.3.2 1)中，我們先提取左公因子， 然后消除左遞歸后，并代入，得到如下的文法，詳見前兩頁的ppt。,First(S) = First(aS)=a First(S)= First(aSAS) First()= a = a, First(A) = +,* Follow(S) =$ 因?yàn)?S-aS，所以把Follow(S)加入到Follow(S)中。 因?yàn)?

7、S-aSAS的第一個(gè)S ，所以把First(AS)=+,*加入到Follow(S)中。 因?yàn)?S-aSAS的第二個(gè)S ，所以Follow(S)加入到Follow(S)中。 所以，F(xiàn)ollow(S)= $, +,* 對 S-aSAS的A ，當(dāng)A后面的S推導(dǎo)出非空時(shí)，把First(S)-=a加入到Follow(A)中。 對 S-aSAS的A ，當(dāng)A后面的S推導(dǎo)出空時(shí)，把Follow(S)=$,+,*加入到Follow(A)中。 所以，F(xiàn)ollow(A)= a, +,*,$ 對于S-aSAS|，因?yàn)镕irst(aSAS) Follow(S)=a $,+,*=空集,所以沒有沖突。 對于A-+|*，因?yàn)?/p>

8、First(+) First(*)=+ *=空集,所以沒有沖突。 所以該文法是LL(1)文法。,A A | 改寫為 A A A A | ,此時(shí)， =(S)S = ,4.4.1 3) S-S(S)S| 消除左遞歸：S- S S-(S)SS| 即 S- S S-(S)SS| ,First(S)= (, First(S) = First(S)= (, 因?yàn)镾是起始符號，所以把$加入到Follow(S)中。 由S-(S)SS的第一個(gè)S，將)加入到Follow(S)中。 由S-(S)SS的第二個(gè)S，將First(S)- 加入到Follow(S) 將Follow(S)加入到Follow(S) 由S-S，將

9、Follow(S)加入到Follow(S)中。 所以，F(xiàn)ollow(S)=Follow(S)= (, ),$ 但是，F(xiàn)irst( (S)SS) Follow(S) = ( ,所以不是LL(1)文法。,預(yù)測分析表,沖突,Follow(S)=Follow(S)= (, ),$ ,First( (S)SS) = （ ,S- S S-(S)SS| ,仔細(xì)分析后，發(fā)現(xiàn)該文法 S-S(S)S| 是二義性文法。 二義性文法不可能是LL(1)文法。 例如：( ) ( ),S,S,(,S,),S,S,S,(,S,),S,S,(,S,),S,S,(,S,),S,對于改造后的文法 S- S S-(S)SS| 也可以畫出兩棵句法分析樹。,“句柄”是和某個(gè)產(chǎn)生式 體匹配的子串，對它的 歸約代表了相應(yīng)的最右 推導(dǎo)的一個(gè)反向步驟。,4.5.2 2）對文法 和