《编译原理》训练题.doc

编译原理训练题第一章一填空题1一个编译程序是一个 ，编译程序完成从 语言 所写的源程序到 语言所写的目标程序的翻译工作。2编译程序的整个工作划分成阶段进行的,典型的划分方法，将编译过程分成六 个阶段： ， ， ， ， ， 。3对编译程序而言，输入数据是 ，输出结果是 。4编译方式与解释方式的根本区别在于 。二 判断题（ ） 1汇编程序是一个编译程序，它把汇编语言程序翻译成机器语言执行。（ ） 2编译程序是一个语言翻译程序，它把汇编语言程序翻译成机器语言执行。三选择题1汇编程序是将 （1） 翻译成 （2） ；编译程序是将（3） 翻译成（4） 。可选项有：a.汇编语言程序 b.机器语言程序c.高级语言程序 d.汇编语言程序或机器语言程序e.汇编语言程序或高级语言程序 f.机器语言程序或高级语言程序2用高级语言编写的程序经编译后产生的程序叫（1） 。用不同语言编写的程序产生（1）后，可用（2）连接在一起生成机器可执行的程序。在机器中真正执行的是（3）。可选项有：a.源程序 b.目标程序 c.函数d.过程 e.机器指令代码 f.模块g.连接程序 h.程序库3编译程序与具体的机器（1），与具体的语言（2）。可选项有：a.有关 b.无关4编译程序是一种常用的 软件。可选项有：a.应用 b.系统5编译程序生成的目标程序 是机器语言的程序。可选项有：a.一定 b.不一定四、思考题1给出一个典型的编译程序的结构框图。2什么是前端和后端？设想相同的前端不同的后端，相同的后端不同的前端生成的编译程序分别有何特征？第二章一填空题1. INT O A在每个过程目标程序的入口都有这样一条指令，用以完成 的工作，A域的值为 。 2. OPR O O在每个过程目标程序的 都有这样一条指令，用以完成 的工作。3PL/0编译程序运行时的存储分配策略采用栈式动态分配，用 链和 链的方式解决递归调用和非局部变量的引用问题。4. 是构成语言文法的单词，是语法成分的最小单位。二、思考题1 若PL/0编译程序运行时的存储分配策略采用栈式动态分配，并用动态链和静态链的方式分别解决递归调用和非局部变量的引用问题，试写出下列程序执行到赋值语句b:=10时运行栈的布局示意图。var x,yprocedure p; var a;procedure q;var b;begin (q)b:=10;end(q);procedure s;var c,d;procedure r; var e,f; begin(r)call q;end(r);begin(s)call r;end(s);begin(p)call s;end(p);begin(main)call p;end(main).2 PL/0编译程序所产生的目标代码是一种假想栈式计算机的汇编语言，请说明该汇编语言中下列指令各自的功能和所完成的操作。INT o AOPR o oCAL o A第三章一填空题1设A是符号串，且A=CD，则X3= 。2、产生式是用于定义 的一种书写规则。3、一个上下文无关文法所含四个组成部分是一组 、一组 、一组 、一组 、。4假设G是一个文法，S是文法的开始符号，如果Sa*X，则称X是 。5文法G产生的 的全体是该文法描述的语言。6文法GS：SAc|aB Aab Bbc描述的语言L（GS）= 。7已知文法GE：E：=T|E+T|E-TT：=F|T*F|T/FF：=（E）|i该文法的开始符号（识别符号）是 终结符号集合VT是 ，非终结符号集合VN是 ，句型T+T*F+i的简单短语有. ，句柄为 。8实际使用中，我们将限制文法中不能含有 和 规则。9GE为: E->E+T|E-T T->T*F|T/F|F F->(E)|i 因为存在推导序列: E=>E+T=>E+T*F 所以句型E+T*F 的短语有: 直接短语有: 句柄为: 10三型文法为： S->aS|a 所描述的语言是 an| n>= 11.文法S->a|(T)T->T,S|S(1) 下面对(a,(a,a)的推导为 推导：S=>(T)=>(T,S)=>(S,S)=>(a,S)=>(a,(T)=>(a,(T,S) =>(a,(S,S)=>(a,(a,S)=>(a,(a,a)二 判断题（ ） 1 设G=（VN，VT，P，S），若P中的每一个产生式满足|,仅仅S除外，则文法G是上下文无关的或2型文法。（ ） 2 设G=（S，A，B，a,b，P，S），其中P由下列产生式组成： SaBbA AaaSbAA BbbSaBB 文法G是上下文无关的或2型文法。（ ） 3 设G=（VN，VT，P，S），若P中的每一个产生式满足是一非终结符,则文法G是上下文有关的或2型文法。（ ） 4若一文法G=（VN，VT，P，S）是上下文无关文法，则该文法G一定是上下文有关文法。（ ） 5若一文法G=（VN，VT，P，S）是3型文法，则该文法G一定是上下文有关文法。（ ）6如果一个文法存在某个句子对应两棵不同的语法树，则这个文法一定是二义的。（ ）7*具有可数的无穷数量的元素，*。（ ）8文法G描述的语言是由文法的识别符号推出的所有符号串的集合（ ）9一个句型中的最右直接推导称为该句型的句柄。（ ）10已知语言L=anbn|n>=1，则文法A:=aAb|，可以产生语言L。（ ）11文法GE为: E->E+T|E-T T->T*F|T/F|F F->(E)|i不是二义的.三选择题1在编译中产生语法树是为了（ ）可选项有：a.语法分析 b.语义分析 c.词法分析 d.产生目标代码2文法G描述的语言是 的集合。可选项有：a 文法G 的字汇表V中所有符号组成的符号串b 文法G的字汇表V 的闭包V*中的所有符号串c 由文法的识别符号推出的所有符号串d 由文法的识别符号推出的所有终结符号串3一个语言的文法是 。可选项有：a 唯一的b 不唯一的c个数有限的4已知语言L=anbbn|n>=1,则下述文法中， 可以产生语言L。可选项有：a Z:=aZb|aAb|b A:=aAb|bb Z:=aAb A:= aAb|b c Z:=AbB A:=Aa|a B:=Bb|bd A:=aAb A:=b5设有文法GI：II1|I0|Ia|Ic|a|b|c下列符号串中是该文法的句子的有 。1Ab0 2.a0c01 3.aaa 4.cb10可选项有：a.1 b.2 3 c.3 4 d.1 2 3 46给定文法ABc|cc，Bc|b下面的符号串中，为该文法句子的是 。1cc 2.bcbc 3.bcbcc 4.bc 可选项有：a.1 b.1 2 c.1 4 d.1 2 47一个句型中的最左 称为该句型的句柄。可选项有：a.短语 b.简单短语 c.素短语 d.终结符号8乔姆斯基把文法分成四种类型，即0型、1型、2型和3型。3型文法也称为（1） ，2型文法是（2） 。可选项有：a.上下文无关文法 b.上下文有关文法.c正则文法 d.短语文法9乔姆斯基的3型语言是这样一种语言，其产生式限制为 。可选项有：a.Aa b.Aa AaB c. ad.10.一个文法G包括四个组成部分依次为：一组（1），一组（2），一个（3），以及一个（4）可选项有：a.字符串 b.字母数字串 c.产生式 d.结束符号 e.开始符号 f.文法 g.非终结符号 h.终结符号11设有文法GS：S：=S*S|S+S|（S）|a该文法 二义性文法。可选项有：a.是 b.不是 c.无法判断12正则式的“|”读作 ，“”读作 ，“*”读作 。可选项有：a并且 b或者 c连接 d闭包13GE为: E->E+T|E-T T->T*F|T/F|F F->(E)|i存在推导序列: E=>E+T=>E+T*F则E+T*F是一个a 句型 b句子14已知文法GE：ET|E+T|E-T TF|T*F|T/F F(E)|i该文法的句型T+T*F+i的直接短语为（ ），该文法的句型T+T*F+I句柄为（ ）。（1）句型中第一个T （2）句型中第二个T （3）T+T （4）T*F（5）F （6）i （7）T+T*F （8）T*F+i （9）T+T*F+i可选项有： a（1）b（1）（2） c（1）（4）（6） d（1）（4）（6）（9） a（4） b（2） c（1） d（6）四、思考题1 文法G=(A,B,C,a,b,c,P,S)其中 P：SAc|aBAabBbc写出L(GS)的全部元素。2为只包含数字、加号和减号的表达式，例如9-2+5，3-1，7等构造一个文法。3已知文法GZ: （1）Z:=aZb （2）Z:=ab写出L(GZ)的全部元素。4写一文法，使其语言是偶正整数的集合。要求：(1)允许0打头 (2) 不允许0打头5已知文法G: 表达式=项|表达式+项|表达式-项 项=因子|项*因子|项/因子因子=（表达式）|i试给出下述表达式的推导及语法树。（1）i*i （2）i+(i+i)6证明下述文法表达式是二义的。表达式=a|(表达式)|表达式运算符表达式运算符=+|-|*|/7令文法GE为：ET|E+T|E-TTF|T*F|T/FF(E)|i证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。8一个上下文无关文法生成句子abbaa的推导树如下：（1） 给出该句子相应的最左推导，最右推导。（2） 该文法的产生式集合P可能有哪些元素？（3） 找出该句子的所有短语，简单短语，句柄。9给出生成下述语言的上下文无关文法：(1) anbnambm| n，m>=0 (2) 1n0m 1m0n| n，m>=010给出生成下述语言的三型文法：(1) an|n=0(2) anbm|n,m>=1 (3)anbmck|n,m,k>=0 第四章一填空题1. 引入有穷自动机，为词法分析程序的自动构造寻找特殊的方法和工具，有穷 自动机分两类： 和 。2确定的有穷自动机是一个 组。3. 确定有穷自动机的化简，是指 ，并且它的状态中 没有两个是 。4. 编译过程的第一个阶段是 。5. 扫描器的任务是从 中识别出一个个 。6如下有穷自动机： 0,1 1 1 0 1CBAX Y该有穷自动机为一个： （DFA/NFA），从图中可看出初态集为 ，终态集为： ，有 个状态。 （能/不能）被该有穷自动机M所识别。f(A,1)= 。二 判断题（ ）1一个确定的有穷自动机（DFA）M是一个五元组：M=（K，f , S , Z ） 其中之一K是有穷集，每个元素称为一个状态，为字母表，SK是唯 一的一个初态，f是转换函数为一个单值函数，若字母表含有n个 输入符，任何一个状态最多有n条弧射出，而且每条弧以一个不同的输入字符标记。（ ）2一个确定的有穷自动机（DFA）M是一个五元组：M=（K，f , S , Z ） 其中之一K是有穷集，每个元素称为一个状态，为字母表，SK是唯 一的一个初态，f是转换函数可为一个多值函数，若字母表含有n个输入符，任何一个状态可有n条以上的弧射出，而且每条弧以一个不同 的输入字符标记。（ ）3DFA是NFA的特例，对于每个NFA M,存在一个DFA M,使得L(M)=L(M)（ ）4如下有穷自动机是一个DFA.三选择题1无符号常数的识别和拼数工作通常都在（ ）阶段完成。可选项有：a.词法分析 b. 语法分析 c. 语义分析 d. 代码生成e.代码优化 f. 表格管理 g. 出错管理2通常高级语言的词法规则可用正则式描述，词法分析器可用（ ）来实现。可选项有：a. 语法树 b.有穷自动机 c.栈 d. 堆3. xyxxy是自动机 接受的。a.可以 . b. 不可以4.yyxy是自动机 接受的。a.可以 b. 不可以5.指出正规式(ab|b)*c 与后面的 串不匹配a.ababbc b.abab c. babc d.c6.指出正规式(a|b)a+(ba)* 与后面的 串不匹配a.ba b.baa c.aa d.bba四思考题1构造正规式1(0|1)*101相应的DFA.2 将书中P66图4.16确定化：3 把下图最小化(书中P66图4.17)：4 构造一个DFA，它接收=0,1上所有满足如下条件的字符串：每个1都有0直接跟在右边。并给出该语言的正规式。第五章一填空题1 是编译程序的核心部分。目前常用的方法有 和 分析法。 2.若有文法GS: SpA SqB AcAd Aa 则FIRSTS= FOLLOWA= 3LL（1）文法的含义：第一个L表明 第二个L表 明 ，1表明 。4当文法不满足LL（1）时不能用 自顶向下分析分析，但可用 自顶向下分析。5文法GS：SAc|aB Aab Bbc描述的语言L（GS）= 。6已知文法GE：E：=T|E+TT：=F|T*FF：=（E）|i改写该文法以消除直接左递归，改写后的文法为：E E， E E|。二、判断题（ ）1. 由LL（1）文法的定义可知若文法中含有间接左递归，该文法肯定是LL（1）文法。（ ）2. 若文法是LL（1）文法，该文法肯定能采用确定的自上向下的语法分析。三选择题1已知文法G（S）：SAB|bC Ab|BaB| CABa|bFIRST(S)=(1) , FIRST(A)= (2) , FIRST(B)=(3) ,FIRST(C)=(4) .可选项有:a. b, b.a, c.a,b, d.a,b,# e.a,b f.#FOLLOW(S)(5) , FOLLOW(A )(6) , FOLLOW(B)(7) , FOLLOW(C)(8) 可选项有：abba，#ca，b，#d#SELECT(SAB)(9) , SELECT (SbC)(10) ,abba，#ca，b，#da,b2已知文法：ETE ETE| TFT T*FT| F(E)i可推出的非终结符有： （1） aE T F bE TcE EdE E TFIRST(E)（2） ，FIRST(E)= （3） FIRST(T)（4） FOLLOW(E)(5) ，FOLLOW(T)(6) FOLLOW(F) (7) SELECT(F(E)= (8) SELECT(Fi)= (9) 可选项有：a， b*, c）， d(，ie，+,) f*，+，#，） g( hi3对于文法：aABe|BaB:=Db|e有人说：因为（aABe）FOLLOW(A),并且（）（），所以文法不是（）文法这种说法（ ）可选项有：a正确 b不正确4下列文法：a|a不是（）文法的理由是（1）可选项有：a.FIRST(S) FIRST(A) b.FIRST(A) FOLLOW(A) c.FIRST(Aa) FIRST(a) d.都不是5已知文法G（S）：SEt|Rt TDR|ERDr|e Da|bd(1) FIRST(S)=(1),FIRST(T)=(2),FIRST®=(3),FIRST(D)=(4).可选项有:A.d,e b.a,b,d,e,e c.a,b d.a,b,# e.a,b,e f.#答案：（）（）（）（）（）（）（），（）（），（）（），（）（）可选项有：，（）该文法的（）分析表为（5）可选项有：6已知文法：（）（）（），（）（）可选项有：，四、思考题1 对下面的文法G:ETEE+E|TFTTT|FPFF*F|P(E)|a|b|(1) 计算这个文法的每个非终结符的FIRST集和FOLLOW集。(2) 证明这个文法是LL(1)的。(3) 构造它的预测分析表。2 已知文法GS如下： S MHa H LSo K dML L eHf M KbLM 判断该文法是否是LL（1）文法。如果是构造LL(1)分析表。3.证明下述文法不是LL（1）的。SC$CbA|aBAa|aC|bAABb|bC|aBB 你能否构造一等价的文法，使其是LL（1）的？并给出判断过程。4证明表达式文法：EE+TTTT*FFF（E）i为LL（1）文法。第七章一填空题1自底向上分析方法是一种 的过程，当分析的栈顶符号串形成句柄 时采取 动作。2编译程序使用的中间代码有多种形式，常见的有 ， ， ，和树形结构。3LR（1）文法的含义：L表明自 R表明自上向下的 ，1表明需 。4自底向上分析的关键问题是在分析过程中如何确定 ，自底向上分析的 移进归约过程是自上向下分析 推导的逆过程。5文法LR（0）的分析表中Si中的S表示 i表示 。6. 文法LR（0）的分析表中rj中的r表示 。7LR分析器的关键部分是 的构造。二 判断题（ ） 20.拓广文法的开始符号S只会在产生式的左部出现。（ ） 21.LR（0）项目集规范族的项目类型分为四种：其中移进项目是形如A->·a, aV（ ） 22.LR项目集规范族的项目类型中归约项目是形如A->·, V*（ ） 23.LR项目集规范族的项目类型中待约项目是形如A->·B,BV三选择题1下列文法：a|a不是（）文法，理由是（）可选项有：a.FIRST(S) FIRST(A) b.FIRST(A) FOLLOW(A) c.FIRST(Aa) FIRST(a) d.都不是2设有文法（0）SS (1)SrD （2）DD,i （3） Di如果构造（）项目集规范族，第一个项目集0中应有（） ；第i项目集中若有一个SrD项目，则该项目集中一定还含有（2） (1) SS (2) SS (3) SrD (4) SrD (5) SrD (6) DD,i (7) DD,i (8) DD,i (9) DD,i (10) Di (11) Di可选项有：a（）（）b（）（）（4）c（6）（0）d（6）（7）（9）3设有文法G:(0) SS (1) SaAd (2) SbAc(3) Sbed (4) Ae如果构造（1）项目集规范族，第一个项目集0中应有（） ；第i项目集中若有一个SaAd,#项目，则该项目集中一定还含有（2） (1) SS,# (2) SS,# (3) SaAd,#(4) SaAd,# (5) SaAD,# (6) SaAd,#(7) SbAc,# (8) SbAc,# (9) SbAC,# (10) SbAc,# (11) Sbed,# (12)Sbed,#(13) SbeD,# (14) Sbed.# (15) Ae,d (16) Ae,d (17) Ae,c (18) Ae,c可选项有：a（）b（）（）（7） （11）c（15）d（17）4LR分析法的归约过程是规范推导（ 推导）的逆过程，所以LR分析过程是一种规范归约过程.a 最右 b最左5设有文法G:(0) SAS| (1) AaA|b如果构造（1）项目集规范族，FIRST(S)= (1) a. a,b b.a,b, c.a,b,# d.一个项目集i中有项目SAS,#,则项目AaA，b中b应为 （2） 一个项目集j中有项目SAS,#,则项目AaA，b中b应为 （3） a. # b. a/b c.a/b/# d. a/b/四、思考题1证明下面文法不是LR（0）但是SLR（1）：EE+TTTT*FFF（E）i2若有定义二进制数的文法如下：SL.L|LLLB|BB0|1(1) 试为该文法构造LR分析表，并说明属哪类LR分析表。(2) 给出输入串101.110的分析过程。3设文法GS为： EaAd EbAc Eaec Ebed Ae 说明该文法是LR（1）文法，构造它的LR（1）分析表4设文法GS： SAS AaAb（1）证明LR（1）文法（2）构造它的LR（1）分析表第八章一、填空题编译过程中，常见的中间语言形式有、和。在编译过程中安排中间代码生成的目的是和。表达式（）的逆波兰表示为。二、判断题（ ） .表达式(ab*c)/(ab)d的逆波兰表示为：abc*+a/b+d-（ ） 2. 表达式(ab*c)/(ab) 的逆波兰表示为：abc*+ab+/三、选择题表达式-a+b*(c+d)的逆波兰式是（）。可选项有：a.ab+-cd+-* b.a-b+c-d+*c.a-b+c-d+* d.a-bcd+*+对任何一个编译程序来说，产生中间代码是（）。可选项有：a.不可缺少的b.不一定必要的3下面赋值语句的逆波兰表示式为（）。x:=a+b*(a+c)*d+e) 可选项有：a. xab+ac+d*e+*:=b. xabac+de+*+:=c: xabac+d*e+*+:=d. a,b,c都不正确下面的逆波兰表达式所代表的中缀形式的表达式是（）。ab+cd+*可选项有：a.a+b+c*d b.(a+b)*(c+d) c.(a+b)*c+d d.a+b*c+d在编译程序中安排中间代码生成的目的是。便于进行存储空间的组织利于目标代码优化利于编译程序的移植利于目标代码的移植利于提高目标代码的质量可选项有：四、思考题给出计算表达式（）（）（）的四元式序列。写出表达式（）的逆波兰表示、三元组表示、四元组表示。第十章一填空题常用的两种动态存贮分配办法是 动态分配和 动态分配。如果在编译时能确定目标程序运行中所需的全部数据空间的大小，编译时安排好目标程序运行时的全部数据空间，确定每个数据对象的存储位置，称这种分配策略为 存储分配。二 判断题（ ）. 栈式动态分配策略是将整个程序的数据空间设计为一个栈，适用于C， PASCAL之类的语言，当调用一个过程时，所需的数据空间就分配在栈顶，当过程工作结束时，释放这部分空间。（ ）2.堆式动态分配策略是将整个程序的数据空间设计为一个栈，适用于C， PASCAL之类的语言，当调用一个过程时，所需的数据空间就分配在栈 顶，当过程工作结束时，释放这部分空间。（ ）.对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。（ ）.过程调用时，参数的传递方法通常有传地址、传值、传名。三选择题动态存储分配时，可以采用的分配方法有（）。（） 以过程为单位的栈式动态存储分配（） 堆存储分配（） 最佳分配方法可选项有：a（）b（）c（）（）d（）（）（）过程调用时，参数的传递方法通常有（）。（）传值（）传地址（）传结果（）传名可选项有：a（）（）b（）（）（）c（）（）（）d（）（）（）（）FORTRAN编译中存储分配是（）动态存储分配。可选项有：a 是b 不是4对于下面的程序procedure p(x,y,z):beginy:=y+2;z:=z+yend;begina:=4;b:=5;p(a+b,a,a);print aend;若参数传递的办法分别为：（）传地址（call by reference）,(2)传值（call by value）, 那么程序执行时所输a分别是（）。可选项有：a. (1) 4 (2) 15 b. (1) 4 (2) 17c. (1)17 (2)4 d .(1)15 (2)4第十一章一填空题根据所涉及程序的范围，优化可分为局部优化， 优化和 优化三种。2局部优化是局限于一个 范围内的一种优化。二 判断题：程序基本块是指（）。（） 一个子程序（） 一个仅有一个入口和一个出口的语句（） 一个没有嵌套的程序段（） 一组顺序执行的程序段，仅有一个入口和一个出口可选项有：a (1) b (2) c (3) d (4) e (1)(4) f (1)(2)第十二章