UN编译原理习题课一.pdf

编译原理 朱雪峰博士 计算机科学与技术系 Tel: O) Email: xuefeng.zhu@cup.edu.cn 1 第一题（P36 第6题） 6. 令文法G 为 6 N →D | ND D→0|1|2|3|4|5|6|7|8|9 ① G 的语言L(G )是什么？ 6 6 ② 给出句子0127、34和568的最左推导和最右推导。 2 第一题（P36 第6题） 解： ① 根据产生式N →D | ND可以看出，N最终可以推出1个 或多个（可以是无穷多个）D ，根据产生式D→0|1|2 |3|4|5|6|7|8|9可以看出，每个D可以推导出0~9 中的某 一个数字。因此，N最终推导出的就是由0~9这10个 数字组成的字符串。因此G 的语言L(G )就是由0~9这 6 6 10个数字组成的字符串。 3 第一题（P36 第6题） ② 句子0127、34和568的最左推导如下： N ⇒ND ⇒NDD ⇒NDDD ⇒DDDD ⇒0DDD ⇒01DD ⇒012 D ⇒0127 N ⇒ND ⇒DD ⇒3D ⇒34 N ⇒ND ⇒NDD ⇒DDD ⇒5DD ⇒56D ⇒568 4 第一题（P36 第6题） ② 句子0127、34和568的最右推导如下： N ⇒ND ⇒N7 ⇒ND7 ⇒N27 ⇒ND27 ⇒N127 ⇒D127 ⇒0127 N ⇒ND ⇒N4 ⇒D4 ⇒34 N ⇒ND ⇒N8 ⇒ND8 ⇒N68 ⇒D68 ⇒568 5 第二题（P36 第7题） 7. 写一个文法，使其语言是奇数集，且每个奇数 不以0开头。 解：首先分析题意，本题希望构造一个文法，由它产生的句 子是奇数，并且不以0开头，也就是说它的每个句子都 是以1、3、5、7、9 中的某个数结尾。如果数字只有一 位，则满足要求，如果有多位，则要求第1位不能是0， 而中间有多少位，每位是什么数字（必须是数字）则没 有什么要求，因此，我们可以把这个文法分3个部分来 完成。 6 第二题（P36 第7题） 解：引入几个非终结符，其中，一个用作产生句子的开头， 可以是1~9之间的数，不包括0 ；一个用来产生句子的结 尾，为奇数；另一个则用来产生以非0整数开头后面跟 任意多个数字的数字串。由此得到文法如下： G(S) ：D→1|3|5|7|9 A→2|4|6|8|D B→A|0 C→CB|A S→CD|D