编译原理(选择填空简答)题

1一、是非题(下列各题，你认为正确的，请在题干的括号内打“√”，错的打“×”。每题1分,共5分)1、算符优先关系表不一定存在对应的优先函数。√2、数组元素的地址计算与数组的存储方式有关。√3、仅考虑一个基本块，不能确定一个赋值是否真是无用的。√4、每个文法都能改写为LL(1)文法。×5、对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。×6、一个LL(1)文法一定是无二义的。7、逆波兰法表示的表达式亦称前缀式。8、目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。9、正规文法产生的语言都可以用上下文无关文法来描述。10、一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。二、选择题：1.编译原理是对（c）。A、机器语言的执行B、汇编语言的翻译C、高级语言的翻译D、高级语言程序的解释执行2.词法分析器的输出结果是（d）。A、单词自身值B、单词在符号表中的位置C、单词的种别编码D、单词的种别编码和自身值3.若文法G定义的语言是无限集，则文法必然是（c）A.前后文无关文法B.正规文法C.二义性文法D.递归文法4.文法：G：S→xSx|y所识别的语言是（d）。A、xnyxmB、(xyx)*C、x*yx*D、xnyxn（n≥0）1．文法G产生的⑴的全体是该文法描述的语言。dA．句型B.终结符集C.非终结符集D.句子2．若文法G定义的语言是无限集，则文法必然是⑵：aA．递归的B前后文无关的C二义性的D无二义性的3．Chomsky定义的四种形式语言文法中，0型文法又称为⑶文法；1型文法又称为⑷文法；2型语言可由⑸识别。A．短语结构文法B前后文无关文法C前后文有关文法D正规文法E图灵机F有限自动机G下推自动机4．一个文法所描述的语言是⑹；描述一个语言的文法是⑺。A．唯一的B不唯一的C可能唯一，好可能不唯一5．数组的内情向量中肯定不含有数组的⑻的信息A．维数B.类型C.维上下界D.各维的界差6．在下述的编译方法中，自底向上的方法有⑼，自顶向下的分析方法有⑽。①简单优先分析②算符优先分析③递归下降分析④预测分析技术⑤LR（K）分析⑥SLR（k）分析⑦LL（k）分析⑧LALR（K）分析A.③④⑦B.③④⑧C.①②⑧D.③④⑤⑥⑦E.①②⑤⑥⑦F.①②⑤⑥⑧⑴D⑵A⑶A⑷C⑸G.⑹A⑺B⑻A⑼F⑽A21、编写一个计算机高级语言的源程序后，到正式上机运行之前，一般要经过__B____这几步①编辑②编译③连接④运行A、①②③④B、①②③C、①③D、①④2、使用高级语言进行编程时，首先可以通过编译程序发现源程序的所有___A__错误和部分___B__错误A、语法B、语义C、语用D运行3、乔姆斯基定义的四种形式语言文法分别为：__（1）_文法（又称_（2）___文法）、（3）___文法（又称_（4）___文法）、__（5）_文法（又称_（6）___文法）、_（7）__文法（又称__（8）__文法）（1）0型（2）短语文法（3）1型（4）上下文有关文法（5）2型（6）上下文无关文法（7）3型（8）正则4、巴科斯—诺尔范式（即BNF）是一种广泛采用的__C__工具A、描述规则B、描述语言C、描述文法D、描述句子给定文法AbA|cc,下面的符号串为该文法句子的是_A①cc②bcbc③bcbcc④bccbcc⑤bbbccA、①⑤B、①③④⑤C、①④D、①②③④⑤5、上下文无关文法__A____产生语言L={anbnci|i=1,n=1}A、可以B、不可以6、文法的二义性与语法的二义性是两个__A___的概念A、不同B、相同C、无法判断7、一个语言的文法是___B____A、唯一的B、不唯一的C、个数有限的8、二义文法是指__D___A、对应有两棵不同语法树的文法B、对应两面三刀种不同推导的文法C、文法中的任何一个非终结符，都存在以它为左部的两面个不同的产生式D、以上说法都是错误的9、关于短语与句柄，正确的论述是：BA、短语就是句柄B、直接短语才可能是句柄C、左短语一定是句柄D、最右短语一定是句柄10、词法分析器的另一个名称为__B_____A、分析器具B、扫描器C、划分处理器D、词法探索器11、递归下降分析方法属于————BA、自左至右B、自顶向下C、自底向上D、自右向左12、算符优先文法是一种自底向上的分析方法，它是以_B__作为每一步归约的对象3A、最左直接短语B、最左素短语C、最左直接短语D、句柄13、赋值语句X:=-(a+b)/(c-d)-(a+b*c)的逆波兰表示为CA、Xab+cd-/-bc*a+-:=B、Xab+/cd-bc*a+--:=C、Xab+-cd-/abc*+-:=D、Xab+cd-/abc*+--:=14、在编译过程中，比较常见的中间语言有D①波兰表示②逆波兰表示③三元式④四元式⑤树型表示A、①③④B、②③④C、①③④⑤D、②③④⑤15、运行阶段存储组织与管理的目的是C①提高编译程序的运行速度②提高目标程序的运行速度③为运行阶段存储分配作准备A、①②B、①③C、②③D、①②③16、编译方法中，动态存储分配的含义是AA、在运行阶段对源程序中的量进行分配B、在编译阶段对源程序中的量进行分配C、在编译阶段对源程序中的量进行分配，在运行时这些量的地址可以根据需要改变D、以上都不正确17、FOTRAN编译中存储分配是_A_____。A静态存储分配B动态存储分配18、与PASCAL语言存储分配方式相似的语言是___A___。AC语言BBASIC语言CFOTRAN-7719、局部优化是局限于______范围内的一种优化。可选项有：A程序的一个基本块B一个函数或一个过程C一个基本的流程语句结构D程序的任何一个局部20、合并表达式中常量运算的目的________。①尽可能合并常量，使用统一的常量标识符替代表达式中的常量②在表达式尽可能去掉重复的常量表达，只留下一个，使表达式尽可能简洁③将可在编译时刻计算的常量运算在编译时刻就算出来，用计算结果替换表达式中出的所有这种常量运算，使生成的代码指令尽可能少可选项有：A①B②C③D①②③三、填空题(每题2分，共20分)1、从功能上说，程序语言的语句大体可分为_执行性_语句和_说明性_语句两大类。2、扫描器的任务是从_源程序_中识别出一个个_单词符号_。3、所谓最右推导是指：_任何一步αβ都是对α中最右非终结符进行替换的_。4、语法分析最常用的两类方法是_自上而下_和_自下而上_分析法。45、一个上下文无关文法所含四个组成部分是一组终结符、一组非终结符、一个开始符号、一组产生式_。6、所谓语法制导翻译方法是__为每个产生式配上一个翻译子程序，并在语法分析的同时执行这些子程序__。7、符号表中的信息栏中登记了每个名字的有关的性质，如_类型、种属、所占单元大小、地址_等等。8、一个过程相应的DISPLAY表的内容为现行的活动记录的地址和所有外出最新活动的记录地址。9、常用的两种动态存贮分配办法是栈式动态分配和堆式动态分配。10、产生式是用于定义_语法范畴_的一种书写规则。11、一般程序语言的语法单位有：表达式、语句、分程序、和函数、过程、程序等等。12、语法分析器的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。13、若源语言用高级语言编写的，目标程序是_等价的机器语言程序或汇编程序，则其翻译程序称为编译程序。14、高级语言经过编译生成的目标程序一般是_机器语言程序或__汇编语言程序_15、一个高级语言的源程序在编写形成后到正式运行前，一般要经过编辑、编译、连接这三个阶段16、假设G是一个文法，S是文法的开始符号，如果S*X，则称X是句型17、乔姆斯基定义的四种形式语言文法分别为：__（1）_文法（又称_（2）___文法）、（3）___文法（又称_（4）___文法）、__（5）_文法（又称_（6）___文法）、_（7）__文法（又称__（8）__文法）（1）0型（2）短语文法（3）1型（4）上下文有关文法（5）2型（6）上下文无关文法（7）3型（8）正则8、确定的有穷自动机是一个（五元组），通常表示为（(S,Σ,δ,s0,F)）19、单词的描述工具有有穷自动机、（正规式）与（正规文法）20、单词的三种描述工具互相方间存在（等价性）21、符号表的内容包括两面部分：_标识符的名字_和__与标识符相关的信息_。11、在编译中，各个阶段均广泛应用于的数据结构是（表），它记录着不同阶段时的信息，以便查询和修改，其中使用期最长的是（符号表）22、在PASCAL中，由于允许用户动态申请与释放内存间，所以必须采用（堆）存储分配技术23、过程与过程引用中信息交换的方法是（参数传递）与（全局变量）四、名词解释(每题2分，共10分)1、遍:指编译程序对源程序或中间代码程序从头到尾扫描一次。2．无环路有向图(DAG):如果有向图中任一通路都不是环路，则称有向图为无环路有向图，简称DAG。3．语法分析:按文法的产生式识别输入的符号串是否为一个句子的分析过程。4．短语:令G是一个文法。S划文法的开始符号，假定αβδ是文法G的一个句型，如果有SαAδ且AB，则称β是句型αβ相对非终结符A的短语。5．后缀式:种把运算量写在前面，把算符写在后面的表示表达式的方法。56．词法分析器:指执行词法分析的程序。7．语法:组规则，用它可以形成和产生一个合式的程序8．最右推导:指对于一个推导序列中的每一步直接推导，被替换的总是当前符号串中的最右非终结符号。9．语法制导翻译:在语法分析过程中，根据每个产生式所对应的语义子程序进行翻译的办法叫做语法制导翻译。10．基本块:指程序中一个顺序执行的语句序列，其中只有一个入口，一个出口，入口即第一个语句。出口即最后一个语句。五、简述题(每题4分，共24分)1、何谓优化？按所涉及的程序范围可分为哪几级优化？2、目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？3、符号表的作用是什么？符号表的查找的整理技术有哪几种?4、所谓DISPLAY表？其作用是什么?5、LL（1）分析法对文法有哪些要求？6、常见的存储分配策略有几种？它们都适合于什么性质的语言？7、常见循环优化都有哪些项目？8、什么是活动记录？它主要由哪些内容构成？1、答：优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。(2分)三种级别：局部优化、循环优化、全局优化。(2分)2、答：目标代码通常采用三种形式：机器语言，汇编语言，待装配机器语言模块。(2分应着重考虑的问题：(1)如何使生成的目标代码较短；(2)如何充分利用寄存器，以减少访问内存次数；(3)如何充分利用指仅系统的的特点。(2分)3、答：作用：登记源程序中出现的各种名字及其信息，以及编译各阶段的进展状况。(2分)主要技术：线性表，对折查找与二叉树，杂凑技术。(2分)4、答：display表是层次显示表。由于过程嵌套允许内层过程引用外层过程定义的数据，因此，当一个过程运行时必须跟踪它的所有外层过程的最新活动记录起始地址，而display表就是用于登记每个外层过程的最新活动记录起始地址。5、答：对于G中的每个产生式A→γ1|γ2|…|γm，其各候选式均应满足：（1）不同的候选式不能推出以同一终结符号打头的符号串，即FIRST(γi)∩FIRST(γj)=φ（1≤i，j≤m；i≠j）（2）若有γjε，则其余候选式γi所能推出的符号串不能以FOLLOW(A)中的终结符号开始，即有FIRST(γi)∩FOLLOW(A)=φ（i≤1,2,…,m；i≠j）6、答：有三种分配存储空间的方式：6（1）静态分配若在编译阶段就能确定源程序中各个数据实体的存储空间大小，则可以采用较简单的静态存储管理。适合静态管理的语言应具备条件：数组上下界是常数、过程调用不允许递归、不允许动态建立数据实体。（2）栈式分配适用于允许递归调用的程序设计语言；（3）堆式分配对于允许程序在运行时为变量动态申请和释放存储空间的语言，采用堆式分配是最有效的解决方案。7、答：不变运算外提；运算强度削弱；消除归纳变量；下标变量地址计算优化