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

同学情

东 北 大 学 继 续 教 育 学 院
     编 译 方 法      试 卷（作业考核 线上2）  A  卷（共   5   页）         
# D: G  t0 G% L7 o$ N5 h总分        题号        一        二        三        四        五        六        七        八        九        十
; h' S! j( J+ x" r# Y3 u* t        得分                                                                               
$ |9 k0 K# q/ u0 Q6 {3 M) y一、更多资料下载：谋学网（www.mouxue.com）（在备选资料中选出一个正确资料，每题3分，共30分）
01. 程序设计语言一般分为(   )和(   )两大类, 其中低级语言通常又称为（   ）
A. 高级语言,低级语言,通用程序语言
8 y  h0 }5 W- v% p- k2 {9 yB. 专用程序语言,高级语言,低级语言
C. 专用程序语言,低级语言,面向机器的语言
D. 高级语言,低级语言,面向机器的语言
0 t& ^, M% [, J: ?8 ^02． 如果编译程序生成的目标是机器代码程序, 则源程序的执行分成两大阶段:（   ）和（   ）
! k5 z7 F* P2 ~0 WA. 编辑阶段, 运行阶段
B. 编译阶段, 连接阶段
) M3 T6 x( F, n4 AC. 编译阶段, 运行阶段
0 ~3 |+ W5 d5 |5 `' t/ aD. 编辑阶段, 连接阶段
03．已知文法G(E) :   
3 {" T1 b; L5 d% O, E1 T. L                          E -> T|E+T|E-T
           T -> F|T*F|T/F
           F -> i|(E)
: P% B3 b( q4 F' y+ [8 V0 ]该文法的开始符号是: (   ), 终结符集合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
- t: G* d6 Z6 V- g6 UC.   E;   {+,-,*,/,i,(,)};   {E,T,F};   T+T*F+i, T+T*F, T,T*F,i
9 a  a! `8 ?' C9 n. _D.   T;   {+,-,*,/,i,(,)};   {E,T,F};   T+T*F+i, T+T*F, T,T*F
) p, u3 `& v/ l4 F4 i8 \0 @$ n04. 文法G所描述的语言是(  )的集合  
A. 文法G的字符表∑中所有符号组成的符号串
B. 文法G的字符表∑的闭包∑*中的所有符号串
C. 由文法的开始符号推出的所有符号串
- I5 g* i0 }! eD. 由文法的开始符号推出的所有终结符号串
9 u' {9 X5 T  j/ H" X05. 有限状态自动机可定义如下五元组：FA=(Q ,∑,Q0 , F ,δ),其中：(   )
; t' L" u( \, F) u$ yA. Q - 状态集合 ,∑ - 字母表,Q0  - 开始状态集合 ,F - 结束状态集合,δ -状态变换函数 ;
B. Q - 状态集合 ,∑ - 字母表,Q0  - 开始状态集合 ,F - 结束状态集合 ,δ - 产生式 ;
C. Q - 状态集合 ,∑ - 字母表,Q0  - 开始状态集合 ,F - 结束状态 ,δ -状态变换函数 ;
06. 词法分析的单词识别中，区分关键字和标识符的方法，通常是把拼得的字符串首先查(   ) , 若(   )则视为(   ) , 否则为(   )
A. 关键字表, 查到, 关键字, 标识符
B. 关键字表, 查不到, 关键字, 标识符
6 R# c( P8 y/ B8 HC. 标识符表, 查到, 关键字, 标识符
) `0 i; Q' x* n5 L1 I% J: w7 pD. 关键字表, 查到, 标识符, 关键字
07. 程序设计语言单词通常可分如下四类(   )
* P$ z4 q9 p" vA. 关键字, 标识符, 常数, 界符
3 r5 y* o9 A5 s' |3 R( ZB. 关键字, 变量, 常数, 界符
+ }% I5 f4 z) u. A9 wC. 整型 , 字符型,  俘点型,  布尔型
08. 编译过程中, 语法分析器的任务是(  )
(1)分析单词是怎样构成的
( h5 j& U6 d& a) t$ d2 v(2)分析单词串是如何构成语句和说明的
* s! b' N" N& V5 Z% O, [% p3 S(3)分析语句和说明是如何构成程序的
4 W* T' i1 U/ A' s$ f) d(4)分析程序的结构
A. (2)和(3)     
B. (4)     
( F  w- e8 }4 I& _" d% X1 ]+ wC. (2),(3),(4)     
7 X& o; @( N4 N9 v6 C4 Q6 ~& UD. (1),(2),(3),(4)
2 O; C: U2 B* R" Q' w09. 设有文法 G(S):   
S -->  a A c | a A S |  b
A -->  d S A | c
指出下述符号串中，那些是该文法的句子？
abcdb,   acc,   acabc,  adbcb,  acbac;
A. abcdb   
B. acabc,  adbcb   
C. acc,   acabc,  acbac   
6 {4 b9 Y0 m) }+ z, o, N5 h8 ^) s/ zD. acc,  adbcb
10. 编译程序在其工作过程中使用最多的数据结构是(  ), 它记录着源程序中的各种信息. 在这些表中, 尤其以(  )最为重要, 它的生存期最长, 使用也最频繁。
A. 线性表 ,  符号表           B. 表 ,  链表   
& B0 j( ]: h* Z5 x$ \  QC. 线性表 , 链表              D. 表 , 符号表
: B, t) g- h- O/ |1 y) J
二、资料来源：谋学网（www.mouxue.com）（每题3分，10道题，30分）
' t' `: K% T. S0 N& ^" x  \# h  d01. “用高级语言书写的源程序都必须通过编译, 产生目标代码程序后才能投入运行.”这种说法(  )
1 V+ h' t) C. U! C5 xA、错误                           B、正确
: @8 L6 G/ s+ [% G5 p02. 编译程序生成的目标程序一定是机器语言的程序。（    ）
, m" z' y5 q6 D% F" sA、错误                           B、正确
4 r, r0 Z9 _) u- P. \5 p9 q" p03. 文法的两种运算系指: 推导和连接。（    ）       
7 W. \, Z4 s- s4 E. rA、错误                           B、正确
04. 文法是用于定义语言的，它可用如下四元组描述:
G(Z)=( VN , VT , Z , p ),其中：Z称为文法的结束符号。（    ）
A、错误                           B、正确
8 J- c2 I! z. }" k3 B5 k05. 有限自动机可用来描述上下文无关语言语言。（    ）
! L1 I+ z' r  n. g' L6 P9 nA、错误                           B、正确
! F. y7 S5 U# I% s% }06. 正规文法是特指文法产生式仅具有如下形式：⑴ A -> aB ⑵ A -> a ⑶ A -> e。（    ）
/ G1 l# x# T0 P1 MA、错误                           B、正确
5 O4 D/ G# a$ l6 b! }$ C/ ?, B07.  TOKEN 是词法分析中单词的一种机内数据结构表示,其结构是{类，值}。（    ）
A、错误                           B、正确
08. 语法分析的任务，是对给定的符号串，判定其是否是某文法的句子。（    ）
A、错误                           B、正确
09.语法分析方法分两类: (1)  自顶向下分析;  (2)  自底向上分析。（    ）
) I; B5 U9 z; V  o- ^7 e) l6 e3 t; M+ TA、错误                           B、正确
10. 过程的一次执行所需要的信息用一块连续的存储区域来管理，这块存储区叫做符号表。（    ）
A、错误                           B、正确
4 P+ i- V7 w& y; t1 U
& Z( K2 G( _0 j- f* c: E: j三、（15分）回答下列问题:  
（1）写出表达式 a*(b-c/d+e) 的逆波兰式:
  L* R4 T. K) K) A; s! q% w# P（2）写出条件语句 if (x>0) x=a+b/10 的四元式序列:
4 l* H2 B+ T- A  A' W0 c（3）设有算术表达式文法如下:
          E -->  T | E + T | E – T  
          T -->  F | T * F | T /  F
$ @8 r. S) W" [- D; g+ B7 ^2 V' M          F -->  i | ( E )    其中: i : 变量或常量；
# l5 S7 J+ V! R, c, t试构造四元式翻译文法并指出其中各翻译子程序的功能:




, D+ v" k3 W3 I4 X




0 h5 W2 X( x1 i2 l  }" L) M
( b3 ~$ y6 M! J" H



6 m! q) a+ d0 f- u7 p
: Z7 M+ i+ s8 S5 ?! c' U/ R四、（15分）试已知符号串集合为：  A= { a bn c ,d │ n≥0   }  
（1）构造相应的有限自动机：
（2）构造相应的文法:    G(S):  
7 d# G- a, _- P& u" Q, F% r（3）已知有限自动机 FA (右图) ：

& t+ U- S: u8 x8 E' K                             FA:                                

     写出 FA 所表示的符号串集合(语言)：  
2 y& C# v. ~  T5 ?3 T
. z2 f% C* I6 a" T" N8 K% _6 d6 Y. B




( k5 K7 Y1 d  _& W3 j


, o( T5 Z( o* w% h0 x8 t8 ~- l



: k- L2 ?9 l+ l5 T- e9 f3 f
五、（10分）设有文法 G(S):
S -> a B d | b A B
                   A -> a A b | b
. A* ]3 [* V' T1 w                   B -> c | B c
（1） 证明 baAbcc 是一个句型，画出此句型的语法树, 指出此句型的短语、简单短语和句柄;
2 V1 S3 f0 N. V+ f, W- h: y$ t（2） 把文法中的左递规产生式变换成非左递规产生式。
8 y& h% p: r2 |: H2 m) ?: \