《编译原理》习题解答-南京邮电大学版.doc
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《《编译原理》习题解答-南京邮电大学版.doc》由会员分享,可在线阅读,更多相关《《编译原理》习题解答-南京邮电大学版.doc(260页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date编译原理习题解答-南京邮电大学版编译原理习题解答:编译原理习题解答:第一次作业:P14 2、何谓源程序、目标程序、翻译程序、汇编程序、编译程序和解释程序?它们之间可能有何种关系?答:被翻译的程序称为源程序;翻译出来的程序称为目标程序或目标代码;将汇编语言和高级语言编写的程序翻译成等价的机器语言,实现此功能的程序称为翻译程序;把汇编语言写的源程序翻译成机器语言的目标程序
2、称为汇编程序;解释程序不是直接将高级语言的源程序翻译成目标程序后再执行,而是一个个语句读入源程序,即边解释边执行;编译程序是将高级语言写的源程序翻译成目标语言的程序。关系:汇编程序、解释程序和编译程序都是翻译程序,具体见P4 图 1.3。P14 3、编译程序是由哪些部分组成?试述各部分的功能?答:编译程序主要由8个部分组成:(1)词法分析程序;(2)语法分析程序;(3)语义分析程序;(4)中间代码生成;(5)代码优化程序;(6)目标代码生成程序;(7)错误检查和处理程序;(8)信息表管理程序。具体功能见P7-9。P14 4、语法分析和语义分析有什么不同?试举例说明。答:语法分析是将单词流分析如
3、何组成句子而句子又如何组成程序,看句子乃至程序是否符合语法规则,例如:对变量 x:= y 符合语法规则就通过。语义分析是对语句意义进行检查,如赋值语句中x与y类型要一致,否则语法分析正确,语义分析则错误。P15 5、编译程序分遍由哪些因素决定?答:计算机存储容量大小;编译程序功能强弱;源语言繁简;目标程序优化程度;设计和实现编译程序时使用工具的先进程度以及参加人员多少和素质等等。补充:1、为什么要对单词进行内部编码?其原则是什么?对标识符是如何进行内部编码的?答:内部编码从“源字符串”中识别单词并确定单词的类型和值;原则:长度统一,即刻画了单词本身,也刻画了它所具有的属性,以供其它部分分析使用
4、。对于标识符编码,先判断出该单词是标识符,然后在类别编码中写入相关信息,以表示为标识符,再根据具体标识符的含义编码该单词的值。补充:2、赋值语句: A:= 5 * C的语法和语义指的是什么?答:语法分析将检查该语句是否符合赋值语句规则,语义是指将 5 * C 的结果赋值为 A 。第二次作业:P38 1、设T111,010,T20,01,1001,计算:T2T1,T1*,T2+。T2T1011,0010,0111,01010,100111,1001010T1*,11,010,1111,11010,01011,010010T2+0,01,1001,00,001,01001,010,0101P38
5、3、令A0,1,2,写出集合A+和A*的七个最短符号串。A+:0,1,2,00,01,02,10(有多种可能)A*:,0,1,2,00,01,02(有多种可能)P38 5、试证明:A+A A*A*A。证明:A+A1A2AnA*A0(即)A+A A*A(A0A+ )AA2A3A4A+A+A(A0A+ )AA*A(证毕)P38 7、设有文法GS:SAAB | IF A THEN A ELSE ABC | B+C | +CCD | C*D | *DDX | (A) | -D 试写出VN和VT。VNS,A,B,C,DVTIF,THEN,ELSE,+,*,X,(,),-P38-39 8、设有文法GS:S
6、aAbABcA | BBidt | 试问下列符号串(1)aidtcBcAb (3)ab (5)aidtcidtcidtb 是否为该文法的句型或句子。(1)SaAbaBcAbaidtcAbaidtcBcAb 句型但不是句子;(3)SaAbaBbabab 是句型也是句子;(5)SaAbaBcAbaidtcAbaidtcBcAbaidtcidtcBbaidtcidtcidtb句型也是句子。P39 10、给定文法:SaB | bAAaS | bAA | aBbS | aBB|b 该文法所描述的语言是什么?L(G)相同个数的a与b以任意次序连接而成的非空符号串。P39 11、试分别描述下列文法所产生的语
7、言(文法开始符号为S):(1) S0S | 01(2) SaaS | bc(3) S: =aSd | aAdA: =aAc | bc(4) S: =ABA: =aAb | abB: =cBd | (1) L(G)0n1| n1; 解题思路:将文法转换为正规表达式(2) L(G)a2nbc | n0;(3) L(G)aibcjdk | i, j, k1, i=j+k-1;或者 L(G)aj+k-1bcjdk | j, k1;(4) L(G)anbncmdm | m0, n1。P39 12、试分别构造产生下列语言的文法: (1) abna | n=0,1,2,3 (2) anbn | n=1,2,
8、3,4 (3) aban | n1 (4) anbam | n, m1 (5) anbmcp | n,m,p0 (6) ambmcp | m,p0(1)GVN,VT,P,S,VNS,A ,VTa,b,P:SaAa 或 SaBAbA | BbB | a(2)GVN,VT,P,S,VNS,VTa,b,P:SaSb |(3)GVN,VT,P,S,VNS,A ,VTa,b,P:SabA 或 SSa | aba AaA | a(4)GVN,VT,P,S,VNS,A ,VTa,b,P:SaS | abA AaA | a(5)GVN,VT,P,S,VNS,A ,B,C ,VTa,b,c,P:SABCAaA
9、|BbB |CcC |(6)GVN,VT,P,S,VNS,A ,VTa,b,c,P:SaSbA |AcA |第三次作业:P39 15. 设文法G规则为:S:=ABB:=a|SbA:=Aa|bB对下列句型给出推导语法树,并求出其句型短语,简单短语和句柄。(2)baabaab (3)bBABb(2) S A B A a S b b B A B a b B a a句型baabaab的短语a, ba, baa, baab, baabaab,简单短语a,句柄 a S(3) A B b B S b A B 短语bB, AB, ABb,bBABb 简单短语bB, AB, 句柄bBP40 18. 分别对i+i
10、*i 和i+i+i中每一个句子构造两棵语法树,从而证明下述文法G是二义的。:=i|()|:=+|-|*|/1 i+i*i i + i * i * i i + i由于句子i+i*i可构造两棵不同的语法树,所以证明该文法是二义的。2. i+i+i i + i + i + i i + i由于句子i+i+i可构造两棵不同的语法树,所以证明该文法是二义的。P40 19. 证明下述文法是二义的1) S:=iSeS|iS|i2) S:=iEtS| iEtSeS|a E:=b 存在句子ibtibtaeibta或者ibtibtaea有两颗不同的语法树3) S:=A|BA:=aCbA|aB:=BCC|aC:=ba
11、 (最简单的就是a为句型)1) 对于句子iiieii可构造两棵不同的语法树,所以证明该文法是二义的。 S i S e S i S i S i i S i S i S e S i i S i3) 对于句子ababa可构造两棵不同的语法树,所以证明该文法是二义的。 S A a C b A b a a S B B C C a b a b a P41 21. 令文法N:=D|ND D:=0|1|2|3|4|5|6|7|8|9给出句子0127,34,568最左推导和最右推导。解:0127的最左推导N=ND=NDD=NDDD=DDDD=0DDD=01DD=012D=01270127的最右推导N=ND=N7
12、=ND7=N27=ND27=N127=D127=012734的最左推导N=ND=DD=3D=3434的最右推导N=ND=N4=D4=34568的最左推导N=ND=NDD=DDD=5DD=56D=568568的最右推导N=ND=N8=ND8=N68=D68=568P41 23. 设有文法如下::=V1V1:=V2|V1iV2V2:=V3|V2+V3|iV3V3:=)V1*|(试分析句子(, )(*, i(, (+(, (+(i(, (+)(i(*i(。解 = V1=V2=V3=(= V1=V2=V3=)V1*=)V2*=)V3*=)(*= V1=V2=iV3=i(= V1=V2=V2+V3=V3
13、+V3=(+V3=(+(= V1=V1iV2= V1iV3= V1i(=V2i(=V2+V3i(=V2+( i(=V3+( i(=(+(i(= V1=V1iV2= V2iV2= V2+V3iV2= V3+V3iV2= (+V3iV2=(+)V1*iV2=(+) V1iV2*iV2=(+) V2iV2*iV2=(+) V3iV2*iV2=(+) (iV2*iV2=(+) (iV2*iV2=(+) (iV3*iV2=(+) (i(*iV2=(+) (i(*iV3=(+) (i(*i(P41 24. 下面文法那些是短语结构文法,上下文有关文法,上下文无关文法,及正规文法?1.S:=aB B:= cB
14、 B:=b C:=c2.S:=aB B:=bC C:=c C:=3.S:=aAb aA:=aB aA:=aaA B:=b A:=a4.S:=aCd aC:=B aC:=aaA B:=b5.S:=AB A:=a B:=bC B:=b C:=c6. S:=AB A:=a B:=bC C:=c C:=7. S:=aA S:= A:=aA A:=aB A:=a B:=b8. S:=aA S:= A:=bAb A:=a正规文法 1 2 7 或者 1上下文无关文法 5 6 8 或者 2 5 6 7 8上下文有关文法 3 短语结构文法 4P41 26. 给出产生下列语言L(G)=W|W0,1+且W不含相邻1
15、的正规文法。 G=(S, A, B, 0, 1, P, S)P: S:=0|1|0S|1A A:=0|0S解题思路一:写出满足要求的符号串,例如0,1,00,01,10,000,101,010,001等,根据符号串从左至右的次序画出状态转换图,然后根据状态转换图来推导出文法。这将会得到S:=0|1|0S|1A|0Z|1Z A:=0|0S|0Z 经过分析其中Z为多余状态可删去。SZ100100A解题思路二:写出其正规表达式(0|10)*(10|0|1)【如果仅有(0|10)*的话推导不出1,因为是连接关系,后面缺了10的话就会以1结尾,同样的道理还要推导出0,所以得到此正规式】,画出转换系统,然
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译原理 编译 原理 习题 解答 南京 邮电大学
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内