编译原理第二次小作业

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)

2、= a, Follow(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(

3、S) = #First(A) = aFollow(A) = bFirst(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,

4、S) (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 | B B idt | 请分别写出下列句型的句柄。(1) aidtcBcAb答：树形图如下：句柄：BcA(2) aidtccb答：树形图如下：句柄：(3) ab答：树形图

5、如下：黄色部分即为句柄：(4) aidtb答：树形图如下：句柄：或idt4. 写出如下文法的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,

6、 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 ),CLOSURE (S b.S, S .aS, S .bS

7、, S .a ),CLOSURE (S aS.), CLOSURE (S bS.),(2)S (L) | aL L,S | S答：设该文法的拓广文法为：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 (

8、L S.), CLOSURE (S L,.S, S .(L), S .a), CLOSURE (S (L).),CLOSURE (S L,S.)所以项目集规范族为：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 (

9、S L,S.)5. 写出如下文法的LR(0)自动机。S SS | (S) | a答：该文法的拓广文法的LR(0)自动机的状态表如下：L0S' .S S .SS S .(S) S .aL1S' S. S S.S 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*L1L4L2L3

10、L2L5L2L3*L3*L4L4L2L3L5L4L2L6L3*L66. 试为如下文法构造SLR(1)语法分析表, 要求画出LR(0)自动机。bexpr bexpr or bterm | bterm bterm bterm and 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

11、 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, (, true, falseFollow(S) = #, or, )First(A) = not, (, true, falseFollow(A) = #, or, ), andFirst(B) = not, (, true, falseFollow(B) = #, or, ), andLR(0)自动机的状态表如下：(# - 起始状态，* - 终结状态)

12、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 ) B .true B .false*L6B true.*L7B false.L8S S or. A A .A and B A .BB .not B

13、B .( S ) B .true B .falseL9A A and .B B .not B B .( S ) B .true B .false*L10B not B.L11B ( S .) S S .or A*L12S S or A. A A .and B*L13A A and B.*L14B ( S ).SLR(1)语法分析表如下：栈顶状态ACTIONGOTOorandnottruefalse()#SAB0s4s6s7s51231s8acc2r3s9r3r33r5r5r5r54s4s6s7s5105s4s6s7s511236r8r8r8r87r9r9r9r98s4s6s7s51239s4s

14、6s7s51310r6r6r6r611s8s1412r2s9r2r213r4r4r4r414r7r7r7r7LR(0)自动机如下：(绿色：起始状态；蓝色：指针；黄色：终结状态)7. 证明文法S A a A b | B b B aA B 是LL(1)文法，但不是SLR(1)文法。答：First(S) = a, bFollow(S) = #First(A) = Follow(A) = a, bFirst(B) = Follow(B) = a, bFor S: First(A a A b) First(BbBa) = a b = Ø由上验证：该文法是LL(1)文法。下证该文法不是SLR(1)文法：该文法的拓广文法为：(1)S