编译原理19春在线作业1-0005
试卷总分:100 得分:100
一、单选题 (共 20 道试题,共 60 分)
1.设有文法G[S]：S→aTS|b|(T)，T→TSd|a，则该文法的右句型是哪个()。
A.aT(T)
B.aTaaS
C.aT(T)dS
D.aTSdS
2.设d是结点n的必经结点(即有d DOM n)，若在流程图中，存在着从结点n到d的有向边，则称此有向边为流程图中的一条什么()。
A.环路
B.环边
C.回路
D.回边
3.假设某程序语言的文法如下：S→a|b|(T)，T→TdS|S，考察该文法的句型(Sd(T)db)，其中：素短语是哪个()。
A.S
B.b
C.(T)
D.Sd(T)
4.假设某程序语言的文法如下S→SaT∣T，T→TbR∣R，R→PdR∣P，P→fSg∣e,则终结符b和a之间的算符优先关系是什么()。
A.大于
B.小于
C.等于
D.无关系
5.设有文法G［S］:S→Ac，A→Sb|a，则利用文法G进行自顶向下的语法分析时会怎样()。
A.不会出现回溯
B.会出现回溯
C.不会出现死循环
D.会出现死循环
6.设有文法G[S]：S→SaT|T，T→TbR|R，R→PdR|P，P→fSｇ|e， 考察该文法的句型SaTbfSgde，其中哪个是句柄()。
A.SaT
B.b
C.fSg
D.e
7.如果一个DFA的两个不同的状态s和t具有什么关系，则称s和t等价()。
A.已区分
B.待区分
C.可区分
D.不可区分
8.一个文法所描述的语言是什么样的()。
A.唯一的
B.不唯一的
C.可能唯一
D.可能不唯一
9.LL(1)分析法的名字中，第二个“L”的含义是什么()。
A.最右推导
B.最右归约
C.最左推导
D.最左归约
10.我们把右部仅含一个非终结符号的产生式，称为什么产生式()。
A.无用
B.有用
C.奇
D.单
11.在设计布尔表达式翻译算法时，什么四元式表示当关系A1<A2 成立时，转向第p四元式()。
A.(jnz, A1,,p)
B.(j<,A1,A2,p)
C.(j, , ,p)
D.(j, A1,A2,p)
12.编译程序已成为现今任何计算机系统的最重要的什么之一()。
A.系统程序
B.应用程序
C.支撑程序
D.自动化程序
13.是否存在能被确定的有穷自动机识别，但不能用正则表达式表示的语言()。
A.存在
B.不存在
C.可能存在
D.无法判定是否存在
14.编译程序与运行系统合称为什么()。
A.翻译系统
B.编译系统
C.实时系统
D.分布式系统
15.当一文法具有左递归的非终结符号A,且A出现在某产生式右部时其左侧有符号B,则在B和A之间的简单优先关系是什么关系()。
A.等于
B.低于
C.等于和低于
D.没有
16.两个有穷自动机等价是指它们的什么相等()。
A.状态数相等
B.有向弧数相等
C.所识别的语言相等
D.状态数和有向弧数相等
17.欲按编译方式在计算机上执行用高级语言编写的程序，一般需经过两个阶段： 第一阶段称为编译阶段，第二阶段称为什么阶段()。
A.解释
B.翻译
C.汇编
D.运行
18.把用一组数学符号和规则来描述语言的方式称为什么()。
A.推演
B.推导
C.形式描述
D.形式语言
19.程序基本块是指什么()。
A.一个子程序
B.一个仅有一个入口和一个出口的语句
C.一个没有嵌套的程序段
D.一组顺序执行的程序段且仅有一个入口和一个出口
20.对于状态转换图中用矢线连接的任意两个结点，把靠箭尾一侧的结点称为该矢线的什么结点()。
A.进入
B.射出
C.初态
D.终态
二、判断题 (共 20 道试题,共 40 分)
21.存在这样的前后文无关语言，用来定义该语言的一切文法都是二义性的。
22.一个二义性文法所描述的语言不是唯一的。
23.一个复杂的表达式须由多个四元式构成的序列来表示。
24.预测分析表中各个元素的值，不包含输入符号串中存在语法错误时的情形。
25.状态转换图中的每一结点均代表在识别或分析过程中扫描器所处的状态。
26.对于那些具有间接左递归性的非终结符号，通过逐步代入有关产生式的方式，可以将它们化为直接左递归的产生式。
27.若给定文法G和某个固定的k，则G是否是LR(k)文法是可判定的。
28.文法G的一个句子对应于多个推导,则G是二义的。
29.若一个句型中出现了某产生式的右部，则此右部一定是该句型的句柄。
30.对任何正规表达式e，都存在一个NFA M，满足L(M)=L(e)。
31.词法分析程序无法自动生成，只能用手工的方式构造。
32.正规文法一定不是二义性的。
33.循环的入口结点是循环中每一结点的必经结点。
34.一个句型的句柄一定是文法某产生式的右部。
35.若在一个文法G的任何产生式的右部，都不会出现两非终结符号相邻的情况，则称G为算符优先文法。
36.程序中的任何控制转移四元式（条件转移、无条件转移、停机等）都是某基本块的出口。
37.有限自动机和正规式不能作为设计扫描器的工具。
38.若一个文法G含有既是左递归亦是右递归的非终结符号，则G必定是无二义性文法。
39.对一个布尔表达式而言，它必须至少有一个真出口，但可以没有假出口。
40.对任何正规表达式e，都存在一个DFA M，满足L(M)=L(e)。
