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

同学情

东 北 大 学 继 续 教 育 学 院
* u. `$ f0 f1 z( u) x6 M3 @     编 译 方 法X     试 卷（作业考核 线上2）  A  卷（共   5   页）         
总分        题号        一        二        三        四        五        六        七        八        九        十
8 Z7 N% u% n8 c& l- E        得分                                                                               
2 m3 i$ K1 ^' d, {% b3 U一、更多资料下载：谋学网（www.mouxue.com）（在备选资料中选出一个正确资料，每题3分，共30分）
8 K: y# B- u% A6 z5 V* N, t; |01. 程序设计语言一般分为(   )和(   )两大类, 其中低级语言通常又称为（   ）
5 V" P3 i0 J3 ?( j8 KA. 高级语言,低级语言,通用程序语言
" Q9 F* }. `' I9 P& MB. 专用程序语言,高级语言,低级语言
- |/ ]6 X2 Z4 I- D3 tC. 专用程序语言,低级语言,面向机器的语言
D. 高级语言,低级语言,面向机器的语言
$ q1 {; a& C" Z5 M/ h# R02． 如果编译程序生成的目标是机器代码程序, 则源程序的执行分成两大阶段:（   ）和（   ）
% H: g$ N' J$ \1 F0 F( h# eA. 编辑阶段, 运行阶段
B. 编译阶段, 连接阶段
C. 编译阶段, 运行阶段
; ]: [' r7 q7 a, J5 ED. 编辑阶段, 连接阶段
03．已知文法G(E) :   
                         E -> T|E+T|E-T
7 K$ R5 d3 `4 S* `: I           T -> F|T*F|T/F
* M9 V+ s" d' j2 O           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
2 d4 f5 V: N; d% }( i7 w1 EB.   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
" X; P: z3 F2 v( g) m4 RD.   T;   {+,-,*,/,i,(,)};   {E,T,F};   T+T*F+i, T+T*F, T,T*F
) Y  R5 Z5 g/ F# O04. 文法G所描述的语言是(  )的集合  
A. 文法G的字符表∑中所有符号组成的符号串
8 Z# }% b) K' k/ hB. 文法G的字符表∑的闭包∑*中的所有符号串
: V9 c4 u7 ^0 `( }3 S2 PC. 由文法的开始符号推出的所有符号串
7 g0 R# L2 F: u6 U4 g! x$ lD. 由文法的开始符号推出的所有终结符号串
05. 有限状态自动机可定义如下五元组：FA=(Q ,∑,Q0 , F ,δ),其中：(   )
. T. N, F, E, }" c# ^A. Q - 状态集合 ,∑ - 字母表,Q0  - 开始状态集合 ,F - 结束状态集合,δ -状态变换函数 ;
1 c# ]9 v) i( C+ }. a0 M; g' v4 wB. Q - 状态集合 ,∑ - 字母表,Q0  - 开始状态集合 ,F - 结束状态集合 ,δ - 产生式 ;
C. Q - 状态集合 ,∑ - 字母表,Q0  - 开始状态集合 ,F - 结束状态 ,δ -状态变换函数 ;
06. 词法分析的单词识别中，区分关键字和标识符的方法，通常是把拼得的字符串首先查(   ) , 若(   )则视为(   ) , 否则为(   )
1 Q% b" f" z/ D! Q& YA. 关键字表, 查到, 关键字, 标识符
B. 关键字表, 查不到, 关键字, 标识符
C. 标识符表, 查到, 关键字, 标识符
. \+ d" _0 @; x# G5 o5 F! k2 ID. 关键字表, 查到, 标识符, 关键字
07. 程序设计语言单词通常可分如下四类(   )
* N. F, `( n4 [3 W* A. gA. 关键字, 标识符, 常数, 界符
B. 关键字, 变量, 常数, 界符
( H$ z0 C* F1 F7 u( DC. 整型 , 字符型,  俘点型,  布尔型
" F6 O) h+ h& Z+ A. x6 Y8 r. {. k' t08. 编译过程中, 语法分析器的任务是(  )
(1)分析单词是怎样构成的
+ }& i( E, D: n7 d; _4 F(2)分析单词串是如何构成语句和说明的
(3)分析语句和说明是如何构成程序的
) {3 ?4 ~7 T4 W( P2 b$ z# ^, x; K(4)分析程序的结构
A. (2)和(3)     
( _4 c8 f: `, ^2 aB. (4)     
* p7 k* W! a3 i+ qC. (2),(3),(4)     
$ V% Q5 g/ B6 VD. (1),(2),(3),(4)
09. 设有文法 G(S):   
7 S5 ^+ h6 v. N2 y, e) DS -->  a A c | a A S |  b
" b) z, j/ b+ V* k) QA -->  d S A | c
( v/ D7 l& ^! t( T' F' J指出下述符号串中，哪些是该文法的句子？
* r. M! W5 l# f# Y6 |7 J: p" B% Fabcdb,   acc,   acabc,  adbcb,  acbac;
0 \; `; d4 V5 i7 s: M' m: {7 AA. abcdb   
9 I3 d- r% L8 C: W) s; EB. acabc,  adbcb   
C. acc,   acabc,  acbac   
D. acc,  adbcb
+ D( ]2 c9 X+ l' o. [3 |* p10. 编译程序在其工作过程中使用最多的数据结构是(  ), 它记录着源程序中的各种信息. 在这些表中, 尤其以(  )最为重要, 它的生存期最长, 使用也最频繁。
A. 线性表 ,  符号表           B. 表 ,  链表   
C. 线性表 , 链表              D. 表 , 符号表

二、资料来源：谋学网（www.mouxue.com）（每题3分，10道题，30分）
# N) m) O, R6 e& N5 y01. “用高级语言书写的源程序都必须通过编译, 产生目标代码程序后才能投入运行.”这种说法(  )
A、错误                           B、正确
( V" Y, v% |+ K0 [# o; P02. 编译程序生成的目标程序一定是机器语言的程序。（    ）
A、错误                           B、正确
03. 文法的两种运算系指: 推导和连接。（    ）       
A、错误                           B、正确
. q" c/ G- C' q% `$ u' T2 F: N04. 文法是用于定义语言的，它可用如下四元组描述:
G(Z)=( VN , VT , Z , p ),其中：Z称为文法的结束符号。（    ）
A、错误                           B、正确
* q9 Q: I, ]$ |/ |) Q05. 有限自动机可用来描述上下文无关语言语言。（    ）
7 ^( W! V0 V/ lA、错误                           B、正确
  B+ U. v4 M% {; M; `* W2 U06. 正规文法是特指文法产生式仅具有如下形式：⑴ A -> aB ⑵ A -> a ⑶ A -> e。（    ）
) ^* e9 E( E- b) v2 ~% q' lA、错误                           B、正确
07.  TOKEN 是词法分析中单词的一种机内数据结构表示,其结构是{类，值}。（    ）
. ?8 `, m! ~: A" T' c+ ^  V  v  ~A、错误                           B、正确
08. 语法分析的任务，是对给定的符号串，判定其是否是某文法的句子。（    ）
A、错误                           B、正确
09.语法分析方法分两类: (1)  自顶向下分析;  (2)  自底向上分析。（    ）
A、错误                           B、正确
10. 过程的一次执行所需要的信息用一块连续的存储区域来管理，这块存储区叫做符号表。（    ）
A、错误                           B、正确
. W1 r  \( F3 A1 Q) \; a
三、（15分）回答下列问题:  
3 s9 n9 ~, g5 @& K5 s（1）写出表达式 a*(b-c/d+e) 的逆波兰式:
1 I2 _2 w- I% J（2）写出条件语句 if (x>0) x=a+b/10 的四元式序列:
（3）设有算术表达式文法如下:
          E -->  T | E + T | E – T  
- F; c4 h- E- m- U7 G/ N' c          T -->  F | T * F | T /  F
6 c. Q. c- A: L; w  X! d: S          F -->  i | ( E )    其中: i : 变量或常量；
试构造四元式翻译文法并指出其中各翻译子程序的功能:
: H/ x; Y6 f" F- y1 j

& \7 e  |8 U% C% g! g% y+ h1 k3 ^
, J* V& N3 w2 E: \; P# q' p( ~) k


1 H7 b# J4 [! y
, d0 X3 ?) L& ^4 u; W
  c% M( v1 V4 J% C. z) V6 p" S



$ w2 G2 O% c3 P4 C6 C


四、（15分）试已知符号串集合为：  A= { a bn c ,d │ n≥0   }  
+ L/ P2 r7 W. _9 o/ o* n+ ?0 J（1）构造相应的有限自动机：
（2）构造相应的文法:    G(S):  
（3）已知有限自动机 FA (右图) ：

                             FA:                                

: \& g; F5 R. }     写出 FA 所表示的符号串集合(语言)：  
) H) T& m- Q" {! _; {1 z



: ~3 S" G) Z! |, R

* u0 Q1 M1 O: G, |/ V
2 W2 }& V/ `, Z, T' W
" V' ~# w. M2 w4 d




" o$ U- Z5 n0 m! X
& i# V5 X1 t$ Y( K. E/ ~五、（10分）设有文法 G(S):
) u- X+ m3 |% |1 F! a1 {9 US -> a B d | b A B
                   A -> a A b | b
$ m2 D) z. t( c. q1 L0 i                   B -> c | B c
. o: R/ n1 A/ s" a  x（1） 证明 baAbcc 是一个句型，画出此句型的语法树, 指出此句型的短语、简单短语和句柄;
（2） 把文法中的左递规产生式变换成非左递规产生式。
3 ]5 \6 s5 F( w' n* ^" L

/ O  l8 J+ G6 L" L1 P/ x