[东北大学]21年12月考试《编译方法》考核作业

奥鹏在线作业

东 北 大 学 继 续 教 育 学 院
0 N2 I6 S( `4 _# K! f' c     编 译 方 法      试 卷（作业考核 线上2）  A  卷（共   5   页）         
; ?$ ~) F8 Q; m+ o& M# T8 f, k总分        题号        一        二        三        四        五        六        七        八        九        十
% d* r5 v; K/ v  Z$ `* K. F        得分                                                                               
5 L4 E6 d' e& H& {7 p一、更多资料下载：谋学网（www.mouxue.com）（在备选资料中选出一个正确资料，每题3分，共30分）
01. 程序设计语言一般分为(   )和(   )两大类, 其中低级语言通常又称为（   ）
A. 高级语言,低级语言,通用程序语言
$ N9 y% Y" N7 d9 ]B. 专用程序语言,高级语言,低级语言
C. 专用程序语言,低级语言,面向机器的语言
D. 高级语言,低级语言,面向机器的语言
02． 如果编译程序生成的目标是机器代码程序, 则源程序的执行分成两大阶段:（   ）和（   ）
A. 编辑阶段, 运行阶段
B. 编译阶段, 连接阶段
C. 编译阶段, 运行阶段
D. 编辑阶段, 连接阶段
03．已知文法G(E) :   
                         E -> T|E+T|E-T
           T -> F|T*F|T/F
           F -> i|(E)
. Z: k" a/ E# O% K0 {该文法的开始符号是: (   ), 终结符集合VT是(   ),非终结符集合VN是(   ),句型T+T*F+i的短语有(   )
A.   E;   {+,-,*,/,(,)};   {E,T,F};   T+T*F+i, T+T*F, T,T*F,i
$ R) J5 k1 s  r, F6 `/ {# eB.   T;   {+,-,*,/,i,(,)};   {E,T,F};   T+T*F+i, T+T*F, T,T*F,i
& d- Q: h  s6 w, Y) F2 {0 YC.   E;   {+,-,*,/,i,(,)};   {E,T,F};   T+T*F+i, T+T*F, T,T*F,i
D.   T;   {+,-,*,/,i,(,)};   {E,T,F};   T+T*F+i, T+T*F, T,T*F
: H8 m8 z4 V9 Q5 K6 `& y04. 文法G所描述的语言是(  )的集合  
A. 文法G的字符表∑中所有符号组成的符号串
B. 文法G的字符表∑的闭包∑*中的所有符号串
2 S% {' t, `2 q4 |# |2 oC. 由文法的开始符号推出的所有符号串
- D. c/ p! r, ~1 ~8 U8 U$ _8 ], ?D. 由文法的开始符号推出的所有终结符号串
05. 有限状态自动机可定义如下五元组：FA=(Q ,∑,Q0 , F ,δ),其中：(   )
4 j+ ?* r% J5 ^6 G7 p: U7 rA. Q - 状态集合 ,∑ - 字母表,Q0  - 开始状态集合 ,F - 结束状态集合,δ -状态变换函数 ;
, N; w! u+ o# P3 K8 @9 i4 oB. Q - 状态集合 ,∑ - 字母表,Q0  - 开始状态集合 ,F - 结束状态集合 ,δ - 产生式 ;
" {/ @+ M+ a% R+ z0 G  CC. Q - 状态集合 ,∑ - 字母表,Q0  - 开始状态集合 ,F - 结束状态 ,δ -状态变换函数 ;
; b# _+ U; W3 H; M# ]06. 词法分析的单词识别中，区分关键字和标识符的方法，通常是把拼得的字符串首先查(   ) , 若(   )则视为(   ) , 否则为(   )
A. 关键字表, 查到, 关键字, 标识符
# _# W3 N! R  _( sB. 关键字表, 查不到, 关键字, 标识符
C. 标识符表, 查到, 关键字, 标识符
D. 关键字表, 查到, 标识符, 关键字
8 f3 b* D7 y5 l07. 程序设计语言单词通常可分如下四类(   )
A. 关键字, 标识符, 常数, 界符
/ n0 d8 c" {7 h, ^0 P& {* T& gB. 关键字, 变量, 常数, 界符
C. 整型 , 字符型,  俘点型,  布尔型
08. 编译过程中, 语法分析器的任务是(  )
$ r" @  R: y: i: h( x$ v. C0 C(1)分析单词是怎样构成的
(2)分析单词串是如何构成语句和说明的
(3)分析语句和说明是如何构成程序的
, s; a1 p- q1 }3 ]- v, B9 i2 B" F" w(4)分析程序的结构
A. (2)和(3)     
8 A7 a' \( l# ?* F( B$ qB. (4)     
C. (2),(3),(4)     
* c* J, }6 C7 O' f9 D7 r( L( y$ PD. (1),(2),(3),(4)
1 [) u& V3 g& P09. 设有文法 G(S):   
8 Z# J5 v, H7 _; o- I2 bS -->  a A c | a A S |  b
A -->  d S A | c
指出下述符号串中，哪些是该文法的句子？
abcdb,   acc,   acabc,  adbcb,  acbac;
A. abcdb   
( N' T5 j3 _- s2 _: k/ E6 a! KB. acabc,  adbcb   
, i) ~! V; _4 O- F  _; X% tC. acc,   acabc,  acbac   
: u/ t& }+ V% z( N4 `D. acc,  adbcb
" Q- K7 C; U2 l; m) _5 r10. 编译程序在其工作过程中使用最多的数据结构是(  ), 它记录着源程序中的各种信息. 在这些表中, 尤其以(  )最为重要, 它的生存期最长, 使用也最频繁。
A. 线性表 ,  符号表           B. 表 ,  链表   
C. 线性表 , 链表              D. 表 , 符号表

( G9 X- f3 E3 ~. p8 P0 i二、资料来源：谋学网（www.mouxue.com）（每题3分，10道题，30分）
, P# Y5 f# P1 a7 ?5 r01. “用高级语言书写的源程序都必须通过编译, 产生目标代码程序后才能投入运行.”这种说法(  )
A、错误                           B、正确
02. 编译程序生成的目标程序一定是机器语言的程序。（    ）
A、错误                           B、正确
4 G" ?$ ?+ n, w, o) ^- d% j0 n! F5 H03. 文法的两种运算系指: 推导和连接。（    ）       
A、错误                           B、正确
. t' |7 L* Z1 ~& B8 b04. 文法是用于定义语言的，它可用如下四元组描述:
G(Z)=( VN , VT , Z , p ),其中：Z称为文法的结束符号。（    ）
$ f5 j& I6 A: C8 F) S$ i# v% CA、错误                           B、正确
* O" y- ^+ ]9 f6 W% G05. 有限自动机可用来描述上下文无关语言语言。（    ）
  f- Y, f! W, J" k- Z9 w/ DA、错误                           B、正确
6 S6 t* p& y! S9 \9 H6 d# _. a06. 正规文法是特指文法产生式仅具有如下形式：⑴ A -> aB ⑵ A -> a ⑶ A -> e。（    ）
A、错误                           B、正确
. M& F' t, ~9 i9 s) g9 H3 F07.  TOKEN 是词法分析中单词的一种机内数据结构表示,其结构是{类，值}。（    ）
+ R* y* U# c: E7 jA、错误                           B、正确
08. 语法分析的任务，是对给定的符号串，判定其是否是某文法的句子。（    ）
A、错误                           B、正确
  l6 v* H- z- T* a3 Y09.语法分析方法分两类: (1)  自顶向下分析;  (2)  自底向上分析。（    ）
A、错误                           B、正确
10. 过程的一次执行所需要的信息用一块连续的存储区域来管理，这块存储区叫做符号表。（    ）
A、错误                           B、正确
& p* c$ |1 Y/ ?9 h) P& Z& l
0 T! K3 ]! G  j5 g) n9 A7 P三、（15分）回答下列问题:  
（1）写出表达式 a*(b-c/d+e) 的逆波兰式:
7 ^# r/ ]* x" h0 t- \3 W& t（2）写出条件语句 if (x>0) x=a+b/10 的四元式序列:
$ O6 P  F0 V7 O0 w（3）设有算术表达式文法如下:
          E -->  T | E + T | E – T  
          T -->  F | T * F | T /  F
          F -->  i | ( E )    其中: i : 变量或常量；
试构造四元式翻译文法并指出其中各翻译子程序的功能:





  _- ^  G! Z& w1 G% _9 @  w
: [) u4 L, f* w! J  v1 {



# y% X" g* W3 U8 r# B* q( a& ^% I
5 S9 S. h7 G  y


! L' S! u2 B) S8 s7 V7 v4 {- k) I2 p
: }7 v0 \/ h0 ]/ |+ {四、（15分）试已知符号串集合为：  A= { a bn c ,d │ n≥0   }  
（1）构造相应的有限自动机：
（2）构造相应的文法:    G(S):  
（3）已知有限自动机 FA (右图) ：
" E6 L8 p1 `: _8 ?0 g
) v, \# k! E3 E# ?6 g2 ?                             FA:                                
  Q0 j' e; x8 G, u4 U$ r% \: f2 z" J
     写出 FA 所表示的符号串集合(语言)：  
8 A& x/ E, W! M- S+ D
" {8 D1 b+ l+ z% U! A( n

% u) r! O1 r; |7 a/ l& v& u
8 W$ P6 i0 _$ W
- G4 X2 u% r, J0 ]3 Q% v! i
( R* }1 a9 C# w0 D  K, t

* v; A# l. H  X" b- y9 T
5 @2 g$ E. ]4 r
# l4 z) X) P! X$ b+ }0 o) r
* S; U) z7 m% P' c3 L0 e
% H0 o' n& k. |  q) C

! Q1 U6 c3 s7 f2 L, ?; Y五、（10分）设有文法 G(S):
0 ?0 Z6 f% _( K+ K2 [! U) HS -> a B d | b A B
2 J; v% C9 i- k, ~. c/ I. }) {                   A -> a A b | b
                   B -> c | B c
（1） 证明 baAbcc 是一个句型，画出此句型的语法树, 指出此句型的短语、简单短语和句柄;
$ V, Y$ T/ T' i. j（2） 把文法中的左递规产生式变换成非左递规产生式。


4 n& X( ?4 D9 N' Y2 t