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.单词在符号表中的位置c.单词的种别
2、编码和自身值 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+d b (a+b)/(c+d) c a+b/(c+d) d a+b+c/d9程序所需的数据空间在程序运行前就可确定，称为_c_管理技术。 a.动态存储 b.栈式存储 c.静态存储 d.堆式存储10.堆式动态分配申请和释放存储空间遵守_d_原则。 a.先请先放
3、 b.先请后放 c.后请先放 d.任意二（每小题10分，共80分）简答题1.画出编译程序的总体结构图，简述各部分的主要功能。2.已知文法GE: EET+|TTTF* | FFF | a 试证：FF*是文法的句型，指出该句型的短语、简单短语和句柄. 3为正规式(a|b) *a(a|b)构造一个确定的有限自动机。4设文法G(S)： S(L)|a S|a LL，S|S (1) 消除左递归和回溯； (2) 计算每个非终结符的FIRST和FOLLOW； (3) 构造预测分析表。5 已知文法 A-aAd| aAb| 判断该文法是否SLR（1）文法，若是构造相应分析表，并对输入串ab#给出分析过程。6构造算
4、符文法GH的算符优先关系（含）。 GH：HH;M|M Md|aHb7已构造出文法G（S）（1）S BB（2）B aB（3）B b1）。给出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：FOLLOW(A)a= 因为，在DFA中无冲突的现象，所以该文法是SLR(1)文法。 (3)SLR(1)分析表 状态 ACTION GO
5、TO a B d # A 0 S2 r3 r3 r3 1 1 acc 2 S2 r3 r3 r3 3 3 S5 S4 4 r1 r1 r1 5 r2 r2 r2 (4)串ab#的分析过程 步骤 状态栈 符号栈 当前字符 剩余字符串 动作 1 0 # a b# 移进 2 02 #a b # 归约A- 3 023 #aA b # 移进 4 0235 #aAb # 归约A- aAb 5 01 #A # 接受 6 【解答】 由Md和Ma得：FIRSTVT(M)=d,a； 由H-H;得：FIRSTVT(H)=； 由HM得：FIRSTVT(M) cFIRSTVT(H)，即FIRSTVT(H)=;,d,a
6、由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； 由MHb得：LASTVT(H)b，即：；b，db，bb 由此得到算符优先关系表，见表3.5。7 【解答】（1）LR分析表如下：
7、（2）分析表状态 ACTION GOTO a b # S B0 s3 s4 1 21 acc 2 S3 S4 53 s3 s4 64 r3 r3 5 R1 R1 r1 6 R2 R2 R2 (3) 句子abaab的分析过程表:句子abaab的分析过程步骤 状态 符号栈 输入串 所得产生式0 #0 # abaad# 1 #03 #a baad# 2 #034 #ab aab# Bb3 #036 #aB aab# BaB4 #02 #B aab# 5 #023 #Ba ab# 6 #0233 #Baa b# 7 #02334 #Baab # 8 #02336 #BaaB # 9 #0236 #Ba
8、B ad# 10 #025 #BB ad# 11 #01 #S d# 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计算机高级语言翻译成低级语言只有解释一种方式。()2在编译中进行语法检查的目的是为了发现程序
9、中所有错误。()3甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。 ( )4正则文法其产生式为 A-a ， A-Bb, A,BVN ， a 、 bVT 。 ()5每个文法都能改写为 LL(1) 文法。 ()6递归下降法允许任一非终极符是直接左递归的。 ()7算符优先关系表不一定存在对应的优先函数。 ()8自底而上语法分析方法的主要问题是候选式的选择。 ()9LR 法是自顶向下语法分析方法。 ()10简单优先文法允许任意两个产生式具有相同右部。 ()二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分)1 一个编译程序中，不
10、仅包含词法分析，_，中间代码生成，代码优化，目标代码生成等五个部分。aA( ) 语法分析 B( )文法分析C( )语言分析D( )解释分析2 词法分析器用于识别_。 cA( ) 字符串B( )语句C( )单词D( )标识符3 语法分析器则可以发现源程序中的_。dA( ) 语义错误 B( ) 语法和语义错误C( ) 错误并校正 D( ) 语法错误4 下面关于解释程序的描述正确的是_。b (1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于 COBOL 和 FORTRAN 语言 (3) 解释程序是为打开编译程序技术的僵局而开发的 A( ) (1)(2) B( ) (1) C(
11、) (1)(2)(3) D( ) (2)(3)5 解释程序处理语言时 , 大多数采用的是_方法。bA( ) 源程序命令被逐个直接解释执行 B( ) 先将源程序转化为中间代码 , 再解释执行C( ) 先将源程序解释转化为目标程序 , 再执行 D( ) 以上方法都可以6 编译过程中 , 语法分析器的任务就是_。b (1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构 A( ) (2)(3) B( ) (2)(3)(4)C( ) (1)(2)(3) D( ) (1)(2)(3)(4)7 编译程序是一种_。cA. ( )
12、 汇编程序 B( ) 翻译程序C( ) 解释程序 D( ) 目标程序8 文法 G 所描述的语言是_的集合。 cA. ( ) 文法 G 的字母表 V 中所有符号组成的符号串B( ) 文法 G 的字母表 V 的闭包 V* 中的所有符号串C( ) 由文法的开始符号推出的所有终极符串D. ( ) 由文法的开始符号推出的所有符号串9 文法分为四种类型，即0型、1型、2型、3型。其中3型文法是_。bA. ( ) 短语文法 B( ) 正则文法C( ) 上下文有关文法D( ) 上下文无关文法10 一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 _。dA(
13、 ) 句子 B( ) 句型C( ) 单词 D( ) 产生式三、填空题(每空1分，共10分)1编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析,中间代码生成,代码优化等几个基本阶段,同时还会伴有_表格处理_和 _出错处理_。 2若源程序是用高级语言编写的,_目标程序_是机器语言程序或汇编程序,则其翻译程序称为 _编译程序_ 。3编译方式与解释方式的根本区别在于_是否生成目标代码_。4对编译程序而言,输入数据是_源程序_, 输出结果是_目标程序_。5产生式是用于定义_语法成分_的一种书写规则。 6语法分析最常用的两类方法是_自上而下_和_自下而上_分析法。 四、简答题（20分）1. 什
14、么是句子？ 什么是语言 ? 答：(1)设G是一个给定的文法，S是文法的开始符号，如果S x(其中xVT*),则称x是文法的一个句子。 (2)设GS是给定文法，则由文法G所定义的语言L(G)可描述为： L(G)xS x,xVT* 。参考答案：(每个2分，共4分)答：(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,
15、9,P,S) P: S-PD|D P-NP|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 的所有短语、简单短语和句柄。解： 该文法
16、的开始符号（识别符号）是E。 该文法的终结符号集合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-A0 A-A0|S1|0 该自动机是确定的吗？若不确定，则对它确定化。解：由于该文法的产生式S-A0，A-A0|S1中没有字符集VT的输入，所以不是确定的自动机。 要将其他确定化，必须先用代入法得到它对应的正规式。把S?A0代入产生式A?S1有：A=A0|A01|0=A(0|01)|0=0(0|01)
