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

同学情

东 北 大 学 继 续 教 育 学 院
     编 译 方 法X     试 卷（作业考核 线上2）  A  卷（共   5   页）         
总分        题号        一        二        三        四        五        六        七        八        九        十
        得分                                                                               
一、更多资料下载：谋学网（www.mouxue.com）（在备选资料中选出一个正确资料，每题3分，共30分）
01. 程序设计语言一般分为(   )和(   )两大类, 其中低级语言通常又称为（   ）
A. 高级语言,低级语言,通用程序语言
4 c/ h6 V( ?6 B3 O# ]B. 专用程序语言,高级语言,低级语言
C. 专用程序语言,低级语言,面向机器的语言
" r( G; u; D; X! BD. 高级语言,低级语言,面向机器的语言
02． 如果编译程序生成的目标是机器代码程序, 则源程序的执行分成两大阶段:（   ）和（   ）
A. 编辑阶段, 运行阶段
B. 编译阶段, 连接阶段
C. 编译阶段, 运行阶段
1 Y9 n& X/ \8 E% ~, n$ UD. 编辑阶段, 连接阶段
03．已知文法G(E) :   
5 D8 v! z" w( o                          E -> T|E+T|E-T
, C# W. L# c. Y) |           T -> F|T*F|T/F
* }; c* M, ]& a: Y* g& j6 Y           F -> i|(E)
  ?8 ^7 q2 w# u' F6 J2 Z该文法的开始符号是: (   ), 终结符集合VT是(   ),非终结符集合VN是(   ),句型T+T*F+i的短语有(   )
