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

奥鹏在线作业

东 北 大 学 继 续 教 育 学 院
     编 译 方 法      试 卷（作业考核 线上2）  A  卷（共   5   页）         
' n! C' F# c8 d9 s# o总分        题号        一        二        三        四        五        六        七        八        九        十
        得分                                                                               
一、更多资料下载：谋学网（www.mouxue.com）（在备选资料中选出一个正确资料，每题3分，共30分）
' z- k8 Y$ W4 [% U$ j; X01. 程序设计语言一般分为(   )和(   )两大类, 其中低级语言通常又称为（   ）
A. 高级语言,低级语言,通用程序语言
, M7 K9 _2 C5 N& X( nB. 专用程序语言,高级语言,低级语言
0 {+ L0 l! d( A5 |C. 专用程序语言,低级语言,面向机器的语言
D. 高级语言,低级语言,面向机器的语言
02． 如果编译程序生成的目标是机器代码程序, 则源程序的执行分成两大阶段:（   ）和（   ）
A. 编辑阶段, 运行阶段
B. 编译阶段, 连接阶段
C. 编译阶段, 运行阶段
D. 编辑阶段, 连接阶段
03．已知文法G(E) :   
                         E -> T|E+T|E-T
           T -> F|T*F|T/F
7 e4 j) I' _5 e& z; D5 i           F -> i|(E)
( M4 |! W: Z8 \% B2 x) K该文法的开始符号是: (   ), 终结符集合VT是(   ),非终结符集合VN是(   ),句型T+T*F+i的短语有(   )
A.   E;   {+,-,*,/,(,)};   {E,T,F};   T+T*F+i, T+T*F, T,T*F,i
8 L) d! @) y* N* YB.   T;   {+,-,*,/,i,(,)};   {E,T,F};   T+T*F+i, T+T*F, T,T*F,i
- Q/ q' n+ n- J1 K+ pC.   E;   {+,-,*,/,i,(,)};   {E,T,F};   T+T*F+i, T+T*F, T,T*F,i
+ m* H9 n1 r  ~" w7 D5 A+ Q4 W/ L5 C/ S5 uD.   T;   {+,-,*,/,i,(,)};   {E,T,F};   T+T*F+i, T+T*F, T,T*F
04. 文法G所描述的语言是(  )的集合  
A. 文法G的字符表∑中所有符号组成的符号串
B. 文法G的字符表∑的闭包∑*中的所有符号串
C. 由文法的开始符号推出的所有符号串
; F2 ]1 Q+ s7 w; r) t* y) m9 L  MD. 由文法的开始符号推出的所有终结符号串
05. 有限状态自动机可定义如下五元组：FA=(Q ,∑,Q0 , F ,δ),其中：(   )
A. Q - 状态集合 ,∑ - 字母表,Q0  - 开始状态集合 ,F - 结束状态集合,δ -状态变换函数 ;
B. Q - 状态集合 ,∑ - 字母表,Q0  - 开始状态集合 ,F - 结束状态集合 ,δ - 产生式 ;
  p/ r$ }, s. U( ^; y0 xC. Q - 状态集合 ,∑ - 字母表,Q0  - 开始状态集合 ,F - 结束状态 ,δ -状态变换函数 ;
; z% O9 i1 x& {, p* q06. 词法分析的单词识别中，区分关键字和标识符的方法，通常是把拼得的字符串首先查(   ) , 若(   )则视为(   ) , 否则为(   )
1 ]6 ?8 d& B/ ~# QA. 关键字表, 查到, 关键字, 标识符
, s: I7 p5 [+ B; u. NB. 关键字表, 查不到, 关键字, 标识符
C. 标识符表, 查到, 关键字, 标识符
D. 关键字表, 查到, 标识符, 关键字
& [- f7 Z  Y* i  o! W# Y07. 程序设计语言单词通常可分如下四类(   )
A. 关键字, 标识符, 常数, 界符
B. 关键字, 变量, 常数, 界符
C. 整型 , 字符型,  俘点型,  布尔型
- d* K4 O" k8 w/ O- t: p6 R5 O08. 编译过程中, 语法分析器的任务是(  )
(1)分析单词是怎样构成的
(2)分析单词串是如何构成语句和说明的
(3)分析语句和说明是如何构成程序的
3 z5 H8 e8 A- ~  b, {: [8 {(4)分析程序的结构
A. (2)和(3)     
5 L# p( \& f. b2 YB. (4)     
C. (2),(3),(4)     
D. (1),(2),(3),(4)
% k: L) }& k5 W$ s/ O; y09. 设有文法 G(S):   
S -->  a A c | a A S |  b
% i" I, o; e0 o( Q5 jA -->  d S A | c
+ Z% Y( M6 [$ G/ w" a指出下述符号串中，哪些是该文法的句子？
( v3 I: [! _9 \$ b; z& T0 Gabcdb,   acc,   acabc,  adbcb,  acbac;
A. abcdb   
B. acabc,  adbcb   
C. acc,   acabc,  acbac   
& A7 G9 s: S& h5 ^4 e$ W0 D" SD. acc,  adbcb
& D9 V1 G4 I7 T4 {, u10. 编译程序在其工作过程中使用最多的数据结构是(  ), 它记录着源程序中的各种信息. 在这些表中, 尤其以(  )最为重要, 它的生存期最长, 使用也最频繁。
9 c1 e7 N5 N* G+ T5 rA. 线性表 ,  符号表           B. 表 ,  链表   
$ ^8 p. U2 X+ A' sC. 线性表 , 链表              D. 表 , 符号表

二、资料来源：谋学网（www.mouxue.com）（每题3分，10道题，30分）
+ ]: f9 N9 }4 x6 e' u, K. T5 y01. “用高级语言书写的源程序都必须通过编译, 产生目标代码程序后才能投入运行.”这种说法(  )
A、错误                           B、正确
02. 编译程序生成的目标程序一定是机器语言的程序。（    ）
. b, I" a4 q& q* L. b7 {A、错误                           B、正确
03. 文法的两种运算系指: 推导和连接。（    ）       
, A' g* N+ V3 `8 {; k& zA、错误                           B、正确
04. 文法是用于定义语言的，它可用如下四元组描述:
G(Z)=( VN , VT , Z , p ),其中：Z称为文法的结束符号。（    ）
3 p- G3 x9 {4 c( tA、错误                           B、正确
$ e5 W9 K7 u- J, t: d2 {3 Z- i5 Z05. 有限自动机可用来描述上下文无关语言语言。（    ）
9 C1 z- z3 W" ]5 v4 VA、错误                           B、正确
06. 正规文法是特指文法产生式仅具有如下形式：⑴ A -> aB ⑵ A -> a ⑶ A -> e。（    ）
A、错误                           B、正确
07.  TOKEN 是词法分析中单词的一种机内数据结构表示,其结构是{类，值}。（    ）
9 t/ O( E8 p3 `0 h/ VA、错误                           B、正确
08. 语法分析的任务，是对给定的符号串，判定其是否是某文法的句子。（    ）
A、错误                           B、正确
09.语法分析方法分两类: (1)  自顶向下分析;  (2)  自底向上分析。（    ）
7 Q9 _* v# |3 }0 qA、错误                           B、正确
10. 过程的一次执行所需要的信息用一块连续的存储区域来管理，这块存储区叫做符号表。（    ）
A、错误                           B、正确
. ~, L, z+ W6 D2 O- r6 h
4 P# a3 |) a" K* y* F三、（15分）回答下列问题:  
; b( Q5 u1 n5 N, a: m; f（1）写出表达式 a*(b-c/d+e) 的逆波兰式:
（2）写出条件语句 if (x>0) x=a+b/10 的四元式序列:
5 @( f; u, K4 G$ z8 b  h（3）设有算术表达式文法如下:
          E -->  T | E + T | E – T  
6 ?- {" q4 ~- L4 u          T -->  F | T * F | T /  F
          F -->  i | ( E )    其中: i : 变量或常量；
试构造四元式翻译文法并指出其中各翻译子程序的功能:
. X' p/ F- h: F% v
/ v2 y4 |1 ^, T/ ]  m
5 T7 p7 j% L4 ?# s, ?; b8 d4 x

% z* L. D5 y8 T" J. \1 |



2 }7 H6 B1 `2 x+ E5 O
% |1 A/ M1 C  d, _8 h, r" y
( w, K/ U& _/ I9 b" ?% y- P
( x+ B3 \& S& s) V# K4 j
/ t% X' v% D( c( O% K# o" ~7 S3 b0 z
/ |" ~; X" \! N- X4 _

& b  _  O! c7 m) K四、（15分）试已知符号串集合为：  A= { a bn c ,d │ n≥0   }  
（1）构造相应的有限自动机：
（2）构造相应的文法:    G(S):  
（3）已知有限自动机 FA (右图) ：
) a3 W8 I5 J+ \( t4 q- t1 |
                             FA:                                
0 j- \1 X  c6 p% s* R8 s
     写出 FA 所表示的符号串集合(语言)：  
7 }0 V) P3 e6 D) d



& r% Q7 D, ]3 `( a! ?


+ ~1 }* V" f; v& I# ]* a





/ ?8 g/ ]* H- `- M, z$ m, L5 j8 ]
, Q* s+ A2 ~$ |五、（10分）设有文法 G(S):
S -> a B d | b A B
5 B2 u/ R) l0 u  b7 L) y/ q                   A -> a A b | b
& c, d$ O: S4 d$ I9 d6 N                   B -> c | B c
（1） 证明 baAbcc 是一个句型，画出此句型的语法树, 指出此句型的短语、简单短语和句柄;
. L. k- x- v8 ^8 `$ ~$ j% _（2） 把文法中的左递规产生式变换成非左递规产生式。