编译原理第二章习题解答.ppt

?西安电子科技大学 ·软件学院 编译原理第二章部分习题解答 ?西安电子科技大学 ·软件学院 第2章习题 根据模式，写出正规式 依据 NFA/DFA，写出正规式 * 难点 正规式?NFA NFA?DFA： ε_闭包，smove DFA最小化 计算量大 ?西安电子科技大学 ·软件学院 1. 根据模式写出正规式 一般思路：（1）分析题意 （2）列举一些最简单的例子 （3）寻找统一规律*,考虑所有可能情况** 习题2.4 (1) 由偶数个0和奇数个1构成的01串 解：① 最简单的串有 0个0和1个1组成的串： 2个0和1个1组成的串： ② 在上述串的中间、两头添加偶数个0和/或偶数个1，即可得到满足题意的其他串。 设偶数个0/偶数个1组成的串，可用正规式 A 表示，则最终正规式： A1A | A0A1A0A 1 010 ，001，100 ** 关键：如何构造正规式 A ? * ?西安电子科技大学 ·软件学院 习题2.4 (1) 由偶数个0和奇数个1构成的01串 ③ 构造正规式 A(偶数个0/偶数个1) a) 长度为2: 00, 11 长度为4：0011, 1100, 0101, 0110, 1001, 1010 b) 前4个串： 由00和11组成的串 正规式B*, B= 00 | 11 c) 后4个串： 由01和10组成的串 正规式C*, C= 01|10 d) 修改正规式C为D： A = (B*|C*)* = (00 | 11|01|10)* 考虑：0001 D = (01|10) (01|10) (00|11)* 最终A = (B|D)* = ( (00|11) | (01|10) (00|11)* (01|10) )* ？ * 1. 根据模式写出正规式 (1) 分析题意 (2)列举一些最简单的例子 (3)寻找规律,考虑所有可能情况 ?西安电子科技大学 ·软件学院 最简单的串： 上述各串重复： (0 | 00 | 01 | 010 )* = (01 | 0)* 再考虑：仅由1组成的串，或 若干1打头的串。 最终的正规式： 习题2.4 (2) 所有不含有子串 011 的01串 思路1：简单例子，观察规律 * 1* | 1*(01|0)* = 1*(01|0)* 1. 根据模式写出正规式 0 , 1, 11, 00, 10, 01, 010, … ?西安电子科技大学 ·软件学院 ① 含有 子串 011 的最简单的串： ② 其中插入若干个0 （注意11之间应至少插入1个0），即可不出现“011”， 正规式为： (0+1) (0+1) 0* 即：每个1前面至少1个0，正规式化简为： (01 | 0)* ③ 再考虑：仅由1组成的串，或 若干1打头的串。 最终的正规式： 1*(01|0)* 0 1 1 习题2.4 (2) 所有不含有子串 011 的01串 0*0 0* 0* 0* 思路2：考虑包含 011 的串，然后构造没有011的串 * 1. 根据模式写出正规式 ?西安电子科技大学 ·软件学院 习题2.4 (4) 块注释 /* … */ 。其中 … 中不含有 子串 */ 。 思路：简单例子，观察规律。 关键：注释中若出现 *：若紧跟的是/则结束注释， 否则仍然是注释。 ① 注释为空： ② 考虑没有 * 的注释： ③ 考虑含 * 的注释： 以上情况 进行或运算，可得： /* ε */ /* [^*]* */ /* (*[^/])* */ ④ 考虑：中间可有若干连续 *，可得最终正规式： /* ([^*]|**[^*/])* ** */ * 1. 根据模式写出正规式 /* ( [^*] | *[^*/] )* */ /* ( [^*] | *[^/] )* */ */] )* */ ?西安电子科技大学 ·软件学院 2.依据NFA/DFA，给出正规式 思路1： 回顾“正规式 与 FA的关系” 正规式、FA是从两个不同的侧面表示一个集合(即正规集)。所以，根本的方法是以正规集为桥梁， - 先分析清楚 FA 识别的集合之结构特征， - 然后再设计此集合的正规式。 * ?西安电子科技