编译原理填空集

注:题目前带*号为很有疑问的。其余的也不是很对，总之答案仅供参考 1.扫描器的任务是从源程序中识别出一个个__单词符号 ____。

2．语法分析最常用的两类方法是自顶向下和___ 自底向上 ______分析法。 3．所谓语法制导翻译方法是____为每个产生式配上一个语义子程序，并在语法分析的同时执行这些程序 ___________。

4.源程序执行的途径有 翻译 和解释途径两类。

5．符号表的作用是 语义检查的依据 和辅助目标代码的生成。 6．词法分析的任务是 从左至右逐个字符地对源程序进行扫描，产生一个个单词序列，用以语法分析 。

7．素短语是指至少含有一终结符 除自身外不含其它素短语 的短语。 8．LL(1)分析法的文法须满足的条件是无回溯和 无左递归 。

9．DFA和NFA间的区别是后继状态是否唯一和 匹配速度快慢 。 10．二义性的解决办法是修改编译算法和 修改文法 。 11．常用的两种动态存贮分配办法是栈式动态分配和__堆式 ___动态分配。

12．从功能上说，程序语言的语句大体可分为执行性语句和__说明性 ____语句两大类。 13．一个上下文无关文法包含四个组成部分是一组终结符号、一组非终结符号、一个开始符号和 一组产生式 。

14．产生式是用于定义__ 语法成分 ___的一种书写规则。

15．动态存储分配实现的方式有 栈式分配 和堆式分配两种。

16．表达式a*(b+c)/d- (f+e)的逆波兰式表示是 abc+*d/fe+- 。 28．常见的中间语言的形式有三元式、 四元式 、逆波兰式和树表示。 17．可用属性文法来说明源语言语义。属性文法由一个 上下文无关文法 和一系列附加在文法上的语义规则构成。

18．词法分析器的另一个名称为 扫描程序 。

19．代码优化可以分 局部优化 、全局优化和循环优化三类。 20

．

文

法

G[S]

：

S?aSb??

描

述

的

语

言

L(G[S])

是

