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

同学情

东 北 大 学 继 续 教 育 学 院
2 Y! J. g. E; @$ L     编 译 方 法      试 卷（作业考核 线上2）  A  卷（共   5   页）         
总分        题号        一        二        三        四        五        六        七        八        九        十
  R7 Y. v8 {  c6 X0 x6 }8 R        得分                                                                               
一、更多资料下载：谋学网（www.mouxue.com）（在备选资料中选出一个正确资料，每题3分，共30分）
; S1 R$ {8 p1 t$ r6 S$ D01. 程序设计语言一般分为(   )和(   )两大类, 其中低级语言通常又称为（   ）
2 a1 M. [4 V* j2 s3 B) p. m/ AA. 高级语言,低级语言,通用程序语言
" F. _( b4 z6 {, y8 B8 mB. 专用程序语言,高级语言,低级语言
1 p/ _  ], y7 q- v. RC. 专用程序语言,低级语言,面向机器的语言
3 h8 g; c1 A' _D. 高级语言,低级语言,面向机器的语言
  L# r* Q/ Y7 I# G  n( a  J) ], O02． 如果编译程序生成的目标是机器代码程序, 则源程序的执行分成两大阶段:（   ）和（   ）
# ]& ?2 P/ l5 K0 qA. 编辑阶段, 运行阶段
B. 编译阶段, 连接阶段
' L8 E; L) ]. J  PC. 编译阶段, 运行阶段
- ~9 t. X4 N7 zD. 编辑阶段, 连接阶段
03．已知文法G(E) :   
                         E -> T|E+T|E-T
           T -> F|T*F|T/F
           F -> i|(E)
