编译原理-练习题讲解.ppt

* * * 作业评讲 教材： 《编译原理教程》 胡元义等编著 2003年第1版 CH.1 补充作业 设已有 和 ，若L? S，写出得到 的过程，用T形图表示。 L L,B A S,A B L,B L语言 L语言 B代码 S语言 Ａ代码 A代码 L语言 A代码 B代码 L语言 L语言 B代码 L语言 Ａ代码 B代码 L语言 B代码 B代码 CH.2 作业 教材上的习题2.3、2.4、2.5、2.7、2.9的主要问题是缺少过程。 CH.2 补充作业1 1. 给出下面的正规表达式： (1) 以01结尾的二进制数串。 解：正规式 (0|1)*01 或 (0*1*)*01 (2) 能被5整除的十进制整数。 解：正规式 (0|1|2|3|4|5|6|7|8|9)*(0|5) 或 (0*1*2*3*4*5*6*7*8*9*)*(0|5) 或 (0|5)|(1|2|3|…|9)(0|1|2|3|…|9)*(0|5) 或 (+ | - |ε)(0|1|2|3|…|9)*(0|5) CH.3.练习题9(P64.) (3) 英文字母组成的所有符号串，要求符号串中的字母依照字典序排列。 解：正规式 (a|A)*(b|B)*(c|C)*(d|D)*…(z|Z)* 或 A*B*C*D*…X*Y*Z* 或 a*b*c*d*…x*y*z* (4) {0,1}上的含有子串010的数字串(至少含一个)。 解：正规式 (0|1)*010(0|1)* 或 (0*1*)*010(0*1*)* CH.2 补充作业2 2. 求正规式1(0|1)*101对应的简化的DFA。 解1: 正规式对应的NFA: X Y 3 4 5 1 1 0 ε 1 1 2 ε 1 0 I I0 I1 {X} {1,3,2} {1,3,2} {3,2} {3,4,2} {3,2} {3,2} {3,4,2} {3,4,2} {3,5,2} {3,4,2} {3,5,2} {3,2} {3,Y,4,2} {3,Y,4,2} {3,5,2} {3,4,2} I I0 I1 初0 1 1 2 3 2 2 3 3 4 3 4 2 5 终5 4 3 CH.2 补充作业3 3. 构造一个DFA,它接受∑={0,1}上所有满足如下条件的字符串: 每个1都有0直接跟在右边。 解：(1) 正规式: (10|0)* 或 0*(100*)* 或 ((10)*|0*)* Y X 1 0 ε 0 ε 1 2 0 1 0 0 1 0 1 2 I I0 I1 {X,1,Y} {1,Y} {2} {1,Y} {1,Y} {2} {2} {1,Y} I I0 I1 初终0 1 2 终 1 1 2 2 1 (3) 确定化DFA: CH.2 补充作业3 解：3. (4) DFA的化简: 0 1 0 0 1 0 1 2 初始: 分为两个组{0,1}和{2} ∵{0,1}0={1} {0,1}1={2} ∴ {0,1}组不再分裂。 最后划分得2个子集: {0,1} 和 {2} 选代表：0、2 最小化的DFA见左图。 0 0 0 2 1 化简的DFA: CH.3 文法和语言作业 P86. 习题3.2、3.3、3.4、3.5、3.6(1)、3.7、2.7(2)，主要问题是没按改过的题作，或作得不对。 3.3 改写为无二义文法G[S]： S→aSb|A A→Ab|b 3.4 改写为无二义文法G[S]： S→aS|a 3.5(1) 描述L={ aibj | ji≥1 }的上下文无关文法可以是： S→aSb|Ab A→Ab|ab 或 S→aSb|aAb A→Ab|b 或 S→AB A→aA|a B→bB|b