编译原理 OCR 整理

说明：已去除手写选项字母、荧光标注和后续解答说明，仅保留题目与选项文本。填空处统一记为 ____。

1.1 完成下列选择题

下列叙述中正确的是____。
- A. 编译程序是将高级语言程序翻译成等价的机器语言程序的程序
- B. 机器语言因其使用过于困难，所以现在计算机根本不使用机器语言
- C. 汇编语言是计算机唯一能够直接识别并接受的语言
- D. 高级语言接近人们的自然语言，但其依赖具体机器的特性是无法改变的
将编译程序分成若干个“遍”是为了____。
- A. 提高编译程序的执行效率
- B. 使编译程序的结构更加清晰
- C. 利用有限的机器内存并提高机器的执行效率
- D. 利用有限的机器内存但降低了机器的执行效率
构造编译程序应掌握____。
- A. 源程序
- B. 目标语言
- C. 编译方法
- D. 以上三项
编译程序绝大多数时间花在____上。
- A. 出错处理
- B. 词法分析
- C. 目标代码生成
- D. 表格管理
编译程序是对____。
- A. 汇编程序的翻译
- B. 高级语言程序的解释执行
- C. 机器语言的执行
- D. 高级语言的翻译

2.1 完成下列选择题

词法分析所依据的是____。
- A. 语义规则
- B. 构词规则
- C. 语法规则
- D. 等价变换规则
词法分析器的输入是____。
- A. 单词符号串
- B. 源程序
- C. 语法单位
- D. 目标程序
词法分析器的输出是____。
- A. 单词的种别编码
- B. 单词的种别编码和自身的值
- C. 单词在符号表中的位置
- D. 单词自身值
状态转换图（见图 2-36）接受的字集为____。
- A. 以 0 开头的二进制数组成的集合
- B. 以 0 结尾的二进制数组成的集合
- C. 含奇数个 0 的二进制数组成的集合
- D. 含偶数个 0 的二进制数组成的集合
对于任一给定的 NFA M，____一个 DFA M'，使 L(M)=L(M')。
- A. 一定不存在
- B. 一定存在
- C. 可能存在
- D. 可能不存在
DFA 适用于____。
- A. 定理证明
- B. 语法分析
- C. 词法分析
- D. 语义加工
下面用正规表达式描述词法的论述中，不正确的是____。
- A. 词法规则简单，采用正规表达式已足以描述
- B. 正规表达式的表示比上下文无关文法更加简洁、直观和易于理解
- C. 正规表达式描述能力强于上下文无关文法
- D. 有限自动机的构造比下推自动机简单且分析效率高
与 (a|b)*(a|b)* 等价的正规式是____。
- A. (a|b)(a|b)*
- B. a*|b*
- C. (ab)*(a|b)*
- D. (a|b)*
在状态转换图的实现中，____一般对应一个循环语句。
- A. 不含回路的分叉结点
- B. 含回路的状态结点
- C. 终态结点
- D. A-C 都不是
已知 DFA Md=({s0,s1,s2},{a,b},f,s0,{s2})，且有：f(s0,a)=s1，f(s1,a)=s2，f(s2,a)=s2，f(s2,b)=s2。则该 DFA M 所能接受的语言可以用正规表达式表示为____。
- A. (a|b)*
- B. aa(a|b)*
- C. (a|b)*aa
- D. a(a|b)*a

3.1 完成下列选择题