该文法的开始符号是: (   ), 终结符集合VT是(   ),非终结符集合VN是(   ),句型T+T*F+i的短语有(   )
3 C" e% v- N2 F. C3 `A.   E;   {+,-,*,/,(,)};   {E,T,F};   T+T*F+i, T+T*F, T,T*F,i
0 e8 [0 t) i5 ^5 AB.   T;   {+,-,*,/,i,(,)};   {E,T,F};   T+T*F+i, T+T*F, T,T*F,i
8 k' t+ b- i1 C3 r; DC.   E;   {+,-,*,/,i,(,)};   {E,T,F};   T+T*F+i, T+T*F, T,T*F,i
, l1 i* u7 e' c1 q3 JD.   T;   {+,-,*,/,i,(,)};   {E,T,F};   T+T*F+i, T+T*F, T,T*F
+ e3 ~# N3 O8 F% @- _04. 文法G所描述的语言是(  )的集合  
A. 文法G的字符表∑中所有符号组成的符号串
4 C. @6 l% G7 I& }( FB. 文法G的字符表∑的闭包∑*中的所有符号串
C. 由文法的开始符号推出的所有符号串
D. 由文法的开始符号推出的所有终结符号串
9 ?$ B2 x5 b( T! j5 ~$ n05. 有限状态自动机可定义如下五元组：FA=(Q ,∑,Q0 , F ,δ),其中：(   )
- E# E, O1 }4 Z! [/ H0 b$ ]A. Q - 状态集合 ,∑ - 字母表,Q0  - 开始状态集合 ,F - 结束状态集合,δ -状态变换函数 ;
B. Q - 状态集合 ,∑ - 字母表,Q0  - 开始状态集合 ,F - 结束状态集合 ,δ - 产生式 ;
C. Q - 状态集合 ,∑ - 字母表,Q0  - 开始状态集合 ,F - 结束状态 ,δ -状态变换函数 ;
06. 词法分析的单词识别中，区分关键字和标识符的方法，通常是把拼得的字符串首先查(   ) , 若(   )则视为(   ) , 否则为(   )
* _* V" H8 P# J# Z" CA. 关键字表, 查到, 关键字, 标识符
0 k9 _$ ]  q/ j) a. BB. 关键字表, 查不到, 关键字, 标识符
C. 标识符表, 查到, 关键字, 标识符
) a: \( V% I; u; T  O& s: QD. 关键字表, 查到, 标识符, 关键字
& j: v; d2 O/ X* Y# w2 Q* e/ f. c07. 程序设计语言单词通常可分如下四类(   )
A. 关键字, 标识符, 常数, 界符
7 F/ I( G8 k/ N* e) cB. 关键字, 变量, 常数, 界符
C. 整型 , 字符型,  俘点型,  布尔型
+ ]$ I, \' _$ O$ z8 x08. 编译过程中, 语法分析器的任务是(  )
(1)分析单词是怎样构成的
(2)分析单词串是如何构成语句和说明的
(3)分析语句和说明是如何构成程序的
1 D2 M2 z0 a" A5 x' S(4)分析程序的结构
A. (2)和(3)     
B. (4)     
C. (2),(3),(4)     
1 H4 o) A9 d' N$ K. ^: m- l4 m6 ^D. (1),(2),(3),(4)
09. 设有文法 G(S):   
S -->  a A c | a A S |  b
; Y) T3 O/ x6 Z, h) T' [  zA -->  d S A | c
指出下述符号串中，那些是该文法的句子？
abcdb,   acc,   acabc,  adbcb,  acbac;
A. abcdb   
B. acabc,  adbcb   
C. acc,   acabc,  acbac   
: _$ r; ], E0 M. E' v/ [D. acc,  adbcb
10. 编译程序在其工作过程中使用最多的数据结构是(  ), 它记录着源程序中的各种信息. 在这些表中, 尤其以(  )最为重要, 它的生存期最长, 使用也最频繁。
# _8 g/ Y4 X& |2 J2 `  a& u- B& _A. 线性表 ,  符号表           B. 表 ,  链表   
8 `  `/ K$ h. AC. 线性表 , 链表              D. 表 , 符号表
# W* j* l) I) N: x9 G7 D
# C, w" u& V4 F$ e$ X) Q二、资料来源：谋学网（www.mouxue.com）（每题3分，10道题，30分）
" M) ?) @+ j$ m6 I. ^. V2 z* E01. “用高级语言书写的源程序都必须通过编译, 产生目标代码程序后才能投入运行.”这种说法(  )
" y* p% F. k" W6 _- P  h* wA、错误                           B、正确
02. 编译程序生成的目标程序一定是机器语言的程序。（    ）
A、错误                           B、正确
03. 文法的两种运算系指: 推导和连接。（    ）       
A、错误                           B、正确
04. 文法是用于定义语言的，它可用如下四元组描述:
8 w4 {9 V5 f1 p9 E: zG(Z)=( VN , VT , Z , p ),其中：Z称为文法的结束符号。（    ）
A、错误                           B、正确
6 l) k- s; _" s* \" r/ R05. 有限自动机可用来描述上下文无关语言语言。（    ）
A、错误                           B、正确
2 W- _! g& M  c) |; @06. 正规文法是特指文法产生式仅具有如下形式：⑴ A -> aB ⑵ A -> a ⑶ A -> e。（    ）
A、错误                           B、正确
07.  TOKEN 是词法分析中单词的一种机内数据结构表示,其结构是{类，值}。（    ）
4 l" F7 J1 H3 \$ \& u% U; zA、错误                           B、正确
& Z+ h3 |, L" O8 S) f. Y08. 语法分析的任务，是对给定的符号串，判定其是否是某文法的句子。（    ）
) _8 w" W! D# y" u0 b1 X" T8 gA、错误                           B、正确
09.语法分析方法分两类: (1)  自顶向下分析;  (2)  自底向上分析。（    ）
A、错误                           B、正确
( u& o# p$ H6 I- A! T" T10. 过程的一次执行所需要的信息用一块连续的存储区域来管理，这块存储区叫做符号表。（    ）
& t5 x- J5 R9 z3 u. VA、错误                           B、正确

三、（15分）回答下列问题:  
（1）写出表达式 a*(b-c/d+e) 的逆波兰式:
（2）写出条件语句 if (x>0) x=a+b/10 的四元式序列:
9 J+ v+ c3 O3 [6 i6 p1 p: Y% s, @8 q（3）设有算术表达式文法如下:
5 i) q+ R' U/ p2 o. B8 N/ F          E -->  T | E + T | E – T  
          T -->  F | T * F | T /  F
          F -->  i | ( E )    其中: i : 变量或常量；
试构造四元式翻译文法并指出其中各翻译子程序的功能:
) A5 s/ i. C* x% s! ~( g1 T
* \* n% y, {, f0 B+ M" n% j4 h
2 `9 e* z8 T/ V, ~! w3 V% k$ k
; \  a9 R8 N; T1 A, X

0 U# O. Q3 G2 m. E
% p9 t7 n: t6 Q, I

* D1 h: Q2 z- d! p# [( j# C


! O( Y' _0 L- }6 d, x
: e9 R8 P2 ~. F' K, s4 ~' Q9 L
, F* p9 j: Z& s* ]6 z+ z  h5 F

) q7 z$ V" @' N  J四、（15分）试已知符号串集合为：  A= { a bn c ,d │ n≥0   }  
（1）构造相应的有限自动机：
) i' \+ y8 R3 z0 B（2）构造相应的文法:    G(S):  
（3）已知有限自动机 FA (右图) ：

                             FA:                                
7 p2 D; u' R) {0 a% W. R9 O0 ?
     写出 FA 所表示的符号串集合(语言)：  



  }$ _2 [* a6 L
; ~; G6 A: f: d5 Q: t# w3 ~8 F0 V

, `: v# f% e) b- @% [& |9 Z



" N% W4 |; N5 v4 o$ d
3 l7 l; v# \+ c6 v- }
0 W- C; x4 V- V" I- r
7 }; T7 z2 `: }' N& M0 U  Z$ p
五、（10分）设有文法 G(S):
0 \" L! Q* \2 |S -> a B d | b A B
                   A -> a A b | b
                   B -> c | B c
（1） 证明 baAbcc 是一个句型，画出此句型的语法树, 指出此句型的短语、简单短语和句柄;
（2） 把文法中的左递规产生式变换成非左递规产生式。


% F- M/ u" n) H