编译原理课后习题答案陈俊老师

《编译原理课后习题答案陈俊老师》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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的个

2、数相等的由a和b组成的字符串。4．能被5整除的数从形式上看，是以0，5结尾的数字串。题目要求不以0开头，注意0不是该语言的句子。所求文法G[S]:S→MF5F→50N→123456789D→N0M→MDN其中，S代表能被5整除且不以0开头的无符号整数;F代表可以出现在个位上的数字;D代表所有数字;N代表所有非零数字;M代表不以零开头的数字串。5．（1）令S为开始符号，产生的w中a的个数恰好比b多一个，令E为一个非终结符号，产生含相同个数的a和b的所有串，则产生式如下：S→aEEabSSSbSSSbE→aEbEbEaEε（2）设

3、文法开始符号为S，产生的w中满足a≤b≤2a。因此，可想到S有如下的产生式（其中B产生1到2个b）：S→aSBSBSaSεB→bbb（3）S→HMTHTTH→123456789T→13579M→MNNN→0H其中，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)扩充条件语句的语法图为：EBNF的语法描述为

4、：〈条件语句〉→if〈条件〉then〈语句〉[else〈语句〉](2)扩充repeat语句的语法图为：EBNF的语法描述为：〈repeat循环语句〉→repeat〈语句〉{；〈语句〉}until〈条件〉第3章1．(1)√(2)√(3)×(4)×(5)√(6)√(7)×(8)√(9)×(10)×2．注意正规式不唯一（1）(01)01（2）101（3）(11)（4）(01010)（5）(01)01(01)（6）103．（1）必须以x开头和x结尾的串（2）每个y至少有一个x跟在后边的串（3）所有含两个相继的x或两个相继的y的串4．1

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

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

7、空狼羊菜空羊现给出一个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文件名

8、的三部分都出现的DFA然后考虑缺省情况：(1)因为.extension可缺省（即：device:name），因此把状态4也作为接受状态。(2)因为name和device一样，都是字母序列，所以在device:缺省时，把到状态2为止得到的字母序列看成是name。由于device