东师11秋《编译原理》第一次在线作业

久爱奥鹏网

久爱奥鹏网 www.92open.com 主要提供奥鹏作业资料，奥鹏在线作业资料，奥鹏离线作业资料以及奥鹏毕业论文，致力打造中国最专业远程教育辅导社区。
2 e+ w2 k& ^( \$ l2 O. K  s$ k- y5 |
一、单选题（共 20 道试题，共 60 分。）V 1.  Chmosky的3型语言是这样一种语言，其产生式限制为什么()。
A. A::=α
8 H- ~+ l+ ?1 L3 iB. A::=a,A::=Ab
C. α::=β
- ~- s8 E* ]9 \  iD. αAβ::=απβ
      满分：3  分
2.  DFA中定义了一个从K×Σ到K的单值映射f，指明若当前的状态为P，而输入字符为a时，则下一个状态是Q,f记为什么()。
3 S- S. s; g& ~8 tA. f(P,Q)=a
B. f(P,a)=Q
C. f(Q,a)=P
5 Z; u! n3 N( |$ J8 I6 W+ tD. f(a,P)=Q
      满分：3  分
3.  对于状态转换图中用矢线连接的任意两个结点，把靠箭尾一侧的结点称为该矢线的什么结点()。
A. 进入
- g' M8 i& t8 m& i% @+ g3 O. Z8 Q% RB. 射出
C. 初态
+ h* C( G, F3 r$ eD. 终态
- ?$ \7 H0 n$ b/ M! Y      满分：3  分
4.  能将汇编语言翻译为机器语言的程序是什么()。
9 @2 g9 n' D! v$ [: }( yA. 汇编程序
B. 编译程序
C. 解释程序
D. 语言程序
      满分：3  分
& l6 {: `) e( j  I  d4 f5.  NFA的要素中不包含哪个成分()。
2 D8 U* r: l  A# ~A. 有穷字母表
, q4 P% v8 v9 N# Y1 m2 E4 s- vB. 初始状态集合
/ N, y' d# a3 S( ]C. 终止状态集合
3 ]& p" P/ q' T( \7 E$ hD. 有限状态集合
3 u' G1 S6 k& H5 `6 h- T      满分：3  分
; v' [8 ?! w# v# v1 ~6.  正规文法和FA在描述同一语言类的意义下是什么关系()。
A. 同构
: {! \4 j  Y1 N5 GB. 相互等价
, _9 i9 r4 F, z- }5 x6 ?C. 可区分
: J+ ]. `8 W  E7 ~' GD. 不可区分
8 g$ c. U, O: g. P" O* b" b4 M      满分：3  分
7.  对于自底向上的语法分析而言，须着重解决的问题是什么()。
A. 如何确定一个规范句型的句柄
* n. t+ [7 Q1 \4 B& eB. 应将句柄归约为哪个非终结符号
* N3 c" g9 g- s0 z* }3 n4 d) mC. 如何确定一个规范句型的句柄，以及应将句柄归约为哪个非终结符号
9 d  W9 Q. z5 e) y8 AD. 以上都不是
      满分：3  分
8.  通常把每个非终结符号的右部符号串称为该非终结符号的什么()。
5 n$ R0 z0 }  x$ \9 L- ]A. 推导项
B. 选择式
* q6 G/ }' _/ a8 A  Z+ ^# FC. 规则项
D. 候选式
. D7 r9 D; v; `      满分：3  分
9.  在BNF表示方法中，“→”表示什么()。
% u4 \7 p; ~& `& M# h, mA. 恒等于
B. 不等于
C. 取决于
D. 定义为
( d8 g/ C0 m6 Y3 d" F/ @      满分：3  分
' l  w0 y6 V) l4 I9 c8 K10.  设有文法G[S]：S→aTS|b|(T)，T→TSd|a，则该文法的左句型是哪个()。
- z# M" X- o, R6 k, ?; cA. aT(T)
B. aTaaS
- ~2 D, e  l" rC. aT(T)Ds
5 _3 p6 u" L; Q0 ?D. aTSdS
      满分：3  分
3 U; m( f  v$ _/ [' B% r0 {11.  句型是由什么推导出的符号串()。
A. 非终结符
; d8 }- X, L" l6 `. S& r5 c5 MB. 终结符
C. 任何符号
, B# k5 Y  S$ r  RD. 开始符号
      满分：3  分
12.  什么问题对具体语言及编译程序的运行环境有很强的依赖性()。
A. 分遍
B. 覆盖
  L  E5 D( h2 e! _* D2 J3 LC. 扫描
6 G' k3 E5 @5 K( ?( S9 x  dD. 翻译
- e% t6 c5 q7 r      满分：3  分
) L% |3 U* [! q( ~13.  是否存在能被确定的有穷自动机识别，但不能用正则表达式表示的语言()。
, D/ f7 O/ ~0 `3 _' |+ A0 V; xA. 存在
3 `. U& V8 ?" L. N. sB. 不存在
C. 可能存在
) u( X* O: \* Q. QD. 无法判定是否存在
3 s& y1 Z# \; y# n% H      满分：3  分
14.  即使A是一个有用的符号，如下哪一类产生式也是不必要的()。
A. A→A
5 s$ ?; n' F3 I$ N+ T6 L; x* h# eB. A→Aa
C. A→aA
9 G: T  I0 S- ]$ w" c+ ]D. A→aAb
, C- _  x9 y8 A  O1 e      满分：3  分
+ y3 P( ~+ J$ i: m% D( {15.  不属于编译程序组成部分的是什么()。
* F9 j' h# ~, j7 s- iA. 词法分析程序
B. 代码生成程序
8 \. S. s( a* S3 X9 AC. 设备管理程序
D. 语法分析程序
      满分：3  分
16.  下述正规表达式中，能描述字母表｛0，1｝上所有长度不为3的符号串的是哪个()。
3 K& a& a) t  TA. (ε|0|1|00|11|10|01)((0|1)(0|1)*)
% {& N. ~* A. \  t# f# |& x8 W( ~5 mB. ε|0|1(00|11|10|01)*
C. ε|0|1(00|11|10|01)(0|1)*
. R- w. \! W" {2 dD. 没有一个
  V5 ]! I% j3 {! \      满分：3  分
17.  正规表达式最适合描述什么()。
0 p8 h: j1 y* J* U- H9 uA. 语法
" F& S+ f. i7 CB. 语义
  [! q6 \& s& m2 ^0 e0 E0 V' U+ NC. 词法
D. 程序变换
4 E5 f2 V+ f: {. i; B! Q. ^! Y      满分：3  分
# g4 q* p7 ]1 q! X  G18.  设G是一右线性文法，并设G中的非终结符号的个数为k，则所要构造的状态转换图共有几个结点()。
A. k-1
B. k
7 A1 z9 y+ ?/ g1 V3 x* Q6 HC. k+1
D. k+2
! s8 M! A( c% @8 @6 w" }( i      满分：3  分
* w/ a: Y; i8 ?( N/ d19.  描述语言L={a的m次方b的n次方|n≥m≥1}的文法是哪个()。
1 Y9 `( E5 g' [2 g$ G& A) [A. Z::=Abb,A::=aA|a,B::=bB|b
; j; H  {1 S6 S/ G& OB. Z::=AB|b,A::=Aa|a,B::=aBb|b
C. Z::=Ab,A::=aAb|a
D. Z::=aAb,A::=Ab|aAb|ε
* g* t* Y  Y) h9 `3 r2 ^( |, H- e$ }  A      满分：3  分
20.  方程X=rX+t的解是什么()。
A. X=rt*
" r' D! k/ z& U  KB. X=t*r
C. X=r*t
D. X=tr*
      满分：3  分
+ p9 J' M: e! C! D6 K6 A
二、判断题（共 20 道试题，共 40 分。）V 1.  每一个NFA都对应有唯一的一个最小化的DFA。
3 C1 }6 W) z1 vA. 错误
# @1 P; `% m9 m& y7 j( CB. 正确
" _- q" p' ?4 v3 n1 ]      满分：2  分
2.  计算机高级语言翻译成低级语言只有解释一种方式。
; ^. [# w) ?( a) m9 tA. 错误
B. 正确
) V. n0 p; `4 y% p6 m" f      满分：2  分
  t$ U+ P: p; b8 _( l3.  在一个状态转换图中，规定从一个结点只能射出一条矢线。
: x' s1 f6 k. t$ k! UA. 错误
B. 正确
      满分：2  分
4.  1型文法常用来描述一个程序设计语言的单词结构。
A. 错误
B. 正确
      满分：2  分
5 P* G1 N7 c% n5 t! t5.  对于要求经一遍扫描就能完成从源程序到目标代码翻译的编译程序，不必产生中间代码。
+ ~" `# h, M- H# |9 wA. 错误
B. 正确
      满分：2  分
6.  上下文无关文法可以产生语言 L＝｛anbncn|n≥l｝。
A. 错误
B. 正确
/ B) B0 s" s, |, e      满分：2  分
4 ~& g9 ~9 o5 x4 Z7.  编译程序生成的目标程序一定是可执行的程序。
A. 错误
5 F. }6 g$ j3 ?: p5 E$ e  M- EB. 正确
      满分：2  分
6 A9 t  [% k3 l8.  对程序语言来说，关键字、标识符、各种常数、各种运算符及分隔符都是单词。
A. 错误
B. 正确
2 G- h! a0 Z; {  Q5 u$ V      满分：2  分
; g- X, R0 ?! o; }  b9.  一个文法所有句子的集合构成该文法定义的语言。
A. 错误
B. 正确
5 X6 |( Z: o& H/ q: _/ U      满分：2  分
7 W, Q- C0 U. D) u* v& Q3 k: M) }0 n# a10.  根据文法等价的概念，可对文法进行等价改造，以期得到所需形式的文法。
. s; x, ^9 f% a4 \$ I5 V7 }& uA. 错误
B. 正确
$ _5 i3 F5 d- e, Z% i4 n% v      满分：2  分
11.  一个仅能处理绝对正确源程序的编译程序才具有实用价值。
A. 错误
B. 正确
      满分：2  分
! J1 J9 }, ?9 u- S2 `12.  若消除文法中的ε-产生式，将会改变文法所定义的语言，故不能消除ε-产生式。
7 B% z8 e  }9 ^4 K) FA. 错误
# X5 x8 f, A1 l" J" U+ _7 N3 MB. 正确
      满分：2  分
13.  每个句型不一定存在一个规范推导。
A. 错误
B. 正确
7 `! w+ y. o1 `9 B      满分：2  分
5 s+ W8 x1 \; B. H' z0 @+ p6 ?14.  当ε∈L(G)时，则G中的ε-产生式肯定不能全部予以消除。
A. 错误
2 B  _+ J7 S( |7 v9 |& jB. 正确
+ E4 H& y! b' z4 T7 b$ e, c      满分：2  分
+ y$ y% B# T5 c% E4 W) `15.  状态转换矩阵的列标题表示状态图中的各个状态。
/ _6 s0 o) m; M- b) }A. 错误
B. 正确
0 O! ?" j6 |: p' j2 K& Y8 _      满分：2  分
: t6 C- ]2 I4 x: D4 L16.  一个NFA对符号串的识别是一个试探的过程。不过，这种不确定性给识别过程带来的反复，不会影响到FA的工作效率。
A. 错误
$ K4 o) ?. z3 {' y3 @! hB. 正确
: @: ^5 q1 F# n: w8 e, i1 N      满分：2  分
17.  对于具有二义性的文法，其规范句型的句柄也是惟一的。
A. 错误
% Y. b; V5 v' ]+ ]B. 正确
1 K1 Q" s4 d% H5 n% i7 t+ L      满分：2  分
18.  正规文法产生的语言都可以用上下文无关文法来描述。
A. 错误
# q7 i+ d, j1 R! dB. 正确
      满分：2  分
19.  一个句型对应的一棵语法树包括了该句型的所有推导。
, S! X7 W7 [1 X7 jA. 错误
B. 正确
      满分：2  分
20.  状态转换图不能作为有限自动机的直观图示。
A. 错误
B. 正确
      满分：2  分

/ J. \. c7 a9 m- U# v+ h) C6 Z1 w+ R久爱奥鹏网 www.92open.com 主要提供奥鹏作业资料，奥鹏在线作业资料，奥鹏离线作业资料以及奥鹏毕业论文，致力打造中国最专业远程教育辅导社区。