资源描述：
《编译原理作业参考答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、编译原理作业参考答案作业一一、是非题1.(×)2.(×)3.(×)4.(×)5.(×)6.(√)7.(√)8.(√)9.(√)10.(×)11.(√)12.(√)13.(√)二、填空题1.（词法分析），（语法分析），（中间代码生成），（代码优化），（目标代码生成）2．（单词符号），（语法单位）。3.（源程序），（单词符号）4.（语法），（语义）5.(词法分析)、(语法分析)、(语义分析)，(中间代码产生)，(代码优化)，(目标代码生成)6.(解释方式)7.(语法规则)8.(上下文无关文法)9.(自上而下分析法)，(自下而上分析法)10.(规范
2、推导)11.(最左归约)三、名词解释题：1．词法分析器-----执行词法分析的程序。2.自编译方式------先对语言的核心部分构造一个小小的编译程序，再以它为工具构造一个能够编译更多语言成分的较大编译程序。如此扩展下去，就像滚雪球一样，越滚越大，最后形成人们所期待的整个编译程序。3.遍-----所谓“遍”就是对源程序或中间结果长头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。4.编译程序-----一种翻译程序:能够把某一种语言程序(称为源语言程序)转换成另一种语言(成为目标程序),而后着与前者在逻辑上是等价的。5.超前搜索-
3、----所谓超前搜索是在词法分析过程中，有时为了确定词性，需超前扫描若干个字符。6.13短语------令G是一个文法，S划文法的开始符号，假定αβδ是文法G的一个句型，如果有SαAδ且Aβ，则称β是句型αβδ相对非终结符A的短语。7.规范句型------由规范推导所得到的句型。8.句柄------一个句型的最左直接短语。9.-规范推导-----最右推导又称为规范推导。四、简答题：1.正规式a(a
4、b)*。2.(a*b
5、b*a)={a,b,ab,ba,aab,bba……}3.状态转换图是一张有限方向图。在状态转换图中，有一个初态，至少一个终态
6、。（用双圈表示）。一个状态转换图可用于识别（或接受）一定的字符串。4.证明:因为L(b(ab)*)={b}{e,ab,abab,ababab,…}={b,bab,babab,bababab,…}L(ba)*b)={e,ba,baba,bababa,…}{b}={b,bab,babab,bababab,…}=L(b(ab)*)所以,b(ab)*=(ba)*b5.正规表达式为b(a
7、b)*aa6.词法分析器的功能输入源程序，按照构词规则分解成一系列单词符号。7.词法分析是编译过程中的一个阶段，在语法分析前进行。词法分析作为一遍，可以简化设计，改进
8、编译效率，增加编译系统的可移植性。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。8.编译预处理:滤掉空格，跳过注释、换行符等。9.句子adccd的分析过程：步骤符号栈输入串产生式0#Sadccd#1#ABadccd#S→BA2#AAaadccd#B→aA3#AAdccd#4#Addccd#A→d135#Accd#6#SBccd#A→BS7#Scccd#B→c8#Scd#9#ABcd#B→c10#Acd#11#Ad#12#dd#A→d13##10.一个文法G别是LL(1)文法的充要条件是:(1)
9、FIRST(α)∩FIRST(β)=Ф(2)如果β=*>ε,FIRST(α)∩FOLLOW(A)=Ф11.(1)消除左递归S→aFS’
10、*aFS’S’→*aFS’
11、εF→+aF
12、+a(2)提公共左因子S→aFS’
13、*aFS’S’→*aFS’
14、εF→+aF’F’→F
15、ε12.句子b(aa)b的规范归约过程：步骤符号栈输入串动作0#b(aa)b#预备1#b(aa)b#移进132#b(aa)b#移进3#b(aa)b#移进4#b(Aa)b#归约5#b(Ma)b#移进6#b(Ma)b#移进7#b(Bb#归约8#bAb#归约9#bAb#移进10#S#接受
16、五、计算题：1.(1)画出句型对应的语法树。句型(S,(a))的语法树如下图所示S(L)S(L)L,SSa(2)句子(a,(a,a)的最左推导S=>(L)=>(L,S)=>(S,S)=>(a,S)=>(a,(L))=>(a,(L,S))=>(a,(S,S))=>(a,(a,S))=>(a,(a,a))2.G[S]:S→A
17、BDD→CD
18、AA→1
19、3
20、5
21、7
22、9B→2
23、4
24、6
25、8
26、A13C→B
27、03.证明：因为文法G[S]存在句子aa有两个不同的最左推导，所以文法G[S]是是二义性的。S=>SaS=>SaSaS=>aSaS=>aaS=>aaS=
28、>SaS=>aS=>aSaS=>aaS=>aa4.所求文法是G[S]:S→ABA→aAc
29、DD→bD
30、bB→aBb
31、aabb5.⑴消除左递，文法变为G’[S]：S→
