《编译原理》模拟期末试题汇总-6套-含答案(共35页).doc
《《编译原理》模拟期末试题汇总-6套-含答案(共35页).doc》由会员分享,可在线阅读,更多相关《《编译原理》模拟期末试题汇总-6套-含答案(共35页).doc(35页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、精选优质文档-倾情为你奉上编译原理模拟试题一一、是非题(请在括号内,正确的划,错误的划)(每个2分,共20分)1计算机高级语言翻译成低级语言只有解释一种方式。()2在编译中进行语法检查的目的是为了发现程序中所有错误。()3甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。 ( )4正则文法其产生式为 A-a , A-Bb, A,BVN , a 、 bVT 。 ()5每个文法都能改写为 LL(1) 文法。 ()6递归下降法允许任一非终极符是直接左递归的。 ()7算符优先关系表不一定存在对应的优先函数。 ()8自底而上语法分析方法的主要问题是候选式的选择。 ()9L
2、R 法是自顶向下语法分析方法。 ()10简单优先文法允许任意两个产生式具有相同右部。 ()二、选择题(请在前括号内选择最确切的一项作为答案划一个勾,多划按错论)(每个4分,共40分)1 一个编译程序中,不仅包含词法分析,_,中间代码生成,代码优化,目标代码生成等五个部分。A( ) 语法分析 B( )文法分析C( )语言分析D( )解释分析2 词法分析器用于识别_。 A( ) 字符串 B( )语句C( )单词 D( )标识符3 语法分析器则可以发现源程序中的_。A( ) 语义错误 B( ) 语法和语义错误C( ) 错误并校正 D( ) 语法错误4 下面关于解释程序的描述正确的是_。 (1) 解释
3、程序的特点是处理程序时不产生目标代码 (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、明是如何构成程序的 (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. ( ) 短语
5、文法 B( ) 正则文法 C( ) 上下文有关文法 D( ) 上下文无关文法10 一个上下文无关文法 G 包括四个组成部分,它们是:一组非终结符号,一组终结符号,一个开始符号,以及一组 _。A( ) 句子 B( ) 句型C( ) 单词 D( ) 产生式三、填空题(每空1分,共10分)1编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析,中间代码生成,代码优化等几个基本阶段,同时还会伴有_表格处理_和 _出错处理_。 2若源程序是用高级语言编写的,_目标程序_是机器语言程序或汇编程序,则其翻译程序称为 _编译程序_ 。3编译方式与解释方式的根本区别在于_是否生成目标代码_。4对编译程序
6、而言,输入数据是_源程序_, 输出结果是_目标程序_。5产生式是用于定义_语法成分_的一种书写规则。 6语法分析最常用的两类方法是_自上而下_和_自下而上_分析法。 四、简答题(20分)1. 什么是句子? 什么是语言 ? 答:(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所定义
7、的语言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|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
8、/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的逆波兰表示和三元式序列。逆波兰表示
9、: 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)*。 代入S-A0有该文法的正规式:0(0|01)*0,所以,改写该文法为确定的自动机为: 由于状态A有3次输入0的重复输入,所以上图只是NFA,
10、下面将它确定化: 下表由子集法将NFA转换为DFA: 由上表可知DFA为:编译原理模拟试题二一、是非题(请在括号内,正确的划,错误的划)(每个2分,共20分)1“ 用高级语言书写的源程序都必须通过编译,产生目标代码后才能投入运行 ”这种说法。( )2若一个句型中出现了某产生式的右部,则此右部一定是该句型的句柄。( )3一个句型的句柄一定是文法某产生式的右部。 ()4在程序中标识符的出现仅为使用性的。 ( )5仅考虑一个基本块,不能确定一个赋值是否真是无用的。 ( )6削减运算强度破坏了临时变量在一基本块内仅被定义一次的特性。 ( )7在中间代码优化中循环上的优化主要有不变表达式外提和削减运算强
11、度。 ( )8算符优先关系表不一定存在对应的优先函数。 ()9数组元素的地址计算与数组的存储方式有关。 ()10编译程序与具体的机器有关,与具体的语言无关。 ( )二、选择题(请在前括号内选择最确切的一项作为答案划一个勾,多划按错论)(每个4分,共40分)1 通常一个编译程序中,不仅包含词法分析,语法分析,中间代码生成,代码优化,目标代码生成等五个部分,还应包括_。A( ) 模拟执行器B( ) 解释器 C( ) 表格处理和出错处理 D( ) 符号执行器2 文法 GN= ( b , N , B , N , NbbB , BbN ),该文法所描述的语言是 A( ) L(GN)=bii0 B( )
12、L(GN)=b2ii0 C( ) L(GN)=b2i+1i0 D( ) L(GN)=b2i+1i13 一个句型中的最左_称为该句型的句柄。A( ) 短语 B( ) 简单短语 C( ) 素短语 D( ) 终结符号 4 设 G 是一个给定的文法, S 是文法的开始符号,如果 S-x( 其中 xV*), 则称 x 是文法 G 的一个_。A( ) 候选式 B( ) 句型 C( ) 单词 D( ) 产生式 5 文法 GE : ETE T TFT F Fa ( E ) 该文法句型 E F (E T) 的简单短语是下列符号串中的_。 ( E T ) E T F F (E T) A( ) 和 B( ) 和 C
13、( ) 和 D( ) 6 若一个文法是递归的,则它所产生的语言的句子_。A( ) 是无穷多个 B( ) 是有穷多个 C( ) 是可枚举的 D( ) 个数是常量 7 词法分析器用于识别_。A( ) 句子 B( ) 句型 C( ) 单词 D( ) 产生式 8 在语法分析处理中, FIRST 集合、 FOLLOW 集合、 SELECT 集合均是_。A. ( ) 非终极符集 B( ) 终极符集 C( ) 字母表 D. ( ) 状态集 9 在自底向上的语法分析方法中,分析的关键是_。 A.( ) 寻找句柄 B.( ) 寻找句型 C.( ) 消除递归 D.( ) 选择候选式 10 在 LR 分析法中,分析
14、栈中存放的状态是识别规范句型_的 DFA 状态。 A.( )句柄 B.( ) 前缀 C.( )活前缀 D.( ) LR(0) 项目 三、填空题(每空1分,共10分)1设G是一个给定的文法,S是文法的开始符号,如果S-x( 其中 xVT*), 则称 x是文法的一个_句子_。 2递归下降法不允许任一非终极符是直接_左_递归的。3自顶向下的语法分析方法的基本思想是:从文法的_开始符号_开始,根据给定的输入串并按照文法的产生式一步一步的向下进行_直接推导_,试图推导出文法的_句子_,使之与给定的输入串_匹配_。 4自底向上的语法分析方法的基本思想是:从输入串入手,利用文法的产生式一步一步地向上进行_直
15、接归约_ ,力求归约到文法的_开始符号_。 5常用的参数传递方式有_传地址_,传值和传名。 6在使用高级语言编程时,首先可通过编译程序发现源程序的全部_语法_错误和语义部分错误。四、简答题(20分)1. 已知文法 GS 为: SdAB AaA|a BBb| GS 产生的语言是什么? 答:GS产生的语言是L(GS)=danbmn1,m0。2. 简述 DFA 与 NFA 有何区别 ? 答:DFA与NFA的区别表现为两个方面:一是NFA可以若干个开始状态,而DFA仅只一个开始状态。 另一方面,DFA的映象M是从K到K,而NFA的映象M是从K到K的子集, 即映象M将产生一个状态集合(可能为空集),而不
16、是单个状态。3. 构造正规式相应的 DFA : 1(1010 * | 1(010) * 1) * 0。解:1(1010 * | 1(010) * 1) * 0对应的NFA为:4. 已知文法G(S) Sa|(T) TT,S|S 写出句子(a,a),a)的规范归约过程及每一步的句柄。解:句型归约规则句柄 (a,a),a)Saa (S,a),a)TSS (T,a),a)Saa (T,S),a)TT,S T,S (S),a) TSS (T),a) SS(T) (T) (S,a) TSS (T,a) Saa (T,S) TT,S T,S (T) S(T)(T) S5. 何谓优化?按所涉及的程序范围可分为
17、哪几级优化?1)优化:对程序进行各种等价变换,使得从变换后的程序出发,能产生更有效的目标代码。 (2) 三种级别:局部优化、循环优化、全局优化。五.计算题(10分) 对下面的文法 G : E-TE E-+E| T-FT T -T| F- PF F- *F| P-(E)|a|b| (1)计算这个文法的每个非终结符的 FIRST 集和 FOLLOW 集。 (4分) (2) 证明这个方法是 LL(1) 的。(4分) (3) 构造它的预测分析表。(2分) 解:(1)计算这个文法的每个非终结符的FIRST集和FOLLOW集。 FIRST集合有: FIRST(E)=FIRST(T)=FIRST(F)=FI
18、RST(P)=(,a,b,; FIRST(E)=+, FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,; FIRST(T)=FIRST(T)=(,a,b,; FIRST(F)=FIRST(P)=(,a,b,; FIRST(F)=FIRST(P)=*,; FIRST(P)=(,a,b,; FOLLOW集合有: FOLLOW(E)=),#; FOLLOW(E)=FOLLOW(E)=),#; FOLLOW(T)=FIRST(E)FOLLOW(E)=+,),#;/不包含 FOLLOW(T)=FOLLOW(T)=FIRST(E)FOLLOW(E)=+,),#; FOLLOW(F)=FI
19、RST(T)FOLLOW(T)=(,a,b,+,),#;/不包含 FOLLOW(F)=FOLLOW(F)=FIRST(T)FOLLOW(T)=(,a,b,+,),#; FOLLOW(P)=FIRST(F)FOLLOW(F)=*,(,a,b,+,),#;/不包含 (2)证明这个方法是LL(1)的。 各产生式的SELECT集合有: SELECT(E-TE)=FIRST(T)=(,a,b,; SELECT(E-+E)=+; SELECT(E-)=FOLLOW(E/)=),# SELECT(T-FT)=FIRST(F)=(,a,b,; SELECT(T-T)=FIRST(T)=(,a,b,; SELE
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译原理 编译 原理 模拟 期末 试题 汇总 答案 35
限制150内