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

奥鹏在线作业

东 北 大 学 继 续 教 育 学 院
     编 译 方 法      试 卷（作业考核 线上2）  A  卷（共   5   页）         
总分        题号        一        二        三        四        五        六        七        八        九        十
8 A2 p9 \. r* m. _3 u: a2 ~: B7 G        得分                                                                               
$ z$ Y: h( l& y3 E$ s! w, l一、更多资料下载：谋学网（www.mouxue.com）（在备选资料中选出一个正确资料，每题3分，共30分）
) c5 c& m" j" {/ N* {1 q( P: W01. 程序设计语言一般分为(   )和(   )两大类, 其中低级语言通常又称为（   ）
0 B' J' \/ ?% Q( U0 qA. 高级语言,低级语言,通用程序语言
B. 专用程序语言,高级语言,低级语言
& |& {+ g/ u5 V9 x' L6 U7 oC. 专用程序语言,低级语言,面向机器的语言
D. 高级语言,低级语言,面向机器的语言
02． 如果编译程序生成的目标是机器代码程序, 则源程序的执行分成两大阶段:（   ）和（   ）
  Z7 Y7 R1 D* _A. 编辑阶段, 运行阶段
' ?8 @: n" j. j) E5 X% t" K0 YB. 编译阶段, 连接阶段
! z* f/ Y3 i5 F7 TC. 编译阶段, 运行阶段
D. 编辑阶段, 连接阶段
2 X# _0 X4 e/ F1 o. J8 S03．已知文法G(E) :   
                         E -> T|E+T|E-T
           T -> F|T*F|T/F
           F -> i|(E)
该文法的开始符号是: (   ), 终结符集合VT是(   ),非终结符集合VN是(   ),句型T+T*F+i的短语有(   )
) Q! e3 T3 ^6 E( jA.   E;   {+,-,*,/,(,)};   {E,T,F};   T+T*F+i, T+T*F, T,T*F,i
  i* O' W* ?; D; z  f5 _6 D8 ZB.   T;   {+,-,*,/,i,(,)};   {E,T,F};   T+T*F+i, T+T*F, T,T*F,i
. D& I2 ]) `' `# Y3 M" ^; ^C.   E;   {+,-,*,/,i,(,)};   {E,T,F};   T+T*F+i, T+T*F, T,T*F,i
: v/ s$ w" N& f* J+ p  D! sD.   T;   {+,-,*,/,i,(,)};   {E,T,F};   T+T*F+i, T+T*F, T,T*F
04. 文法G所描述的语言是(  )的集合  
7 t7 h2 u, ?% L  T; EA. 文法G的字符表∑中所有符号组成的符号串
* r* d% R5 V8 W: y+ ~# a" u5 cB. 文法G的字符表∑的闭包∑*中的所有符号串
C. 由文法的开始符号推出的所有符号串
9 _: R1 k+ h, W& ^D. 由文法的开始符号推出的所有终结符号串
$ f+ ?. d8 x( ?1 _, ?5 F05. 有限状态自动机可定义如下五元组：FA=(Q ,∑,Q0 , F ,δ),其中：(   )
; M& @" ^! `9 I; P( b) AA. Q - 状态集合 ,∑ - 字母表,Q0  - 开始状态集合 ,F - 结束状态集合,δ -状态变换函数 ;
B. Q - 状态集合 ,∑ - 字母表,Q0  - 开始状态集合 ,F - 结束状态集合 ,δ - 产生式 ;
C. Q - 状态集合 ,∑ - 字母表,Q0  - 开始状态集合 ,F - 结束状态 ,δ -状态变换函数 ;
06. 词法分析的单词识别中，区分关键字和标识符的方法，通常是把拼得的字符串首先查(   ) , 若(   )则视为(   ) , 否则为(   )
  ]5 L1 C3 ?. d+ Z; tA. 关键字表, 查到, 关键字, 标识符
, U! r3 X9 G% Q( O$ E0 M  EB. 关键字表, 查不到, 关键字, 标识符
C. 标识符表, 查到, 关键字, 标识符
D. 关键字表, 查到, 标识符, 关键字
07. 程序设计语言单词通常可分如下四类(   )
A. 关键字, 标识符, 常数, 界符
( ?# P2 f+ K1 k, f' z$ x7 D8 GB. 关键字, 变量, 常数, 界符
C. 整型 , 字符型,  俘点型,  布尔型
& J' k4 `2 x. R# q! \0 i" \" D- w08. 编译过程中, 语法分析器的任务是(  )
(1)分析单词是怎样构成的
8 O% J3 a  R4 m7 p% z9 o$ Q(2)分析单词串是如何构成语句和说明的
/ U0 n! S6 w& f! w! P- |(3)分析语句和说明是如何构成程序的
4 u7 v. ]+ ]# R( K, b(4)分析程序的结构
3 f2 I  e8 ^* Z4 S+ l" y5 AA. (2)和(3)     
B. (4)     
. V, B' ~5 |4 l, K4 a% A+ dC. (2),(3),(4)     
/ z+ J4 n" _  t9 Q2 r1 ZD. (1),(2),(3),(4)
09. 设有文法 G(S):   
S -->  a A c | a A S |  b
" V6 _$ T; n0 m9 m" B6 D3 A5 s. LA -->  d S A | c
指出下述符号串中，哪些是该文法的句子？
abcdb,   acc,   acabc,  adbcb,  acbac;
3 b& B; w; z% R& g5 B: c) WA. abcdb   
- U3 W/ @+ {5 }$ C6 H, a. QB. acabc,  adbcb   
& l0 ?& G; @. a* }% b% sC. acc,   acabc,  acbac   
: v" q7 S1 h& p* b- u% U- bD. acc,  adbcb
10. 编译程序在其工作过程中使用最多的数据结构是(  ), 它记录着源程序中的各种信息. 在这些表中, 尤其以(  )最为重要, 它的生存期最长, 使用也最频繁。
A. 线性表 ,  符号表           B. 表 ,  链表   
& x% o/ k9 D9 {8 `C. 线性表 , 链表              D. 表 , 符号表
0 f$ \  E% n; O0 |% ]9 |+ U
二、资料来源：谋学网（www.mouxue.com）（每题3分，10道题，30分）
01. “用高级语言书写的源程序都必须通过编译, 产生目标代码程序后才能投入运行.”这种说法(  )
A、错误                           B、正确
% q) w: d8 H; m/ G02. 编译程序生成的目标程序一定是机器语言的程序。（    ）
7 L, ~9 Y  U0 j: eA、错误                           B、正确
2 {. @' @; ~7 q1 S2 X  s& Q03. 文法的两种运算系指: 推导和连接。（    ）       
A、错误                           B、正确
04. 文法是用于定义语言的，它可用如下四元组描述:
/ G& Z6 z& g  b. O/ A3 GG(Z)=( VN , VT , Z , p ),其中：Z称为文法的结束符号。（    ）
A、错误                           B、正确
05. 有限自动机可用来描述上下文无关语言语言。（    ）
) J, d: P6 J+ D- tA、错误                           B、正确
06. 正规文法是特指文法产生式仅具有如下形式：⑴ A -> aB ⑵ A -> a ⑶ A -> e。（    ）
5 m6 I; [1 `' [) z! ?2 j( qA、错误                           B、正确
07.  TOKEN 是词法分析中单词的一种机内数据结构表示,其结构是{类，值}。（    ）
A、错误                           B、正确
' W) O$ c% |% J" H" d3 E6 i08. 语法分析的任务，是对给定的符号串，判定其是否是某文法的句子。（    ）
$ s* V2 ~' A" x! d- fA、错误                           B、正确
5 _) {" g* d* D+ `09.语法分析方法分两类: (1)  自顶向下分析;  (2)  自底向上分析。（    ）
: ?5 S, M7 A& D8 XA、错误                           B、正确
: v: @9 {+ X, u) ?: u10. 过程的一次执行所需要的信息用一块连续的存储区域来管理，这块存储区叫做符号表。（    ）
A、错误                           B、正确

8 I% U+ q; V2 r* _三、（15分）回答下列问题:  
（1）写出表达式 a*(b-c/d+e) 的逆波兰式:
（2）写出条件语句 if (x>0) x=a+b/10 的四元式序列:
- I2 R0 H! B  Q) k（3）设有算术表达式文法如下:
1 W' Z) v4 I: J          E -->  T | E + T | E – T  
          T -->  F | T * F | T /  F
% b6 X: t. j, @4 a* J( [7 \: U% a7 L          F -->  i | ( E )    其中: i : 变量或常量；
  e1 [# }# r- x! U试构造四元式翻译文法并指出其中各翻译子程序的功能:

% k0 A0 M* D' M. E9 p* L" X
8 a- C* U+ g* {4 m
# ^: _* p! U& m) W& z$ d
% Y$ z  a) s7 c$ O

5 c4 q' P1 S+ R" n# ^8 y' R
8 S& D" A! x, e" O2 Z4 G% o6 v
. t! G6 C" N6 `

- [7 I( Y: Q6 A2 r9 k

8 }  d/ O7 t! F" t9 ]
' a  y/ Z$ C4 ?" u, ?

四、（15分）试已知符号串集合为：  A= { a bn c ,d │ n≥0   }  
（1）构造相应的有限自动机：
. E6 R: a! J1 O  j$ Y: \6 r5 U5 |（2）构造相应的文法:    G(S):  
（3）已知有限自动机 FA (右图) ：

) K" g+ _, X. O  _) s% O                             FA:                                

( J( S0 P, M0 E6 t# B( E     写出 FA 所表示的符号串集合(语言)：  

( G$ u1 x) g* u
& [, T9 z" W7 M

1 m) z# \4 @; s( z1 j9 q



$ o5 {1 r. r2 U: t9 m, O1 P6 R" d4 G

7 V  W" G* S* P4 z7 u


& Z6 O6 b9 w8 u+ T$ u- b" E  I
) g5 \+ n8 V4 [' X- X# ~1 U五、（10分）设有文法 G(S):
& `: `4 P% M  e" ~8 U3 pS -> a B d | b A B
                   A -> a A b | b
# f3 ?" r& k( h, ]0 P$ M                   B -> c | B c
8 C9 ^4 Y" [+ k( J3 ~  }# n- W3 N! p$ E（1） 证明 baAbcc 是一个句型，画出此句型的语法树, 指出此句型的短语、简单短语和句柄;
1 v0 n0 E1 x7 j* {/ _* {/ L（2） 把文法中的左递规产生式变换成非左递规产生式。
! l  n5 \3 l& o