3 {3 T- i* k; X1 P/ e3 LA.   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
D.   T;   {+,-,*,/,i,(,)};   {E,T,F};   T+T*F+i, T+T*F, T,T*F
5 ^2 t+ f% u2 E' F04. 文法G所描述的语言是(  )的集合  
* I5 @5 A& {  s$ i9 A6 uA. 文法G的字符表∑中所有符号组成的符号串
B. 文法G的字符表∑的闭包∑*中的所有符号串
4 ]3 }6 {6 N& [9 z! I& N" @C. 由文法的开始符号推出的所有符号串
D. 由文法的开始符号推出的所有终结符号串
05. 有限状态自动机可定义如下五元组：FA=(Q ,∑,Q0 , F ,δ),其中：(   )
A. Q - 状态集合 ,∑ - 字母表,Q0  - 开始状态集合 ,F - 结束状态集合,δ -状态变换函数 ;
2 A$ J7 O0 q4 y8 {B. Q - 状态集合 ,∑ - 字母表,Q0  - 开始状态集合 ,F - 结束状态集合 ,δ - 产生式 ;
C. Q - 状态集合 ,∑ - 字母表,Q0  - 开始状态集合 ,F - 结束状态 ,δ -状态变换函数 ;
/ K# l- F. T1 z0 C  G06. 词法分析的单词识别中，区分关键字和标识符的方法，通常是把拼得的字符串首先查(   ) , 若(   )则视为(   ) , 否则为(   )
0 V' {; d6 Z2 aA. 关键字表, 查到, 关键字, 标识符
B. 关键字表, 查不到, 关键字, 标识符
- u, W/ U/ `( X7 M8 d% B) h7 XC. 标识符表, 查到, 关键字, 标识符
D. 关键字表, 查到, 标识符, 关键字
4 w/ I% W' L- A- X* P  X% t* |2 b07. 程序设计语言单词通常可分如下四类(   )
% O2 ~0 R, g0 e' Y3 P" w$ OA. 关键字, 标识符, 常数, 界符
, _. [: c9 g  S% K' l( f1 M  F" i) p0 {4 gB. 关键字, 变量, 常数, 界符
$ g2 \8 ^$ B! _& T% e) IC. 整型 , 字符型,  俘点型,  布尔型
08. 编译过程中, 语法分析器的任务是(  )
, i8 L5 [, y1 L6 a1 z& y- w(1)分析单词是怎样构成的
(2)分析单词串是如何构成语句和说明的
$ N4 w2 g. Y8 N! k+ p(3)分析语句和说明是如何构成程序的
(4)分析程序的结构
) X  h, f$ L, [" L0 R$ D+ F1 ^A. (2)和(3)     
B. (4)     
C. (2),(3),(4)     
( z& n0 u5 {+ L- K+ V' [. Z- n' KD. (1),(2),(3),(4)
/ \8 X& t! h- c. j' H2 C2 u: g0 v0 T09. 设有文法 G(S):   
S -->  a A c | a A S |  b
  N3 R% y, K9 k2 N; s* ^9 Q+ QA -->  d S A | c
指出下述符号串中，哪些是该文法的句子？
) z- @6 k9 n! V. {- z. C  L6 wabcdb,   acc,   acabc,  adbcb,  acbac;
A. abcdb   
! ~: O  P- w/ h/ i. _% E' _4 k. p: GB. acabc,  adbcb   
6 U- U8 r; ], V; V/ ZC. acc,   acabc,  acbac   
D. acc,  adbcb
10. 编译程序在其工作过程中使用最多的数据结构是(  ), 它记录着源程序中的各种信息. 在这些表中, 尤其以(  )最为重要, 它的生存期最长, 使用也最频繁。
& h9 }8 Z6 v# i. q7 c5 ]' GA. 线性表 ,  符号表           B. 表 ,  链表   
C. 线性表 , 链表              D. 表 , 符号表
6 l* H1 K& E" w' i0 h" ^: p
+ i& `3 W. M/ j. \* G二、资料来源：谋学网（www.mouxue.com）（每题3分，10道题，30分）
/ W: C* i" f1 `2 R. @% o; f3 K01. “用高级语言书写的源程序都必须通过编译, 产生目标代码程序后才能投入运行.”这种说法(  )
A、错误                           B、正确
# }% ], e8 F; y+ i6 O7 A- z8 b02. 编译程序生成的目标程序一定是机器语言的程序。（    ）
A、错误                           B、正确
' s& ^2 Q4 o  {" u  P: c; @6 F03. 文法的两种运算系指: 推导和连接。（    ）       
A、错误                           B、正确
04. 文法是用于定义语言的，它可用如下四元组描述:
- y2 Z9 r, `4 x  M& j; z& n2 OG(Z)=( VN , VT , Z , p ),其中：Z称为文法的结束符号。（    ）
A、错误                           B、正确
05. 有限自动机可用来描述上下文无关语言语言。（    ）
5 U! Q# _( [2 {+ [, Q' A/ d( CA、错误                           B、正确
06. 正规文法是特指文法产生式仅具有如下形式：⑴ A -> aB ⑵ A -> a ⑶ A -> e。（    ）
3 L3 Q" g# o  |+ |A、错误                           B、正确
- P; {" B5 S% ~# z8 s$ k07.  TOKEN 是词法分析中单词的一种机内数据结构表示,其结构是{类，值}。（    ）
0 W6 Y7 P- a! n0 {& X% j% HA、错误                           B、正确
08. 语法分析的任务，是对给定的符号串，判定其是否是某文法的句子。（    ）
% b/ Q7 @/ W* E/ QA、错误                           B、正确
09.语法分析方法分两类: (1)  自顶向下分析;  (2)  自底向上分析。（    ）
4 P9 C2 T9 n) r; TA、错误                           B、正确
10. 过程的一次执行所需要的信息用一块连续的存储区域来管理，这块存储区叫做符号表。（    ）
/ b9 a1 Q5 I8 ?7 |& GA、错误                           B、正确
3 x( g7 Q; s, `+ `5 a! N
三、（15分）回答下列问题:  
3 v) t. H! L1 I, j（1）写出表达式 a*(b-c/d+e) 的逆波兰式:
1 D6 Q0 p1 F5 d* V（2）写出条件语句 if (x>0) x=a+b/10 的四元式序列:
（3）设有算术表达式文法如下:
% g+ Y/ g- `5 A          E -->  T | E + T | E – T  
+ K; k+ f6 u1 j+ ]5 z# B' y          T -->  F | T * F | T /  F
/ _1 y" @7 }& `( h          F -->  i | ( E )    其中: i : 变量或常量；
试构造四元式翻译文法并指出其中各翻译子程序的功能:
: W* @1 j; t5 G. T2 G2 q

1 h6 v+ V- t/ M8 \
( B' F( R; A$ S& X! T5 a
; w% e" v1 t' K4 B" h




0 m$ j  l4 t6 b  h5 |5 h0 g4 d1 E



* s, ]. M. R9 P, Z
% ?% D1 P' b2 o9 P+ b( B: {# |
四、（15分）试已知符号串集合为：  A= { a bn c ,d │ n≥0   }  
4 M, T; W8 k) s4 L6 P0 p/ B（1）构造相应的有限自动机：
（2）构造相应的文法:    G(S):  
（3）已知有限自动机 FA (右图) ：
. k- C& S, `; m4 @. e
' g2 s) y( C9 S                             FA:                                

     写出 FA 所表示的符号串集合(语言)：  

& `8 l/ T, ^+ G4 [4 H
. ]" O# Y) Y& [
2 T- p( }$ \3 P; H% r8 Y  A+ n


# j9 Z7 G* R% V

; _2 x) D% O8 n% j3 ^  R/ `
8 D" t& R5 ^, {  l; y
0 L& T5 G  T/ g+ {7 F# g

( \% q4 Z4 A5 a$ X; }3 o
% ?# F" s1 v, [3 ?& B
: R( p6 C3 B; ~5 c% k五、（10分）设有文法 G(S):
' l; f1 U- y; N3 `$ GS -> a B d | b A B
                   A -> a A b | b
' h2 n! _# S; A2 Q. Y3 E  [                   B -> c | B c
（1） 证明 baAbcc 是一个句型，画出此句型的语法树, 指出此句型的短语、简单短语和句柄;
（2） 把文法中的左递规产生式变换成非左递规产生式。