编译原理考试习题及答案.ppt
《编译原理考试习题及答案.ppt》由会员分享,可在线阅读,更多相关《编译原理考试习题及答案.ppt(65页珍藏版)》请在第壹文秘上搜索。
1、程程 序序 设设 计计 语语 言言 Chapter 3.Chapter 3.词法分析词法分析22023-4-16CH.3.CH.3.练习题练习题8(8(P64.)P64.)n8.8. 给出下面的正规表达式给出下面的正规表达式。(1) 以以01结尾的二进制数串结尾的二进制数串; 正规式正规式 (0|1)*01(2) 能被能被5整除的十进制整数整除的十进制整数; 允许任意允许任意0开头:开头: (0|1|2|3|4|5|6|7|8|9)*(0|5) 不允许不允许0开头(开头(0本身除外):本身除外):(0|5)|(1|2|3|9)(0|1|2|3|9)*(0|5)32023-4-16CH.3.CH
2、.3.练习题练习题7(7(P64.)P64.)n7.7. (1) 1(0|1)*101 构造构造DFADFA。解解1: 正规式对应的正规式对应的NFA:XY34511011210 I I0 I1X 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,23,Y,4,23,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 (1) 正规式正规式 1(0|1)*101DFA:x3,Y,4,23,4,23,5,211011,3,23,20100101 I I0
3、 I1X 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,23,Y,4,23,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 (1) 正规式正规式 1(0|1)*101DFA: I I0 I1X 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,23,Y,4,23,5,2 3,4,2 I I0 I1初初0 1 1 2 3 2 2 3 3 4 3 4 2 5
4、终终5 4 30534110112010010162023-4-16CH.3.CH.3.练习题练习题7(7(P64.)P64.)n7.7. 构造下列正规式相应的构造下列正规式相应的DFADFA。 (1) 1(0|1)*101 解解2: 正规式对应的正规式对应的NFA:04123110110 I I0 I10 初初01 11 11 11,2 21,2 21,3 31,2 21,3 31 11,2,4 41,2,4终终4 1,3 31,2 210423110110010DFA:72023-4-16n7.7. 构造下列正规式相应的构造下列正规式相应的NFANFA。( (P64.)P64.) (2)
5、1(1010*|1 (010)*1)*0XY201131010*1 (010)*1XY201136451100*7811(010)*82023-4-16n7.7. 构造下列正规式相应的构造下列正规式相应的NFANFA。( (P64.)P64.) (2) 1(1010*|1 (010)*1)*0XY201136451100*7811(010)*XY2011364511007811910010XY2011364511007811910010XY201136451100781191001211017.7. (2) 1(1010*|1 (010)*1)*0的的NFANFA。102023-4-16CH.
6、3.CH.3.练习题练习题14(14(P64.)P64.)n(1) 正规式正规式: (10|0)* (2) NFA: 确定化确定化:YX1001201001012 I I0 I1X,1,Y 1,Y2 1,Y1,Y2 21,Y I I0 I1初终初终0 1 2 终终 1 1 2 2 1 DFA:112023-4-16CH.3.CH.3.练习题练习题14(14(P64.)P64.)n(1) 正规式正规式: (10|0)* (2) NFA:YX1001201001012DFA:构造一个构造一个DFA,它接受,它接受 S0,1上所有满足如下条件上所有满足如下条件的字符串:每个的字符串:每个1都有都有0
7、直直接跟在右边。接跟在右边。10010DFA:(最简最简)程程 序序 设设 计计 语语 言言 Chapter 2.Chapter 2.高级语言及高级语言及其语法描述其语法描述13CH.2.CH.2.练习题练习题6(6(P36.)P36.)n6.6.令文法令文法G6G6为为: : N D|ND D 0|1|2|3|4|5|6|7|8|9N D|ND D 0|1|2|3|4|5|6|7|8|9n(1) (1) G6G6的语言的语言L(G6)L(G6)是什么是什么? ?n注意注意:集合的写法不正确:集合的写法不正确n解:解:L(G6)=0,1,2,3,4,5,6,7,8,9L(G6)=0,1,2,3
8、,4,5,6,7,8,9+ + =0=0 9 9数字构成的所有数字串,可以数字构成的所有数字串,可以0 0开头开头 n(2) (2) 给出句子给出句子01270127、3434和和568568的最左和最右推导。的最左和最右推导。n注意注意:1)1)步骤,步骤,和和 的区别的区别;2) 2) 不能写为不能写为n解:解:01270127的最左推导:的最左推导:N NNDNDNDDNDDNDDDNDDDDDDDDDDD 0DDD0DDD0101DDDD012012D D01270127 0127 0127的最右推导:的最右推导:N NNDNDN7N7ND7ND7N27N27ND27ND27 N127
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 考试 习题 答案