编译原理练习题库.doc

编译原理练习题库一、填空题1.若源程序是用高级语言编写的，目标程序是_，则其翻译程序称为编译程序。2.词法分析和语法分析本质上都是对源程序的_进行分析。3.如果源语言(编写源程序的语言)是高级语言，而目标语言是某计算机的汇编语言或机器语言，则这种翻译程序称为_。4.对编译程序而言，输入数据是_,输出结果是_。5. _，是构成语言文法的单词，是语法成分的最小单位。6.由PL0的EBNF可知，PL0语言可看成是PASCAL语言的子集，它的编译程序是一个_。7.每个非终结符是一个语法成分，在书写语言程序时并不出现，它是由_和_、或终结符串定义的。8.PL0的目标程序为假想栈式计算机的汇编语言，与具体计算机_。9.由于对某些非终结符可以递归定义，这就使得_可用有穷的文法描述。10.凡是具有某种特殊性质的客体的聚合，都可称为_。11.如果集合中元素个数为零，即集合中不含有任何元素，这样的集合称为_，记为。12.例 设 P=（1，2），（3，4），（2，2）Q=（4，7），（2，9），（3，1）则PQ=_13.符号串与符号组成顺序_，如符号串ab_ba，符号申001也_010。14.假设G是一个文法，S是文法的开始符号，如果S=*x,则称x是_。15. 文法G产生的_的全体是该文法描述的语言。 答案：1.机器语言程序或汇编程序2.结构3.编译程序4.源程序，目标程序。5.终结符6.编译解释执行系统7.终结符和非终结符串 8.无关 9.无穷的句子集 10.集合 11.空集 12.（1，9），（3，7），（2，5） 13.有关,不同于,不同于14.句型 15.句子 二、选择题1.编译程序是一种常用的_软件。a.应用 b.系统 c.工具 d.测试2.在使用高级语言编程时，首先可通过编译程序发现源程序的全部_错误和部分_错误。a.语法 b.语义 c. 语用 d.运行3.编译程序生成的目标程序_是机器语言的程序。a.一定 b.不一定 c.某种情况下一定 d.某种情况下不一定4.编译程序生成的目标程序_是可执行的程序。a.一定 b.不一定 c.某种情况下一定 d.某种情况下不一定5.一个语言的文法是_.a惟一的 b不惟一的 c.个数有限的 d.无限的6.巴科斯-诺尔范式(即BNF)是一种广泛采用的_的工具。 a描述规则 b.描述语言 c描述文法 d描述句子7.正规文法_二义性的。 a.可以是 b.一定不是 c.一定是8.设有文法GS：S:=S*S|S+S|(S)|a该文法_二义性文法。a.是 b.不是 c.无法判断 9. 编译过程中扫描器的任务包括_。 组织源程序的输入 按词法规则分割出单词，识别出其属性，并转换成属性字的形式输出 删除注解 删除空格及无用字符 行计数、列计数 发现并定位词法错误 建立符号表 a b c d10、编译过程中，语法分析器的任务是_ 。 A.分析单词是怎样构成的 B.分析单词串是如何构成语句和说明的 C.分析语句和说明是如何构成程序的 D.分析程序的结构 a.BC b.D cBCD dABCD11、下列文法GS的句型aRaSbaTb,b 的最左素短语 为_。 S-aTb|， T-R R-RS|S a.aTb b.aSb c.S d.R e. , 12. 一个正规语言只能对应()？A 一个正规文法；B 一个最小有限状态自动机；C.一个下推自动机D.一个确定的有限自动机13文法GA：A AaB BAb Ba是()：A 正规文法B 二型文法C.上下无关文法D. 不确定14下面说法正确的是()：A 一个SLR（1）文法一定也是LALR（1）文法B 一个LR（1）文法一定也是LALR（1）文法15一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL（1）文法的()：A 必要条件B 充分必要条件 C.充分条件16、一个右线性文法G一定是 （ ） ALL（1）文法 CSLR（1）文法 BLR（1）文法 D上述三者都不是17、设A、B为任意两个集合，由所有属于集合A或属于集合B的元素组成的集合，叫做集合A与B的_ a.空集 b. 全集 c. 并集 d. 交集18、在集合X上的关系R，如果合(x，y) R，便必有(y，x) R，则称关系R是_。 a.自反的 b.对称的 c.传递的 d.正向的19、在状态转换图中，结点代表_，用圆圈表示。 a.输入缓冲区 b.向前搜索 c.状态 d.字符串20、正则式的“*”读作_。a，并且 L或者 c连接 d闭包21、_是编译过程的核心部分 a. 语法结构 b. 语法分析 c. 源程序 d. 单词符号22、高级语言编译程序常用的语法分析方法中，递归下降分析法属于_ 分析方法。 可选项有；a. 自左至右 b自顶向下 c自底向上 d自右向左23、算符优先分析法每次都是对_进行归约，简单优先分析法每次都是对句柄进行归约。a最左短语 b.简单短语 c. 最左素短浯 d素短语 答案：1.b 2.a. 3.b 4.b 5.b 6.b 7.c 7.a 8.a 9.d 10. c 11.b 12B 13B 14 A 15A 16.A 17.c 18.b 19.c 20d 21b 22b 23d三、综合题1.“含有优化部分的编译程序的执行效率高”，这种说法正确吗？ 2.有人认为编译程序的五个组成部分却一不可，这种看法正确吗？ 3.PL0编译程序对语法错误的处理采用哪两种办法? 4. 设文法G(S)：S(L)|a S|aLL，S|S(1) 消除左递归和回溯；(2) 计算每个非终结符的FIRST和FOLLOW； 5.设有文法G：s:=Qc|cQ:=Rb|bR:=Sa|a试求HARD(S),HARD(Q),HARD(R).6.优先函数与优先关系矩阵各有什么优缺点？ 7. 文法GN为： N-D|ND D-0|1|2|3|4|5|6|7|8|9 GN的语言是什么？8、 给定PASCAL程序语句while ab do if a0 then a:=a-1 else a:=a+1;1. 将该语句翻译成逆波兰式；2. 给出编译程序扫描到then处及分号处时所得的四元式序列。9.如何计算FIRST集？答案：1.答：含有优化功能的编译程序，其优化是指对生成的目标代码进行优化，而不是编译程序本身得到优化，它提高目标代码的效率，而不是编译程序的效率。所以，上述说法不对。2.答：不正确。编译程序的五个组成部分中，词法分析，语法分析，语义分析和代码生成是必须完成的，而代码优化是为了提高目标程序的质量，它不是必需的，没有优化部分的编译程序也能生成目标代码。3. (1)对于一些易于校正的错误，如丢了逗号、分号等，则指出出错位置，并加以校正。校正的方式就是补上逗号或分号。 (2)对某些错误，编译程序难于确定校正的措施，为了使当前的错误不致影响整个程序的崩溃，把错误尽量局限在一个局部的语法单位中。这样就需跳过一些后面输入的单词符号，直到读入一个。 4解： (1)S(L)|aSSS|LSLLSL|(2)FIRST)S)(，aFOLLOW(S)#，)FIRST(S)，a,FOLLOW(S)#，)FIRST(L)(，aFOLLOW(L) )FIRST(L)，FOLLOW(L )(3)a，()SSLLSaSS(L)SSSSSSSLSLLSLLL5.HARD(S)=S,Q,R,a,b,c HARD(Q)=S,Q,R,a,b,c HARD(R)=S,Q,R,a,b,c6.(1)优先函数可以节省存储空间，但不能真实反映符号间的优先关系。利用优先函数进行语法分析时，有时不能及时发现错误，延长了分析步骤。(2)优先关系矩阵能真实反映符号间的优先关系，但不象优先函数那样可以节省存储空间7. GN的语言是V+。V=0,1,2,3,4,5,6,7,8,9 N=ND=NDD. =NDDDD.D=D.D 8.9. 根据定义计算由FIRST集定义 FIRST ()=a|=a， a， ， V若=, 则规定FIRST()。 对每一文法符号XV，计算FIRST(X)(a) 若X，则FIRST(X)=X(b) 若X，且有产生式Xa，a，则aFIRST(X)(c) 若X，且有产生式X，则FIRST(X)(d) 若X，Y1，Y2，Yi，而有产生式XY