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

久爱奥鹏网

久爱奥鹏网 www.92open.com 主要提供奥鹏作业资料，奥鹏在线作业资料，奥鹏离线作业资料以及奥鹏毕业论文，致力打造中国最专业远程教育辅导社区。
. L* k5 V4 q8 p  S8 T6 {* N0 F9 Z
一、单选题（共 20 道试题，共 60 分。）V 1.  Chmosky的3型语言是这样一种语言，其产生式限制为什么()。
* u+ d- b' Y) X" j( B' R6 @A. A::=α
7 y; r' x! l, l0 t3 ~6 R, E9 M" NB. A::=a,A::=Ab
C. α::=β
" A' I8 m* @/ n. DD. αAβ::=απβ
3 G0 Y5 _1 S3 [, A: N      满分：3  分
1 ?/ h( U9 H* F9 J2 z* a1 v2.  DFA中定义了一个从K×Σ到K的单值映射f，指明若当前的状态为P，而输入字符为a时，则下一个状态是Q,f记为什么()。
A. f(P,Q)=a
0 O5 {* b) u& i( j1 E  mB. f(P,a)=Q
  o# g3 m: f! Y$ [3 jC. f(Q,a)=P
D. f(a,P)=Q
- {1 t9 Z; e* O5 @$ e! a- v      满分：3  分
& Y6 h$ Q4 p  \. F% {, T  m' v3.  对于状态转换图中用矢线连接的任意两个结点，把靠箭尾一侧的结点称为该矢线的什么结点()。
A. 进入
B. 射出
& y, F$ v$ ]1 O# VC. 初态
D. 终态
0 e1 Q6 C& @( D3 O% I, n6 X  h      满分：3  分
4.  能将汇编语言翻译为机器语言的程序是什么()。
A. 汇编程序
B. 编译程序
7 `+ |( {0 }& b! fC. 解释程序
D. 语言程序
3 ~0 E: N3 v7 `. O+ G      满分：3  分
" q' T+ v9 c4 m# j% c5.  NFA的要素中不包含哪个成分()。
A. 有穷字母表
B. 初始状态集合
9 k! W* w* V% d/ ^. {C. 终止状态集合
D. 有限状态集合
      满分：3  分
3 @5 V' w6 q$ @( r) g9 r6.  正规文法和FA在描述同一语言类的意义下是什么关系()。
A. 同构
B. 相互等价
C. 可区分
D. 不可区分
      满分：3  分
5 A& o1 s& m4 |- }" Y7.  对于自底向上的语法分析而言，须着重解决的问题是什么()。
A. 如何确定一个规范句型的句柄
B. 应将句柄归约为哪个非终结符号
2 [  }' p/ C9 R( w- N6 @3 y1 A8 mC. 如何确定一个规范句型的句柄，以及应将句柄归约为哪个非终结符号
$ w8 t) }& I  ^7 a1 ]5 dD. 以上都不是
: ]* Y* p. Q: ~: }) E' \7 b      满分：3  分
8.  通常把每个非终结符号的右部符号串称为该非终结符号的什么()。
3 I5 m% ?$ b6 }4 a$ J4 sA. 推导项
3 H9 d! Q$ [0 g5 J$ t5 s$ WB. 选择式
. \& u, b8 n( C& JC. 规则项
D. 候选式
      满分：3  分
9.  在BNF表示方法中，“→”表示什么()。
A. 恒等于
B. 不等于
4 a0 S# v- W0 A8 o4 L  SC. 取决于
$ V, A! m8 _; O( {) X6 xD. 定义为
      满分：3  分
10.  设有文法G[S]：S→aTS|b|(T)，T→TSd|a，则该文法的左句型是哪个()。
7 D* Q% z& }0 {7 J. z6 IA. aT(T)
B. aTaaS
C. aT(T)Ds
D. aTSdS
      满分：3  分
6 A0 b0 p. b" I11.  句型是由什么推导出的符号串()。
A. 非终结符
% c: [) ~0 Q- N( r; |' R5 ], p" Y+ |% lB. 终结符
; h* E! \) `6 X3 b1 s& g* X9 lC. 任何符号
- B0 G5 M6 P( P0 XD. 开始符号
      满分：3  分
2 O( c3 F6 w" {2 x12.  什么问题对具体语言及编译程序的运行环境有很强的依赖性()。
4 \$ T& m& n' l- `A. 分遍
B. 覆盖
- p- N: H: }) G, G0 ?C. 扫描
0 ?: N. H, J2 I0 P8 k3 J- T& WD. 翻译
      满分：3  分
0 e. a$ u7 a$ j; {, O( ^13.  是否存在能被确定的有穷自动机识别，但不能用正则表达式表示的语言()。
: z$ f) r1 }* [+ J% s# X; p! cA. 存在
B. 不存在
C. 可能存在
* x& ?( n* E1 e2 p) TD. 无法判定是否存在
      满分：3  分
6 q- l- R  I+ L( t14.  即使A是一个有用的符号，如下哪一类产生式也是不必要的()。
! U( c' H7 W, Z; UA. A→A
B. A→Aa
* q5 Q! m: Q# i( t# |- eC. A→aA
$ a: M% p' C8 A# o4 _, S3 U1 \: SD. A→aAb
      满分：3  分
$ E9 x2 Q, y* Q9 d. ?15.  不属于编译程序组成部分的是什么()。
5 _. ?, ]0 s( ~* o5 uA. 词法分析程序
) p2 C* V7 q( o  j; s9 oB. 代码生成程序
, e. {9 `+ Q6 |3 R% H2 RC. 设备管理程序
6 k& F! g: @$ D+ h& xD. 语法分析程序
      满分：3  分
# v* X( L1 ~% P8 X$ _16.  下述正规表达式中，能描述字母表｛0，1｝上所有长度不为3的符号串的是哪个()。
. @. |; @& n$ Y+ v5 s" k$ ]. R8 \A. (ε|0|1|00|11|10|01)((0|1)(0|1)*)
% m! I$ E2 J% y! rB. ε|0|1(00|11|10|01)*
C. ε|0|1(00|11|10|01)(0|1)*
D. 没有一个
/ i6 R& k3 }' R% m2 N2 ^( d      满分：3  分
# V1 R( K& K$ J' A17.  正规表达式最适合描述什么()。
& y# k' n% Z" Z! V3 f" oA. 语法
. l2 o8 I; w; h8 F0 P+ WB. 语义
C. 词法
D. 程序变换
3 p" t( W2 x' F/ w" f. w0 q      满分：3  分
, Y& Q, c- D/ Y18.  设G是一右线性文法，并设G中的非终结符号的个数为k，则所要构造的状态转换图共有几个结点()。
5 p" T) I& y2 }0 f# v8 DA. k-1
; m- C$ f% M+ a4 Z6 lB. k
- ]: j! _: _2 C+ ~  l5 l* yC. k+1
D. k+2
      满分：3  分
4 r& m+ B9 x/ x6 w) P! f* `19.  描述语言L={a的m次方b的n次方|n≥m≥1}的文法是哪个()。
' b9 ^& S2 Q3 m4 n9 YA. Z::=Abb,A::=aA|a,B::=bB|b
B. Z::=AB|b,A::=Aa|a,B::=aBb|b
9 e3 ^2 v2 Q8 ^! q0 X5 dC. Z::=Ab,A::=aAb|a
D. Z::=aAb,A::=Ab|aAb|ε
      满分：3  分
20.  方程X=rX+t的解是什么()。
A. X=rt*
* m! e6 |' \, Y  N) ]$ uB. X=t*r
/ ?1 Z' v# D7 F+ d$ t: x; t) rC. X=r*t
2 q7 g+ \. P' _% h! ?D. X=tr*
      满分：3  分

二、判断题（共 20 道试题，共 40 分。）V 1.  每一个NFA都对应有唯一的一个最小化的DFA。
A. 错误
B. 正确
, g6 f! l4 V- F' [      满分：2  分
8 m! H3 Y3 F- C8 M1 m2.  计算机高级语言翻译成低级语言只有解释一种方式。
- E/ n" t. w. S5 \* z' FA. 错误
) ~! {; w& B9 C; ^: ~B. 正确
5 w) W, _$ W0 n# c/ [! \( o6 Q7 @      满分：2  分
3.  在一个状态转换图中，规定从一个结点只能射出一条矢线。
A. 错误
! z% G, v( L' o: r: j3 zB. 正确
      满分：2  分
4.  1型文法常用来描述一个程序设计语言的单词结构。
& D9 l! i: h6 l, xA. 错误
B. 正确
      满分：2  分
8 x2 J7 U! p' q) A+ f5.  对于要求经一遍扫描就能完成从源程序到目标代码翻译的编译程序，不必产生中间代码。
; @* N& j% O* K" ~/ ZA. 错误
4 e$ K! w& O) x  \B. 正确
      满分：2  分
6.  上下文无关文法可以产生语言 L＝｛anbncn|n≥l｝。
4 Z: r( ]5 I% y# V$ ~A. 错误
B. 正确
( O$ z/ e3 O8 m# h/ e) x; q/ v7 d      满分：2  分
7.  编译程序生成的目标程序一定是可执行的程序。
A. 错误
B. 正确
. P5 Q+ e3 y2 U$ z6 e7 U6 B      满分：2  分
8.  对程序语言来说，关键字、标识符、各种常数、各种运算符及分隔符都是单词。
8 Z3 T5 G* ?0 c$ L7 FA. 错误
; ^+ A0 s6 {) y! r4 Q* CB. 正确
! v8 {* \3 t* U8 m      满分：2  分
0 m' ]5 U" t# `1 {# C! y/ X9.  一个文法所有句子的集合构成该文法定义的语言。
A. 错误
3 _! x. Q0 B! N5 P2 R! SB. 正确
      满分：2  分
; v8 S" M+ a7 d) M- o10.  根据文法等价的概念，可对文法进行等价改造，以期得到所需形式的文法。
$ l, Y- q$ z* W3 z3 V# t* AA. 错误
B. 正确
( ]9 S' D5 y7 c# h( v      满分：2  分
- C  h/ d. u; U: r+ d: z11.  一个仅能处理绝对正确源程序的编译程序才具有实用价值。
4 a1 ~/ D/ n* EA. 错误
3 \2 m" c# z0 eB. 正确
8 @* {- i0 Z& D) F. [# c      满分：2  分
+ P8 q; L2 ^' z4 U12.  若消除文法中的ε-产生式，将会改变文法所定义的语言，故不能消除ε-产生式。
9 }3 X0 ~& v& q* GA. 错误
B. 正确
# `4 @9 h) g4 O4 ~# V5 q# y- V      满分：2  分
13.  每个句型不一定存在一个规范推导。
A. 错误
/ I# f9 R+ Y9 A  _5 tB. 正确
5 `% U. \# _) \: ]      满分：2  分
14.  当ε∈L(G)时，则G中的ε-产生式肯定不能全部予以消除。
8 t3 O$ Y% m0 c6 FA. 错误
B. 正确
      满分：2  分
15.  状态转换矩阵的列标题表示状态图中的各个状态。
* v  z! Q9 q! S  W# `6 DA. 错误
3 R# a# Z0 k" @3 {6 L5 E9 nB. 正确
      满分：2  分
7 ]+ p! }, z- ~* M  ]3 x) [; Y8 e16.  一个NFA对符号串的识别是一个试探的过程。不过，这种不确定性给识别过程带来的反复，不会影响到FA的工作效率。
2 K  p$ _8 x$ E9 ZA. 错误
" p. @  |; S& H( I6 rB. 正确
: Q1 f% `1 l, P* _5 \      满分：2  分
17.  对于具有二义性的文法，其规范句型的句柄也是惟一的。
A. 错误
3 C8 O  v# q' u) eB. 正确
      满分：2  分
18.  正规文法产生的语言都可以用上下文无关文法来描述。
: C& J8 G( D! XA. 错误
6 ]9 S) e- b% x1 Q+ D8 `) ~0 }B. 正确
      满分：2  分
: j5 N* R! B7 ~6 i- c* A& m" `  w- E, N19.  一个句型对应的一棵语法树包括了该句型的所有推导。
A. 错误
1 w% {) {2 j( L% e/ k6 ^B. 正确
# w" E3 ]+ r9 z" h8 A      满分：2  分
8 t) @$ ~) _9 _4 ]20.  状态转换图不能作为有限自动机的直观图示。
A. 错误
' P9 l  M% A6 ^B. 正确
      满分：2  分

久爱奥鹏网 www.92open.com 主要提供奥鹏作业资料，奥鹏在线作业资料，奥鹏离线作业资料以及奥鹏毕业论文，致力打造中国最专业远程教育辅导社区。