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

同学情

东 北 大 学 继 续 教 育 学 院
2 i8 r& H# I7 v$ a& m' R+ ~- [     编 译 方 法X     试 卷（作业考核 线上2）  A  卷（共   5   页）         
0 W7 ~% e- P' q6 z0 R6 |总分        题号        一        二        三        四        五        六        七        八        九        十
( }5 }" }1 Z4 y0 E* ~        得分                                                                               
一、更多资料下载：谋学网（www.mouxue.com）（在备选资料中选出一个正确资料，每题3分，共30分）
01. 程序设计语言一般分为(   )和(   )两大类, 其中低级语言通常又称为（   ）
% F6 @! z# I5 j: i9 }( ~% f; SA. 高级语言,低级语言,通用程序语言
B. 专用程序语言,高级语言,低级语言
C. 专用程序语言,低级语言,面向机器的语言
, O! U  e4 g" tD. 高级语言,低级语言,面向机器的语言
02． 如果编译程序生成的目标是机器代码程序, 则源程序的执行分成两大阶段:（   ）和（   ）
/ c' _5 o3 x* r9 p4 LA. 编辑阶段, 运行阶段
& z, R& g( H& {% O9 UB. 编译阶段, 连接阶段
C. 编译阶段, 运行阶段
: ]6 p, k$ M' t: m  E% iD. 编辑阶段, 连接阶段
03．已知文法G(E) :   
                         E -> T|E+T|E-T
           T -> F|T*F|T/F
6 V; n( b2 b/ R/ }/ x6 m           F -> i|(E)
9 s' d1 H# A( d; j$ y4 h该文法的开始符号是: (   ), 终结符集合VT是(   ),非终结符集合VN是(   ),句型T+T*F+i的短语有(   )
A.   E;   {+,-,*,/,(,)};   {E,T,F};   T+T*F+i, T+T*F, T,T*F,i
B.   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
, V, g! P1 [) iD.   T;   {+,-,*,/,i,(,)};   {E,T,F};   T+T*F+i, T+T*F, T,T*F
04. 文法G所描述的语言是(  )的集合  
/ |3 e7 ]0 {) e8 l* K) tA. 文法G的字符表∑中所有符号组成的符号串
; P) S' W" R, ?2 Y/ W; l6 k5 E' N* o/ lB. 文法G的字符表∑的闭包∑*中的所有符号串
/ F; `. E- X8 d, XC. 由文法的开始符号推出的所有符号串
D. 由文法的开始符号推出的所有终结符号串
05. 有限状态自动机可定义如下五元组：FA=(Q ,∑,Q0 , F ,δ),其中：(   )
A. Q - 状态集合 ,∑ - 字母表,Q0  - 开始状态集合 ,F - 结束状态集合,δ -状态变换函数 ;
B. Q - 状态集合 ,∑ - 字母表,Q0  - 开始状态集合 ,F - 结束状态集合 ,δ - 产生式 ;
: O/ E0 X7 ?' f, pC. Q - 状态集合 ,∑ - 字母表,Q0  - 开始状态集合 ,F - 结束状态 ,δ -状态变换函数 ;
# N, i4 O( b# U& k' v4 X5 |1 ^4 `) e06. 词法分析的单词识别中，区分关键字和标识符的方法，通常是把拼得的字符串首先查(   ) , 若(   )则视为(   ) , 否则为(   )
A. 关键字表, 查到, 关键字, 标识符
. ?6 X! f6 ?* }) k6 z1 t8 Q6 m, eB. 关键字表, 查不到, 关键字, 标识符
C. 标识符表, 查到, 关键字, 标识符
D. 关键字表, 查到, 标识符, 关键字
  b* O5 x  t! u% H/ N9 e07. 程序设计语言单词通常可分如下四类(   )
