编译原理 教学课件 作者 李冬梅 施海虎习题答案 编译原理课后习题答案.doc

《编译原理 教学课件 作者 李冬梅 施海虎习题答案 编译原理课后习题答案.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第1章1．(1)×(2)√(3)×(4)×(5)×(6)√第2章1．(1)√(2)√(3)×(4)×(5)×(6)×2．（1）终结符：0，1，2，3，4，5，6，7，8，9，10非终结符：N，S，E，D（2）①NSES10D10110②NSES0SD0S10D101101DESN1D01110最右推导的语法树0ESNDS1（3）偶数的集合3．（1）句子abab的两个相应的最右推导：SaSbSaSbaSbSaSbaSbaSbabababSaSbSaSbabSaSbabSababab （2）此文法产生的语言是：所有a的个数与b的个数相等的由a和b组成的

2、字符串。4．能被5整除的数从形式上看，是以0，5结尾的数字串。题目要求不以0开头，注意0不是该语言的句子。所求文法G[S]:S→MF

3、5F→5

4、0N→1

5、2

6、3

7、4

8、5

9、6

10、7

11、8

12、9D→N

13、0M→MD

14、N其中，S代表能被5整除且不以0开头的无符号整数;F代表可以出现在个位上的数字;D代表所有数字;N代表所有非零数字;M代表不以零开头的数字串。5．（1）令S为开始符号，产生的w中a的个数恰好比b多一个，令E为一个非终结符号，产生含相同个数的a和b的所有串，则产生式如下：S→aE

15、Ea

16、bSS

17、SbS

18、SSbE→aEbE

19、bEaE

20、ε（2）设文法开始

21、符号为S，产生的w中满足

22、a

23、≤

24、b

25、≤2

26、a

27、。因此，可想到S有如下的产生式（其中B产生1到2个b）：S→aSBS

28、BSaS

29、εB→b

30、bb（3）S→HMT

31、HT

32、TH→1

33、2

34、3

35、4

36、5

37、6

38、7

39、8

40、9T→1

41、3

42、5

43、7

44、9M→MN

45、NN→0

46、H其中，H代表奇数头，T代表奇数尾，M代表整数，N代表数字6．（1）1型（2）2型（3）3型7．正确的程序为：vara,b,c;beginread(a,b);c:=100;ifa>0thenbeginb:=b+1;write(b)end;write(a,b,c);end.8．(1)扩充条件语句的语法图为：

47、EBNF的语法描述为：〈条件语句〉→if〈条件〉then〈语句〉[else〈语句〉](2)扩充repeat语句的语法图为：EBNF的语法描述为：〈repeat循环语句〉→repeat〈语句〉{；〈语句〉}until〈条件〉第3章1．(1)√(2)√(3)×(4)×(5)√(6)√(7)×(8)√(9)×(10)×2．注意正规式不唯一（1）(0

48、1)*01（2）1*01*（3）(11)*（4）(0*10*10*)*（5）(0

49、1)*01(0

50、1)*（6）1*0*3．（1）必须以x开头和x结尾的串（2）每个y至少有一个x跟在后边的串（3）所有含两个相继

51、的x或两个相继的y的串4．12453othersothers/***/标记为others的边是指字符集中未被别的边指定的任意其它字符。分析：这个DFA的状态数及含义并不难确定，见下面的五个状态说明。状态1：注释开始状态。状态2：进入注释体前的中间状态。状态3：表明目前正在注释体中的状态。状态4：离开注释前的中间状态。状态5：注释结束状态，即接受状态。在这个DFA中，最容易忽略的是状态4到本身的’*’转换。这个边的含义是：在离开注释前的中间状态，若下一个字符是’*’，那么把刚才读过的’*’看成是注释中的一个字符，而把这下一个字符看成可能是结束注释的第

52、一个字符。若没有这个边，那么象/****Thisisacomment****/这样的注释就被拒绝。另外，上面的状态转换图并不完整。例如，对于状态1，没有指明遇到其它字符怎么办。要把状态转换图画完整，还需引入一个死状态6，.进入这个状态就再也出不去了。因为它不是接受状态，因此进入这个状态的串肯定不被接受。完整的状态转换图见下图，其中all表示任意字符。在能够说清问题时，通常我们省略死状态和所有到它的边。12453othersothers/***/6othersothersallall5．先写出渡河的方法，串中对象顺序为人来回渡河时所运的货物的顺序：①

53、羊空菜羊狼空羊②羊空狼羊菜空羊现给出一个NFA:M=(Σ,Q,0,{9},f)其中Σ={羊，空，菜，狼}Q={0,1,2,3,4,5,6,7,8,9}转换函数f(0,羊)=1,f(1,空)=2,f(2,菜)=3,f(2,狼)=5,f(3,羊)=4f(5,羊)=6,f(4,狼)=7,f(6,菜)=7,f(7,空)=8,f(8,羊)=96．这个DFA和无符号数的DFA有类似的地方。首先考虑device:和.extension全都出现的情况。（即：device:name.extension）这时的DFA比较容易构造。ll123456l:ll.l文件名的三

54、部分都出现的DFA然后考虑缺省情况：(1)因为.extension可缺省（即：device:name），因此把状态4也作为