资源描述：
《编译原理习题解答.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、本演示文稿可能包含观众讨论和即席反应。使用PowerPoint可以跟踪演示时的即席反应，在幻灯片放映中，右键单击鼠标请选择“会议记录”选择“即席反应”选项卡必要时输入即席反应单击“确定”撤消此框此动作将自动在演示文稿末尾创建一张即席反应幻灯片，包括您的观点。编译程序的设计原理与实现如何让计算机认识、理解和执行高级程序设计语言？龚俊2004年1月第5章习题解答1：【习题4.2】构造下述文法的递归子程序：G(S):S->aASb
2、Bd;A->cS
3、;B->bB
4、d【解】入口出口aerr2NEXT(w)Aerr1NEXT(w)NEXT(w)S子程序nn
5、nyy入口cNEXT(w)出口遇时nySbBdNEXT(w)yS入口bNEXT(w)出口nyBdNEXT(w)err3ynB子程序A子程序※是LL(1)文法!!第5章习题解答2：【习题5.2】已知文法：S->aASb①
6、Bd②A->cS③
7、④B->bB⑤
8、d⑥（1）求选择集合；证明是LL(1)文法；（2）构造LL(1)分析表。G(S):⑴select(①)={a}select(②)={b,d}⑶select(⑤)={b}select(⑥)={d}⑵select(③)={c}select(④)=follow(A)={a,b,d}abcd＃S①②②
9、A④④③④B⑤⑥【解】（1）求选择集合（2）LL(1)分析表:∵三对选择集合两两不相交!∴G(S)是LL(1)文法!第5章习题解答3：【习题5.3】P92_4.1；设有文法G(A):判断LL(1)?A->BCc①
10、gDB②;B->bCDE③
11、④;C->DaB⑤
12、ca⑥;D->dD⑦
13、⑧;E->gAf⑨
14、c⑩【解】select(①)=first(B)+first(C)={b,d,a,c};select(⑤)=first(D)+{a}={d,a};select(④)=follow(B)={a,c,d,f,g,#}follow(B)=first(C)
15、+follow(A)+follow(C)={a,c,d,f,g,#}follow(C)={c}+first(D)+first(E)={c,d,g}follow(D)={b}+follow(A)+first(E)+{a}={a,b,c,f,g,#}follow(A)={f,#}select(②)={g};select(③)={b};select(⑥)={c};select(⑦)={d};select(⑧)=follow(D)={a,b,c,f,g,#}select(⑨)={d};select(⑩)={c};※是LL(1)文法！第5章习题解答5：【习题
16、5.4】P92_4.3设有文法G(S):化为LL(1)文法！S->A;A->B
17、AiB;B->C
18、B+C;C->)A*
19、(【解】文法变换，消除左递归：A->B
20、AiB=>A->B{iB}或A->BA`;A`->iBA`
21、B->C
22、B+C=>B->C{+C}或B->CB`;B`->+CB`
23、整理后得：G`(S):S->A①；A->BA`②;A`->iBA`③
24、④B->CB`⑤;B`->+CB`⑥
25、⑦;C->)A*⑧
26、(⑨select(③)={i};select(④)={*,#};select(⑥)={+};select(⑦)={i,*,#};
27、select(⑧)={)};select(⑨)={(};⑴⑵⑶∵三对选择集合中，两两不相交！∴G`(S)是LL(1)文法！第5章习题解答6：【习题5.10】P94_4.10考虑文法：G(S)S->aA
28、bB;A->0A
29、1;B->0B
30、1⑴构造活前缀的DFA(即句柄识别器)【解】※扩展文法，编码：Z->S1(0)S->a2A3(1)
31、b4B5(2)A->06A7(3)
32、18(4)B->09B10(5)
33、111(6)①②③⑥⑦⑧⑨⑩0+SaA0OKr(1)r(3)r(4)r(2)bA1B0④0Br(5)r(6)111⑤011※活前缀的DFA(即句柄识
34、别器):∵句柄识别器(DFA)中无冲突状态！∴G(S)是LR(0)文法!⑵是LR(0)文法吗？第5章习题解答7：B10111099r(5)r(5)r(5)r(6)r(5)10S1SA7A3AOK1r(2)r(2)r(2)r(2)r(2)5b4a20B5111094r(4)r(4)r(4)r(4)r(4)8r(6)r(3)18r(1)181r(6)r(3)r(1)#066r(3)r(3)r(3)7r(6)r(6)r(6)11r(1)r(1)r(1)32B0ba06⑶G(S)的LR(0)分析表：第5章习题解答8：【习题5.12】P94_4.9设有文法G
35、(S):S->rD;D->D,i
36、i【解】⑴构造活前缀的DFA(即句柄识别器)※扩展文法，编码：Z->S1(0)S->r2
