编译原理试题及答案（期末复习版）

历年试题及答案一（每项选择 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.单词的种别编码和自身值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/d 9程序所需的数据空间在程序运行前就可确定，称为 c_管理技术。 a.动态存储b.栈式存储c.静态存储d.堆式存储 10.堆式动态分配申请和释放存储空间遵守d原则。 a.先请先放b.先请后放c.后请先放d.任意二（每小题 10 分，共 80 分）简答题 1.画出编译程序的总体结构图，简述各部分的主要功能。 2. 已知文法 GE:EET+|T TTF* | F FF | 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 构造算符文法 GH 的算符优先关系（含）。 GH：HH;M|MMd|aHb 7已构造出文法 G（S） （1）SBB （2）BaB （3）Bb 1）。给出 DFA 图 2）.给出 LR 分析表 3）假定输入串为 abaab，请给出 LR 分析过程（即状态，符号，输入串的变化过程）。 8 将下面的语句翻译成四元式序列：while AA (1) A->aAd (2)A-> aAb (3)A-> (2)构造识别活前缀的 DFAFOLLOW(A)=d,b,# 对于状态 I0：FOLLOW(A)a= 对于状态 I1：FOLLOW(A)a= 因为，在 DFA 中无冲突的现象，所以该文法是 SLR(1)文法。 (3)SLR(1)分析表 状态ACTIONGOTOaBd#A0S2r3r3r31 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) cFIRSTVT(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#存在，即有=，#,也即；， #, b>#。 对形如 Pab，或 PaQb，有 a=b，由 Ma|b 得：a=b； 对形如 PaR，而 bFIRSTVT(R)，有 ab。 由 H；M 得：；;，即：；，d>；，b； 由 MHb 得：LASTVT(H)>b，即：；b，d>b，bb 由此得到算符优先关系表，见表 3.5。7【解答】 （1）LR 分析表如下： （2）分析表状态ACTIONGOTOab#SB 0s3s412 1acc 2S3S45 3s3s464r3r3 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#02336#BaaB# 9#0236#BaBad# 10#025#BBad# 11#01#Sd# 12#d# 13识别成功8【解答】 该语句的四元式序列如下（其中 E1、E2 和 E3 分别对应：A2，4->3 (3)求出流图中的循环: 回边 5->2 对应的循环：2、5、3、4； 回边 4->3 对应的循环：3、4 编译原理模拟试题一一、是非题（请在括号内，正确的划，错误的划×）（每个 2 分，共 20 分） 1计算机高级语言翻译成低级语言只有解释一种方式。(×) 2在编译中进行语法检查的目的是为了发现程序中所有错误。(×) 3甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系 统功能完全相同。 ( ) 4正则文法其产生式为 A->a ， A->Bb,A,BVN ， a 、 bVT 。 (×) 5每个文法都能改写为 LL(1) 文法。 () 6递归下降法允许任一非终极符是直接左递归的。 () 7算符优先关系表不一定存在对应的优先函数。 (×) 8自底而上语法分析方法的主要问题是候选式的选择。 (×) 9LR 法是自顶向下语法分析方法。 (×) 10简单优先文法允许任意两个产生式具有相同右部。 (×) 二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每 个 4 分，共 40 分) 1 一个编译程序中，不仅包含词法分析，中间代码生成，代码优化， 目标代码生成等五个部分。 A( ) 语法分析B( )文法分析C( )语言分析D( )解释分析 2 词法分析器用于识别。 A( ) 字符串 B( )语句 C( )单词D( )标识符 3 语法分析器则可以发现源程序中的。 A( ) 语义错误B( ) 语法和语义错误 C( ) 错误并校正D( ) 语法错误 4 下面关于解释程序的描述正确的是。 (1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于 COBOL 和 FORTRAN 语言 (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( ) (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( ) 上下文 无关文法 10 一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一 组终结符号，一个开始符号，以及一组。 A( ) 句子B( ) 句型 C( ) 单词D( ) 产生式 三、填空题(每空 1 分，共 10 分) 1编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析,中间代码 生成,代码优化等几个基本阶段,同时还会伴有 表格处理和出错处理 。 2若源程序是用高级语言编写的, 目标程序 是机器语言程序或汇编程序, 则其翻译程序称为编译程序。 3编译方式与解释方式的根本区别在于 是否生成目标代码。 4对编译程序而言,输入数据是源程序 , 输出结果是 目标程序。 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|N D->0|2|4|6|8N->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|NR->QR|Q D->2|4|6|8N->1|2|3|4|5|6|7|8|9 Q->0|1|2|3|4|5|6|7|8|93. 已知文法 GE 为：ET|E+T|E-T TF|T*F|T/F F （ E ） |i 该文法的开始符号（识别符号）是什么？ 请给出该文法的终结符号集合 VT 和非终结符号集合 VN 。 找出句型 T+T*F+i 的所有短语、简单短语和句柄。 解： 该文法的开始符号（识别符号）是 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 该自动机是确定的吗？若不确