L(G[S])={(a^nb^n|n>=0} 。

21．素短语是指至少含有一终结符和 除自身外不包含其它素短语 的短语。

22．无环路有向图(DAG)是指 如果有向图中任一通路都不是环路，则称庐有向图为无环路有向图，简称DAG 。 23．所谓优化是指 加快运行速度 和减少存储空间。

24．翻译程序分为解释程序、 编译程序 和汇编程序三种。 25．单词的描述工具有 有穷自动机 、正规式和正规方法。

26．文法G[S]：S?aSa?cc描述的语言L(G[S])是 L(G[S])={(a^ncc^n|n>=0} 。 27．算符优先方法每次是对 最左短语 进行归约，规范归约每次是对句柄进行归约。

*28．中间代码的产生是随编译中语法分析处理而进行的，所以叫做 的中间代码生成。

*29．文法G[S]：S?aAb|aBb B?cBd?? 描述的语言L(G[S])是 。 30．说明语句的翻译的任务是 把有关属性填入符号表 和为变量分配空间。 31．算符文法是指 它的任何产生式的右部都不含两个相继（并列）的非终结符 ，算符优先文法是指构造算符优先表时，不产生冲突的文法。

32．符号表的主要操作包括符号表的初始化、符号表的查找和 符号表中分程序结构层次的管理 。

33．字母表{a,b}上，每个a均有一个b紧跟其后的所有符号串的集合的正规式表示为 (b)*(ab)*(b)* 。

34．下推自动机是一个七元组，通常表示为 ( Q, Σ, Γ, δ, q0, Z0, F ) 。

35．PDA的含义是指 下推自动机 。 *36．文法

G[S]：S?aAb|aaBbb B?cBd?cd 描述的语言

L(G[S])

是 。

37．一个确定有穷自动机可以通过消除__ 无用状态 和等价状态而转换成一个最小的与之等价的有穷自动机。

38．LR(K)方法可以分为LR(0)、SLR(1)、 LR（1） 和LALR(1)四种。 39．高级语言的翻译方式有解释和编译，它们的主要区别在于 是否产生目的代码 。

40．字母表{a,b,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．左线性文法的每条规则形如A?a和_ A→Ba __。

50．OPG的含义是指： 算符优先文法 。 51．词法分析器用于区分单词，语法分析器则用于发现源程序中的 语法错误 。

52．全局优化是指____ 跨越多个基本块的全局范围内的优化 。 53．一个程序设计语言应具备 语法 、语义和语用三个方面。 54

．

表

达

式

-A/(B+C)/((D+F)*(E-G))

的

逆

波

兰

式

表

示

是

A-BC+/DF+EG-*/ 。

55．Chomsky把文法分为四种形式，它们分别是0型文法、1型文法、2型文法和 3型文法 。

56．自底向上语法分析方法的基本思想是：由输入的符号串出发，利用文法的规则一步步 进行 向上规约 __，试图归约到文法的开始符号。

57．LR(0)项目集的相容性是指 无移进—规约项目并存 _____和无两归约项目并存。

58．在某些特殊情况下利用提取公因子和 消除左递归 使一个非LL(1)文法转换为LL(1)文法。

59．局部优化是指 基本块 内的优化。

60．LL分析器由三个部份组成，它们总控程序、 预测分析表 __和分析栈。 61

．

语

句

x=A/(B-C)-(D+F*(E+G))

的

逆

波

兰

式

表

示

是

xABC-/DFEG+*+-= 。

62．LR(0)的项目集的项目类型可分为归约项目、待约项目、接受项目和 移进项目 。 63．句子分析分为自底向上和 自顶向下 两种类型。

64．DAG的含义是指： 无回路有向图 。 65．优先函数有两种构造方法，它们是关系图法和 构造优先函数法 。 66．文法G[S]：S?ABC A?aA?a B?bB?? C?cC?cc 描述的语言L(G[S])是

L(G[S])={a^ib^jc^k|i>=1,j>=0,k>=2} 。

67． 在有穷自动机中，两个状态等价的条件是蔓延性条件和 一致性条件 。 68．自顶向下分析方法一般有LL(1)方法和 递归下降法 两种分析方法。 69．属性文法是一个三元组(G，V，F)，分别表示一个上下文无关文法、属性的集合和 关于属性的属性断言或一组属性的计算规则 。 70．3型文法要求每条规则形如A?a和 A→ aB 。

71．3型文法有两种特殊形式，它们是左线性文法和 右线性文法 。 72．文法G[S]：S?aAb|B B?cBd?ccdd 描述的语言L(G[S])是 。

73．多余规则是指 某条规则的左部终结符不在其他任何规则中出现 和一旦用到此规则推不出终结符号串出来。

74．3型语言可以被 有穷自动机 来识别，2型语言可以被下推自动机来识别。 75．字母表{a,b}上，以aa打头的所有符号串的集合的正规式表示为aa（a|b）* 。

76．素短语是指 至少含有一终结符 和 不含其它素短语的短语。

77．优先分析方法可分为简单优先分析方法和 算符优先分析方法 。 78．文法的实用性限制是不能有有害规则和__ 多余规则 ______。

79．词法分析的任务是__逐个读入源程序字符并按照构词规则切分成一系列单词 _________________。

80．LR分析器有三个部份组成，它们总控程序、 预测分析表 __和分析栈。 81

．

语

句

x=-a+(b-c)*d+f+e/g

的

逆

波

兰

式

表

示

是

xa-bc-d*+f+eg/+= 。

82．语义子程序的功能是改变变量的值、查填符号表、 产生中间代码 和发现并报错。

83．一个确定有穷自动机可以通过消除无用状态和_ 多余状态 __而转换成一个最小的与之等价的有穷自动机。

84．DFA所能识别的语言定义为： （正则文法的定义） 。

85．根据与机器的相关性，优化可以分为与机器有关的优化和___ 与机器无关的优化 ____两类。

86．引入中间语言的目的是便于目标代码的生成和___ 便于移植 ______。

87．语法分析的任务是____ 识别由词法分析给出的单词符号序列是否是给定文法的正确句子 _________________。

88．LR的含义是_ 自左向右规约 ___。 89

．

语

句

x=a*(b+c)/d+(f+e)*g

的

逆

波

兰

式

表

示

是

xabc+*d/fe+g*+= 。

90．与机器无关的优化常见的有合并常量、消除公共子表达式、削减运算强度和 外提循环式中的变量 。

91．语义分析含有如下两方面的任务一是静态语义审查，二是 动态语义解释执行 。

92．文法G[S]：S?AB A?aA?a B?bB?? 描述的语言L(G[S])是 L(G[S])={a^i b^j|i>=1,j>=0} 。

93．词法分析的单词可以分为常量、运算符、特殊符号、关键字和 界符 。 94．局部优化是指在只有一个 入口 和一个出口的基本程序块上进行的优化。 95．符号表的表项排列结构可以分为线性表组织、有序表组织和 散列表组织 三种结构。

96．递归子程序分析法属于自顶向下语法分析方法，LR语法分析方法属于 自底向上 语法分析文法。

97．一个DFA要求 初态 唯一和后继状态唯一。

98．上下文无关文法的每一条规则形如 A→β 。 99．下推自动机的英文简称为 PDA 。

100．单词的描述工具有有穷自动机、正规则文法和 正规式 三类。 101G[S]：S?SS?? 描述的语言^n|n>=2} 。

102系统的关键字和系统定义的运算符、分隔符都各自单独定义为一个词类，那么词类定义中除了常量和 标识符 以外，别的词类就一般不需附加信息。 103分析的文法须满足的条件是 和无回溯。

104符号表表的内容包括两部份：标识符的名字和 名字有关的信息 。

105 编译中，各个阶段广泛采用的数据结构是表，它记录不同阶段时的不同信息，以便查询和修改。其中使用期最长的是 符号表 。

106G优化的基本方法是：第一步___从四元式序列构造DAG _____， 第二步再从DAG图重新写成四元式序列。

107制导翻译时修改文法的目的是便于生成四元和__ ______。

L(G[S])是 L(G[S])={

（β

）

108式a+(b-c)*d+(f+e)/g的逆波兰式表示是 abc-d*+fe+g/+ 。 109自动机一般分为NFA和_ DFA __。

112[S]是一个文法，它产生 所有句子 的全体是该文法所定义的语言。

本文来源：https://www.bwwdw.com/article/xhna.html