UN_编译原理(习题课)(一).pdf

1 编译原理 朱雪峰朱雪峰博士博士 计算机科学与技术系计算机科学与技术系 Tel 89733787 O Email xuefeng zhu 2 第一题 第一题 P36 第第6题 题 6 令文法G6为 N D ND D 0 1 2 3 4 5 6 7 8 9 G6的语言L G6 是什么 给出句子0127 34和568的最左推导和最右推导 3 第一题 第一题 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个 数字组成的字符串 因此G6的语言L G6 就是由0 9这 10个数字组成的字符串 4 第一题 第一题 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 5 第一题 第一题 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 6 第二题 第二题 P36 第第7题 题 7 写一个文法 使其语言是奇数集 且每个奇数 不以0开头 解 首先分析题意 本题希望构造一个文法 由它产生的句 子是奇数 并且不以0开头 也就是说它的每个句子都 是以1 3 5 7 9中的某个数结尾 如果数字只有一 位 则满足要求 如果有多位 则要求第1位不能是0 而中间有多少位 每位是什么数字 必须是数字 则没 有什么要求 因此 我们可以把这个文法分3个部分来 完成 7 第二题 第二题 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 8 第三题 第三题 P36 第第8题 题 8 令文法为 E T E T E T T F T F T F F E i 给出i i i i i i 的最左推导和最右推导 给出i i i i i i和i i i的语法树 9 第三题 第三题 P36 第第8题 题 解 1 最左推导为 E E T T T F T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i 2 最右推导为 E E T E T F E T i E F i E i i T i i F i i i i i E T T F T E T E T T E F T E i T T i T F i T i i F i i i i i 10 第三题 第三题 P36 第第8题 题 2 i i i i i i和i i i的语法树分别如下 11 第四题 第四题 P36 第第9题 题 9 证明下面的文法是二义的 S iSeS iS i 证明 根据文法二义性的定义 如果要证明该文法是二义的 必须找到一个句子 使得该句子具有两个不同的最右 推导或两个不同的语法树 我们首先分析这个文法 根 据我们对程序设计语言的了解 不难发现 这个文法应 该是用来表示if else 结构的 用 i 代表 if 或语句集 e 代表 else 因此我们就要到if else 结构中去 找二义性 12 第四题 第四题 P36 第第9题 题 我们知道 程序语言一般都规定else部分是和它前面离 它最近的没有被匹配的if语句进行匹配 而上面这个文 法体现不出这种限制 因此我们可以找这样一个句子 在else前面有两个if 如句子iiiei else和不同的if进行 匹配时就会产生不同的语义 考虑句子iiiei 存在如下两个最右推导 S iSeS iSei iiSei iiiei S iS iiSeS iiSei iiiei 由此该文法是二义的 13 第五题 第五题 P36 第第10题 题 10 把下面的文法改写为无二义的 S SS S 解 本题给出的文法是二义的 关键在于S SS是产生二义 性的根源 我们将该产生式改造成等价的递归结构 消 除二义性 将文法改造成G S S TS T T S 14 第六题 第六题 P36 第第11题 题 11 给出下面语言的相应文法 L1 anbnci n 1 i 0 L2 aibncn n 1 i 0 L3 anbnambm n m 0 L4 1n0m1m0n n m 0 15 第六题 第六题 P36 第第11题