资源描述：
《编译原理试题及答案(二)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、编译原理参考答案程序设计语言Chapter4.自上而下语法分析2021/7/15CH.4.练习题1(P81.)1.考虑下面文法G1:S→a
2、^
3、(T)T→T，S
4、S(1)消去G1的左递归。然后对每个非终结符,写出不带回溯的递归子程序。解(1)消左后的文法G1’:S→a
5、^
6、(T)T→ST’T’→,ST’
7、ε2021/7/15CH.4.练习题1(P81.)解(1)不带回溯的递归子程序:S→a
8、^
9、(T)ProcedureS;Beginifsym=‘a’orsym=‘^’thenadvanceelseifsym=‘(‘thenbegin
10、advance;T;ifsym=‘)’thenadvanceelseerrorendelseerrorEnd;CH.4.练习题1(P81.)解(1)不带回溯的递归子程序:T→ST’ProcedureT;BeginS;T’end;解(1)不带回溯的递归子程序:T’→,ST’
11、εprocedureT’;beginifsym=‘,’thenbeginadvance;S;T’endEnd;CH.4.练习题1(P81.)(2)经改写后的文法是否是LL(1)的?给出它的预测分析表。消左后的文法G1’:S→a
12、^
13、(T)T→ST’T’→,ST’
14、
15、ε(2)因为G1’:①文法不含左递归;②对S→a
16、^
17、(T)FIRST(a)={a},FIRST(^)={^},FIRST((T))={(},集合互不相交且不含ε;③对T’→,ST’
18、εFIRST(,ST’)={,},FIRST(ε)={ε},其交集为空。但ε∈FIRST(T’)=FIRST(,ST’)∩FIRST(ε)={，,ε},然而，FOLLOW(T’)={)}FIRST(T’)={，,ε}，两者不相交。所以，G1’是LL(1)文法。CH.4.练习题1(P81.)(2)构造G1’的预测分析表:①对S→a
19、^
20、(T)②对T→ST
21、’FIRST(a)={a}FIRST(ST’)={a,^,(}FIRST(^)={^}③对T’→,ST’
22、εFIRST((T))={(}FIRST(,ST’)={,}预测分析表:FOLLOW(T’)={)}a^(),#SS→aS→^S→(T)TT→ST’T→ST’T→ST’T’T’→εT’→,ST’2021/7/15CH4.1.(3)给出对符号串(a，^)的分析过程步骤符号栈输入串动作,所用产生式.0#S(a,^)#初始；用S,(查表1#)T((a,^)#S→(T),展开S2#)Ta,^)#匹配(；用T,a查表3#)T’Sa,^)#
23、T→ST’,展开T;用S,a查表4#)T’aa,^)#S→a,展开S5#)T’,^)#匹配a;用T’,,查表6#)T’S,,^)#T’→,ST’,展开T’7#)T’S^)#匹配,；用S,^查表8#)T’^^)#S→^,展开S9#)T’)#匹配^；用T’,)查表10#))#T’→ε,展开T’11##匹配)12##分析成功,结束分析CH.4.练习题3(P82.)3.下面文法中,哪些是LL(1)的,说明理由。(1)S→ABcA→a
24、εB→b
25、ε。解，因为FOLLOW(S)={#}①文法不含左递归;FIRST(S)={a,b,c}②对A→a
26、
27、ε候选式的FIRST集合互不相交;ε∈FIRST(A)但,FOLLOW(A)={b,c}FIRST(A)={a,ε}两者不相交。③B→b
28、ε其候选式的FIRST集合互不相交;ε∈FIRST(B)但，FOLLOW(B)={c}FIRST(B)={b,ε}两者也不相交。所以，文法是LL(1)文法。CH.4.练习题3(P82.)3.下面文法中,哪些是LL(1)的,说明理由。(2)S→AbA→a
29、B
30、εB→b
31、ε。解(1)因为FOLLOW(S)={#}对A→a
32、B
33、ε;FIRST(S)={a,b}FIRST(B)={b,ε}与FIRST(
34、ε)={ε}相交;所以文法不是LL(1)文法。解(2)对A→a
35、ε因为ε∈FIRST(A)={a,b,ε}，FOLLOW(A)={b},FOLLOW和FIRST两者相交。所以文法不是LL(1)文法。CH.4.练习题3(P82.)3.下面文法中,哪些是LL(1)的,说明理由。(3)S→ABBAA→a
36、εB→b
37、ε。解，虽然FOLLOW(S)={#}①文法不含左递归;FIRST(S)={a,b,ε}②对A→a
38、ε，其候选式的FIRST集合不相交;对B→b
39、ε，其候选式的FIRST集合也不相交;但对A→a
40、ε（由B→b
41、ε出发证明也可）F
42、OLLOW(A)={a,b,#},FIRST(A)={a,ε}两者相交。所以，文法不是LL(1)文法。CH.4.练习题3(P82.)3.下面文法中,哪些是LL(1)的,说明理由。(4)S→aSe
43、BB→bBe
44、CC→cCe
45、d。解，因
