编译原理自测(一二三)及答案

编译原理自测一一、是非题(下列各题，你认为正确的，请在题干的括号内打“√”，错的打“×”。每题1分,共5分)1、算符优先关系表不一定存在对应的优先函数。A.正确B.不正确2、数组元素的地址计算与数组的存储方式有关。A.正确B.不正确3、仅考虑一个基本块，不能确定一个赋值是否真是无用的。A.正确B.不正确4、每个文法都能改写为LL(1)文法。A.正确B.不正确5、对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。A.正确B.不正确二、填空题1、从功能上说，程序语言的语句大体可分为执行性语句和说明性语句两大类。2、扫描器的任务是从源程序中识别出一个个单词符号。3、所谓最右推导是指：任何一步αβ都是。(任何一步αβ都是对α中最右非终结符进行替换的)4、语法分析最常用的两类方法是自上而下和自下而上分析法。5、一个上下文无关文法所含四个组成部分是一组终结符号，。(一组终结符号，一组非终结符号、一个开始符号、一组产生式)6、所谓语法制导翻译方法是为每个产生式配。(为每个产生式配上一个翻译子程序，并在语法分析的同时执行这些子程序)7、符号表中的信息栏中登记了每个名字的有关的性质，如类型、种属、所等等。8、一个过程相应的DISPLAY表的内容为现行活动记录地。9、常用的两种动态存贮分配办法是栈式动态分配和堆式动态分配。10、产生式是用于定义语法范畴的一种书写规则。三、名词解释1．遍－－指编译程序对源程序或中间代码程序从头到尾扫描一次。2．无环路有向图(DAG)－－如果有向图中任一通路都不是环路，则称庐有向图为无环路有向图，简称DAG。3．语法分析－－按文法的产生式识别输入的符号串是否为一个句子的分析过程。4．短语－－令G是一个文法。S划文法的开始符号，假定αβδ是文法G的一个句型，如果有SαAδ且AB，则称β是句型αβ相对非终结符A的短语。5．后缀式－－一种把运算量写在前面，把算符写在后面的表示表达式的方法。编译原理自测二一、是非题(下列各题，你认为正确的，请在题干的括号内打“√”，错的打“×”。每题1分,共5分)1、一个LL(1)文法一定是无二义的。A.正确B.不正确2、逆波兰法表示的表达式亦称前缀式。A.正确B.不正确3、目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。A.正确B.不正确4、正规文法产生的语言都可以用上下文无关文法来描述。A.正确B.不正确5、一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。A.正确B.不正确二、填空题1、语法分析是依据语言的语法规则进行的，中间代码产生是依据语言的语义规则进行的。2、程序语言的单词符号一般可以分为基本字、标识等等。（基本字、标识符、常量、算符、界符）3、语法分析器的输入是单词符号串，其输出是语法单位4、所谓自上而下分析法是指。（从开始符号出发，向下推导，推出句子）5、如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。6、对于文法G，仅含终结符号的句型称为句子。7、逆波兰式ab+c+d*e-所表达式为(a+b+c)*d-e。8、一个名字的属性包括类型和作用域。9、对于数据空间的存贮分配，FORTRAN采用静态存储分配策略，PASCAL采用动态存储分配策略。10、所谓优化是指对程序进行各。（对程序进行各种等价变换，使得从变换后的程序出发，能生成更有效的目标代码）三、名词解释1．词法分析器——指执行词法分析的程序。2．语法——一组规则，用它可以形成和产生一个合式的程序3．最右推导——指对于一个推导序列中的每一步直接推导，被替换的总是当前符号串中的最右非终结符号。4．语法制导翻译——在语法分析过程中，根据每个产生式所对应的语义子程序进行翻译的办法叫做语法制导翻译。5．基本块——指程序中一个顺序执行的语句序列，其中只有一个入口，一个出口，入口即第一个语句。出口即最后一个语句。编译原理自测三一选择题(每空2分,共20分)1、文法G产生的⑴的全体是该文法描述的语言。A.句型B.终结符集C.非终结符集D.句子2、若文法G定义的语言是无限集，则文法必然是⑵：A.递归的B.前后文无关的C.二义性的D.无二义性的3、Chomsky定义的四种形式语言文法中，0型文法又称为⑶文法；1型文法又称为⑷文法；2型语言可由⑸识别。A.短语结构文法B.前后文无关文法C.前后文有关文法D.正规文法E.图灵机F.有限自动机G.下推自动机A.短语结构文法B.前后文无关文法C.前后文有关文法D.正规文法E.图灵机F.有限自动机G.下推自动机A.短语结构文法B.前后文无关文法C.前后文有关文法D.正规文法E.图灵机F.有限自动机G.下推自动机4、一个文法所描述的语言是⑹；描述一个语言的文法是⑺。A.唯一的B.不唯一的C.可能唯一,可能不唯一A.唯一的B.不唯一的C.可能唯一,可能不唯一5、数组的内情向量中肯定不含有数组的⑻的信息A.维数B.类型C.维上下界D.各维的界差6、在下述的编译方法中，自底向上的方法有⑼，自顶向下的分析方法有⑽。①简单优先分析②算符优先分析③递归下降分析④预测分析技术⑤LR（K）分析⑥SLR（k）分析⑦LL（k）分析⑧LALR（K）分析A.③④⑦B.③④⑧C.①②⑧D.③④⑤⑥⑦E.①②⑤⑥⑦F.①②⑤⑥⑧A.③④⑦B.③④⑧C.①②⑧D.③④⑤⑥⑦E.①②⑤⑥⑦F.①②⑤⑥⑧二、简答题1．LL（1）分析法对文法有哪些要求？对于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）2．常见的存储分配策略有几种？它们都适合于什么性质的语言？有三种分配存储空间的方式：（1）静态分配若在编译阶段就能确定源程序中各个数据实体的存储空间大小，则可以采用较简单的静态存储管理。适合静态管理的语言应具备条件：数组上下界是常数、过程调用不允许递归、不允许动态建立数据实体。（2）栈式分配适用于允许递归调用的程序设计语言；（3）堆式分配对于允许程序在运行时为变量动态申请和释放存储空间的语言，采用堆式分配是最有效的解决方案。3．常见循环优化都有哪些项目？不变运算外提；运算强度削弱；消除归纳变量；下标变量地址计算优化。4．什么是活动记录？它主要由哪些内容构成？一个过程的一次执行所需信息的管理，是通过称为活动记录的连续存储块来实现的。活动记录的主要内容有：（1）临时变量域存放目标程序临时变量的值；（2）局部数据域存放过程本次执行时的局部数据、简单变量及数组内情向量等；（3）机器状态域保存在调用过程前有关机器状态的信息，包括各寄存器的当前值及返回地址等；（4）存取链为访问其它活动记录中所存放的非局部数据所提供的链地址；（5）控制链指向主调过程的活动记录；（6）实参存放主调过程为被调用过程所提供的实参信息；（7）返回值为主调过程存放被调过程的返回值