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

第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） ①N SES10 D10110 ②N SES0 SD0S10D10110 （3）偶数的集合 3．（1）句子abab的两个相应的最右推导：S aSbS aSbaSbS aSbaSb aSbab abab S aSbS aSb abSaSb abSab abab ? （2）此文法产生的语言是：所有a的个数与b的个数相等的由a和b组成的字符串。G[S]: S→MF|5 F→5|0 N→1|2|3|4|5|6|7|8|9 D→N|0 M→MD|N 其中，S代表能被5整除且不以0开头的无符号整数; F代表可以出现在个位上的数字; D代表所有数字; N代表所有非零数字; M代表不以零开头的数字串。 5．（1）令S为开始符号，产生的w中a的个数恰好比b多一个，令E为一个非终结符号，产生含相同个数的a和b的所有串，则产生式如下： S→ aE|Ea|bSS|SbS|SSb E→ aEbE|bEaE|ε （2）设文法开始符号为S，产生的w中满足|a|≤|b|≤2|a|。因此，可想到S有如下的产生式 （其中B产生1到2个b）： S → aSBS|BSaS|ε B → b|bb （3） S→HMT|HT|T H→1|2|3|4|5|6|7|8|9 T→ 1|3|5|7|9 M→MN|N N→0|H 其中，H代表奇数头奇数var a,b,c; begin read(a,b); c:=100; if a0 then begin b:=b+1; write(b) end; write(a,b,c); end. 8．(1) 扩充条件语句的语法图为： EBNF的语法描述为：〈条件语句〉→if〈条件〉then〈语句〉[else〈语句〉](2) 扩充repeat语句的语法图为： EBNF的语法描述为：〈语句〉→ repeat〈语句〉{；〈语句〉}until〈条件〉 (1) √ (2) √ (3) × (4) × (5) √ (6) √ (7) × (8) √ (9) × (10) × 2．注意 正规式不唯一 （1）(0|1)*01 （2）1*01* （3）(11)* （4）(0*10*10*)* （5）(0|1)*01(0|1)* （6）1*0* 3．（1）必须以 x 开头和x结尾的串 （2）每个 y 至少有一个 x 跟在后边的串 （3）所有含两个相继的x或两个相继的y的串 4． 标记为others的边是指字符集中未被别的边指定的任意其它字符。 分析：这个DFA的状态数及含义并不难确定，见下面的五个状态说明。 状态1：注释开始状态。 状态2：进入注释体前的中间状态。 状态3：表明目前正在注释体中的状态。 状态4：离开注释前的中间状态。 状态5：注释结束状态，即接受状态。 在这个DFA中，最容易忽略的是状态4到本身的’*’转换。这个边的含义是：在离开注释前的中间状态，若下一个字符是’*’，那么把刚才读过的’*’看成是注释中的一个字符，而把这下一个字符看成可能是结束注释的第一个字符。若没有这个边，那么象 /**** This is a comment ****/ 这样的注释就被拒绝。 另外，上面的状态转换图并不完整。例如，对于状态1，没有指明遇到其它字符怎么办。要把状态转换图画完整，还需引入一个死状态6，.进入这个状态就再也出不去了。因为它不是接受状态，因此进入这个状态的串肯定不被接受。完整的状态转换图见下图，其中all表示任意字符。在能够说清问题时，通常我们省略死状态和所有到它的边。 5．先写出渡河的方法，串中对象顺序为人来回渡河时所运的货物的顺序：①羊空菜羊狼空羊②羊空狼羊菜空羊 现给出一个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,羊)=4 f(5,羊)=6, f(4,狼)=7, f(6,菜)=7, f(7,空)=8, f(8,羊)=9 6．这个DFA和无符号数的DFA有类似的地方。 首先考虑device:和.extension全都出现的情况。（即：device:name.extension）这时的DFA比较容易构造。 然后考虑缺省情况： 因为.