【计算机】南理工《编译原理》题库—填空题答案

1、注:题目前带*号为很有疑问的。其余的也不是很对，总之答案仅供参考1.扫描器的任务是从源程序中识别出一个个_单词符号 _。2语法分析最常用的两类方法是自顶向下和_ 自底向上 _分析法。3所谓语法制导翻译方法是_为每个产生式配上一个语义子程序，并在语法分析的同时执行这些程序_。4.源程序执行的途径有 翻译 和解释途径两类。5符号表的作用是 语义检查的依据 和辅助目标代码的生成。6词法分析的任务是 从左至右逐个字符地对源程序进行扫描，产生一个个单词序列，用以语法分析 。7素短语是指至少含有一终结符 除自身外不含其它素短语 的短语。8ll(1)分析法的文法须满足的条件是无回溯和 无左递归 。9dfa和

2、nfa间的区别是后继状态是否唯一和 初态是否唯一 。10二义性的解决办法是修改编译算法和 修改文法 。11常用的两种动态存贮分配办法是栈式动态分配和_堆式 _动态分配。12从功能上说，程序语言的语句大体可分为执行性语句和_说明性 _语句两大类。13一个上下文无关文法包含四个组成部分是一组终结符号、一组非终结符号、一个开始符号和 一组产生式 。14产生式是用于定义_ 语法成分 _的一种书写规则。15动态存储分配实现的方式有 栈式分配 和堆式分配两种。16表达式a*(b+c)/d- (f+e)的逆波兰式表示是 abc+*d/fe+- 。28常见的中间语言的形式有三元式、 四元式 、逆波兰式和树表示

