编译原理及实现课后习题答案

编译原理及实现课后习题答案

ID:15902195

大小:539.00 KB

页数:34页

时间:2018-08-06

编译原理及实现课后习题答案_第1页
编译原理及实现课后习题答案_第2页
编译原理及实现课后习题答案_第3页
编译原理及实现课后习题答案_第4页
编译原理及实现课后习题答案_第5页
资源描述:

《编译原理及实现课后习题答案》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、2.1设字母表A={a},符号串x=aaa,写出下列符号串及其长度:x0,xx,x5以及A+和A*.x0=(aaa)0=ε

2、x0

3、=0xx=aaaaaa

4、xx

5、=6x5=aaaaaaaaaaaaaaa

6、x5

7、=15A+=A1∪A2∪….∪An∪…={a,aa,aaa,aaaa,aaaaa…}A*=A0∪A1∪A2∪….∪An∪…={ε,a,aa,aaa,aaaa,aaaaa…}2.2令∑={a,b,c},又令x=abc,y=b,z=aab,写出如下符号串及它们的长度:xy,xyz,(xy)3xy=abcb

8、xy

9、=4xyz=abcbaab

10、xyz

11、=7(xy)3=(ab

12、cb)3=abcbabcbabcb

13、(xy)3

14、=122.3设有文法G[S]:S∷=SS*

15、SS+

16、a,写出符号串aa+a*规范推导,并构造语法树。S=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*SSS*SS+aaa2.4已知文法G[Z]:Z∷=U0∣V1、U∷=Z1∣1、V∷=Z0∣0,请写出全部由此文法描述的只含有四个符号的句子。Z=>U0=>Z10=>U010=>1010Z=>U0=>Z10=>V110=>0110Z=>V1=>Z01=>U001=>1001Z=>V1=>Z01=>V101=>01012.5已知文法G[S]:S∷=ABA∷=aA︱ε

17、B∷=bBc︱bc,写出该文法描述的语言。A∷=aA︱ε描述的语言:{an

18、n>=0}B∷=bBc︱bc描述的语言:{bncn

19、n>=1}L(G[S])={anbmcm

20、n>=0,m>=1}2.6已知文法E∷=T∣E+T∣E-T、T∷=F∣T*F∣T/F、F∷=(E)∣i,写出该文法的开始符号、终结符号集合VT、非终结符号集合VN。开始符号:EVt={+,-,*,/,(,),i}Vn={E,F,T}ETE+FTE+iFT*T2.7对2.6题的文法,写出句型T+T*F+i的短语、简单短语以及句柄。短语:T+T*F+iT+T*FiiTT*F简单短语:iT*FT句柄:T2.8

21、设有文法G[S]:S∷=S*S

22、S+S

23、(S)

24、a,该文法是二义性文法吗?SSS*S+SaaaSSS+S*Saaa根据所给文法推导出句子a+a*a,画出了两棵不同的语法树,所以该文法是二义性文法。2.9写一文法,使其语言是奇正整数集合。A::=1

25、3

26、5

27、7

28、9

29、NAN::=0

30、1

31、2

32、3

33、4

34、5

35、6

36、7

37、8

38、92.10给出语言{anbm

39、n,m≥1}的文法。G[S]:S::=ABA::=aA

40、aB::=bB

41、b3.1有正则文法G[Z]:Z::=Ua

42、Vb,U::=Zb

43、b,V::=Za

44、a,画出该文法的状态图,并检查句子abba是否合法。解:该文法的状态图如下:SUV

45、Zaaabbb句子abba合法。3.2状态图如图3.35所示,S为开始状态,Z为终止状态。写出相应的正则文法以及V,Vn和Vt。SAZabab图3-35状态图解:左线性文法G[Z]:右线性文法G’[S]:Z::=Ab

46、bS::=aA

47、bA::=Aa

48、aA::=aA

49、bV={Z,A,a,b}V={S,A,a,b}Vn={Z,A}Vn={S,A}Vt={a,b}Vt={a,b}3.3构造下列正则表达式相应的NFA:1(1

50、0)*

51、01(1010*

52、1(010)*1)*0解:正则表达式:1(1

53、0)*

54、01、SZ1(1

55、0)*

56、02、SZ1(1

57、0)*03、SAZ01ε014

58、、q0q1010,1q2正则表达式:1(1010*

59、1(010)*1)*001354621010107801011ε01a,baa3.4将图3.36的NFAM确定化图3.36状态图解:abq0={0}{0,1}{1}q1={0,1}{0,1}{1}q2={1}{0}ΦDFA:q0q1q2ababa3.4将图3.37的DFA化简。014253aaaaaabbbbbb图3.37DFA状态图解:划分ab{0,1}{1}{2,4}{2,3,4,5}{1,3,0,5}{3,5,2,4}划分ab{0,1}{1}{2,4}{2,4}{0,1}{3,5}{3,5}{3,5}{2,4}q

60、0={0,1}q1={2,4}q2={3,5}化简后的DFA:q0q1q2baaabb4.1对下面文法,设计递归下降分析程序。S→aAS

61、(A),A→Ab

62、c解:首先将左递归去掉,将规则A→Ab

63、c改成A→c{b}非终结符号S的分析程序如下:过程SINPUTSYM=’a’INPUTSYM=下一个符号YNINPUTSYM=’(’INPUTSYM=下一个符号YINPUTSYM=’)’INPUTSYM=下一个符号YNN出口错误错误过程A过程S过程A非终结符号A的分析程序如下:过程AINPUTSYM=’c’INPUTSYM=下一个符号YINPUT

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

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

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