编译原理习题和课件.ppt
程序设计语言程序设计语言编译原理编译原理2023/2/22中国科大中国科大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。2023/2/22中国科大中国科大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极小化。极小化。a aa astartstart0 01 12 23 3a ab bb bb bb bb b4 42023/2/22中国科大中国科大1.1叙述正规式叙述正规式(00|11)(01|10)(00|11)(01|10)(00|11)描述的语言。描述的语言。答案：答案：该正规式所描述的语言是，所有由偶数个该正规式所描述的语言是，所有由偶数个0和偶数个和偶数个1构成的串。构成的串。另外，和该正规式等价的正规式有另外，和该正规式等价的正规式有 (00|11|(01|10)(00|11)(01|10)。2023/2/22中国科大中国科大1.2 给出下面的正规表达式给出下面的正规表达式（1 1）能被五整除的十进制整数）能被五整除的十进制整数）能被五整除的十进制整数）能被五整除的十进制整数(0|5)|(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*(0|5)(0|5)|(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*(0|5)（2 2）包含奇数个）包含奇数个）包含奇数个）包含奇数个1 1或奇数个或奇数个或奇数个或奇数个0 0的二进制数串的二进制数串的二进制数串的二进制数串 0*1(0|10*1)*|1*0(1|01*0)*0*1(0|10*1)*|1*0(1|01*0)*（3 3）包含偶数个）包含偶数个）包含偶数个）包含偶数个0 0和奇数个和奇数个和奇数个和奇数个1 1的二进制数串的二进制数串的二进制数串的二进制数串 even_0_even_1even_0_even_1 (00|11)(00|11)(01|10)(00|11)(01|10)(00|11)(01|10)(00|11)(01|10)(00|11)1 1 even_0_even_1even_0_even_1|0(00|11)|0(00|11)(01|10)(01|10)even_0_even_1even_0_even_12023/2/22中国科大中国科大1.3 构造一个构造一个DFA，它接受，它接受 =0,1上上0和和1的个数都是偶数的字符串。的个数都是偶数的字符串。0 01 11 11 11 11 10 03 30 00 02 20 0startstart情况情况情况情况0 0 0 0：0 0 0 0偶和偶和偶和偶和1 1 1 1偶（作为状态偶（作为状态偶（作为状态偶（作为状态0 0 0 0）情况情况情况情况1 1 1 1：0 0 0 0偶和偶和偶和偶和1 1 1 1奇（作为状态奇（作为状态奇（作为状态奇（作为状态1 1 1 1）情况情况情况情况2 2 2 2：0 0 0 0奇和奇和奇和奇和1 1 1 1偶（作为状态偶（作为状态偶（作为状态偶（作为状态2 2 2 2）情况情况情况情况3 3 3 3：0 0 0 0奇和奇和奇和奇和1 1 1 1奇（作为状态奇（作为状态奇（作为状态奇（作为状态3 3 3 3）2023/2/22中国科大中国科大1.4 构造一个构造一个DFA，它接受，它接受 S=0,1上能被上能被5整除的二进制数。整除的二进制数。开始开始开始开始0 01 12 23 34 41 10 00 01 10 01 10 01 10 01 12023/2/22中国科大中国科大1.5 为正规式为正规式(a|b)a(a|b)(a|b)构造构造NFA。1 1a a2 2a ab b3 3a ab b0 0startstarta ab b2 23 34 45 51 16 60 07 7a ab b a a9 98 8a ab b a ab b 2023/2/22中国科大中国科大1.6 用状态转换图表示接收用状态转换图表示接收(a|b)aa的确定的有限自动机的确定的有限自动机1 10 02 2startstarta aa ab ba ab bb b2023/2/22中国科大中国科大1.7 1.7 用状态转换图表示接收用状态转换图表示接收用状态转换图表示接收用状态转换图表示接收(a|b)(a|b)a(a|b)(a|b)a(a|b)(a|b)的确定的有限自动机。的确定的有限自动机。的确定的有限自动机。的确定的有限自动机。b ba ab ba a2 20 01 13 34 46 67 7a aa ab ba aa ab bb bstartstart5 5a ab ba ab b2023/2/22中国科大中国科大1.8 将将1.5 题得到的题得到的NFA变换成变换成DFA答案：答案：所得的所得的DFA和和1.7题的结果是同构的题的结果是同构的2023/2/22中国科大中国科大1.9 将下图的将下图的DFA极小化极小化a aa astartstart0 01 12 23 3a ab bb bb bb bb b4 40 01 12 2b bb bb bb b4 4a aa astartstart最简最简最简最简DFADFADFADFA2023/2/22中国科大中国科大1.10 将习题将习题1.7结果的结果的DFA极小化极小化答案：答案：习题习题1.71.7结果的结果的DFADFA，即该，即该DFADFA已是最简已是最简DFADFA2023/2/22中国科大中国科大1.11 一个一个C语言编译器编译下面的函数时，报告语言编译器编译下面的函数时，报告parse error before else。这是因为。这是因为else的前面少了一个分号。但是的前面少了一个分号。但是如果第一个注释如果第一个注释/*then part*/误写成误写成/*then part 那么该编译器发现不了遗漏分号的错误。这是为什么？那么该编译器发现不了遗漏分号的错误。这是为什么？long gcd(p,q)long gcd(p,q)long p,q;long p,q;if(p%q=0)if(p%q=0)/*then part*/*then part*/return qreturn q elseelse/*else part*/*else part*/return gcd(q,p%q);return gcd(q,p%q);2023/2/22中国科大中国科大