程序语言的语义需要用____来描述。
- A. 上下文无关文法
- B. 上下文有关文法
- C. 正规文法
- D. 短语文法
2 型文法对应____。
- A. 图灵机
- B. 有限自动机
- C. 下推自动机
- D. 线性界限自动机
下述结论中，____是正确的。
- A. 1 型语言 ⊂ 0 型语言
- B. 2 型语言 ⊂ 1 型语言
- C. 3 型语言 ⊂ 2 型语言
- D. A-C 均不成立
有限状态自动机能识别____。
- A. 上下文无关文法
- B. 上下文有关文法
- C. 正规文法
- D. 短语文法
文法 G[S]：S→xSx|y 所识别的语言是____。
- A. xyx
- B. (xyx)*
- C. x^n y x^n (n≥0)
- D. x* y x*
只含有单层分枝的子树称为“简单子树”，则句柄的直观解释是____。
- A. 子树的末端结点（即树叶）组成的符号串
- B. 简单子树的末端结点组成的符号串
- C. 最左简单子树的末端结点组成的符号串
- D. 最左简单子树的末端结点组成的符号串且该字符串必须含有终结符
下面对语法树错误的描述是____。
- A. 根结点用文法 G[S] 的开始符 S 标记
- B. 每个结点用 G[S] 的一个终结符或非终结符标记
- C. 如果某结点标记为 ε，则它必为叶结点
- D. 内部结点可以是非终结符
由文法开始符 S 经过零步或多步推导产生的符号序列是____。
- A. 短语
- B. 句柄
- C. 句型
- D. 句子
设文法 G[S]：S→SA|A，A→a|b，则对句子 aba 的规范推导是____。
- A. S⇒SA⇒SAA⇒AAA⇒aAA⇒abA⇒aba
- B. S⇒SA⇒SAA⇒AAA⇒AAa⇒Aba⇒aba
- C. S⇒SA⇒SAA⇒SAa⇒Sba⇒Aba⇒aba
- D. S⇒SA⇒Sa⇒SAa⇒Sba⇒Aba⇒aba
如果文法 G[S] 是无二义的，则它的任何句子 α，其____。
- A. 最左推导和最右推导对应的语法树必定相同
- B. 最左推导和最右推导对应的语法树可能不同
- C. 最左推导和最右推导必定相同
- D. 可能存在两个不同的最右推导，但它们对应的语法树相同
一个句型的分析树代表了该句型的____。
- A. 推导过程
- B. 归约过程
- C. 生成过程
- D. 翻译过程
规范归约中的“可归约串”由____定义。
- A. 直接短语
- B. 最右直接短语
- C. 最左直接短语
- D. 最左素短语
规范归约是指____。
- A. 最左推导的逆过程
- B. 最右推导的逆过程
- C. 规范推导
- D. 最左归约的逆过程
文法 G[S]：S→aAcB|Bd，A→AaB|c，B→bScA|b，则句型 aAcbBdcc 的短语是____。
- A. Bd
- B. cc
- C. a
- D. b
文法 G[E]：E→E+T|T，T→T*P|P，P→(E)|i，则句型 P+T+i 的句柄和最左素短语是____。
- A. P+T 和 T
- B. P 和 P+T
- C. i 和 P+T+i
- D. P 和 P
采用自顶向下分析，必须____。
- A. 消除左递归
- B. 消除右递归
- C. 消除回溯
- D. 提取公共左因子
对文法 G[E]：E→E+S|S，S→S*F|F，F→(E)|i，则 FIRST(S)=____。
- A. {(}
- B. {(, i}
- C. {i}
- D. {(,)}
确定的自顶向下分析要求文法满足____。
- A. 不含左递归
- B. 不含二义性
- C. 无回溯
- D. A-C 项
递归下降分析器由一组递归函数组成，且每一个函数对应文法的____。
- A. 一个终结符
- B. 一个非终结符
- C. 多个终结符
- D. 多个非终结符
LL(1) 分析表需要预先定义和构造两族与文法有关的集合____。
- A. FIRST 和 FOLLOW
- B. FIRSTVT 和 FOLLOW
- C. FIRST 和 LASTVT
- D. FIRSTVT 和 LASTVT
设 a、b、c 是文法的终结符且满足优先关系 a=b 和 b=c，则____。
- A. 必有 a=c
- B. 必有 c=a
- C. 必有 b=a
- D. A-C 都不一定成立
算符优先分析法要求文法____。
- A. 不存在 ...QR... 的句型且任何终结符对 (a,b) 满足 a=b、a<b 和 a>b 三种关系之一
- B. 不存在 ...QR... 的句型且任何终结符对 (a,b) 至多满足 a=b、a<b 和 a>b 三种关系之一
- C. 可存在 ...QR... 的句型且任何终结符对 (a,b) 至多满足 a=b、a<b 和 a>b 三种关系之一
- D. 可存在 ...QR... 的句型且任何终结符对 (a,b) 满足 a=b、a<b 和 a>b 三种关系之一
任何算符优先文法____优先函数。
- A. 有一个
- B. 没有
- C. 有若干个
- D. 可能有若干个
在算符优先分析中，用____来刻画可归约串。
- A. 句柄
- B. 直接短语
- C. 素短语
- D. 最左素短语
下面最左素短语必须具备的条件中有错误的是____。
- A. 至少包含一个终结符
- B. 至少包含一个非终结符
- C. 除自身外不再包含其他素短语
- D. 在句型中具有最左性
对文法 G[S]：S→b|Λ|(T)，T→T,S|S，其 FIRSTVT(T) 为____。
- A. {b, Λ, (}
- B. {b, Λ, )}
- C. {,, b, Λ, (}
- D. {,, b, Λ, )}
对文法 G[E]：E→E*T|T，T→T+i|i，句子 1+2*8+6 归约的值为____。
- A. 23
- B. 42
- C. 30
- D. 17
下述 FOLLOW 集构造方法中错误的是____。
- A. 对文法开始符 S 有 #∈FOLLOW(S)
- B. 若有 A→αBβ，则将 FIRST(β)\{ε}⊆FOLLOW(B)
- C. 若有 A→αB，则有 FOLLOW(B)⊆FOLLOW(A)
- D. 若有 A→αB，则有 FOLLOW(A)⊆FOLLOW(B)
若文法 G[S] 的产生式有 ...AB... 出现，则对 A 求 FOLLOW 集正确的是____。
- A. FOLLOW(B)⊂FOLLOW(A)
- B. FIRSTVT(B)⊂FOLLOW(A)
- C. FIRST(B)\{ε}⊂FOLLOW(A)
- D. LASTVT(B)⊂FOLLOW(A)
下面____是自底向上分析方法。
- A. 预测分析法
- B. 递归下降分析器
- C. LL(1) 分析法
- D. 算符优先分析法
下面____是采用句柄进行归约的。
- A. 算符优先分析法
- B. 预测分析法
- C. SLR(1) 分析法
- D. LL(1) 分析法
一个____指明了在分析过程中某时刻能看到产生式多大一部分。
- A. 活前缀
- B. 前缀
- C. 项目
- D. 项目集
若 B 为非终结符，则 A→α·Bβ 为____项目。
- A. 接受
- B. 归约
- C. 移进
- D. 待约
在 LR(0) 的 ACTION 子表中，如果某一行中存在标记为 rj 的栏，则____。
- A. 该行必定填满 rj
- B. 该行未填满 rj
- C. 其他行也有 rj
- D. GOTO 子表中也有 rj
LR 分析法解决“移进/归约”冲突时，左结合意味着____。
- A. 打断联系实行移进
- B. 打断联系实行归约
- C. 建立联系实行移进
- D. 建立联系实行归约
LR 分析法解决“移进/归约”冲突时，右结合意味着____。
- A. 打断联系实行归约
- B. 建立联系实行归约
- C. 建立联系实行移进
- D. 打断联系实行移进
若项目集 Ik 含有 A→α·，则在状态 k 时，仅当面临的输入符号 a∈FOLLOW(A) 时才采取“将 α 归约为 A”动作的一定是____。
- A. LALR(1) 文法
- B. LR(0) 文法
- C. LR(1) 文法
- D. SLR(1) 文法
同心集合并又可能产生新的____冲突。
- A. “归约/接受”
- B. “移进/移进”
- C. “移进/归约”
- D. “归约/归约”

4.1 完成下列选择题

中间代码的优点是____。
- A. 节省存储空间
- B. 编译时间短
- C. 编译结构在逻辑上更为简单明确
- D. 节省内存且编译时间短
四元式之间的联系是通过____实现的。
- A. 指示器
- B. 临时变量
- C. 符号表
- D. 程序变量
间接三元式表示法的优点为____。
- A. 采用间接码表，便于优化处理
- B. 节省存储空间，不便于表的修改
- C. 便于优化处理，节省存储空间
- D. 节省存储空间，不便于优化处理
表达式 (¬A∨B)∧(C∨D) 的逆波兰表示为____。
- A. ¬AB∨∧CD∨
- B. A¬B∨CD∨∧
- C. AB∨¬CD∨∧
- D. A¬B∨∧CD∨
后缀式____对应的中缀表达式是 a-(-b)*c（注：@ 表示求负运算）。
- A. a-b@c*
- B. ab@-c*
- C. ab-c@*
- D. ab@c*-
后缀式 ab+cd+/ 可用中缀表达式____来表示。
- A. a+b/c+d
- B. (a+b)/(c+d)
- C. a+b/(c+d)
- D. a+b+c/d
表达式 (a+b)*c 的后缀表达式为____。
- A. ab*c+
- B. abc*+
- C. ab+c*
- D. abc+*
中间代码生成时所依据的是____。
- A. 语法规则
- B. 词法规则
- C. 语义规则
- D. 等价变换规则
四元式表示法的优点为____。
- A. 不便于优化处理但便于表的更动
- B. 不便于优化处理但节省存储空间
- C. 便于优化处理也便于表的更动
- D. 便于表的更动也节省存储空间
有一语法制导翻译如下所示：
```
S→bAb  { print"1" }
A→(B   { print"2" }
A→a    { print"3" }
B→Aa)  { print"4" }
```
若输入序列为 b(((aa)a)a)b，且采用自底向上的分析方法，则输出序列为____。
- A. 32224441
- B. 34242421
- C. 12424243
- D. 34442212

5.1 完成以下选择题

优化可生成____的目标代码。
- A. 运行时间较短
- B. 占用存储空间较小
- C. 运行时间短但占用内存空间大
- D. 运行时间短且占用存储空间小
下列优化方法中不是针对循环的是____。
- A. 强度削弱
- B. 删除归纳变量
- C. 删除多余运算
- D. 代码外提
对一个基本块来说，____是正确的。
- A. 有一个入口语句和一个出口语句
- B. 有一个入口语句和多个出口语句
- C. 有多个入口语句和一个出口语句
- D. 有多个入口语句和多个出口语句
____不能作为一个基本块的入口。
- A. 程序的第一个语句
- B. 条件转移语句转移到的语句
- C. 无条件转移语句后的下一条语句
- D. 无条件转移语句转移到的语句
基本块内的优化为____。
- A. 代码外提，删除归纳变量
- B. 删除多余运算，删除无用赋值
- C. 强度削弱，代码外提
- D. 循环展开，循环合并
在程序流图中，称具有____的结点序列为一个循环。
- A. 非连通的且只有一个入口结点
- B. 强连通的但有多个入口结点
- C. 非连通的但有多个入口结点
- D. 强连通的且只有一个入口结点
关于必经结点的二元关系，下列叙述中不正确的是____。
- A. 满足自反性
- B. 满足传递性
- C. 满足反对称性
- D. 满足对称性
已知有向边 a→b 是一条回边，则由它组成的循环是____的所有结点组成的。
- A. 由结点 a、结点 b 以及有通路到达 b 但该通路不经过 a
- B. 由结点 a、结点 b 以及有通路到达 a 但该通路不经过 b
- C. 仅由结点 a 以及有通路到达 a 但该通路不经过 b
- D. 仅由结点 b 以及有通路到达 b 但该通路不经过 a
对循环中各基本块的每个四元式，如果它的____，则将此四元式标记为“不变运算”。
- A. 每个运算对象为常数
- B. 每个运算对象定值点在循环内
- C. 每个运算对象定值点在循环外
- D. 每个运算对象为常数或者定值点在循环外
循环中进行代码外提时，对循环 L 中的不变运算 S: A=B op C 或 A=op B 或 A=B，____。
- A. S 所在的结点是 L 的所有出口结点的必经结点
- B. A 在 L 中其它地方未再定值
- C. 不变运算 S 中的 B 和 C 必须是常量
- D. L 中的所有 A 的引用点只有 S 中 A 的定值才能到达

6.1 完成下列选择题

分配目标程序数据空间的基本策略分为____。
- A. 栈式分配和堆式分配
- B. 局部分配和整体分配
- C. 静态分配和动态分配
- D. 程序运行之前分配
过程的 DISPLAY 表中记录了____。
- A. 过程的连接数据
- B. 过程的嵌套层次
- C. 过程的返回地址
- D. 过程的入口地址
过程 P1 调用 P2 时，连接数据不包含____。
- A. 嵌套层次显示表
- B. 老 SP 值
- C. 返回地址
- D. 全局 DISPLAY 表地址
堆式动态分配申请和释放存储空间遵守____原则。
- A. 先请先放
- B. 先请后放
- C. 后请先放
- D. 任意
栈式动态分配与管理在过程返回时应做的工作有____。
- A. 保护老 SP
- B. 恢复老 SP
- C. 保护老 TOP
- D. 释放老 TOP
如果活动记录中没有 DISPLAY 表，则说明____。
- A. 程序中不允许有递归定义的过程
- B. 程序中不允许有嵌套定义的过程
- C. 程序中既不允许有嵌套定义的过程，也不允许有递归定义的过程
- D. 程序中允许有递归定义的过程，也允许有嵌套定义的过程
两个不同过程的活动，其生存期是____的。
- A. 重叠且不嵌套
- B. 不重叠却嵌套
- C. 重叠且嵌套
- D. 不重叠也不嵌套
编译的动态存储分配含义是____。
- A. 在运行阶段对源程序中的各种变量、常量进行分配
- B. 在编译阶段对源程序中的各种变量、常量进行分配
- C. 在编译阶段对源程序中的各种变量、常量进行分配，在运行时这些各种变量、常量的地址可以根据需要修改
- D. A-C 都不是

7.1 完成下列选择题

评价一个代码生成器最重要的指标是____。
- A. 代码的正确性
- B. 代码的高效性
- C. 代码的简洁性
- D. 代码的维护性
编译程序生成的目标代码通常有____。
- A. 可立即执行的机器语言代码
- B. 汇编语言代码
- C. 待装配的机器语言代码模块
- D. A-C 项
设计一个代码生成器要考虑____。
- A. 具体的机器结构
- B. 指令格式
- C. 字长及寄存器个数和种类
- D. A-C 项

8.1 完成下列选择题

符号表的组织方式中不包括____方式。
- A. 按标识符种属
- B. 按标识符名字
- C. 直接
- D. 间接
分程序结构的高级语言中，编译程序使用____来区别标识符的作用域。
- A. 说明标识符的过程或函数名
- B. 说明标识符的过程或函数的静态层次
- C. 说明标识符的过程或函数的动态层次
- D. 标识符的行号
在常用的符号表构造和处理方法中，____符号表常把符号表组织成二叉树形式。
- A. 线性
- B. 无序
- C. 散列
- D. 有序
在目标代码生成阶段，符号表用于____。
- A. 目标代码生成
- B. 语义检查
- C. 语法检查
- D. 地址分配
错误的局部化是指____。
- A. 把错误理解成局部的错误
- B. 对错误在局部范围内进行纠正
- C. 当发现错误时，跳过错误所在的语法单位继续分析下去
- D. 当发现错误时立即停止编译，待用户改正错误后再继续编译