3、。17可用属性文法来说明源语言语义。属性文法由一个 上下文无关文法 和一系列附加在文法上的语义规则构成。18词法分析器的另一个名称为 扫描器 。19代码优化可以分 局部优化 、全局优化和循环优化三类。20文法gs：sasbe 描述的语言l(gs)是 l(gs)=(anbn|n=0 。21素短语是指至少含有一终结符和 除自身外不包含其它素短语 的短语。22无环路有向图(dag)是指 如果有向图中任一通路都不是环路，则称庐有向图为无环路有向图，简称dag 。23所谓优化是指 加快运行速度 和减少存储空间。24翻译程序分为解释程序、 编译程序 和汇编程序三种。25单词的描述工具有 有穷自动机 、正规

4、式和正规方法。26文法gs：sasacc描述的语言l(gs)是 l(gs)=(anccan|n=0 。27算符优先方法每次是对 最左素短语 进行归约，规范归约每次是对句柄进行归约。*28中间代码的产生是随编译中语法分析处理而进行的，所以叫做 的中间代码生成。*29文法gs：saab|abb bcbde 描述的语言l(gs)是 。30说明语句的翻译的任务是 把有关属性填入符号表 和为变量分配空间。31算符文法是指 它的任何产生式的右部都不含两个相继（并列）的非终结符 ，算符优先文法是指构造算符优先表时，不产生冲突的文法。32符号表的主要操作包括符号表的初始化、符号表的查找和 符号表中分程序结构层

5、次的管理 。33字母表a,b上，每个a均有一个b紧跟其后的所有符号串的集合的正规式表示为 (b)*(ab)*(b)* 。34下推自动机是一个七元组，通常表示为 ( q, , , , q0, z0, f ) 。35pda的含义是指 下推自动机 。*36文法gs：saab|aabbb bcbdcd 描述的语言l(gs)是 。37一个确定有穷自动机可以通过消除_ 无用状态 和等价状态而转换成一个最小的与之等价的有穷自动机。38lr(k)方法可以分为lr(0)、slr(1)、 lr（1） 和lalr(1)四种。39高级语言的翻译方式有解释和编译，它们的主要区别在于 是否产生目的代码 。40字母表a,b

6、,c上，以aa结尾的所有符号串的集合的正规式表示为 (a|b|c)*aa 。41下推自动机是用来识别 2型语言 ，有穷自动机用来识别3型语言。42从功能上说，程序语言的语句大体可分为说明性语句和_ 执行性 _语句两大类。43汇编程序是将汇编语言程序翻译成 机器语言 。44编译程序是将高级语言翻译成 汇编语言程序 。45句柄是指_ 一个句型的最左直接短语 。46过程信息表中必须包括过程名、参数信息和 过程入口地址 _。47表达式a/(b-c)*(d/f+e*g)的逆波兰式表示是 abc-/df/eg*+* 。48与机器有关的优化包括_ 多处理器优化 、无用代码优化、寄存器优化和特殊指令优化。49

7、左线性文法的每条规则形如aa和_ aba _。50opg的含义是指： 算符优先文法 。51词法分析器用于区分单词，语法分析器则用于发现源程序中的 语法错误 。52全局优化是指_ 跨越多个基本块的全局范围内的优化 。53一个程序设计语言应具备 语法 、语义和语用三个方面。54表达式-a/(b+c)/(d+f)*(e-g)的逆波兰式表示是 a-bc+/df+eg-*/ 。55chomsky把文法分为四种形式，它们分别是0型文法、1型文法、2型文法和 3型文法 。56自底向上语法分析方法的基本思想是：由输入的符号串出发，利用文法的规则一步步进行 向上规约 _，试图归约到文法的开始符号。57lr(0)

8、项目集的相容性是指 无移进规约项目并存 _和无两归约项目并存。58在某些特殊情况下利用提取公因子和 消除左递归 使一个非ll(1)文法转换为ll(1)文法。59局部优化是指 基本块 内的优化。60ll分析器由三个部份组成，它们总控程序、 预测分析表 _和分析栈。61语句x=a/(b-c)-(d+f*(e+g)的逆波兰式表示是 xabc-/dfeg+*+-= 。62lr(0)的项目集的项目类型可分为归约项目、待约项目、接受项目和 移进项目 。63句子分析分为自底向上和 自顶向下 两种类型。64dag的含义是指： 无回路有向图 。65优先函数有两种构造方法，它们是关系图法和 构造优先函数法 。66

9、文法gs：sabc aaaa bbbe ccccc 描述的语言l(gs)是 l(gs)=aibjck|i=1,j=0,k=2 。67 在有穷自动机中，两个状态等价的条件是蔓延性条件和 一致性条件 。68自顶向下分析方法一般有ll(1)方法和 递归下降法 两种分析方法。69属性文法是一个三元组(g，v，f)，分别表示一个上下文无关文法、属性的集合和 关于属性的属性断言或一组属性的计算规则 。703型文法要求每条规则形如aa和 a ab 。713型文法有两种特殊形式，它们是左线性文法和 右线性文法 。72文法gs：saab|b bcbdccdd 描述的语言l(gs)是 。73多余规则是指 文法中某

10、些非终结符不在其他任何规则中出现 和一旦用到此规则推不出终结符号串出来。743型语言可以被 有穷自动机 来识别，2型语言可以被下推自动机来识别。75字母表a,b上，以aa打头的所有符号串的集合的正规式表示aa（a|b）* 。76素短语是指 至少含有一终结符 和 不含其它素短语的短语。77优先分析方法可分为简单优先分析方法和 算符优先分析方法 。78文法的实用性限制是不能有有害规则和_ 多余规则 _。79词法分析的任务是_逐个读入源程序字符并按照构词规则切分成一系列单词 _。80lr分析器有三个部份组成，它们总控程序、 分析表或分析函数 _和分析栈。81语句x=-a+(b-c)*d+f+e/g的

11、逆波兰式表示是 xa-bc-d*+f+eg/+= 。82语义子程序的功能是改变变量的值、查填符号表、 产生中间代码 和发现并报错。83一个确定有穷自动机可以通过消除无用状态和_ 合并等价状态 _而转换成一个最小的与之等价的有穷自动机。84dfa所能识别的语言定义为： （正则文法的定义） 。？85根据与机器的相关性，优化可以分为与机器有关的优化和_ 与机器无关的优化 _两类。86引入中间语言的目的是便于目标代码的生成和_ 便于优化 _。87语法分析的任务是_ 识别由词法分析给出的单词符号序列是否是给定文法的正确句子 _。88lr的含义是_ 第一个l代表自左向右扫描字符串，第二个r表示最右推导 _

12、。89语句x=a*(b+c)/d+(f+e)*g的逆波兰式表示是 xabc+*d/fe+g*+= 。90与机器无关的优化常见的有合并常量、消除公共子表达式、削减运算强度和 外提循环式中的变量 。91语义分析含有如下两方面的任务一是静态语义审查，二是 生成中间代码或目标代码 。92文法gs：sab aaaa bbbe 描述的语言l(gs)是 l(gs)=ai bj|i=1,j=0 。93词法分析的单词可以分为常量、运算符、特殊符号、关键字和 界符 。（和书上不一样）94局部优化是指在只有一个 入口 和一个出口的基本程序块上进行的优化。95符号表的表项排列结构可以分为线性表组织、有序表组织和 散列

13、表组织 三种结构。96递归子程序分析法属于自顶向下语法分析方法，lr语法分析方法属于 自底向上 语法分析文法。97一个dfa要求 初态 唯一和后继状态唯一。98上下文无关文法的每一条规则形如 a 。99下推自动机的英文简称为 pda 。100单词的描述工具有有穷自动机、正规则文法和 正规式 三类。101gs：sssb 描述的语言l(gs)是 l(gs)= （）n|n=2 。102系统的关键字和系统定义的运算符、分隔符都各自单独定义为一个词类，那么词类定义中除了常量和 标识符 以外，别的词类就一般不需附加信息。103分析的文法须满足的条件是 和无回溯。104符号表表的内容包括两部份：标识符的名字和 名字有关的信息 。105 编译中，各个阶段广泛采用的数据结构是表，它记录不同阶段