资源描述：
《编译原理第二次小作业》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、Homework2向首兴20140134211.对于一个文法若消除了左递归、提取了左公因子后是否一定为LL(1)文法？试对下面文法进行改写，并对改写后的文法进行判断。(1)A→aABe
2、aB→Bb
3、d答：对该文法消除左递归：B→Bb
4、d=>B→dCC→bC
5、ε对该文法提取左公因子：A→aABe
6、a=>A→aDD→ABe
7、ε改写后的文法：A→aDB→dCC→bC
8、εD→ABe
9、εFirst(A)={a}Follow(A)={d,#}First(B)={d}Follow(B)={e}First(C)={b,ε}Follow(C)={e}First(D)={a,ε}
10、Follow(D)={d,#}ForC:First(bC)∩First(ε)={b}∩{ε}=ØFirst(bC)∩Follow(C)={b}∩{e}=ØForD:First(ABe)∩First(ε)={a}∩{ε}=ØFirst(ABe)∩Follow(D)={a}∩{d,#}=Ø由上验证：该文法是LL(1)文法。(2)S→Ab
11、BaA→aA
12、aB→a答：该文法没有左递归；对该文法提取左公因子：A→aA
13、a=>A→aCC→A
14、ε改写后的文法：S→Ab
15、BaA→aCB→aC→A
16、εFirst(S)={a}Follow(S)={#}First(A)={a}Fo
17、llow(A)={b}First(B)={a}Follow(B)={a}First(C)={a,ε}Follow(C)={b}ForS:First(Ab)∩First(Ba)={a}∩{a}={a}由上验证：该文法不是LL(1)文法。2.给定文法G(S):S→a
18、^
19、(T)T→T,S
20、S写出如下句型的最左归约。(1)(a,a)答：(a,a)→(S,a)→(T,a)→(T,S)→(T)→S(2)(a,(a,a))答：(a,(a,a))→(S,(a,a))→(T,(a,a))→(T,(S,a))→(T,(T,a))→(T,(T,S))→(T,(T))→(T,S)→
21、(T)→S(3)(((a,a),^,(a)),a)答：(((a,a),^,(a)),a)→(((S,a),^,(a)),a)→(((T,a),^,(a)),a)→(((T,S),^,(a)),a)→(((T),^,(a)),a)→((S,^,(a)),a)→((T,^,(a)),a)→((T,S,(a)),a)→((T,(a)),a)→((T,(S)),a)→((T,(T)),a)→((T,S),a)→((T),a)→(S,a)→(T,a)→(T,S)→(T)→S3.给定文法G(S):S→aAbA→BcA
22、BB→idt
23、ε请分别写出下列句型的句柄。(1)aid
24、tcBcAb答：树形图如下：句柄：BcA(1)aidtccb答：树形图如下：句柄：ε(2)ab答：树形图如下：黄色部分即为句柄：ε(3)aidtb答：树形图如下：句柄：ε或idt4.写出如下文法的LR(0)项目集规范族。(1)S→aS
25、bS
26、a答：设该文法的拓广文法为：S'→SS→aS
27、bS
28、a如下计算其LR(0)项目集规范族：C:={CLOSURE({S'→.S})}RepeatForC中每一项目集I和每一文法符号XDoifGO(I,X)非空且不属于CThen把GO(I,X)放入C中UntilC不再增大计算流程：C:={CLOSURE({S'→.S,S→.a
29、S,S→.bS,S→.a})}C:={CLOSURE({S'→.S,S→.aS,S→.bS,S→.a}),CLOSURE({S'→S.}),CLOSURE({S→a.S,S→a.,S→.aS,S→.bS,S→.a}),CLOSURE({S→b.S,S→.aS,S→.bS,S→.a}),CLOSURE({S→aS.}),CLOSURE({S→bS.}),}所以项目集规范族为：C:={CLOSURE({S'→.S,S→.aS,S→.bS,S→.a}),CLOSURE({S'→S.}),CLOSURE({S→a.S,S→a.,S→.aS,S→.bS,S→.a}),C
30、LOSURE({S→b.S,S→.aS,S→.bS,S→.a}),CLOSURE({S→aS.}),CLOSURE({S→bS.}),}(2)S→(L)
31、aL→L,S
32、S答：设该文法的拓广文法为：S'→SS→(L)
33、aL→L,S
34、S计算流程：C:={CLOSURE({S'→.S,S→.(L),S→.a})}C:={CLOSURE({S'→.S,S→.(L),S→.a}),CLOSURE({S'→S.}),CLOSURE({S→(.L),L→.L,S,L→.S,S→.(L),S→.a}),CLOSURE({S→a.}),CLOSURE({S→L.,S,S→(L.
35、)}),CLOSURE({L→S.})
