东师编译原理2012秋在线作业答案
2012秋第一次在线作业试卷总分：100 测试时间：--
一、单选题（共20道试题，共60分。）
1.所谓NFA的确定化，是指对任给的NFA，都能相应地构造一DFA，使它们有相同的什么()。
A. 状态集
B. 符号集
C. 接受集
D. 结点集
满分：3分
2.通常我们只考虑最左归约即规范规约,是为了使语法分析能按一种什么方法来进行()。
A. 确定的
B. 任意的
C. 无序的
D. 有序的
满分：3分
3.设有文法G：S→aTS|b|(T)，T→TSd|a，则该文法的左句型是哪个()。
A. aT(T)
B. aTaaS
C. aT(T)Ds
D. aTSdS
满分：3分
4.在BNF表示方法中，“→”表示什么()。
A. 恒等于
B. 不等于
C. 取决于
D. 定义为
满分：3分
5.设G是一右线性文法，并设G中的非终结符号的个数为k，则所要构造的状态转换图共有几个结点()。
A. k-1
B. k
C. k+1
D. k+2
满分：3分
6.汇编程序是将什么程序改造成目标语言程序的翻译程序()。
A. 机器语言
B. 汇编语言
C. 高级语言
D. 低级语言
满分：3分
7.描述语言L={a的m次方b的n次方|n≥m≥1}的文法是哪个()。
A. Z::=Abb,A::=aA|a,B::=bB|b
B. Z::=AB|b,A::=Aa|a,B::=aBb|b
C. Z::=Ab,A::=aAb|a
D. Z::=aAb,A::=Ab|aAb|ε
满分：3分
8.对于状态转换图中用矢线连接的任意两个结点，把靠箭尾一侧的结点称为该矢线的什么结点()。
A. 进入
B. 射出
C. 初态
D. 终态
满分：3分
9.下列工作中，不是由扫描器完成的任务有哪个()。
A. 分析源程序的结构
B. 按词法规则分割出单词
C. 删除注解
D. 删除空格及无用字符
满分：3分
10.能将汇编语言翻译为机器语言的程序是什么()。
A. 汇编程序
B. 编译程序
C. 解释程序
D. 语言程序
满分：3分
11.编译程序能够发现的错误中,除了语法错误,还有什么错误()。
A. 执行
B. 语义
C. 语用
D. 运行
满分：3分
12.一个上下文无关文法G包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组什么()。
A. 句子
B. 句型
C. 单词
D. 产生式
满分：3分
13.将不含形如A→A的产生式和不含无用符号及无用产生式的文法称为什么文法()。
A. 有用的
B. 已化简的
C. 已改造的
D. 确定的
满分：3分
14.词法分析时，单词的识别依据什么来实现()。
A. 下推自动机
B. 图灵机
C. 状态转换图
D. 抽象机
满分：3分
15.对于自底向上的语法分析而言，须着重解决的问题是什么()。
A. 如何确定一个规范句型的句柄
B. 应将句柄归约为哪个非终结符号
C. 如何确定一个规范句型的句柄，以及应将句柄归约为哪个非终结符号
D. 以上都不是
满分：3分
16.若文法G定义的语言是无限集，则文法G必然是什么样的()。
A. 递归的
B. 前后文无关的
C. 二义性的
D. 无二义性的
满分：3分
17.一个句型中的句柄指的是最左什么()。
A. 短语
B. 直接短语
C. 素短语
D. 终结符号
满分：3分
18.正则式的“·”读作什么()。
A. 并且
B. 或者
C. 连接
D. 闭包
满分：3分
19.正规式和正规集之间是否有一一对应的关系()。
A. 存在
B. 不存在
C. 描述
D. 无法确定
满分：3分
20.下述正规表达式中与(a*|b)*(c|d)等价的是哪个()。
A. a*(c|d)|b(c|d)
B. a*(c|d)*|b(c|d)*
C. a*(c|d)|b*(c|d)
D. (a*|b)*c|(a*|b)*d
满分：3分
二、判断题（共20道试题，共40分。）
1.对程序语言来说，关键字、标识符、各种常数、各种运算符及分隔符都是单词。
A. 错误
B. 正确
满分：2分
2.状态转换图中的每一结点均代表在识别或分析过程中扫描器所处的状态。
A. 错误
B. 正确
满分：2分
3.若消除文法中的ε-产生式，将会改变文法所定义的语言，故不能消除ε-产生式。
A. 错误
B. 正确
满分：2分
4.存在既不是左句型也不是右句型的句型。
A. 错误
B. 正确
满分：2分
5.一个文法所有句子的集合构成该文法定义的语言。
A. 错误
B. 正确
满分：2分
6.若G是已化简的文法，则G中的每一符号X都能推出非终结符号串来。
A. 错误
B. 正确
满分：2分
7.有限自动机和正规式不能作为设计扫描器的工具。
A. 错误
B. 正确
满分：2分
8.若G是已化简的文法，则G中的每一符号X至少在一个句子中出现。
A. 错误
B. 正确
满分：2分
9.编译程序生成的目标程序一定是可执行的程序。
A. 错误
B. 正确
满分：2分
10.存在这样的前后文无关语言，用来定义该语言的一切文法都是二义性的。
A. 错误
B. 正确
满分：2分
11.语法树的根结点以文法的非终结符号标记。
A. 错误
B. 正确
满分：2分
12.字母表A的自反传递闭包就是A上所有符号串所组成的集合。
A. 错误
B. 正确
满分：2分
13.对每一个左线性文法G1，一定存在一个右线性文法G2，使得L（G1）＝L（G2）。
A. 错误
B. 正确
满分：2分
14.状态转换图不能作为有限自动机的直观图示。
A. 错误
B. 正确
满分：2分
15.使用解释程序翻译程序时，在源程序未执行完的情况下，也能重新执行已执行过的部分。
A. 错误
B. 正确
满分：2分
16.回溯不会降低语法分析的效率，故不需要避免。
A. 错误
B. 正确
满分：2分
17.计算机高级语言翻译成低级语言只有解释一种方式。
A. 错误
B. 正确
满分：2分
18.上下文无关文法可以产生语言 L＝｛anbncn|n≥l｝。
A. 错误
B. 正确
满分：2分
19.规则的作用，一方面用于定义或描述语言中的语法范畴，另一方面，也常用来产生 (即推导)语言中的句子。
A. 错误
B. 正确
满分：2分
20.在一个状态转换图中，规定从一个结点只能射出一条矢线。
A. 错误
B. 正确
满分：2分
2012秋第二次在线作业
试卷总分：100 测试时间：--
一、单选题（共20道试题，共60分。）
1.对于文法S→BAb|c，A→Aa|d，B→Sa，消除左递归性后，与原文法等价的文法是什么()。
A. S→BAb|c，A→dA′，A′→aA′|ε，B→Sa
B. S→SaAb|c，A→Aa|d
C. S→SaAb|c，A→Aa|d，B→Sa
D. S→cS′，S′→aAbS′|ε，A→dA′，A′→aA′|ε
满分：3分
2.把形如的项目称为一个什么项目()。
A. LR(1)
B. LR(0)
C. SLR(1)
D. LALR(1)
满分：3分
3.基本块的性质中包含哪一条()。
A. 只有一个入口语句和一个出口语句
B. 有一个入口语句和多个出口语句
C. 有多个入口语句和一个出口语句
D. 有多个入口语句和多个出口语句
满分：3分
4.文法Z→ABb|c，A→Ba，B→Za中含有什么样的非终结符号()。
A. 直接左递归
B. 直接右递归
C. 间接左递归
D. 间接右递归
满分：3分
5.在通常的语法分析方法中，哪种方法特别适用于表达式的分析()。
A. 算符优先分析法
B. LR分析法
C. 递归下降分析法
D. LL(1)分析法
满分：3分
6.数组的存储通常有几种方式()。
A. 1种
B. 两种
C. 3种
D. 4种
满分：3分
7.循环不变运算外提时，应把循环中的不变运算提到循环的什么中()。
A. 入口结点
B. 出口结点
C. 首结点
D. 前置结点
满分：3分
8.在下述的语法分析方法中，属于自顶向下的分析方法有哪些()。
A. 简单优先分析
B. 算符优先分析
C. 递归下降分析
D. LR(k)分析
满分：3分
9.不属于确定各基本块入口规则的四元式是什么()。
A. 程序的第1个四元式
B. 由控制转移所转向的四元式
C. 紧跟在无条件转移四元式之后的四元式
D. 紧跟在条件转移四元式之后的四元式
满分：3分
10.自底向上分析开始时，首先在栈底放置什么符号，然后将输入符号逐个推入栈内()。
A. 界符#及开始符号S
B. 开始符号S
C. 界符#号
D. 当前的输入符号
满分：3分
11.文法S→aAa|aBb|bAb|bBa，A→x，B→x是哪一类文法()。
A. LR(0)文法
B. SLR(1)文法
C. LR(1)文法
D. 都不是
满分：3分
12.对一个什么文法G构造相应的优先矩阵，若此矩阵中无多重定义的元素，则可确认G为一算符优先文法()。
A. LL(1)
B. LR(1)
C. 简单优先
D. 算符
满分：3分
13.LR分析表中的哪一个元素指明，当栈顶状态为I且正扫视的输入符号为a时要完成的分析动作()。
A. GOTO
B. ACTION
C. CLOSURE
D. GO
满分：3分
14.当一文法具有左递归的非终结符号A,且A出现在某产生式右部时其左侧有符号B,则在B和A之间的简单优先关系是什么关系()。
A. 等于
B. 低于
C. 等于和低于
D. 没有
满分：3分
15.LL(1)分析法的名字中，第一个“L”的含义是什么()。
A. 自左至右
B. 自顶向下
C. 自底向上
D. 自右至左
满分：3分
16.设有文法G：E→E+T|T，T→T*F|F，F→(E)|i，则终结符*和+之间的算符优先关系是什么()。
A. 大于
B. 小于
C. 等于
D. 无关系
满分：3分
17.在编译程序采用的优化方法中，什么不是在循环语句范围内进行的()。
A. 循环不变运算外提
B. 线性窥孔优化
C. 消除归纳变量
D. 削弱运算强度
满分：3分
18.在下述的语法分析方法中，属于自底向上的方法是哪个()。
A. 递归下降分析
B. 预测分析技术
C. SLR(k)分析
D. LL(k)分析
满分：3分
19.下述语句类中，什么在编译时通常不产生可执行代码()。
A. 赋值语句
B. 流程控制语句
C. 复合语句
D. 说明语句
满分：3分
20.在定义程序中的一个循环时，流程图中的一个结点指的是什么()。
A. 一个四元式
B. 几个四元式
C. 一个基本块
D. 几个基本块
满分：3分
二、判断题（共20道试题，共40分。）
1.若给定文法G，则G是否是LR(1)文法是可判定的。
A. 错误
B. 正确
满分：2分
2.逆波兰表示只能用于表示表达式，不能用于表示其它的语法结构。
A. 错误
B. 正确
满分：2分
3.文法G：E→E＋T|T，T→T*F|F，F→(E)|i是简单优先文法。
A. 错误
B. 正确
满分：2分
4.算符优先分析法只能识别由算符优先文法描述的句子。
A. 错误
B. 正确
满分：2分
5.若文法G的任何一对终结符号之间，至多只有三种算符优先关系之一成立，则称G为算符优先文法。
A. 错误
B. 正确
满分：2分
6.LL(1)分析表可用一个二维数组表示，它的每一列与文法的一个终结符号或界符#相关联。
A. 错误
B. 正确
满分：2分
7.一个程序是正确的是指该程序的语法是完全正确的。
A. 错误
B. 正确
满分：2分
8.布尔表达式有两个基本的作用：一是在某些控制语句中作为实现控制转移的条件；二是用于计算逻辑值本身。
A. 错误
B. 正确
满分：2分
9.对于文法G： A→aABe|Ba，B→dB|ε，有人说：因为 FIRST（aABe）∩ FOLLOW（A）＝，FIRST（Ba）∩ FOLLOW（A）≠，所以，文法G不是LL（l）文法。
A. 错误
B. 正确
满分：2分
10.文法的任意两个符号对之间都存在简单优先关系。
A. 错误
B. 正确
满分：2分
11.对于规模较大的文法，采用手工的方式来计算各个FIRST集和FOLLOW集几乎是不可能的。
A. 错误
B. 正确
满分：2分
12.即使构成循环的一组结点是强连通的，也会使其中有一部分不能被重复地执行。
A. 错误
B. 正确
满分：2分
13.文法G：S→aSb|aSa|c是LR（0）文法。
A. 错误
B. 正确
满分：2分
14.出现在赋值号左部的下标变量，可只具有左值。
A. 错误
B. 正确
满分：2分
15.削弱运算强度的优化是指将原循环中的所有乘法运算都替换为加法运算。
A. 错误
B. 正确
满分：2分
16.合并已知量的目的是使表达式尽可能短。
A. 错误
B. 正确
满分：2分
17.在流程图中的一组结点构成一个循环时，可以有若干个入口结点，但出口结点必须是惟一的。
A. 错误
B. 正确
满分：2分
18.最左素短语可能不是相应文法的任何产生式的右部。
A. 错误
B. 正确
满分：2分
19.在中间代码优化中循环上的优化主要有不变表达式外提和削减运算强度。
A. 错误
B. 正确
满分：2分
20.若给定文法G，则是否存在一个k使得G是一个LR（k）文法的问题是不可判定的。
A. 错误
B. 正确
满分：2分
页:
[1]