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

同学情

东 北 大 学 继 续 教 育 学 院
     编 译 方 法      试 卷（作业考核 线上2）  A  卷（共   5   页）         
* M& N* H$ d2 b  {' ?- A总分        题号        一        二        三        四        五        六        七        八        九        十
' g5 n( o! ]# t' [) Q5 M! S        得分                                                                               
: Z% x; g9 ^3 U( D0 t4 T一、更多资料下载：谋学网（www.mouxue.com）（在备选资料中选出一个正确资料，每题3分，共30分）
01. 程序设计语言一般分为(   )和(   )两大类, 其中低级语言通常又称为（   ）
+ b: u: z" A& e: g. AA. 高级语言,低级语言,通用程序语言
B. 专用程序语言,高级语言,低级语言
& e0 P( W3 x2 cC. 专用程序语言,低级语言,面向机器的语言
4 j* c, |  ~. YD. 高级语言,低级语言,面向机器的语言
02． 如果编译程序生成的目标是机器代码程序, 则源程序的执行分成两大阶段:（   ）和（   ）
A. 编辑阶段, 运行阶段
" K. |4 L8 _7 J" \; aB. 编译阶段, 连接阶段
3 h3 v9 U8 J8 e7 XC. 编译阶段, 运行阶段
D. 编辑阶段, 连接阶段
( @0 B# H6 D* Q7 F2 K3 N6 N03．已知文法G(E) :   
4 a. T" i% G. }, u                          E -> T|E+T|E-T
1 Y. G" f# u3 F' D) n' }# o           T -> F|T*F|T/F
           F -> i|(E)
该文法的开始符号是: (   ), 终结符集合VT是(   ),非终结符集合VN是(   ),句型T+T*F+i的短语有(   )
A.   E;   {+,-,*,/,(,)};   {E,T,F};   T+T*F+i, T+T*F, T,T*F,i
: R0 ?; [, l! ~  L3 s. B6 \B.   T;   {+,-,*,/,i,(,)};   {E,T,F};   T+T*F+i, T+T*F, T,T*F,i
; w# `1 B8 y+ F/ \, rC.   E;   {+,-,*,/,i,(,)};   {E,T,F};   T+T*F+i, T+T*F, T,T*F,i
0 r! m, g' i+ E8 l) d& P+ z% A" DD.   T;   {+,-,*,/,i,(,)};   {E,T,F};   T+T*F+i, T+T*F, T,T*F
% b1 W1 o9 s) _" U  E1 p/ u0 u0 w04. 文法G所描述的语言是(  )的集合  
+ u5 o+ y/ }) xA. 文法G的字符表∑中所有符号组成的符号串
B. 文法G的字符表∑的闭包∑*中的所有符号串
C. 由文法的开始符号推出的所有符号串
$ H* e  c, q- u1 C: ~D. 由文法的开始符号推出的所有终结符号串
05. 有限状态自动机可定义如下五元组：FA=(Q ,∑,Q0 , F ,δ),其中：(   )
A. Q - 状态集合 ,∑ - 字母表,Q0  - 开始状态集合 ,F - 结束状态集合,δ -状态变换函数 ;
B. Q - 状态集合 ,∑ - 字母表,Q0  - 开始状态集合 ,F - 结束状态集合 ,δ - 产生式 ;
: c, P0 B/ L1 U" @' XC. Q - 状态集合 ,∑ - 字母表,Q0  - 开始状态集合 ,F - 结束状态 ,δ -状态变换函数 ;
5 V) M$ W4 R* @9 l9 z8 l+ L7 n06. 词法分析的单词识别中，区分关键字和标识符的方法，通常是把拼得的字符串首先查(   ) , 若(   )则视为(   ) , 否则为(   )
A. 关键字表, 查到, 关键字, 标识符
B. 关键字表, 查不到, 关键字, 标识符
3 m! V5 C: n9 K% X1 \: {C. 标识符表, 查到, 关键字, 标识符
" a4 _* B! X5 I2 u8 `& LD. 关键字表, 查到, 标识符, 关键字
07. 程序设计语言单词通常可分如下四类(   )
A. 关键字, 标识符, 常数, 界符
B. 关键字, 变量, 常数, 界符
8 I: o% i; V2 P% ^, FC. 整型 , 字符型,  俘点型,  布尔型
08. 编译过程中, 语法分析器的任务是(  )
7 ]3 K% Z2 h. {  a& B4 N5 R(1)分析单词是怎样构成的
(2)分析单词串是如何构成语句和说明的
(3)分析语句和说明是如何构成程序的
(4)分析程序的结构
% c5 l0 d: j& M) YA. (2)和(3)     
9 x2 A7 m4 f5 q3 t7 ^' @0 Q! c! R/ p  mB. (4)     
% J1 a- k. Y, l0 |8 _, t  c) vC. (2),(3),(4)     
& ~4 U  e6 \( H  z+ SD. (1),(2),(3),(4)
5 Q8 ]. A$ R7 x09. 设有文法 G(S):   
0 x' y$ M9 ^  O; ^S -->  a A c | a A S |  b
A -->  d S A | c
3 v% B' }; i* U指出下述符号串中，那些是该文法的句子？
abcdb,   acc,   acabc,  adbcb,  acbac;
A. abcdb   
B. acabc,  adbcb   
C. acc,   acabc,  acbac   
$ o  |9 [' N; G# mD. acc,  adbcb
10. 编译程序在其工作过程中使用最多的数据结构是(  ), 它记录着源程序中的各种信息. 在这些表中, 尤其以(  )最为重要, 它的生存期最长, 使用也最频繁。
A. 线性表 ,  符号表           B. 表 ,  链表   
; J2 C' H/ c' [( UC. 线性表 , 链表              D. 表 , 符号表

* F& I! U( l5 C3 Q2 `二、资料来源：谋学网（www.mouxue.com）（每题3分，10道题，30分）
01. “用高级语言书写的源程序都必须通过编译, 产生目标代码程序后才能投入运行.”这种说法(  )
A、错误                           B、正确
02. 编译程序生成的目标程序一定是机器语言的程序。（    ）
A、错误                           B、正确
  J8 i# m9 G5 W: F03. 文法的两种运算系指: 推导和连接。（    ）       
A、错误                           B、正确
04. 文法是用于定义语言的，它可用如下四元组描述:
G(Z)=( VN , VT , Z , p ),其中：Z称为文法的结束符号。（    ）
0 {/ v9 f2 }% c1 v( [/ G* OA、错误                           B、正确
05. 有限自动机可用来描述上下文无关语言语言。（    ）
1 A% K# a9 b1 H. O8 B; y( P: e( gA、错误                           B、正确
. D, z# R6 R% h, c- X# K! A' ?06. 正规文法是特指文法产生式仅具有如下形式：⑴ A -> aB ⑵ A -> a ⑶ A -> e。（    ）
2 _" l  z) P6 E( ~+ I' f- F9 w) jA、错误                           B、正确
: y1 \6 {% Z8 n" |07.  TOKEN 是词法分析中单词的一种机内数据结构表示,其结构是{类，值}。（    ）
  H8 H- C0 [8 @! oA、错误                           B、正确
3 n6 }& s/ d4 t08. 语法分析的任务，是对给定的符号串，判定其是否是某文法的句子。（    ）
A、错误                           B、正确
* m2 s& [' h: z, C7 J09.语法分析方法分两类: (1)  自顶向下分析;  (2)  自底向上分析。（    ）
A、错误                           B、正确
3 F" V" Y. X1 P6 W5 i6 v, e10. 过程的一次执行所需要的信息用一块连续的存储区域来管理，这块存储区叫做符号表。（    ）
A、错误                           B、正确

三、（15分）回答下列问题:  
6 r8 U" x: x9 M; |- l（1）写出表达式 a*(b-c/d+e) 的逆波兰式:
* h+ v5 N9 g% i4 f5 U# G9 R7 X（2）写出条件语句 if (x>0) x=a+b/10 的四元式序列:
（3）设有算术表达式文法如下:
          E -->  T | E + T | E – T  
          T -->  F | T * F | T /  F
6 H# R; m+ X+ X$ ~6 B5 M          F -->  i | ( E )    其中: i : 变量或常量；
  ~6 I& _6 C$ N+ S* Q9 |试构造四元式翻译文法并指出其中各翻译子程序的功能:

6 ?# y& O1 R  [, [4 E
; v* Z' {+ B/ z4 p" f
* t+ d; P; ]( C0 P0 S, x/ r: j6 b


) u" l$ L. ?, S5 u( T6 J: u6 {
5 {- i/ J  F8 q; J
5 b* }" H- l9 f6 \6 M' F% F% |

4 L% e5 R6 N& x$ _) X" a9 T
& u3 C+ n/ Q4 e5 N
8 l3 z  `6 \, H9 l

& g$ c- o3 R2 N* {- t
/ ?' U5 a4 ?1 {( O) E  `- B四、（15分）试已知符号串集合为：  A= { a bn c ,d │ n≥0   }  
* ]- J: X$ M$ n（1）构造相应的有限自动机：
（2）构造相应的文法:    G(S):  
（3）已知有限自动机 FA (右图) ：

  J- I2 q8 F: T. u  Q                             FA:                                

$ w7 z* T  H; y6 J& K6 T2 A     写出 FA 所表示的符号串集合(语言)：  




1 ~) i) t3 L" F" g

# {! @- `/ X" F* w& i0 [2 B
) W5 W3 Q) X" z+ ~9 B5 z

2 e, o& P) I2 b! z


  p, C  z1 t- r

五、（10分）设有文法 G(S):
: h& {" C+ z/ VS -> a B d | b A B
# E4 R$ j6 e) G* |                   A -> a A b | b
                   B -> c | B c
（1） 证明 baAbcc 是一个句型，画出此句型的语法树, 指出此句型的短语、简单短语和句柄;
（2） 把文法中的左递规产生式变换成非左递规产生式。
* j7 q' r# H# z6 O- W1 A

1 x! o, f6 ]& t- \- d