编译原理(李冬梅施海虎着)人民邮电出版社课后答案解析【khdaw_lxywyl】.pdf

第 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 SE S10 D10 110 ②N SE S0 SD0 S10 D10 110 N N S E S E D 1 0 S D 0 1 D 1 1 110 最右推导的语法树 （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 至少有一