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

《UN_编译原理(习题课)(一).pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编译原理朱雪峰博士计算机科学与技术系Tel:89733787(O)Email:xuefeng.zhu@cup.edu.cn1第一题（P36第6题）6.令文法G为6N→D

2、NDD→0

3、1

4、2

5、3

6、4

7、5

8、6

9、7

10、8

11、9①G的语言L(G)是什么？66②给出句子0127、34和568的最左推导和最右推导。2第一题（P36第6题）解：①根据产生式N→D

12、ND可以看出，N最终可以推出1个或多个（可以是无穷多个）D，根据产生式D→0

13、1

14、2

15、3

16、4

17、5

18、6

19、7

20、8

21、9可以看出，每个D可以推导出0~9中的某一个数字。因此，N最终推导出的就是由0~9这10个数字组成的字符串。因此

22、G的语言L(G)就是由0~9这6610个数字组成的字符串。3第一题（P36第6题）②句子0127、34和568的最左推导如下：N⇒ND⇒NDD⇒NDDD⇒DDDD⇒0DDD⇒01DD⇒012D⇒0127N⇒ND⇒DD⇒3D⇒34N⇒ND⇒NDD⇒DDD⇒5DD⇒56D⇒5684第一题（P36第6题）②句子0127、34和568的最右推导如下：N⇒ND⇒N7⇒ND7⇒N27⇒ND27⇒N127⇒D127⇒0127N⇒ND⇒N4⇒D4⇒34N⇒ND⇒N8⇒ND8⇒N68⇒D68⇒5685第二题（P36第7题）7.写一个文法，使其语言是奇数集，且每个奇数不以0开头。解：

23、首先分析题意，本题希望构造一个文法，由它产生的句子是奇数，并且不以0开头，也就是说它的每个句子都是以1、3、5、7、9中的某个数结尾。如果数字只有一位，则满足要求，如果有多位，则要求第1位不能是0，而中间有多少位，每位是什么数字（必须是数字）则没有什么要求，因此，我们可以把这个文法分3个部分来完成。6第二题（P36第7题）解：引入几个非终结符，其中，一个用作产生句子的开头，可以是1~9之间的数，不包括0；一个用来产生句子的结尾，为奇数；另一个则用来产生以非0整数开头后面跟任意多个数字的数字串。由此得到文法如下：G(S)：D→1

24、3

25、5

26、7

27、9A→2

28、4

29、6

30、8

31、D

32、B→A

33、0C→CB

34、AS→CD

35、D7第三题（P36第8题）8.令文法为E→T

36、E+T

37、E-TT→F

38、T*F

39、T/FF→(E)

40、i①给出i+i*i、i*(i+i)的最左推导和最右推导；②给出i+i+i、i+i*i和i-i-i的语法树。8第三题（P36第8题）解：（1）最左推导为：E⇒E+T⇒T+T⇒F+T⇒i+T⇒i+T*F⇒i+F*F⇒i+i*F⇒i+i*iE⇒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

41、*i⇒T+i*i⇒F+i*i⇒i+i*iE⇒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)9第三题（P36第8题）（2）i+i+i、i+i*i和i-i-i的语法树分别如下：10第四题（P36第9题）9.证明下面的文法是二义的S→iSeS

42、iS

43、i证明：根据文法二义性的定义，如果要证明该文法是二义的，必须找到一个句子，使得该句子具有两个不同的最右推导或两个不同的语法树。我们首先分析这个文法，根据我们对程序设计语言的了解，不难发现，这个文法应该是用来表示if…els

44、e…结构的（用“i”代表“if”或语句集，“e”代表“else”）。因此我们就要到if…else…结构中去找二义性。11第四题（P36第9题）ł我们知道，程序语言一般都规定else部分是和它前面离它最近的没有被匹配的if语句进行匹配。而上面这个文法体现不出这种限制，因此我们可以找这样一个句子，在else前面有两个if（如句子iiiei），else和不同的if进行匹配时就会产生不同的语义。ł考虑句子iiiei，存在如下两个最右推导：S⇒iSeS⇒iSei⇒iiSei⇒iiieiS⇒iS⇒iiSeS⇒iiSei⇒iiiei由此该文法是二义的。12第五题（P36第10题

45、）10.把下面的文法改写为无二义的：S→SS

46、(S)

47、()解：本题给出的文法是二义的，关键在于S→SS是产生二义性的根源，我们将该产生式改造成等价的递归结构，消除二义性。将文法改造成G(S)：S→TS

48、TT→(S)

49、()13第六题（P36第11题）11.给出下面语言的相应文法L={anbnci

50、n≥1,i≥0}1L={aibncn

51、n≥1,i≥0}2L={anbnambm

52、n,m≥0}3L={1n0m1m0n

53、n,m≥0}414第六题（P36第11题）解：分析L，要求a和b的个数一样多，并至少为1个，而c的1个数为0个以上即可，因此，我们可以使用一个非终结符去生成

54、anbn串