编译原理(第二版)清华大学张桂琴,吕映芝著答案编译原理(第二版)清华大学张桂琴,吕映芝著答案.pptVIP

第3章 作业 P3.8 G=({A,B,S},{a,b,c},P,S) P: S→Ac|aB A→a b B→b c 写出L(G[S])的全部元素。 2. 文法G[N]为： N→D|ND D→0|1|2|3|4|5|6|7|8|9 写出L(G[N])。 3. 为只包含数字、加号和减号的表达式，写文法。 4. 已知文法G[Z]: 5. 写文法，使其语言是偶正整数的集合。要求 （1）允许0打头 （2）不允许0打头 6. 已知文法G： 表达式 →项|表达式+项|表达式-项 项 →因子|项*因子|项/因子 因子 →(表达式)|I 给出 i+i*i 的推导和语法树。 E → T |E+T | E-T T → F |T*F | T/F F →(E) | i 6. E → T |E+T | E-T T → F |T*F | T/F F →(E) | i 6. E → T |E+T | E-T T → F |T*F | T/F F →(E) | i 7.证明下面的文法是二义的 E → i |(E) | EOE O → + | - | * | / 8. 下面文法是二义的吗？ G=({A,B,S},{a,b,c},P,S) P: S→Ac|aB A→a b B→b c 9. 考虑下面的上下文无关文法， S→SS* |SS+|a （1）表明通过此文如何生成串aa+a*，并构造语法树。 （2）该文法生成的语言是什么？ 10. 文法：S→S(S)S |ε （1）该文法生成的语言是什么？ （2）是二义的吗？ 14. 给出生成下述语言的上下文无关文法。 （1）{anbnambm|n,m ≥0} 14. 给出生成下述语言的上下文无关文法。 （2）{1n0m1m0n|n,m ≥0} 16. 给出生成下述语言的三型文法。 （1）{an|n ≥0} 19. 刻画语言的语法有几种方式？ 补充练习 给出生成下述语言的文法。 （1）{anbam|n ,m0} 构造文法实例（见第3章课件-p72） 给出生成下述语言的文法。 1.语言L={aibj|i≠j, i,j0} 思路：该语言可视为两个语言的并集： L1={aibj| ij0}， L2={aibj| ji0} 参考答案 (1) S?AC|CB A?aA|a B?bB|b C?aCb|ab （ C: a、b个数相等） ） * * 答： {abc} S A c b a 答： 非负整数的集合 N N D D N D 2 4 0 答： L→L+D| L-D | D D→0|1|2|3|4|5|6|7|8|9 L L D D L D 2 4 6 + - Z::=aZb Z::=a b 写出L(G[Z]). 答： L(G[Z])={anbn|n≥1} Z a b Z b a Z a b 答： （1） S→XYZ | 2 | 4 | 6 | 8|0S X→1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Z→0 | 2 | 4 | 6 | 8 Y→YX | Y0 |ε 答： （2）S→XYZ | 2 | 4 | 6 | 8 X→1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Z→0 | 2 | 4 | 6 | 8 Y→YX | Y0 |ε 5.1 允许0打头的非负偶数 S→DS |0 | 2 | 4 | 6 | 8 D→ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 5.2 不允许0打头的非负偶数 S→D1 A | 2 | 4 | 6 | 8 D1 →1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 A→D1A | 0A| 0 | 2 | 4 | 6 | 8 （1）与5.1的区别在于： 一个没有0，一个有0。 E T + E F * T T i F F i i E?E+T?T+T?F+T?i+T?i+T*F ? i+F*F ?i+i*F? i+i*i i+i*i i+(i+i) E T F i T + E ) E ( F T + E T F i F F i F i+i*i