2013-2014-2编译原理试卷A带答案

第1页共5页2013–2014学年第二学期计算机科学与技术专接本专业编译原理试卷（A）卷一、填空题（每空2分，10个空，共20分，请将正确的答案填写在答题纸上）1.若将X语言的源程序翻译成Y语言的程序，翻译的实现语言为Z语言，则称Z语言是翻译的宿主语言2.设有字母表Σ={a,bb,c},字母表Σ上的符号串ω=abbc、，则|ω3|=93.设有有限自动机如下图所示，设I={x}，则Ib={1,2,3}4.语言中具有独立意义的最小语法单位是单词5.设有文法S→ABcA→a|εB→b|ε，则First(S)={a,b,c}6.规范归约中的可归约串是指（句柄）。7.中间代码产生是依据语言的语义规则进行的8.存储分配的基本单元是过程的活动记录9.在基本块范围内的优化称为局部优化10.在目标代码生成阶段，符号表是地址分配___的依据。二、选择题（每题2分，10题，共20分）（在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填在答题纸上。错选、多选或未选均无分。）1.目前最常用的文法表示方法为………………………………（A）题号一二三四五合计得分阅卷人河北科技师范学院装订线系（部）班级学号姓名第2页共5页A.BNF表示法B.YACCC.LexD.DAG2.下图所示自动机所描述的语言是…………………………………………（B）A.aa(ε(a|b)*(a|b))B.aa((a|b)*|ab)C.aa((a|b)|ab)D.aa((a|b|ab)*3.词法分析器的输出结果是…………………………………………………（C）A．单词的种别编码B．单词在符号表中的位置C．单词的种别编码和属性值D．单词属性值4.在自顶向下的语法分析方法中，分析的关键是…………………………（D）A.寻找句柄B.寻找句型C.消除递归D.选择候选式5.设有文法G[S]为：SABAAa|bBBa|Sb，下面哪个不是句型baSb的短语…………………………………………………………………………………（C）A.baSbB.SbC.aSbD.ba6.在编译过程中，引起源程序发生质的变化的阶段是………………………（B）A.语法分析B.语义分析C.词法分析D.中间代码生成7.常用的两种动态存贮分配办法是动态分配和动态分配………（A）A.栈式、堆式B.栈式、队列式C.堆式、队列式D.记录式、队列式8.有代码为x=a+b+c;y=a+b+d;可以采用的优化方法是……………………………………………………（B）A.常量的合并与传播B.公共子表达式删除C.无用赋值的删除D.死代码删除9.设有如下代码段，则其可以被划分的基本块的个数为……………………（C）ReadNI=N5ba第3页共5页J=2L1：ifI≤JgotoL3I∶=I-JJ∶=J+1gotoL1L3：Print′YES′haltA.2B.3C.4D.510.经过编译所得到的目标程序是……………………………（D）A．四元式序列B．间接三元式序列C．二元式序列D．机器语言程序或汇编语言程序三、判断题（每题1分，10题，共10分）（对的打“√”号错误的打“×”，写在答题纸上）1.解释程序和编译程序的区别在于是否生成目标代码…………（√）2.若一个文法是递归的，则它所产生语言的句子个数必定是无穷的……………………………………………………………………（√）3.词法分析应遵循的是语义规则…………………………………(×）4.语法分析方法中的递归下降分析法属于自底向上分析方法…（×）5.算符优先分析法的实质就是借助优先关系来寻找可规约串…（√）6.编译中进行语法检查的目的是为了发现程序中所有错误……（×）7.中间代码产生是依据语言的语义规进行的…………………（√）8.环境把名字映射到左值，而状态把左值映射到右值…………（√）9.含有优化功能的编译程序执行效率高…………………………(×）10.目标代码指令越丰富，代码生成的工作越复杂………………(×）四、简答题（共四小题，每题5分，共20分）1.设有确定的有限自动机M:（{1,2,3,4,5},{a,b},f，1，{4,5}）f（1，a）=2f（1，b）=3f（2，a）=2f（2，b）=3第4页共5页f（3，a）=4f（4，a）=5f（4，b）=3f（5，a）=2画出其状态转换图和状态转换矩阵状态转换图2.设文法G(S)：S→(L)|Sa|aL→L，S|La|ab消除其左递归，写出写出左递归后的文法S→(L)S’|aS’S’→aS’|εL→abL’L’→,SL’|aL’|ε3.有文法G(S):S→a|∧|(T)T→T,S|S求非终结符S和T的FIRSTVT和LASTVT答案：FIRSTVT(S)={a，∧，（}FIRSTVT(T)={，，a，∧，（}LASTVT（S）={a，∧，)}LASTVT（T）={，，a，∧，)}4.写出赋值语句a=w+(a+b)*(c+d/(e-10)+8)的逆波兰式和四元式表示逆波兰式：wab+cde10-/+8+*=四元式：+abt1-e10t2/dt2t3+ct3t4+t48t5*t1t5t6第5页共5页+wt6t7=t7a五、分析题（3小题，每题10分，共30分）1.给定非确定的有限自动机M如下图所示将M确定化，并画出确定化后的状态转换图（要求：写出步骤）2.设有文法G[S]:S→bBS′S′→aBS′|εA→S|aB→Ac其LL(1)分析表如下利用此分析表判断输入串bacaac（改）是否为文法G[S]的句子，给出bacaac的分析过程3.应用DAG对下面的基本块进行优化，写出优化后的基本块（要求写出过程）1.T0:=3.146.T3:=2*T0abc#SS→bBS′S′S′→aBS′S′→εS′→εAA→aA→SBB→AcB→Ac012345678910εεεabεεεabbεε第6页共5页2.T1:=2*T07.T4:=R+r3.T2:=R+r8.T5:=T3*T44.A:=T1*T29.T6:=R-r5.B:=A10.B:=T5*T第7页共5页