编译原理作业20150515(答案)

编译原理作业20150515(答案)

ID:6712105

大小:350.00 KB

页数:11页

时间:2018-01-23

编译原理作业20150515(答案)_第1页
编译原理作业20150515(答案)_第2页
编译原理作业20150515(答案)_第3页
编译原理作业20150515(答案)_第4页
编译原理作业20150515(答案)_第5页
资源描述:

《编译原理作业20150515(答案)》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第3章作业【编辑人:陈芳芳】1.写一文法,使其语言是偶正整数的集合。要求:(1)允许0打头;(2)不允许0打头。【解】:(1)允许0打头且含0的偶正整数集合的文法为:N—>(0

2、D

3、E)N

4、(E

5、0)D—>1

6、3

7、5

8、7

9、9E—>2

10、4

11、6

12、8(2)不允许0打头的偶正整数集合的文法为:R—>(D

13、E)N

14、EN—>(0

15、D

16、E)N

17、(E

18、0)D—>1

19、3

20、5

21、7

22、9E—>2

23、4

24、6

25、8(3)允许0打头的偶正整数集合的文法为:S—>0S

26、RR—>(D

27、E)N

28、EN—>(0

29、D

30、E)N

31、(E

32、0)D—>1

33、3

34、5

35、7

36、9E—>2

37、4

38、6

39、82.

40、一个上下文无关文法生成句子abbaa的推导树如下:SABSaSBBAa11Ɛbba(1)给出该句子的相应的最左推导,最右推导。(2)该文法的产生式集合P可能有哪些元素?(3)找出该句子的所有短语,简单短语,句柄。【解】:(1)最左推导:S=>ABS=>aBS=>aSBBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa最右推导:S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Abbaa=>abbaa(2)产生式集合P:S—>ABS

41、Aa

42、ƐA—>aB—>SBB

43、b(3)短语:a,Ɛ,

44、b,bb,aa,abbaa直接短语:a,Ɛ,b句柄:a3、给出生成下述语言的上下文无关文法:(1){anbnambm

45、n,m>=0}(2){1n0m1m0n

46、n,m>=0}【解】:(1)S—>AAA—>aAb

47、Ɛ(2)S—>1S0

48、AA—>0A1

49、Ɛ11第4章课后作业1.构造一个状态数最小的DFA,它接受∑={0,1}上所有倒数第二个字符为1的字符串。(编辑:张超)解:①构造正规式:(0│1)*1(0│1)②由正规式构造NFA:③NFA转化为DFA:T0=ε-closure({0})={0}用子集构造法求DFA状态,T0为初态,T2,T3

50、为终态。状态ε-closure(move(Ti,0))ε-closure(move(Ti,1))T0={0}{0}{0,1}T1={0,1}{0,2}{0,1,2}T2={0,2}{0}{0,1}T3={0,1,2}{0,2}{0,1,2}用0,1,2,3代表T0,T1,T2,T3,得到如下DFA:11④最小化DFA:P0=({0,1},{2,3})P1=({0},{1},{2},{3})∴无等价状态。∵没有找到多余状态,∴无多余状态。∴上图为最小化的DFA。2、将下图的NFA确定化为DFA,并最小化。(编辑:张超)解:用子集构造法求DF

51、A状态,T0为初态,T3为终态。状态ε-closure(move(Ti,a))ε-closure(move(Ti,b))T0={X,1,2}{1,2}{1,2,3}T1={1,2}{1,2}{1,2,3}11T2={1,2,3}{1,2,Y}{1,2,3}T3={1,2,Y}{1,2}{1,2,3}用0,1,2,3代表T0,T1,T2,T3,得到如下DFA:最小化:①{0,1,2}{3}②{0,1}{2}{3}③{0,1}{2}{3}0和1是等价的,∴得到最小化的DFA如下:11第5-7章课后作业(含答案)1、将文法G[S]改写为等价的G

52、′[S],使G′[S]不含左递归和左公共因子。G[S]:S→bSAe

53、bAA→Abd

54、dc

55、a【解】:G[S]:S→bS’S’→SAe

56、AA→(dc

57、a)A’A’→bdA’

58、ε2、有文法G[S]:S→ABfA→BbS

59、eB→dAg

60、ε证明文法G是LL(1)文法,并构造预测分析表【解】:①计算FIRST、FOLLOW、SELECT集产生式FIRSTFOLLOWSELECT左部右部SABfdbe#gdfdbeABbSdbgdfdbeeeBdAgdbfdεεbf由上表可知:该文法中,所有相同左部不同右部的产生式SELECT集两两相交均为空集,所

61、以该文法为LL(1)文法。②构造预测分析表fbedg#SABfABfABfABbSeBbSBεεdAg113、已知文法G[S]:S→(A)│a│bA→AcS│S构造文法的算符优先矩阵,并判断该文法是否是算符优先文法。【解】:①拓展该文法:S’→#S#S→(A)│a│bA→AcS│S②计算FIRSTVT与LASTVT:FIRSTVTLASTVTS’##S(ab)abAc(abc)ab③计算算符优先关系:#=#(=)##LASTVT(A)>)LASTVT

62、(A)>c④构造算符优先矩阵(注:按终结符出现顺序列表):()abc#(<=<<<)>>>a>>>b>>>c<><<>#<<<=⑤因为该文法G为2型文法,且不含空产生式,没有形如U®…VW…的

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。