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

同学情

东 北 大 学 继 续 教 育 学 院
     编 译 方 法      试 卷（作业考核 线上2）  A  卷（共   5   页）         
4 H2 |6 w( g6 X) }# O! T! v总分        题号        一        二        三        四        五        六        七        八        九        十
4 N0 @9 C  h) [- S' z5 w) X        得分                                                                               
. K+ N# ]$ O! _0 V) W5 o- w一、更多资料下载：谋学网（www.mouxue.com）（在备选资料中选出一个正确资料，每题3分，共30分）
& e8 \1 ]+ c  _$ M; j1 _01. 程序设计语言一般分为(   )和(   )两大类, 其中低级语言通常又称为（   ）
8 x1 \3 B& d% P# N, C: B4 j4 c! x# [A. 高级语言,低级语言,通用程序语言
B. 专用程序语言,高级语言,低级语言
6 b. N  m2 K& N. nC. 专用程序语言,低级语言,面向机器的语言
' H( X& b4 x1 |+ a( AD. 高级语言,低级语言,面向机器的语言
02． 如果编译程序生成的目标是机器代码程序, 则源程序的执行分成两大阶段:（   ）和（   ）
A. 编辑阶段, 运行阶段
$ q  T0 K$ E* {2 ?9 |% kB. 编译阶段, 连接阶段
1 F' R; w2 j% ZC. 编译阶段, 运行阶段
D. 编辑阶段, 连接阶段
03．已知文法G(E) :   
2 E0 W. }7 T9 T2 _$ U                          E -> T|E+T|E-T
           T -> F|T*F|T/F
; `# G% ]; F- Q0 M           F -> i|(E)
' Y9 ~% i* l6 Q; D+ i: _该文法的开始符号是: (   ), 终结符集合VT是(   ),非终结符集合VN是(   ),句型T+T*F+i的短语有(   )
7 W) [: W& l6 WA.   E;   {+,-,*,/,(,)};   {E,T,F};   T+T*F+i, T+T*F, T,T*F,i
. K7 B; w5 b6 f" C8 ZB.   T;   {+,-,*,/,i,(,)};   {E,T,F};   T+T*F+i, T+T*F, T,T*F,i
C.   E;   {+,-,*,/,i,(,)};   {E,T,F};   T+T*F+i, T+T*F, T,T*F,i
: F6 `5 K* {1 X- ?! LD.   T;   {+,-,*,/,i,(,)};   {E,T,F};   T+T*F+i, T+T*F, T,T*F
04. 文法G所描述的语言是(  )的集合  
A. 文法G的字符表∑中所有符号组成的符号串
B. 文法G的字符表∑的闭包∑*中的所有符号串
! H$ u/ v$ ]4 _0 T( IC. 由文法的开始符号推出的所有符号串
% F( Y. q& Q8 \: s9 F! Z% U5 CD. 由文法的开始符号推出的所有终结符号串
5 N; e1 E  N) [$ b( h05. 有限状态自动机可定义如下五元组：FA=(Q ,∑,Q0 , F ,δ),其中：(   )
& ^5 c& _4 V2 r: FA. Q - 状态集合 ,∑ - 字母表,Q0  - 开始状态集合 ,F - 结束状态集合,δ -状态变换函数 ;
# ]4 P$ U) A. j5 d. yB. Q - 状态集合 ,∑ - 字母表,Q0  - 开始状态集合 ,F - 结束状态集合 ,δ - 产生式 ;
C. Q - 状态集合 ,∑ - 字母表,Q0  - 开始状态集合 ,F - 结束状态 ,δ -状态变换函数 ;
& T4 H) U+ t9 N2 s06. 词法分析的单词识别中，区分关键字和标识符的方法，通常是把拼得的字符串首先查(   ) , 若(   )则视为(   ) , 否则为(   )
A. 关键字表, 查到, 关键字, 标识符
7 \- P2 B0 m1 H/ k! t1 @B. 关键字表, 查不到, 关键字, 标识符
C. 标识符表, 查到, 关键字, 标识符
5 O) ?+ K4 N* W0 G8 oD. 关键字表, 查到, 标识符, 关键字
, r* }$ h, q+ k0 S& }- I6 B# C9 \* |07. 程序设计语言单词通常可分如下四类(   )
/ P2 T* c. c! a5 N6 mA. 关键字, 标识符, 常数, 界符
B. 关键字, 变量, 常数, 界符
/ ], u, ?. S! n. KC. 整型 , 字符型,  俘点型,  布尔型
08. 编译过程中, 语法分析器的任务是(  )
4 |; Y" H$ V) A% j1 k8 ?( D(1)分析单词是怎样构成的
(2)分析单词串是如何构成语句和说明的
: v: o% `7 \$ n' Y; s1 b% ](3)分析语句和说明是如何构成程序的
(4)分析程序的结构
A. (2)和(3)     
B. (4)     
  m9 s+ T9 F/ M0 bC. (2),(3),(4)     
D. (1),(2),(3),(4)
09. 设有文法 G(S):   
+ W% P9 f+ {" J$ _3 }  O: jS -->  a A c | a A S |  b
A -->  d S A | c
指出下述符号串中，那些是该文法的句子？
abcdb,   acc,   acabc,  adbcb,  acbac;
- u1 B( C* P8 _: [8 Q: ZA. abcdb   
; l5 L1 e4 P  u! j: z3 X- m$ lB. acabc,  adbcb   
C. acc,   acabc,  acbac   
% E/ t' I; H2 G/ ~) e, ND. acc,  adbcb
  t$ {) J' U. G5 L10. 编译程序在其工作过程中使用最多的数据结构是(  ), 它记录着源程序中的各种信息. 在这些表中, 尤其以(  )最为重要, 它的生存期最长, 使用也最频繁。
" h) ^/ c' V  ]3 UA. 线性表 ,  符号表           B. 表 ,  链表   
C. 线性表 , 链表              D. 表 , 符号表
  [' S# _+ I7 {
二、资料来源：谋学网（www.mouxue.com）（每题3分，10道题，30分）
01. “用高级语言书写的源程序都必须通过编译, 产生目标代码程序后才能投入运行.”这种说法(  )
A、错误                           B、正确
02. 编译程序生成的目标程序一定是机器语言的程序。（    ）
A、错误                           B、正确
- P% e/ V  t: n$ ?9 @" f03. 文法的两种运算系指: 推导和连接。（    ）       
A、错误                           B、正确
04. 文法是用于定义语言的，它可用如下四元组描述:
; z" c" X! |- g7 dG(Z)=( VN , VT , Z , p ),其中：Z称为文法的结束符号。（    ）
& J1 G2 S* a5 aA、错误                           B、正确
05. 有限自动机可用来描述上下文无关语言语言。（    ）
% `" ^" Q; D" D/ J1 L8 i4 uA、错误                           B、正确
06. 正规文法是特指文法产生式仅具有如下形式：⑴ A -> aB ⑵ A -> a ⑶ A -> e。（    ）
" H8 |# Y# K3 e. [) M0 C) sA、错误                           B、正确
07.  TOKEN 是词法分析中单词的一种机内数据结构表示,其结构是{类，值}。（    ）
7 O+ g/ {. m$ q4 D4 d  m+ R. f! zA、错误                           B、正确
08. 语法分析的任务，是对给定的符号串，判定其是否是某文法的句子。（    ）
% w/ ]0 u  t6 P& U) R, fA、错误                           B、正确
09.语法分析方法分两类: (1)  自顶向下分析;  (2)  自底向上分析。（    ）
' [' j. ^3 l1 r6 GA、错误                           B、正确
10. 过程的一次执行所需要的信息用一块连续的存储区域来管理，这块存储区叫做符号表。（    ）
/ d1 c! {3 q: C, z  zA、错误                           B、正确

2 l' [4 @7 W- g* L3 [# y& k6 m三、（15分）回答下列问题:  
（1）写出表达式 a*(b-c/d+e) 的逆波兰式:
（2）写出条件语句 if (x>0) x=a+b/10 的四元式序列:
（3）设有算术表达式文法如下:
/ N. }, X  C4 u2 h          E -->  T | E + T | E – T  
( @5 m. I, z& F8 m          T -->  F | T * F | T /  F
( A1 d% g. @! |+ X: I) d- F          F -->  i | ( E )    其中: i : 变量或常量；
/ B& z2 O6 N( ]3 K* Q" z- M试构造四元式翻译文法并指出其中各翻译子程序的功能:

2 k3 v  i! y# W


* P/ `/ E4 N+ z0 d  n
2 j3 H) y2 `5 Q. n# w6 Y


8 L& J, \7 e" q' i* F


+ E9 p* n0 C, ]2 y

