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

同学情

东 北 大 学 继 续 教 育 学 院
7 Z+ ^/ w" Y. m. r: Z0 o0 I     编 译 方 法X     试 卷（作业考核 线上2）  A  卷（共   5   页）         
& c( c/ A, Y+ a2 L: t: x) }5 J总分        题号        一        二        三        四        五        六        七        八        九        十
9 w7 Q$ o$ N8 f) q* L" {7 f- l        得分                                                                               
一、更多资料下载：谋学网（www.mouxue.com）（在备选资料中选出一个正确资料，每题3分，共30分）
& E1 Y  f% ]$ o" y01. 程序设计语言一般分为(   )和(   )两大类, 其中低级语言通常又称为（   ）
( E5 ~5 I( e: L/ c1 t4 iA. 高级语言,低级语言,通用程序语言
B. 专用程序语言,高级语言,低级语言
- d5 D1 h1 D6 g- @1 M9 x, x- SC. 专用程序语言,低级语言,面向机器的语言
9 E6 P8 M% h- o& z6 HD. 高级语言,低级语言,面向机器的语言
% E1 }5 @# I. `% F02． 如果编译程序生成的目标是机器代码程序, 则源程序的执行分成两大阶段:（   ）和（   ）
A. 编辑阶段, 运行阶段
+ M6 g0 z( w) U$ a4 Z7 xB. 编译阶段, 连接阶段
& l# Y1 u+ G2 wC. 编译阶段, 运行阶段
5 d4 j+ ~( w  O; R+ vD. 编辑阶段, 连接阶段
03．已知文法G(E) :   
                         E -> T|E+T|E-T
           T -> F|T*F|T/F
           F -> i|(E)
" x4 ]5 H) y( y- ^/ h2 r该文法的开始符号是: (   ), 终结符集合VT是(   ),非终结符集合VN是(   ),句型T+T*F+i的短语有(   )
% q4 A2 B0 d) QA.   E;   {+,-,*,/,(,)};   {E,T,F};   T+T*F+i, T+T*F, T,T*F,i
$ U/ }$ _2 q5 f/ d% q* L7 d# dB.   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
D.   T;   {+,-,*,/,i,(,)};   {E,T,F};   T+T*F+i, T+T*F, T,T*F
04. 文法G所描述的语言是(  )的集合  
A. 文法G的字符表∑中所有符号组成的符号串
B. 文法G的字符表∑的闭包∑*中的所有符号串
5 ]( K) \4 d5 E( a  V7 ^C. 由文法的开始符号推出的所有符号串
D. 由文法的开始符号推出的所有终结符号串
05. 有限状态自动机可定义如下五元组：FA=(Q ,∑,Q0 , F ,δ),其中：(   )
+ z4 v; A' c* e1 w6 E% k. uA. Q - 状态集合 ,∑ - 字母表,Q0  - 开始状态集合 ,F - 结束状态集合,δ -状态变换函数 ;
B. Q - 状态集合 ,∑ - 字母表,Q0  - 开始状态集合 ,F - 结束状态集合 ,δ - 产生式 ;
4 g8 D. U3 M1 a, |/ I7 k1 T' \C. Q - 状态集合 ,∑ - 字母表,Q0  - 开始状态集合 ,F - 结束状态 ,δ -状态变换函数 ;
06. 词法分析的单词识别中，区分关键字和标识符的方法，通常是把拼得的字符串首先查(   ) , 若(   )则视为(   ) , 否则为(   )
A. 关键字表, 查到, 关键字, 标识符
B. 关键字表, 查不到, 关键字, 标识符
C. 标识符表, 查到, 关键字, 标识符
D. 关键字表, 查到, 标识符, 关键字
3 u5 P  ^9 o% y* [. F07. 程序设计语言单词通常可分如下四类(   )
: x1 D6 W) Y3 p% `A. 关键字, 标识符, 常数, 界符
0 ]/ e2 ?1 K8 \* r$ q" sB. 关键字, 变量, 常数, 界符
/ c6 e; t% e1 z) z, ]( y9 XC. 整型 , 字符型,  俘点型,  布尔型
08. 编译过程中, 语法分析器的任务是(  )
(1)分析单词是怎样构成的
(2)分析单词串是如何构成语句和说明的
(3)分析语句和说明是如何构成程序的
% U/ W* r( b8 U$ m3 |(4)分析程序的结构
A. (2)和(3)     
- B8 U. _7 l! ]" fB. (4)     
. L- U; x$ x9 z3 R+ k( y$ fC. (2),(3),(4)     
D. (1),(2),(3),(4)
09. 设有文法 G(S):   
S -->  a A c | a A S |  b
+ n8 [& k1 ~: N7 P  f) d) n2 y) \A -->  d S A | c
" a) {1 d  ?6 {% r( o指出下述符号串中，哪些是该文法的句子？
( i4 w; z& v0 }4 h  q' O: \6 {+ _abcdb,   acc,   acabc,  adbcb,  acbac;
) E5 A# {% p5 z* b8 EA. abcdb   
B. acabc,  adbcb   
# \! K0 i4 m0 s4 TC. acc,   acabc,  acbac   
( A0 S/ `+ X6 YD. acc,  adbcb
10. 编译程序在其工作过程中使用最多的数据结构是(  ), 它记录着源程序中的各种信息. 在这些表中, 尤其以(  )最为重要, 它的生存期最长, 使用也最频繁。
. b  h) o* o; }A. 线性表 ,  符号表           B. 表 ,  链表   
C. 线性表 , 链表              D. 表 , 符号表

