《编译原理习题和》PPT课件.ppt
2020/8/13,中国科大,程序设计语言编译原理,2020/8/13,中国科大,1.1 叙述正规式(00 | 11) ( (01 | 10) (00 | 11) (01 | 10) (00 | 11) ) 描述的语言。 1.2 给出下面的正规表达式: (1)能被五整除的十进制整数 (2)包含奇数个1或奇数个0的二进制数串 (3)包含偶数个0和奇数个1的二进制数串 1.3 构造一个DFA,它接受 = 0, 1上0和1的个数都是偶数的字符串。 1.4 构造一个DFA,它接受 = 0, 1上能被5整除的二进制数。 1.5 为正规式(a | b) a (a | b) (a | b)构造NFA。,2020/8/13,中国科大,1.6 用状态转换图表示接收(a | b) aa的确定的DFA. 1.7 用状态转换图表示接收(a | b) a (a | b) (a | b)的DFA. 1.8 将1.5 题得到的NFA变换成DFA。 1.9 将下图的DFA极小化。 1.10 将习题1.7结果的DFA极小化。,2020/8/13,中国科大,1.1叙述正规式 (00 | 11) ( (01 | 10) (00 | 11) (01 | 10) (00 | 11) ) 描述的语言。 答案:该正规式所描述的语言是,所有由偶数个0和偶数个1构成的串。 另外,和该正规式等价的正规式有 ( 00 | 11 | ( (01 | 10) (00 | 11) (01 | 10) ) ) 。,2020/8/13,中国科大,1.2 给出下面的正规表达式 (1)能被五整除的十进制整数 (0|5) | (1|2|3|4|5|6|7|8|9) (0|1|2|3|4|5|6|7|8|9)*(0|5) (2)包含奇数个1或奇数个0的二进制数串 0*1(0|10*1)*|1*0(1|01*0)* (3)包含偶数个0和奇数个1的二进制数串 even_0_even_1 (00 | 11) ( (01 | 10) (00 | 11) (01 | 10) (00 | 11) ) 1 even_0_even_1 | 0 (00 | 11) (01 | 10) even_0_even_1,2020/8/13,中国科大,1.3 构造一个DFA,它接受 = 0, 1上0和1的个数都是偶数的字符串。,0,start,情况0:0偶和1偶(作为状态0) 情况1:0偶和1奇(作为状态1) 情况2:0奇和1偶(作为状态2) 情况3:0奇和1奇(作为状态3),2020/8/13,中国科大,1.4 构造一个DFA,它接受 = 0, 1上能被5整除的二进制数。,2020/8/13,中国科大,1.5 为正规式 (a | b) a (a | b) (a | b) 构造NFA。,2020/8/13,中国科大,1.6 用状态转换图表示接收 (a | b) aa 的确定的有限自动机,2020/8/13,中国科大,1.7 用状态转换图表示接收 (a | b) a (a | b) (a | b) 的确定的有限自动机。,a,b,a,b,2020/8/13,中国科大,1.8 将1.5 题得到的NFA变换成DFA 答案:所得的DFA和1.7题的结果是同构的,2020/8/13,中国科大,1.9 将下图的DFA极小化,最简DFA,2020/8/13,中国科大,1.10 将习题1.7结果的DFA极小化 答案:习题1.7结果的DFA,即该DFA已是最简DFA,2020/8/13,中国科大,1.11 一个C语言编译器编译下面的函数时,报告parse error before else。这是因为else的前面少了一个分号。但是如果第一个注释 /* then part */ 误写成 /* then part 那么该编译器发现不了遗漏分号的错误。这是为什么? long gcd(p,q) long p,q; if (p%q = 0) /* then part */ return q else /* else part */ return gcd(q, p%q); ,