A. 关键字, 标识符, 常数, 界符
B. 关键字, 变量, 常数, 界符
C. 整型 , 字符型,  俘点型,  布尔型
; m! t" G8 R; L0 L+ M+ ?08. 编译过程中, 语法分析器的任务是(  )
(1)分析单词是怎样构成的
(2)分析单词串是如何构成语句和说明的
(3)分析语句和说明是如何构成程序的
- _; a& h3 k4 Q- w; U2 U2 i! @(4)分析程序的结构
% B, F; E$ w" p7 _# NA. (2)和(3)     
8 _9 {4 P2 ^& e' v" y5 {5 sB. (4)     
C. (2),(3),(4)     
D. (1),(2),(3),(4)
9 D# w0 _4 v) J" `* w09. 设有文法 G(S):   
S -->  a A c | a A S |  b
$ z( _+ x+ @* W- B, F; h) j- iA -->  d S A | c
, z3 C% x5 |5 q& E) n5 `指出下述符号串中，哪些是该文法的句子？
- p- _/ O) t; h0 labcdb,   acc,   acabc,  adbcb,  acbac;
A. abcdb   
B. acabc,  adbcb   
C. acc,   acabc,  acbac   
# i0 V9 h! l( q4 D+ MD. acc,  adbcb
10. 编译程序在其工作过程中使用最多的数据结构是(  ), 它记录着源程序中的各种信息. 在这些表中, 尤其以(  )最为重要, 它的生存期最长, 使用也最频繁。
A. 线性表 ,  符号表           B. 表 ,  链表   
. q3 Z5 V$ m  ?9 JC. 线性表 , 链表              D. 表 , 符号表
2 R: J! f4 W" A! M
二、资料来源：谋学网（www.mouxue.com）（每题3分，10道题，30分）
01. “用高级语言书写的源程序都必须通过编译, 产生目标代码程序后才能投入运行.”这种说法(  )
A、错误                           B、正确
  H0 P0 n8 o. g8 _& f8 G02. 编译程序生成的目标程序一定是机器语言的程序。（    ）
' T; E4 A+ Q" X1 f6 lA、错误                           B、正确
+ _1 D; Q: z, ?. [0 Z% N8 I03. 文法的两种运算系指: 推导和连接。（    ）       
, [% L( e3 J1 Q9 B2 g$ SA、错误                           B、正确
04. 文法是用于定义语言的，它可用如下四元组描述:
G(Z)=( VN , VT , Z , p ),其中：Z称为文法的结束符号。（    ）
- N& C- y+ N! y/ F# U  J& ]( X  cA、错误                           B、正确
3 I7 U6 B4 B1 @+ T- o" [05. 有限自动机可用来描述上下文无关语言语言。（    ）
A、错误                           B、正确
06. 正规文法是特指文法产生式仅具有如下形式：⑴ A -> aB ⑵ A -> a ⑶ A -> e。（    ）
A、错误                           B、正确
07.  TOKEN 是词法分析中单词的一种机内数据结构表示,其结构是{类，值}。（    ）
A、错误                           B、正确
08. 语法分析的任务，是对给定的符号串，判定其是否是某文法的句子。（    ）
; G8 I0 V8 i) G% ^. l) \: oA、错误                           B、正确
09.语法分析方法分两类: (1)  自顶向下分析;  (2)  自底向上分析。（    ）
3 @5 R3 V, R" X) }, vA、错误                           B、正确
10. 过程的一次执行所需要的信息用一块连续的存储区域来管理，这块存储区叫做符号表。（    ）
A、错误                           B、正确
: W) X# k) v7 _, A6 B' |
* o( Q  R# N! U3 G4 W三、（15分）回答下列问题:  
, G. L3 T- h' ]+ X6 P（1）写出表达式 a*(b-c/d+e) 的逆波兰式:
" r3 g2 V9 U& x% W% A# F（2）写出条件语句 if (x>0) x=a+b/10 的四元式序列:
1 I& i9 w! o0 x  b" H: r9 e# b) L（3）设有算术表达式文法如下:
4 R6 \' f6 p6 s          E -->  T | E + T | E – T  
# [" j7 T+ F3 q6 r5 k          T -->  F | T * F | T /  F
          F -->  i | ( E )    其中: i : 变量或常量；
试构造四元式翻译文法并指出其中各翻译子程序的功能:
, ]0 ~; o( ^) l; J7 W- D+ h1 e


( Y+ U5 I1 _; `7 K, M" `5 k
, ^; Y/ D& V0 G4 G& m/ o, X" c


  m9 ^; Q3 ?" L8 |0 d




' ~% O' _& h. ~0 n
; E, k  l; q$ d8 n2 @  M5 \
9 m' f# ~9 W% t' u3 }! C- K
$ t/ K) @; U- O+ W/ x+ i四、（15分）试已知符号串集合为：  A= { a bn c ,d │ n≥0   }  
（1）构造相应的有限自动机：
) ]9 y$ W& \. E- @（2）构造相应的文法:    G(S):  
* v# J2 P! e# F3 Y0 A: F5 g& H: R（3）已知有限自动机 FA (右图) ：
7 W5 _4 d5 N& p8 W0 h
2 `$ f3 v8 k* a4 E" i  o                             FA:                                
: ?% t. ?! r; c
     写出 FA 所表示的符号串集合(语言)：  
- F" q* w8 ?7 Q
: i  X, z. B8 c% l5 k




' w7 g* |) Y9 j. }

$ c% b# [2 B7 _* Q7 I4 Z3 U

- ^1 J/ ?) q4 c$ u* ?3 g


$ K, z" b6 A8 w0 a$ F
五、（10分）设有文法 G(S):
S -> a B d | b A B
                   A -> a A b | b
7 r1 R% x: F0 z5 z0 t, E5 Q                   B -> c | B c
) D9 ?8 t* ~. _) X（1） 证明 baAbcc 是一个句型，画出此句型的语法树, 指出此句型的短语、简单短语和句柄;
8 \$ i& P; P- r: r1 c（2） 把文法中的左递规产生式变换成非左递规产生式。
  b/ X/ J% T- x. M  M) V, v
. y: M8 ^: U* r+ ~# D4 X% U' k
0 S) x' [0 r/ _$ P8 Y