% n2 z6 p. ~& h# G  }3 K* @二、资料来源：谋学网（www.mouxue.com）（每题3分，10道题，30分）
& A: R  X) d4 Z9 q  U+ l01. “用高级语言书写的源程序都必须通过编译, 产生目标代码程序后才能投入运行.”这种说法(  )
A、错误                           B、正确
02. 编译程序生成的目标程序一定是机器语言的程序。（    ）
A、错误                           B、正确
03. 文法的两种运算系指: 推导和连接。（    ）       
- L. v7 @' b. H+ g% j+ UA、错误                           B、正确
5 ]/ q$ m* m4 K4 x3 n; ?6 u04. 文法是用于定义语言的，它可用如下四元组描述:
8 N9 m2 \: p& z& T8 wG(Z)=( VN , VT , Z , p ),其中：Z称为文法的结束符号。（    ）
A、错误                           B、正确
. M7 a  [8 c( p& r8 _05. 有限自动机可用来描述上下文无关语言语言。（    ）
A、错误                           B、正确
06. 正规文法是特指文法产生式仅具有如下形式：⑴ A -> aB ⑵ A -> a ⑶ A -> e。（    ）
0 l# e" I/ L4 jA、错误                           B、正确
; l; G# s+ B1 R2 T: A( ~+ |' i/ g& S07.  TOKEN 是词法分析中单词的一种机内数据结构表示,其结构是{类，值}。（    ）
  ?* ?  h( I; D1 F* @8 w* \9 lA、错误                           B、正确
- }0 D# q, f: j2 s9 s# K' j08. 语法分析的任务，是对给定的符号串，判定其是否是某文法的句子。（    ）
A、错误                           B、正确
. U4 X9 U, t' I3 H# v/ A3 P" r, u09.语法分析方法分两类: (1)  自顶向下分析;  (2)  自底向上分析。（    ）
; U% r, C' N. vA、错误                           B、正确
10. 过程的一次执行所需要的信息用一块连续的存储区域来管理，这块存储区叫做符号表。（    ）
A、错误                           B、正确

三、（15分）回答下列问题:  
（1）写出表达式 a*(b-c/d+e) 的逆波兰式:
3 l1 _# _$ p7 b（2）写出条件语句 if (x>0) x=a+b/10 的四元式序列:
（3）设有算术表达式文法如下:
          E -->  T | E + T | E – T  
: g! d6 q1 v" ?. f! N' ?8 |4 u          T -->  F | T * F | T /  F
          F -->  i | ( E )    其中: i : 变量或常量；
, K/ p2 B( _: p$ p试构造四元式翻译文法并指出其中各翻译子程序的功能:



$ a3 E1 z" a0 b: a& Z$ }' S
* w3 w9 j8 J+ r" ?0 p1 W

( o5 M& d) i$ W6 C" A0 N$ M

" D* i7 J7 ?0 e% K+ k



& [# l" R9 r, n


四、（15分）试已知符号串集合为：  A= { a bn c ,d │ n≥0   }  
5 j2 J% p  Q$ F; d  a) ], o7 P! ~* j3 q" ]（1）构造相应的有限自动机：
0 d7 a3 i6 l3 h& W（2）构造相应的文法:    G(S):  
（3）已知有限自动机 FA (右图) ：
# @, U5 G, c: g0 b
, }2 H7 G( v, V$ _3 }) |4 W) Z                             FA:                                
# B; Z, h& A- N" b% z
( @* h$ v2 H& k& x  j; H     写出 FA 所表示的符号串集合(语言)：  

# z+ G4 d' M( M2 ~3 p1 I4 v% P; `
# T3 @+ [7 q0 u- q

- S" ?, s$ u1 W
. ~0 x+ P5 \0 J) A3 n- u
4 p: M" p* Y  S. [

7 y% ?' s' |7 G9 U! Y, U* B6 o




1 }6 P% k+ o- R6 n  w6 D3 ~
五、（10分）设有文法 G(S):
S -> a B d | b A B
) w3 a- p* ]! u: ?3 |                   A -> a A b | b
                   B -> c | B c
（1） 证明 baAbcc 是一个句型，画出此句型的语法树, 指出此句型的短语、简单短语和句柄;
（2） 把文法中的左递规产生式变换成非左递规产生式。


7 {+ T. {" D! u1 f2 j; S