编译原理试题及答案(期末复习版)

资源描述

《编译原理试题及答案(期末复习版)》由会员分享，可在线阅读，更多相关《编译原理试题及答案(期末复习版)（29页珍藏版）》请在金锄头文库上搜索。

1、历年试题及答案历年试题及答案一（每项选择 2 分，共 20 分）选择题 1将编译程序分成若干个“遍”是为了_b_。 a.提高程序的执行效率 b.使程序的结构更加清晰 c.利用有限的机器内存并提高机器的执行效率 d.利用有限的机器内存但降低了机器的执行效率 2构造编译程序应掌握_d_。 a.源程序b.目标语言 c.编译方法d.以上三项都是 3变量应当 c。 a.持有左值b.持有右值 c.既持有左值又持有右值d.既不持有左值也不持有右值 4编译程序绝大多数时间花在_d_上。 a.出错处理b.词法分析 c.目标代码生成d.管理表格 5词法分析器的输出结果是_c_。 a.单词的种别编码b.单词在符

2、号表中的位置 c.单词的种别编码和自身值d.单词自身值 6正规式 MI 和 M2 等价是指_c_。 a. MI 和 M2 的状态数相等b.Ml 和 M2 的有向弧条数相等。 C.M1 和 M2 所识别的语言集相等d. Ml 和 M2 状态数和有向弧条数相等 7中间代码生成时所依据的是c。 a语法规则b词法规则c语义规则d等价变换规则 8后缀式 ab+cd+/可用表达式_b_来表示。 a a+b/c+db (a+b)/(c+d)c a+b/(c+d)d a+b+c/d 9程序所需的数据空间在程序运行前就可确定，称为_c_管理技术。 a.动态存储b.栈式存储c.静态存储d.堆式存储 10.堆式动态

4、 SLR（1）文法，若是构造相应分析表，并对输入串 ab#给出分析过程。 6 构造算符文法 GH的算符优先关系（含）。 GH：HH;M|M Md|aHb 7已构造出文法 G（S）（1）SBB （2）BaB （3）Bb 1）。给出 DFA 图 2）.给出 LR 分析表 3）假定输入串为 abaab，请给出 LR 分析过程（即状态，符号，输入串的变化过程）。 8 将下面的语句翻译成四元式序列： while ACBA (1)A-aAd (2)A- aAb (3)A- (2)构造识别活前缀的DFA FOLLOW(A)=d,b,# 对于状态 I0：FOLLOW(A)a= 对于状态 I1：FOL

5、LOW(A)a= 因为，在 DFA 中无冲突的现象，所以该文法是 SLR(1)文法。 (3)SLR(1)分析表状态ACTIONGOTO aBd#A 0S2r3r3r31 1acc 2S2r3r3r33 3S5S4 4r1r1r1 5r2r2r2 (4)串 ab#的分析过程步骤状态栈符号栈当前字符剩余字符串动作 10#ab#移进 202#ab#归约 A- 3023#aAb#移进 40235#aAb#归约 A- aAb 501#A#接受 6【解答】由 Md 和 Ma得：FIRSTVT(M)=d,a ；由 H-H;得：FIRSTVT(H)=；由 HM 得：FIRSTVT(M) cFIRST

