编译原理考试习题及答案

《编译原理考试习题及答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、程序设计语言Chapter3.词法分析编译原理参考答案2021/7/5CH.3.练习题8(P64.)8.给出下面的正规表达式。(1)以01结尾的二进制数串;正规式(0

2、1)*01(2)能被5整除的十进制整数;允许任意0开头：(0

3、1

4、2

5、3

6、4

7、5

8、6

9、7

10、8

11、9)*(0

12、5)不允许0开头（0本身除外）：(0

13、5)

14、(1

15、2

16、3

17、…

18、9)(0

19、1

20、2

21、3

22、…

23、9)*(0

24、5)2021/7/5CH.3.练习题7(P64.)7.(1)1(0

25、1)*101构造DFA。解1:正规式对应的NFA:XY345110ε112ε10II0I1{X}{1,3,2}{1,3,2}{3,2}

26、{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}II0I1初01123223343425终5432021/7/5(1)正规式1(0

27、1)*101DFA:x3,Y,4,23,4,23,5,211011,3,23,20100101II0I1{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}{

28、3,4,2}II0I1初01123223343425终5432021/7/5(1)正规式1(0

29、1)*101DFA:II0I1{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}II0I1初01123223343425终543053411011201001012021/7/5CH.3.练习题7(P64.)7.构造下列正规式相应的DFA。(1)1(0

30、1)*101解2:正规式对应的NFA:04123110

31、110II0I1{0}初0{1}1{1}1{1}1{1,2}2{1,2}2{1,3}3{1,2}2{1,3}3{1}1{1,2,4}4{1,2,4}终4{1,3}3{1,2}210423110110010DFA:2021/7/57.构造下列正规式相应的NFA。(P64.)(2)1(1010*

32、1(010)*1)*0XY20ε113ε1010*1(010)*1XY20ε113ε6451100*7811(010)*2021/7/57.构造下列正规式相应的NFA。(P64.)(2)1(1010*

33、1(010)*1)*0XY20ε113ε6451100*7811(010)*XY

34、20ε113ε645110078119εε10010εε2021/7/5XY20ε113ε645110078119εε10010εεXY20ε113ε645110078119εε100εε1211017.(2)1(1010*

35、1(010)*1)*0的NFA。2021/7/5CH.3.练习题14(P64.)(1)正规式:(10

36、0)*(2)NFA:确定化:YX10ε0ε1201001012II0I1{X,1,Y}{1,Y}{2}{1,Y}{1,Y}{2}{2}{1,Y}II0I1初终012终11221DFA:2021/7/5CH.3.练习题14(P64.)(1)正规式:(

37、10

38、0)*(2)NFA:YX10ε0ε1201001012DFA:构造一个DFA，它接受S＝{0,1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。10010DFA:(最简)2021/7/5程序设计语言Chapter2.高级语言及其语法描述编译原理参考答案2021/7/5CH.2.练习题6(P36.)6.令文法G6为:N→D

39、NDD→0

40、1

41、2

42、3

43、4

44、5

45、6

46、7

47、8

48、9(1)G6的语言L(G6)是什么?注意：集合的写法不正确解：L(G6)={0,1,2,3,4,5,6,7,8,9}+={09数字构成的所有数字串，可以0开头}(2)给出句子0127、34和5

49、68的最左和最右推导。注意：1)步骤，和的区别；2)不能写为→解：0127的最左推导：NNDNDDNDDDDDDD0DDD01DD012D01270127的最右推导：NNDN7ND7N27ND27N127D1270127+CH.2.练习题8(P36.)8.令文法为E→T

50、E+T

51、E-TT→F

52、T*F

53、T/FF→(E)

54、i(1)给出i+i*i、i*(i+i)的最左推导和最右推导。解：此处仅以i*(i+i)为例给出答案最左推导ETT*FF*Fi*Fi*(E)i*(E+T)i*(T+T)i*