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

《編譯原理第4章習(xí)題答案.pptx》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、編譯原理習(xí)題答案-第4章作業(yè)7：P1194.2.1P1204.2.2(3)4.2.3作業(yè)8：P1264.3.14.3.2(1)作業(yè)9：P1364.4.3作業(yè)10：P1364.4.1（3）P1424.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)閷?duì)于文法產(chǎn)生的每一個(gè)符號(hào)串，不存在兩棵不同的分析樹（或兩種不同的最左或最右推導(dǎo)）。5）描述這個(gè)文法生成的語言。以

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

3、相同多個(gè)0和1的串的集合。4）所有由0和1組成的并且0的個(gè)數(shù)和1的個(gè)數(shù)不同的串的集合。S?A

4、BA?AA

5、E0E（A是0比1多的串）B?BB

6、E1E（B是1比0多的串）E?0E1E

7、1E0E

8、?（E是0和1的個(gè)數(shù)相等的串）5）所有由0和1組成的且其中不包含子串011的串的集合。6）所有由0和1組成的形如xy的串的集合，其中且x和y等長。S?AB

9、BAA?XAX

10、0（A是奇數(shù)長度，中間為0的串）B?XBX

11、1（B是奇數(shù)長度，中間為1的串）X?0

12、14.3.1下面是一個(gè)只包含符號(hào)a和b的正則表達(dá)式的文法。它使用+替代表示并運(yùn)算的字符“｜”，以避

13、免和文法中作為元符號(hào)使用的豎線相混淆：1）對(duì)這個(gè)文法提取左公因子。２）提取左公因子的變換能使這個(gè)文法適用于自頂向下的語法分析技術(shù)嗎？不可以。文法中依然存在左遞歸。３）提取左公因子之后，從原文法中消除左遞歸。４）得到的文法適用于自頂向下的語法分析嗎？適用。因?yàn)槲姆ㄖ胁淮嬖谧蠊蜃?，也不存在左遞歸。4.3.21)S->SS+

14、SS*

15、aa.提取左公因子：S->SSA

16、aA->+

17、*b.提取左公因子的變換能使這個(gè)文法適用于自頂向下的語法分析技術(shù)嗎？不可以。文法中依然存在左遞歸。c.消除左遞歸：S->aS’S’->SAS’

18、?A->+

19、*d.得到的

20、文法適用于自頂向下的語法分析嗎？適用。因?yàn)槲姆ㄖ胁淮嬖谧蠊蜃?，也不存在左遞歸S->aS’S’->aS’AS’

21、?A->+

22、*代入A?A?

23、?改寫為A??A?A???A?

24、?4.4.3S->SS+

25、SS*

26、aFIRST(S)={a}因?yàn)镾是起始符號(hào)，把{$}加入到Follow(S)中。對(duì)于S->SS+的第一個(gè)S，把First(S+)={a}加入到Follow(S)中。對(duì)于S->SS*的第一個(gè)S，把First(S*)={a}加入到Follow(S)中。對(duì)于S->SS+的第二個(gè)S，把First(+)={+}加入到Follow(S)中。對(duì)于S->

27、SS*的第二個(gè)S，把First(*)={*}加入到Follow(S)中。所以，F(xiàn)OLLOW(S)={a,+,*,$}僅消除左遞歸后的文法：FIRST(S)={a}，F(xiàn)IRST(S')={a,?}FOLLOW(S)=FOLLOW(S')={+,*,$}題目中并沒有要求我們消除左遞歸，所以第一個(gè)答案才是符合要求的。下頁還有內(nèi)容。S->aS’S’->aS’AS’

28、?A->+

29、*4.3.21)中，我們先提取左公因子，然后消除左遞歸后，并代入，得到如下的文法，詳見前兩頁的ppt。First(S)=First(aS’)={a}First(S’)=Fir

30、st(aS’AS’)∪First(?)={a}∪{?}={a,?}First(A)={+,*}Follow(S)={$}因?yàn)镾->aS’，所以把Follow(S)加入到Follow(S’)中。因?yàn)镾’->aS’AS’的第一個(gè)S’，所以把First(AS’)={+,*}加入到Follow(S’)中。因?yàn)镾’->aS’AS’的第二個(gè)S’，所以Follow(S)加入到Follow(S’)中。所以，F(xiàn)ollow(S’)={$,+,*}對(duì)S’->aS’AS’的A，當(dāng)A后面的S’推導(dǎo)出非空時(shí)，把First(S’)-{?}={a}加入到Follow(A)

31、中。對(duì)S’->aS’AS’的A，當(dāng)A后面的S’推導(dǎo)出空時(shí)，把Follow(S’)={$,+,*}加入到Follow(A)中。所以，F(xiàn)ollow(A)={a,+,*,$}對(duì)于S’-