6、VT(H)，即 FIRSTVT(H)=;,d,a 由 Md 和 Mb 得：LASTVT(M)=d,b；由 H-，；m 得：LASTVT(H)=；；由 HM 得：LASTVT（M）cLASTVT(H），即 LASTVT(H)=;,d,b 对文法开始符 H,有#H#存在，即有=，#,也即；， #d. #, b#。对形如 Pab，或 PaQb，有 a=b，由 Ma|b 得：a=b；对形如 PaR，而 bFIRSTVT(R)，有 ab。由 H；M 得：；FIRSTVT(M)，即：：d，：a 由 MaH得：aFIRSTVT(H)，即：a；，a;，即：；，d；，b；由

7、MHb 得：LASTVT(H)b，即：；b，db，bb 由此得到算符优先关系表，见表 3.5。 7【解答】（1）LR 分析表如下：（2）分析表状态ACTIONGOTO ab#SB 0s3s412 1acc 2S3S45 3s3s46 4r3r3 5R1R1r1 6R2R2R2 (3) 句子 abaab 的分析过程表:句子 abaab 的分析过程步骤状态符号栈输入串所得产生式 0#0#abaad# 1#03#abaad# 2#034#abaab#Bb 3#036#aBaab#BaB 4#02#Baab# 5#023#Baab# 6#0233#Baab# 7#02334#Baab# 8

8、#02336#BaaB# 9#0236#BaBad# 10#025#BBad# 11#01#Sd# 12#d# 13识别成功 8【解答】该语句的四元式序列如下（其中 E1、E2 和 E3 分别对应：ACBD, A=1 和 AD 并且关系运算符优先级高）： 100 (j,A,C,102) 101(j,_,_,113）/*E1 为 F*/ 102 (j2，4-3 (3)求出流图中的循环: 回边 5-2 对应的循环：2、5、3、4；回边 4-3 对应的循环：3、4 编译原理模拟试题一一、是非题（请在括号内，正确的划，错误的划）（每个 2 分，共 20 分） 1计算机高级语言翻译成低级语言只

9、有解释一种方式。() 2在编译中进行语法检查的目的是为了发现程序中所有错误。() 3甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。 ( ) 4正则文法其产生式为 A-a ， A-Bb,A,BVN ， a 、 bVT 。 () 5每个文法都能改写为 LL(1) 文法。 () 6递归下降法允许任一非终极符是直接左递归的。 () 7算符优先关系表不一定存在对应的优先函数。 () 8自底而上语法分析方法的主要问题是候选式的选择。 () 9LR 法是自顶向下语法分析方法。 () 10简单优先文法允许任意两个产生式具有相同右部。 () 二、选择题(请在前括号内选择最

10、确切的一项作为答案划一个勾，多划按错论)(每个 4 分，共 40 分) 1 一个编译程序中，不仅包含词法分析，_，中间代码生成，代码优化，目标代码生成等五个部分。 A( ) 语法分析B( )文法分析C( )语言分析D( )解释分析 2 词法分析器用于识别_。 A( ) 字符串 B( )语句 C( )单词D( )标识符 3 语法分析器则可以发现源程序中的_。 A( ) 语义错误B( ) 语法和语义错误 C( ) 错误并校正D( ) 语法错误 4 下面关于解释程序的描述正确的是_。 (1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于 COBOL 和 FORTRAN 语言

11、 (3) 解释程序是为打开编译程序技术的僵局而开发的 A( ) (1)(2)B( ) (1)C( ) (1)(2)(3)D( ) (2)(3) 5 解释程序处理语言时 , 大多数采用的是_方法。 A( ) 源程序命令被逐个直接解释执行 B( ) 先将源程序转化为中间代码 , 再解释执行 C( ) 先将源程序解释转化为目标程序 , 再执行 D( ) 以上方法都可以 6 编译过程中 , 语法分析器的任务就是_。 (1) 分析单词是怎样构成的(2)分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的(4) 分析程序的结构 A( ) (2)(3) B( ) (2)(3)(4)C(

12、) (1)(2)(3) D( ) (1)(2)(3)(4) 7 编译程序是一种_。 A. ( ) 汇编程序 B( ) 翻译程序 C( ) 解释程序D( ) 目标程序 8 文法 G 所描述的语言是_的集合。 A. ( ) 文法 G 的字母表 V 中所有符号组成的符号串 B( ) 文法 G 的字母表 V 的闭包 V* 中的所有符号串 C( ) 由文法的开始符号推出的所有终极符串 D. ( ) 由文法的开始符号推出的所有符号串 9 文法分为四种类型，即 0 型、1 型、2 型、3 型。其中 3 型文法是_。 A. ( ) 短语文法 B( ) 正则文法 C( ) 上下文有关文法D( ) 上下文无关文

13、法 10 一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 _。 A( ) 句子B( ) 句型 C( ) 单词D( ) 产生式三、填空题(每空 1 分，共 10 分) 1 编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析,中间代码生成,代码优化等几个基本阶段,同时还会伴有_表格处理_和 _出错处理_。 2若源程序是用高级语言编写的,_目标程序_是机器语言程序或汇编程序, 则其翻译程序称为 _编译程序_ 。 3编译方式与解释方式的根本区别在于_是否生成目标代码_。 4对编译程序而言,输入数据是_源程序_, 输出结果是_目标

14、程序_。 5产生式是用于定义_语法成分_的一种书写规则。 6语法分析最常用的两类方法是_自上而下_和_自下而上_分析法。四、简答题（20 分） 1. 什么是句子？什么是语言 ? 答：(1)设 G 是一个给定的文法，S 是文法的开始符号，如果 S x(其中 xVT*),则称 x 是文法的一个句子。 (2)设 GS是给定文法，则由文法 G 所定义的语言 L(G)可描述为：L(G)xS x,xVT* 。 2. 写一文法，使其语言是偶正整数的集合,要求： (1)允许 0 打头； (2) 不允许 0 打头。解：(1)GS=(S,P,D,N,0,1,2,9,P,S) P: S-PD|D P-NP

15、|N D-0|2|4|6|8 N-0|1|2|3|4|5|6|7|8|9 (2)GS=(S,P,R,D,N,Q ,0,1,2,9,P,S) P: S-PD|P0|D P-NR|N R-QR|Q D-2|4|6|8 N-1|2|3|4|5|6|7|8|9 Q-0|1|2|3|4|5|6|7|8|9 3. 已知文法 GE 为： ET|E+T|E-T TF|T*F|T/F F （E）|i 该文法的开始符号（识别符号）是什么？请给出该文法的终结符号集合 VT 和非终结符号集合 VN 。找出句型 T+T*F+i 的所有短语、简单短语和句柄。解：该文法的开始符号（识别符号）是E。该文法的终结符号

16、集合 VT=+、-、*、/、（、）、i。非终结符号集合 VN=E、T、F。句型 T+T*F+I 的短语为i、T*F、第一个 T、T+T*F+i; 简单短语为 i、T*F、第一个 T;句柄为第一个 T。 4. 构造正规式相应的 NFA:1(0|1)*101 解1(0|1)*101对应的NFA为 5. 写出表达式(ab*c)/(ab)d 的逆波兰表示和三元式序列。逆波兰表示：abc*ab/d 三元式序列： (*，b，c) (，a，) (， a，b) (/，) (，d) 五.计算题（10 分）构造下述文法 GS 的自动机： S-A0A-A0|S1|0 该自动机是确定的吗？若不确定，则对它确定化。解：由于该文法的产生式 S-A0，A-A0|S1 中没有字符集 VT 的输入，所以不是确定的自动机。要将其他确定化，必须先用代入法得到它对应的正规

展开阅读全文