《编译原理》期末考试复习题

1《编译原理》期末考试复习题一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分）×1．计算机高级语言翻译成低级语言只有解释一种方式。()×2．在编译中进行语法检查的目的是为了发现程序中所有错误。()√3．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。()×4．正则文法其产生式为A-a，A-Bb,A,B∈VN，a、b∈VT。()√5．每个文法都能改写为LL(1)文法。()√6．递归下降法允许任一非终极符是直接左递归的。()×7．算符优先关系表不一定存在对应的优先函数。()×8．自底而上语法分析方法的主要问题是候选式的选择。()×9．LR法是自顶向下语法分析方法。()×10．简单优先文法允许任意两个产生式具有相同右部。()三、填空题(每空1分，共10分)1．编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析,中间代码生成,代码优化等几个基本阶段,同时还会伴有_____和____。表格管理出错处理_2．若源程序是用高级语言编写的,____是机器语言程序或汇编程序,则其翻译程序称为____。_目标程序_编译程序3．编译方式与解释方式的根本区别在于____。是否生成目标代码_4．对编译程序而言,输入数据是____,输出结果是_____。_源程序目标程序25．产生式是用于定义____的一种书写规则。_语法成分6．语法分析最常用的两类方法是_____和____分析法。自上而下_自下而上四、简答题（20分）1.什么是句子？什么是语言?答：(1)设G是一个给定的文法，S是文法的开始符号，如果Sx(其中x∈VT*),则称x是文法的一个句子。(2)设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为：L(G)＝{x│Sx,x∈VT*}。一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分）×1．对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。()×2．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。()√3．递归下降分析法是自顶向上分析方法。()×4．产生式是用于定义词法成分的一种书写规则。()√5．LR法是自顶向下语法分析方法。()√6．在SLR（1）分析法的名称中，S的含义是简单的。()×7．综合属性是用于“自上而下”传递信息。()×8．符号表中的信息栏中登记了每个名字的属性和特征等有关信息，如类型、种属、所占单元大小、地址等等。()×9．程序语言的语言处理程序是一种应用软件。()×10．解释程序适用于COBOL和FORTRAN语言。()三、填空题(每空1分，共10分)1．一个句型中的最左简单短语称为该句型的___句柄__。32．对于文法的每个产生式都配备了一组属性的计算规则，称为__语义规则___。3．一个典型的编译程序中，不仅包括__词法分析___、__语法分析___、__中间代码生成___、代码优化、目标代码生成等五个部分，还应包括表格处理和出错处理。4．从功能上说，程序语言的语句大体可分为__执行性___语句和__说明性___语句两大类。5．扫描器的任务是从__源程序___中识别出一个个___单词符号__。6．产生式是用于定义__语法范畴___的一种书写规则。一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分）×1．编译程序是对高级语言程序的解释执行。()×2．一个有限状态自动机中，有且仅有一个唯一的终态。()√3．一个算符优先文法可能不存在算符优先函数与之对应。()×4．语法分析时必须先消除文法中的左递归。()√5．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。()√6．逆波兰表示法表示表达式时无须使用括号。()×7．静态数组的存储空间可以在编译时确定。()×8．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。()×9．两个正规集相等的必要条件是他们对应的正规式等价。()×10．一个语义子程序描述了一个文法所对应的翻译工作。()三、填空题(每空1分，共10分)1．计算机执行用高级语言编写的程序主要有两种途径：____和_____。解释_编译42．扫描器是_____，它接受输入的_____，对源程序进行_____并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。词法分析器源程序词法分析3．自上而下分析法采用____、归约、错误处理、_____等四种操作。移进_接受4．一个LR分析器包括两部分：一个总控程序和_____。一张分析表5．后缀式abc-/所代表的表达式是____。_a/(b-c)6．局部优化是在___范围内进行的一种优化。_基本块_一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分）1．设r和s分别是正规式，则有L(r|s)=L(r)L(s)。(×)2．确定的自动机以及不确定的自动机都能正确地识别正规集。(√)3．词法分析作为单独的一遍来处理较好。(×)4．构造LR分析器的任务就是产生LR分析表。(√)5．规范归约和规范推导是互逆的两个过程。(×)6．同心集的合并有可能产生新的“移进”/“归约”冲突。(×)7．LR分析技术无法适用二义文法。(×)8．树形表示和四元式不便于优化，而三元式和间接三元式则便于优化。(×)59．程序中的表达式语句在语义翻译时不需要回填技术。(√)10．对中间代码的优化依赖于具体的计算机。(×)三、填空题(每空1分，共10分)1．词法分析基于__正则___文法进行，即识别的单词是该类文法的句子。2．语法分析基于__上下文无关___文法进行，即识别的是该类文法的句子。语法分析的有效工具是__语法树___。3．分析句型时，应用算符优先分析技术时，每步被直接归约的是__最左素短语___，而应用LR分析技术时，每步被直接归约的是___句柄__。4．语义分析阶段所生成的与源程序等价的中间表示形式可以有__逆波兰___、___四无式表示__与___三元式表示__等。一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分）1．一个LL(l)文法一定是无二义的。(×)7．LR法是自顶向下语法分析方法。(×)2．正规文法产生的语言都可以用上下文无关文法来描述。(×)3．一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。(√)4．目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。(×)5．逆波兰法表示的表达式亦称前缀式。(√)6．如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。(√)8．数组元素的地址计算与数组的存储方式有关。(×)9．算符优先关系表不一定存在对应的优先函数。(×)10．对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。(×)三、填空题(每空1分，共10分)61．语法分析是依据语言的__语法___规则进行的，中间代码产生是依据语言的__语义___规进行的。2．语法分析器的输入是__单词符号串___，其输出是__语法单位___。3．一个名字的属性包括__类型___和__作用域___。4．产生式是用于定义___语法成分__的一种书写规则。5．逆波兰式ab+c+d*e-所表达的表达式为__(a+b+c)*d-e___。6．语法分析最常用的两类方法是__自上而下___和__自下而上___分析法。二、填空题（每空2分，共22分）1．已知文法G[S]：S→(A)|a，A→AcS|S|b；该文法的开始符号是S，非终结符号集合为{S,A}，终结符号集合为{a,b,c,(,)}。2．描述源程序中的单词结构有3种方法：有穷自动机，正规式和正规文法。3．自上而下的语法分析方法有LL(1)和递归下降方法。4．设有文法G[S]：S→Sa|a，构造它的拓广文法，引入一个产生式：Sˊ→S；则I。=Closure（{[Sˊ→·S，＃]}）={[Sˊ→·S，＃],[S→·Sa，＃/a],[S→·a，＃/a]}。5．在LR（0）项目集规范族中，若有项目：AAbB，其中TbV，称该项目为移进项目。6.LL(1)语法分析方法中应解决的主要问题是消除回溯；LR语法分析方法中应解决的主要问题是项目冲突。三、判断题（判断下列各题的正错，若正确，在括号中写“正”；否则写“错”。每题2分，共16分）1．一个文法有二义性，则由它描述的语言一定具有二义性。（错）2．若一个语言有无穷多个句子，则定义该语言的文法一定是递归的。（正）3．若有正规式a*b，则与之等价的文法应该是G[A]：A→aA|b。（正）4．设有文法G[A]：A→aB，B→bB|b，则该文法是LL(1)文法。（错）5．由文法法G的开始符号S推导出来的符号串，称为文法G的句子。（错）6．最左素短语是句型最左边的短语。（错）7．LR语法分析法是一种规范规约的分析方法。（正）78．存在能够被确定的有穷自动机DFA识别，却不能用正规式表示的语言。（错）1.文法G的一个句子对应于多个推导，则G是二义性的。（×）2.动态的存储分配是指在运行阶段为源程序中的数据对象分配存储单元。（√）3.算符优先文法采用“移进－规约”技术，其规约过程是规范的。（×）4.删除归纳变量是在强度削弱以后进行。（√）5.在目标代码生成阶段，符号表用于目标代码生成。（×）一．填空题（每空2分，共20分）1.不同的编译程序关于数据空间的存储分配策略可能不同，但大部分编译中采用的方案有两种：静态存储分配方案和动态存储分配方案，而后者又分为（1）和（2）。2.规范规约是最（3）规约。3.编译程序的工作过程一般划分为5个阶段：词法分析、（4）、语义分析与中间代码生成，代码优化及（5）。另外还有（6）和出错处理。4．表达式x+y*z/(a+b)的后缀式为（7）。5．文法符号的属性有综合属性和（8）。6．假设二位数组按行存放，而且每个元素占用一个存储单元，则数组a[1..15,1..20]某个元素a[i，j]的地址计算公式为（9）。7．局部优化是局限于一个（10）范围内的一种优化。答案：：(1)栈式动态存储分配(2)堆式动态存储分配(3)左(4)语法分析(5)目标代码生成(6)表格管理(7)xyz*ab+/+(8)继承属性8(9)a+(i-1)*20+j-1(10)基本块一、填空题（每空2分，共20分）1目标程序（targetcode）语法分析（syntaxanalyzer）代码优化器（codeoptimizer）代码产生器（codegenerator）符号表管理（symboltablemanager）2继承属性（inheritedattribute）3局部优化（localoptimization）4四元式（quatriple）5E+*()id二、填空题（本大题共5小题，每小题2分，共10分）1．编译程序首先要识别出源程序中每个(单词)，然后再分析每个(句子)并翻译其意义。2．编译器常用的语法分析方法有(自底向上)和(自顶向下)两种。3．通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的(分析)，中间代码生成、代码优化与目标代码的生成则是对源程序的(综合)。4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即(静态存储分配)方案和(动态存储分配)方案。5．对编译程序而言，输入数据是(源程序)，输出结果是(目标程序)。三、名词解释题(共5小题，每小题4分，共20分)1．词法分析词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位，并转换成统一的内部表示(token)，送给语法分析程序。2．LL(1)文法若文法的任何两个产生式A|都满足下面两个条件：（1）FIRST()FIRST()=；（2）若*，那么FIRST()FOLLOW(A)=。我们把满足这两个条件的文法叫做LL(1)文法，其中的第一个L代表从左向右扫描输入，第二个L表示产生最左推导，1代表在决定分析器的每步动作时向前