《2015秋北语编译原理试题和答案解析》由会员分享,可在线阅读,更多相关《2015秋北语编译原理试题和答案解析(55页珍藏版)》请在金锄头文库上搜索。
1、北京语言大学网络教育学院编译原理模拟试卷一一、【单项选择题】(本大题共10小题,每小题2分,共20分)在每小题列出的四个选 项中只有一个选项是符合题目要求的,请将正确选项前的字母填在答题卷相应题号处。1、一个编译程序中,包含词法分析、(A )、中间代码生成、代码优化、目标代码生 成等五个部分。A语法分析B文法分析C语言分析D解释分析2、词法分析器用于识别(C )。A字符串B语句C单词D标识符3、语法分析器则可以发现源程序中的(D )。A语义错误B语法和语义错误C错误并校正D语法错误4、下面关于解释程序的描述正确的是(B)。(1) 解释程序的特点是处理程序时不产生目标代码。(2) 解释程序适用于
2、COBOL和FORTRAN语言。(3) 解释程序是为打开编译程序技术的僵局而开发的。A (1)(2)B (1)C (1) 2)(3)D (2)(3)5、解释程序处理语言时,大多数采用的是(B )方法。A 源程序命令被逐个直接解释执行B 先将源程序转化为中间代码,再解释执行C 先将源程序解释转化为目标程序,再执行D 以上方法都可以6、编译过程中,语法分析器的任务就是(B )。(1) 分析单词是怎样构成的(2) 分析单词串是如何构成语句和说明的(3) 分析语句和说明是如何构成程序的(4)分析程序的结构A (2)(3)B(2)(3)(4)C(1)(2)(3)D(1)(2)(3)(4)7、编译程序是一
3、种(C)。A汇编程序B翻译程序C解释程序D目标程序8、文法G所描述的语言是(C)的集合。A 文法G的字母表V中所有符号组成的符号串B 文法G的字母表V的闭包V*中的所有符号串C 由文法的开始符号推出的所有终极符号串D 由文法的开始符号推出的所有符号串9、文法分为四种类型,即0型、1型、2型、3型。其中3型文法是(B )。A短语文法B正规文法C上下文有关文法D上下文无关文法10、一个上下文无关文法G包括四个组成部分,它们是:一组非终结符号,一组终结 符号,一个开始符号,以及一组(D )。A 句子B句型C单词D规则二、【判断题】(本大题共10小题,每小题2分,共20分)正确的填T,错误的填F,填在
4、答题卷相应题号处。11、计算机高级语言翻译成低级语言只有解释一种方式。(F )12、如果一个文法存在某个句子对应两棵或者两棵以上不同的语法树,则说这个文法是 二义的。(T )13、甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能 完全相同。(T )14、正则文法其产生式为 A-a, A-Bb, A,BEVN, a、bGVT。(F )15、程序所需的数据空间在程序运行前就可确定,称为静态存储管理技术。(T )16、递归下降法允许任一非终结符是直接左递归的。(T )17、算符优先关系表不一定存在对应的优先函数。(F )18、自底而上语法分析方法的主要问题是候选式的选择。(F
5、 )19、LR法是自顶向下语法分析方法。(F )20、简单优先文法允许任意两个产生式具有相同右部。(F )三、【填空题】(本大题共10小空,每小空2分,共20分)请将答案填写在答题卷相应题号处。21、扫描器的任务是从(源程序 )中识别出一个个(单词符号 )。22、若源程序是用高级语言编写的,(目标程序)是机器语言程序或汇编程序,则其翻译程序称为(编译程序 )。23、编译方式与解释方式的根本区别在于(是否生成目标代码)。24、对编译程序而言,输入数据是(源程序),输出结果是(目标程序 )o25、产生式是用于定义(语法成分 )的一种书写规则。26、语法分析最常用的两类方法是(自上而下 )和(自下而
6、上 )分析法。四、【简答题】(本大题共4小题,每小题10分,共40分)请将答案填写在答题卷相应 题号处。27、什么是句子?什么是语言?(1) 设G是一个给定的文法,S是文法的开始符号,如果S-x(其中xEVT*),则称x是 文法的一个句子。(2) 设GS是给定文法,则由文法G所定义的语言L(G)可描述为:L(G) = x|S-x,x GVT*。28、写一文法,使其语言是偶正整数的集合,要求:(假定。为正整数)(1) 允许0打头;(2) 不允许0打头。(1) GS = (S,P,D,N,0,1,2,9,P,S)P:S-PD|DP-NP|ND-0|2|4|6|8N-0|1|2|3|4|5|6|7|
7、8|9(2) GS = (S,P,R,D,N,Q ,0,1,2,9,P,S)P:S-PD|P0|DP-NR|NR-QR|QD-2|4|6|8N-1|2|3|4|5|6|7|8|9Q-0|1|2|3|4|5|6|7|8|929、现有文法GS:S T aAbA T BcA|BBT idt| e请问aidtcBcAb是句型还是句子,为什么?S n aAb n aBcAb n aidtcAb n aidtcBcAb是句型但不是句子。30、构造正规式相应的NFA : 1(0|1)*101o1(0|1)* 101 对应的 NFA 为北京语言大学网络教育学院编译原理模拟试卷二一、【单项选择题】(本大题共10
8、小题,每小题2分,共20分)在每小题列出的四个选 项中只有一个选项是符合题目要求的,请将正确选项前的字母填在答题卷相应题号处。1、通常一个编译程序中,不仅包含词法分析,语法分析,中间代码生成,代码优化,目标代码生成等五个部分,还应包括(C )A解释器B模拟执行器C表格管理和出错处理D符号执行器2、文法 GN=(b, N,B,N, NTb|bB,BTbN),该文法所描述的语言是(C ) 0A L(GN)=bi|iN0B L(GN)=b2i|iN0C L(GN)=b2i+1|iN0D L(GN)=b2i+1|iN13、一个句型中的最左(B )称为该句型的句柄。A短语B简单短语 C素短语D终结符号4
9、、设G是一个给定的文法,S是文法的开始符号,如果S-x(其中xEV*),则称x 是文法G的一个(B ) oA候选式B句型C单词D产生式5、文法 GE:ETT|E + TTTF|T 大 FFTa| ( E )该文法句型E + F大(E + T)的简单短语是下列符号串中的(B )o(E + T )E + TFF大(E + T)A和B和C和D6、若一个文法是递归的,则它所产生的语言的句子(A )oA是无穷多个B是有穷多个C是可枚举的D个数是常量7、把汇编语言程序翻译成机器可执行的目标程序的工作是由(B )完成的。A编译器B汇编器C解释器D预处理器8、在语法分析处理中,FIRST集合、FOLLOW集合
10、、SELECT集合均是(B )。A非终极符集B终极符集C字母表D状态集9、在自底向上的语法分析方法中,分析的关键是(A )。A寻找句柄B寻找句型C消除递归D选择候选式10、在LR分析法中,分析栈中存放的状态是识别规范句型(C )的DFA状态。A句柄B前缀C活前缀D LR(0)项目二、【判断题】(本大题共10小题,每小题2分,共20分)正确的填T,错误的填F,填 在答题卷相应题号处。11、“用高级语言书写的源程序都必须通过编译,产生目标代码后才能投入运行”这种 说法。(F )12、最左推导常被称为规范推导。(F )13、一个句型的句柄一定是文法某产生式的右部。(T )14、在程序中标识符的出现仅
11、为使用性的。(F )15、仅考虑一个基本块,不能确定一个赋值是否真是无用的。(T )16、削减运算强度破坏了临时变量在一基本块内仅被定义一次的特性。(T )17、在中间代码优化中循环上的优化主要有不变表达式外提和削减运算强 度。 (F )18、一个有限状态自动机中,有且仅有一个唯一的终态。(F )19、数组元素的地址计算与数组的存储方式无关。(F)20、编译程序与具体的机器有关,与具体的语言无关。(F)三、【填空题】(本大题共10小空,每小空2分,共20分)请将答案填写在答题卷相应 题号处。21、后缀式abc-/所代表的表达式是(a/(b-c)。22、递归下降法不允许任一非终结符是直接(左)递
12、归的。23、自顶向下的语法分析方法的基本思想是:从文法的(开始符号)开始,根据给定的输入串并按照文法的产生式一步一步的向下进行(直接推导),试图推导出文法 的(句子),使之与给定的输入串(匹配 )。24、自底向上的语法分析方法的基本思想是:从输入串入手,利用文法的产生式一步一,步地向上进行(直接归约),力求归约到文法的(开始符号)。25、常用的参数传递方式有(传地址),传值和传名。26、在使用高级语言编程时,首先可通过编译程序发现源程序的全部( 语法 )错 误和部分语义错误。四、【简答题】(本大题共4小题,每小题10分,共40分)请将答案填写在答题卷相应 题号处。27、现有文法GS:S T a
13、AbA T BcA|BBT idt| e请问aidtccb是句型还是句子,为什么?S n aAb n aBcAb n aidtcAb n aidtcBcAb n aidtc e cAb n aidtccAbnaidtccBb naidtcc e b n aidtccb 是句型,也是句子。28、简述DFA与NFA有何区别?DFA与NFA的区别表现为两个方面:一是NFA可以若干个开始状态,而DFA 仅只一个开始状态。另一方面,DFA的映象M是从KXE到K,而NFA的映 象M是从KXE到K的子集,即映象M将产生一个状态集合(可能为空集), 而不是单个状态。29、写出表达式(a+b)/(a-b)-a(a+b*c)的三元式序列及四元式序列。三元式:(1) .(+,a,b)(2) .(-,a,b)(3) .(/,(2)(4) .(*,b,c)(5) .(+,a,)(6) .(-, (3), (5)四元式:(1) .(+,a,b,T1)(2) .(-,a,b,T2)(3) .(/,T1,T2,T3)(4) .(*,b,c,T4)(5) .(+,a,T4,T5)(6).(-,T3,T5,T6)30、已知文法G(S)Sa|A|(T)TTT, S|S写出句子(a, a), a)的规范归约过程及每一步的句柄。句型归约规则句柄(a,a),a)