编译原理课习题答案陈俊老师.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） = 1 \* GB3 ①N SES10 D10110 = 2 \* GB3 ②N SES0 SD0S10D10110 1DESN1D01 110最右推导的语法树0ESNDS1 1 D E S N 1 D 0 1 110最右推导的语法树 0 E S N D S 1 （3）偶数的集合 3．（1）句子abab的两个相应的最右推导： S aSbS aSbaSbS aSbaSb aSbab abab S aSbS aSb abSaSb abSab abab ? （2）此文法产生的语言是：所有a的个数与b的个数相等的由a和b组成的字符串。 4．能被5整除的数从形式上看，是以0，5结尾的数字串。题目要求不以0开头，注意0不是该语言的句子。 所求文法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代表奇数头，T代表奇数尾，M代表整数，N代表数字 6．（1）1型（2）2型（3）3型 7．正确的程序为： 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循环语句〉→ repeat〈语句〉{；〈语句〉}until〈条件〉 第3章 1．(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． 12 1 2 4 5 3 others others / * * * / 标记为others的边是指字符集中未被别的边指定的任意其它字符。 分析：这个DFA的状态数及含义并不难确定，见下面的五个状态说明。 状态1：注释开始状态。 状态2：进入注释体前的中间状态。 状态3：表明目前正在注释体中的状态。 状态4：离开注释前的中间状态。 状态5：注释结束状态，即接受状态。 在这个DFA中，最容易忽略的是状态4到本身的’*’转换。这个边的含义是：在离开注释前的中间状态，若下一个字符是’*’，那么把刚才读过的’*’看成是注释中的一个字符，而把这下一个字符看成可能是结束注释的第一个字符。若没有这个边，那么象 /**** This is a comment ****/ 这样的注释就被拒绝。 另外，上面的状态转换图并不完整。例如，对于状态1，没有指明遇到其它字符怎么办。要把状态转换图画完整，还需引入一个死状态6，.进入这个状态就再也出不去了。因为它不是接受状态，因此进入这个状态的串肯定不被接受。完整的状态转换图见下图，其中all表示任意字符。在能够说清问题时，通常我们省略死状态和所有到它的边。 12 1 2 4 5 3 others others / * * * / 6 others others all all 5．先写出渡河的方法，串中对象顺序为人来回渡河时所运的货物的顺序：