0 y0 O) ^0 ]4 ?  W0 c# O

4 y, ^  j4 E9 U  s: _四、（15分）试已知符号串集合为：  A= { a bn c ,d │ n≥0   }  
1 l1 v  d8 U2 X9 f! }$ H（1）构造相应的有限自动机：
% z+ [) }/ r* Q% D（2）构造相应的文法:    G(S):  
9 A5 x. \  f6 `  ^3 Z（3）已知有限自动机 FA (右图) ：
/ }' ~* |8 ^! r8 |+ Y) x
                             FA:                                
9 m' D  N) \' x% r! }$ c
' Y+ L/ s$ j: @+ {! N     写出 FA 所表示的符号串集合(语言)：  


! i, S; S* m) p4 x+ o* q

. Y7 b" L2 y: [; g0 P
7 v( _" g/ D8 R) ?9 z; ]
# D8 M. ^( r: M- R: F/ Y







9 m  j! ^5 z( ?' t4 d五、（10分）设有文法 G(S):
S -> a B d | b A B
: H6 d+ u* L; s$ Q3 d6 N" d- t                   A -> a A b | b
                   B -> c | B c
; _' l9 B  h1 j（1） 证明 baAbcc 是一个句型，画出此句型的语法树, 指出此句型的短语、简单短语和句柄;
' D  D$ i6 E  I8 i3 i5 |1 L7 k（2） 把文法中的左递规产生式变换成非左递规产生式。
( N- d. D2 ?+ ?; P, P8 K# `  P
& l4 R6 C! S& R  o; Y. P0 b; E- G; p% X3 z
8 p2 O, \4 h3 H6 ]6 f