2015秋北语编译原理试卷和答案

北京语言大学网络教育学院《编译原理》模拟试卷一一、【单项选择题】(本大题共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)解释程序适用于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、编译程序是一种（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，填在答题卷相应题号处。11、计算机高级语言翻译成低级语言只有解释一种方式。（F）12、如果一个文法存在某个句子对应两棵或者两棵以上不同的语法树，则说这个文法是二义的。（T）13、甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。（T）14、正则文法其产生式为A-a，A-Bb,A,B∈VN，a、b∈VT。（F）15、程序所需的数据空间在程序运行前就可确定，称为静态存储管理技术。（T）16、递归下降法允许任一非终结符是直接左递归的。（T）17、算符优先关系表不一定存在对应的优先函数。（F）18、自底而上语法分析方法的主要问题是候选式的选择。（F）19、LR法是自顶向下语法分析方法。（F）20、简单优先文法允许任意两个产生式具有相同右部。（F）三、【填空题】（本大题共10小空，每小空2分，共20分）请将答案填写在答题卷相应题号处。21、扫描器的任务是从（源程序）中识别出一个个（单词符号）。22、若源程序是用高级语言编写的，（目标程序）是机器语言程序或汇编程序，则其翻译程序称为（编译程序）。23、编译方式与解释方式的根本区别在于（是否生成目标代码）。24、对编译程序而言，输入数据是（源程序），输出结果是（目标程序）。25、产生式是用于定义（语法成分）的一种书写规则。26、语法分析最常用的两类方法是（自上而下）和（自下而上）分析法。四、【简答题】（本大题共4小题，每小题10分，共40分）请将答案填写在答题卷相应题号处。27、什么是句子？什么是语言？(1)设G是一个给定的文法，S是文法的开始符号，如果S-x(其中x∈VT*),则称x是文法的一个句子。(2)设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为：L(G)＝{x│S-x,x∈VT*}。28、写一文法，使其语言是偶正整数的集合,要求：（假定0为正整数）(1)允许0打头；(2)不允许0打头。(1)G[S]=({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|8|9(2)G[S]=({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、现有文法G[S]：SaAbABcA|BBidt|请问aidtcBcAb是句型还是句子，为什么？SaAbaBcAbaidtcAbaidtcBcAb是句型但不是句子。30、构造正规式相应的NFA:1(0|1)*101。1(0|1)*101对应的NFA为北京语言大学网络教育学院《编译原理》模拟试卷二一、【单项选择题】(本大题共10小题，每小题2分，共20分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。1、通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括（C）[A]解释器[B]模拟执行器[C]表格管理和出错处理[D]符号执行器2、文法G[N]=（{b}，{N，B}，N，{N→b│bB，B→bN}），该文法所描述的语言是（C）。[A]L(G[N])={bi│i≥0}[B]L(G[N])={b2i│i≥0}[C]L(G[N])={b2i+1│i≥0}[D]L(G[N])={b2i+1│i≥1}3、一个句型中的最左（B）称为该句型的句柄。[A]短语[B]简单短语[C]素短语[D]终结符号4、设G是一个给定的文法，S是文法的开始符号，如果S-x(其中x∈V*),则称x是文法G的一个（B）。[A]候选式[B]句型[C]单词[D]产生式5、文法G[E]：E→T∣E＋TT→F∣T﹡FF→a∣（E）该文法句型E＋F﹡(E＋T)的简单短语是下列符号串中的（B）。①（E＋T）②E＋T③F④F﹡(E＋T)[A]①和③[B]②和③[C]③和④[D]③6、若一个文法是递归的，则它所产生的语言的句子（A）。[A]是无穷多个[B]是有穷多个[C]是可枚举的[D]个数是常量7、把汇编语言程序翻译成机器可执行的目标程序的工作是由（B）完成的。[A]编译器[B]汇编器[C]解释器[D]预处理器8、在语法分析处理中，FIRST集合、FOLLOW集合、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、在程序中标识符的出现仅为使用性的。（F）15、仅考虑一个基本块，不能确定一个赋值是否真是无用的。（T）16、削减运算强度破坏了临时变量在一基本块内仅被定义一次的特性。（T）17、在中间代码优化中循环上的优化主要有不变表达式外提和削减运算强度。（F）18、一个有限状态自动机中，有且仅有一个唯一的终态。（F）19、数组元素的地址计算与数组的存储方式无关。（F）20、编译程序与具体的机器有关，与具体的语言无关。（F）三、【填空题】（本大题共10小空，每小空2分，共20分）请将答案填写在答题卷相应题号处。21、后缀式abc-/所代表的表达式是（a/(b-c)）。22、递归下降法不允许任一非终结符是直接（左）递归的。23、自顶向下的语法分析方法的基本思想是：从文法的（开始符号）开始，根据给定的输入串并按照文法的产生式一步一步的向下进行（直接推导），试图推导出文法的（句子），使之与给定的输入串（匹配）。24、自底向上的语法分析方法的基本思想是：从输入串入手，利用文法的产生式一步一步地向上进行（直接归约），力求归约到文法的（开始符号）。25、常用的参数传递方式有（传地址），传值和传名。26、在使用高级语言编程时，首先可通过编译程序发现源程序的全部（语法）错误和部分语义错误。四、【简答题】（本大题共4小题，每小题10分，共40分）请将答案填写在答题卷相应题号处。27、现有文法G[S]：SaAbABcA|BBidt|请问aidtccb是句型还是句子，为什么？SaAbaBcAbaidtcAbaidtcBcAbaidtccAbaidtccAbaidtccBbaidtccbaidtccb是句型，也是句子。28、简述DFA与NFA有何区别？DFA与NFA的区别表现为两个方面:一是NFA可以若干个开始状态，而DFA仅只一个开始状态。另一方面，DFA的映象M是从K×∑到K，而NFA的映象M是从K×∑到K的子集，即映象M将产生一个状态集合（可能为空集），而不是单个状态。29、写出表达式(a+b)/(a-b)-a(a+b*c)的三元式序列及四元式序列。三元式：⑴.(+,a,b)⑵.(-,a,b)⑶.(/,⑴,⑵)⑷.(*,b,c)⑸.(+,a,⑷)⑹.(-,⑶,⑸)四元式：⑴.(+,a,b,T1)⑵.(-,a,b,T2)⑶.(/,T1,T2,T3)⑷.(*,b,c,T4)⑸.(+,a,T4,T5)⑹.(-,T3,T5,T6)30、已知文法G(S)S→a|∧|(T)T→T，S|S写出句子((a，a)，a)的规范归约过程及每一步的句柄。句型归约规则句柄((a，a)，a)S→aa((S，a)，a)T→SS((T，a)，a)S→aa((T，S)，a)T→T，ST，S((T)，a)S→(T)(T)(S，a)T→SS(T，a)S→aa(T，S)T→T，ST，S(T)S→(T)(T)S北京语言大学网络教育学院《编译原理》模拟试卷三选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。1、文法G产生的（D）的全体是该文法描述的语言。[A]句型[B]终结符集[C]非终结符集[D]句子2、若文法G定义的语言是无限集，则文法必然是（A）。[A]递归的[B]前后文无关的[C]二义性的[D]无二义性的3、四种形式语言文法中，1型文法又称为（C）文法。[A]短语结构文法[B]前后文无关文法[C]前后文有关文法[D]正规文法4、一个文法所描述的语言是（A）。[A]唯一的[B]不唯一的[C]可能唯一，也可能不唯一[D]都不对5、（B）和代码优化部分不是每个编译程序都必需的。[A]语法分析[B]中间代码生成[C]词法分析[D]目标代码生成6、（B）是两类程序语言处理程序。[A]高级语言程序和低级语言程序[B]解释程序和编译程序[C]编译程序和操作系统[D]系统程序和应用程序7、数组的内情向量中肯定不含有数组的（D）的信息。[A]维数[B]类型[C]维上下界[D]各维的界差8、（A）是一种典型的解释型语言。[A]BASIC[B]C[C]FORTRAN[D]PASCAL9、文法分为四种类型，即0型、1型、2型、3型。其中2型文法是（D）。[A]短语文法[B]正则文法[C]上下文有关文法[D]上下文无关文法10、与编译系统相比，解释系统（D）。[A]比较简单、可移植性好、执行速度快[B]比较复杂、可移植性好、执行速度快[C]比较简单、可移植性差、执行速度慢[D]比较简单、可移植性好、执行速度慢二、【判断题】(本大题共10小题，每小题2分，共20分)正确的填T，错误的填