《编译原理第二次小作业》由会员分享，可在线阅读，更多相关《编译原理第二次小作业（15页珍藏版）》请在金锄头文库上搜索。
1、Homework 2向首兴20140134211. 对于一个文法若消除了左递归、提取了左公因子后是否一定为LL(1)文法？试对下面文法进行改写，并对改写后的文法进行判断。(1)A aABe | aB Bb | d答：对该文法消除左递归：B Bb | d= B dCC bC | 对该文法提取左公因子：A aABe | a=A aDD ABe | 改写后的文法：A aDB dCC bC | D ABe | First(A) = aFollow(A) = d, #First(B) = dFollow(B) = eFirst(C) = b, Follow(C) = eFirst(D) = a, Fol
2、low(D) = d, #For C: First(bC) First() = b = First(bC) Follow(C) = b e = For D: First(ABe) First() = a = First(ABe) Follow(D) = a d, # = 由上验证：该文法是LL(1)文法。(2)S Ab| BaA aA | aB a答：该文法没有左递归；对该文法提取左公因子：A aA | a=A aCC A | 改写后的文法：S Ab| BaA aCB aC A | First(S) = aFollow(S) = #First(A) = aFollow(A) = bFirst(
3、B) = aFollow(B) = aFirst(C) = a, Follow(C) = bFor S: First(Ab) First(Ba) = a a = a 由上验证：该文法不是LL(1)文法。2. 给定文法G(S):S a | | (T)T T,S | 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) (T) S(3) (a,a),(a),a)答：(a,a),(a),a
4、) (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 | B B idt | 请分别写出下列句型的句柄。(1) aidtcBcAb答：树形图如下：句柄：BcA(2) aidtccb答：树形图如下：句柄：(3) ab答：树形图如下：黄色部分即为句柄：(4) aidtb答：树形图如下：句柄：或idt4
5、. 写出如下文法的LR(0)项目集规范族。(1)S aS | bS | a答：设该文法的拓广文法为：S SS aS | bS | a如下计算其LR(0)项目集规范族：C := CLOSURE (S .S)RepeatFor C 中每一项目集I和每一文法符号XDo if GO(I, X)非空且不属于CThen 把GO(I, X)放入C中Until C不再增大计算流程：C := CLOSURE (S .S, S .aS, S .bS, S .a) C := CLOSURE (S .S, S .aS, S .bS, S .a),CLOSURE (S S.),CLOSURE (S a.S, S a.,
6、 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 ),CLOSURE (S b.S, S .aS, S .bS, S .a ),CLOSURE (S aS.), CLOSURE (S bS.),(2)S (L) | aL L,S | S答：设该文法的拓广
7、文法为：S SS (L) | aL L,S | 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.),CLOSURE (L S.), CLOSURE (S L,.S, S .(L), S .a), CLOSURE (S (L).),CLOSURE (S L,S.)所以项目集规范族为：C := CLOSU
8、RE (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.),CLOSURE (L S.), CLOSURE (S L,.S, S .(L), S .a), CLOSURE (S (L).),CLOSURE (S L,S.)5. 写出如下文法的LR(0)自动机。S SS | (S) | a答：该文法的拓广文法的LR(0)自动机的状态表如下：L0S .S S .SS S .(S) S .aL1S S. S S.S
9、 S .SS S .(S) S .aL2S (.S) S .SS S .(S) S .aL3S a.L4S SS. S S.S S .SS S .(S) S .aL5S (S.) S S.S S .SS S .(S) S .aL6S (S).该文法的拓广文法的LR(0)自动机的状态转移表如下：(# - 起始状态，* - 终结状态)S()a#L0L1L2L3*L1L4L2L3L2L5L2L3*L3*L4L4L2L3L5L4L2L6L3*L66. 试为如下文法构造SLR(1)语法分析表, 要求画出LR(0)自动机。bexpr bexpr or bterm | bterm bterm bterm a
10、nd bfactor | bfactor bfactor not bfactor | ( bexpr ) | true | false 说明：bexpr, bterm, 和 bfactor为非终结符，其它符号为终结符。答：令S = bexpr, A = bterm, B = bfactor.该文法的拓广文法为：(1)S S(2)S S or A(3)S A(4)A A and B(5)A B(6)B not B(7)B ( S )(8)B true(9)B falseFirst(S) = not, (, true, falseFollow(S) = #First(S) = not, (, tr
11、ue, falseFollow(S) = #, or, )First(A) = not, (, true, falseFollow(A) = #, or, ), andFirst(B) = not, (, true, falseFollow(B) = #, or, ), andLR(0)自动机的状态表如下：(# - 起始状态，* - 终结状态)L0S .S S .S or A S .A A .A and B A .BB .not B B .( S ) B .true B .false*L1S S. S S. or A*L2S A. A A. and B*L3A B.L4B not .B B .not B B .( S ) B .true B .falseL5B ( .S ) S .S or A S .A A .A and B A .BB .not B B .( S
