资源描述：
《编译原理习题答案_向张幸儿老师索取》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、习题16．试用各种不同的形式表示法描述1⅓的一切精度的近似值集合。解：省略表示法{1.3,1.33,1.333,……}描述表示法{1.3i
2、i≥1}或{1}{.3i
3、i>=1}错误：{x
4、x=1+3∑10-i
5、i>=1},因为形式表示不应涉及任何含义。错误：G[N]:N::=1.MM::=M3M::=3,因为文法仅一组重写规则，不是语言。若给出答案：L(G[N])，正确，但不简洁7.设字母表x={0,1,2,3,4,5,6,7},X+与X*各是什么？各举出4个不同长度的符号串作为例子。解：X是字母表x的正闭包，X*
6、是字母表的闭包，X*={ε}∪X+X+={0,1,00,01,123,345,1234,2345，…}因此是一切可能带前导0的八进制数的集合X*={ε,0,1,00,01,12,345,3456,…}X+:0,1,00,123X*:,1,00,123习题22．设文法G[]的规则是:::=a
7、b
8、c
9、a
10、c
11、0
12、1试写出VT与VN,并对下列符号串a、ab0、a0c01、0a、11与aaa给出可能的推导。解：VT={a,b,c,0,1}VN={}a:=>
13、aab0:=>0不能直接推导出b0,因此不能直接推导出ab0(不能写:=>0=>b0不能推导出ab0)a0c01:=>1=>01=>c01=>0c01=>a0c010a:=>a不能直接推导出0a(不能写:=>a=>0a不能推导出0a）11:=>1不能直接推导出11(不能写：=>1=>11不能推导出11)aaa:=>a=>aa=>aaa3．设G
14、[E]:E::=T
15、E+T
16、E-TT::=F
17、T*F
18、T/FF::=(E)
19、i1)试给出关于(i)、i*i-i与(i+i)/i的推导。2)证明E+T*F*i+I是该文法的句型，然后列出它的一切短语与简单短语。解：1）给出推导E=>T=>F=>(E)=>(T)=>(F)=>(i)不能写：E=>T=>F=>(E)=>(i)可以写:E=>T=>F=>(E)=>+(i)E=>E-T=>T-T=>T*F-T=>F*F-T=>i*F-T=>i*i-T=>i*i-F=>i*i-i(最左推导)或E=>E-T=>E-F=>E-i=>
20、T-i=>T*F-i=>T*i-i=>F*i-i=>i*i-i(最右推导)E=>T=>T/F=>F/F=>(E)/F=>(E+T)/F=>(T+T)/F=>(F+T)/F=>(i+T)/F=>(i+F)/F=>(i+i)/F=>(i+i)/i(最左推导)或E=>T=>T/F=>T/i=>F/i=>(E)/i=>(E+T)/i=>(E+F)/i=>(E+i)/i=>(T+i)/i=>(F+i)/i=>(i+i)/i(最右推导)2)证明E+T*F*i+i是该文法的句型：E=>E+T=>E+T+T=>E+T*F+T=>E
21、+T*F*F+T=>E+T*F*i+T=>E+T*F*i+F=>E+T*F*i+i或E=>E+T=>E+F=>E+i=>E+T+i=>E+T*F+i=>E+T*i+i=>E+T*F*i+i即，E=>*E+T*F*i+i，所以是该文法的句型。因为E=>*EE=>+E+T*F*i+iE=>*E+iE=>+E+T*F*iE=>*E+T+iT=>+T*F*iE=>*E+T*F*i+TT=>+iE=>*E+T*i+iT=>T*FE=>*E+T*F*F+FF=>i(=>+包括=>)所以句型E+T*F*i+i中相对于E的短语有E
22、+T*F*i+i和E+T*F*i相对于T的短语有T*F*i、T*F和i相对于F的短语有i所以句型E+T*F*i+i中相对于T的简单短语有T*F相对于F的简单短语有i不能用画语法分析树的方法来寻找短语，因按教学进度，还未讲到语法分析树。简单短语可如下寻找：首先寻找与规则右部相同的子符号串，把它归约成相应的非终结符号后,看是否是句型,如果仍是，则此子符号串是简单短语，否则不是。例如，子符号串E+T,可归约成E,但归约后成为E*F*i+i,显然不是句型，所以，E+T不是简单短语。对于短语，类似地寻找，即，先找子符号串,看
23、它能否归约到某个非终结符号,再看归约后得到的新符号串是否是句型，是，则是短语，否则，不是短语。当在学习了语法分析树之后，可以也应该使用语法分析树来寻找短语与简单短语。6．试为下列语言构造相应的文法。1）{anbmcmdn
24、m,n≥1}解:写出句子的一般形式:a…aab…bbbccc…cdd…dBBBAA易见可有文法G[A]：A::=aAd
25、aBdB::=bc
