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