编译原理试卷答案练习题

一.填空题:1-01.编译程序的工作过程一般可以划分为_ _等几个基本阶段,同时还会伴有_ _和 .1-02.若源程序是用高级语言编写的,目标程序是 _ _,则其翻译程序称为编译程序.1-03.编译方式与解释方式的根本区别在于_ _.1-04.翻译程序是这样一种程序,它能够将_ _转换成与其等价的_ _.1-05.对编译程序而言,输入数据是_ _,输出结果是 _ _.1-06.如果编译程序生成的目标程序是机器代码程序,则源程序的执行分为两大阶段:_ _和_ _.如果编译程序生成的目标程序是汇编语言程序,则源程序的执行分为三个阶段: _ _,_ _和_ _ .1-07.一个典型的编译程序中，不仅包括_ _等五个部分，还应包括_ _和_ _。其中，词法分析器用于识别_ _。1-08.如果编译程序生成的目标程序是汇编语言程序，则源程序的执行分为三个阶段: _ ， 汇编阶段和运行阶段。1-09.编译方式与解释方式的根本区别为是否 _ 。2-01.所谓最右推导是指： 。2-02.一个上下文无关文法所含四个组成部分是 。2-03.产生式是用于定义 的一种书写规则。2-04.设GS是给定文法，则由文法G所定义的语言L(G)可描述为： 。2-05.设G是一个给定的文法，S是文法的开始符号，如果Sx（其中xV*），则称x是文法的一个 。2-06.设G是一个给定的文法，S是文法的开始符号，如果Sx(其中xVT*),则称x是文法的一个 。3-01.扫描器的任务是从源程序中识别出一个个 。4-01.语法分析最常用的两类方法是_ _和_ _分析法。4-02.语法分析的任务是识别给定的终极符串是否为给定文法的 _。4-03.递归下降法不允许任一非终极符是直接 _递归的。4-04.自顶向下的语法分析方法的关键是 _ 的问题。4-05.递归下降分析法是自 _ 分析方法。4-06.自顶向下的语法分析方法的基本思想是：从文法的 _开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导，试图推导出文法的 _ ，使之与给定的输入串匹配。5-01.自底向上的语法分析方法的基本思想是：从给定的终极符串开始，根据文法的规则一步一步的向上进行 ，试图 到文法的 。5-02.自底向上的语法分析方法的基本思想是：从输入串入手，利用文法的产生式一步一步地向上进行 ，力求 到文法的 。5-03.简单优先方法每次归约当前句型的 ，算符优先方法每次归约当前句型的 ，二者都是不断移进输入符号，直到符号栈顶出现 的尾，再向前找到 的头，然后归约。5-04.在LR（0）分析法的名称中，L的含义是 ，R的含义是 ，0 的含义是 。5-05.在SLR（1）分析法的名称中，S的含义是 。6-01.所谓属性文法是 _。6-02.综合属性是用于 _传递信息。6-03.继承属性是用于 传递信息。6-04.终结符只有 ，它们由词法分析器提供。8-01.符号表中的信息栏中登记了每个名字的 ，如类型、种属、所占单元大小、地址等等。8-02.一个过程相应的DISPLAY表的内容为 。9-01.一个过程相应的DISPLAY表的内容为_ _ 。9-02.常用的两种动态存贮分配办法是_ _动态分配和_ _动态分配。9-03.常用的参数传递方式有 _ ，传值和传名。10-01局部优化是局限于一个 _范围内的一种优化。10-02.代码优化的主要目标是如何提高 _ 和如何减少 _ 。二.选择题:1-10.一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括_ _.其中,_ _和代码优化部分不是每个编译程序都必需的.词法分析器用于识别_ _,语法分析器则可以发现源程序中的_ _. (1) a.模拟执行器 b.解释器 c.表格处理和出错处理 d.符号执行器 (2) a.语法分析 b.中间代码生成 c.词法分析 d.目标代码生成 (3) a.字符串 b.语句 c.单词 d.标识符 (4) a.语义错误 b.语法和语义错误 c.错误并校正 d.语法错误1-11.程序语言的语言处理程序是一种_ _. _ _是两类程序语言处理程序,他们的主要区别在于_ _. (1) a.系统软件 b.应用软件 c.实时系统 d.分布式系统 (2) a.高级语言程序和低级语言程序 b.解释程序和编译程序 c.编译程序和操作系统 d.系统程序和应用程序 (3) a.单用户与多用户的差别 b.对用户程序的查错能力c.机器执行效率 d.是否生成目标代码1-12.汇编程序是将_ _翻译成_ _,编译程序是将_ _翻译成_ _ .a.汇编语言程序 b.机器语言程序 c.高级语言程序d. a 或者 b e. a 或者 c f. b 或者 c1-13.下面关于解释程序的描述正确的是_ _. (1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于COBOL 和 FORTRAN 语言 (3) 解释程序是为打开编译程序技术的僵局而开发的 a. (1)(2) b. (1) c. (1)(2)(3) d.(2)(3)1-14.高级语言的语言处理程序分为解释程序和编译程序两种.编译程序有五个阶段，而解释程序通常缺少_ _和_ _.其中，_ _的目的是使最后阶段产生的目标代码更为高效. 与编译系统相比，解释系统_ _.解释程序处理语言时,大多数采用的是_ _方法. (1): a. 中间代码生成 b.目标代码生成 c.词法分析 d.语法分析 e.代码优化 (2): a.比较简单,可移植性好,执行速度快 b.比较复杂,可移植性好,执行速度快 c.比较简单,可移植性差,执行速度慢 d.比较简单,可移植性好,执行速度慢 (3): a.源程序命令被逐个直接解释执行 b.先将源程序转化为之间代码,再解释执行c.先将源程序解释转化为目标程序,在执行 d.以上方法都可以1-15.用高级语言编写的程序经编译后产生的程序叫 .用不同语言编写的程序产生_ _后,可用_ _连接在一起生成机器可执行的程序.在机器中真正执行的是_e_.a. 源程序 b. 目标程序 c. 函数 d. 过程 e. 机器指令代码 f. 模块 g. 连接程序 h.程序库1-16.要在某一台机器上为某种语言构造一个编译程序,必须掌握下述三方面的内容: _ , , .a. 汇编语言 b. 高级语言 c. 源语言 d. 目标语言e. 程序设计方法 f. 编译方法 g. 测试方法 h. 机器语言1-17.由于受到具体机器主存容量的限制,编译程序几个不同阶段的工作往往被组合成_ _,诸阶段的工作往往是_ _进行的. (1) a. 过程 b. 程序 c. 批量 d.遍 (2) a. 顺序 b. 并行 c. 成批 d.穿插1-18.编译程序与具体的机器_ _, 与具体的语言_ _.a. 有关 b.无关1-20.编译过程中,语法分析器的任务就是_ _. (1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构a. (2)(3) b. (2)(3)(4) c. (1)(2)(3) d.(1)(2)(3)(4)1-21.编译程序是一种常用的_ _软件.a. 应用 b. 系统1-22.编写一个计算机高级语言的源程序后,到正式上机运行之前，一般要经过_ _这几步. (1) 编辑 (2) 编译 (3) 连接 (4) 运行a. (1)(2)(3)(4) b. (1)(2)(3) c. (1)(3) d.(1)(4)1-23.编译程序必须完成的工作有_ _. (1) 词法分析 (2) 语法分析 (3) 语义分析 (4) 代码生成 (5) 之间代码生成 (6) 代码优化a. (1)(2)(3)(4) b. (1)(2)(3)(4)(5) c. (1)(2)(3)(4)(5)(6) d. (1)(2)(3)(4)(6) e. (1)(2)(3)(5)(6)1-24.“用高级语言书写的源程序都必须通过编译,产生目标代码后才能投入运行”这种说法_ _.a. 不正确 b.正确1-25.把汇编语言程序翻译成机器可执行的目标程序的工作是由_ _完成的.a. 编译器 b. 汇编器 c. 解释器 d. 预处理器1-26.编译程序生成的目标程序_ _是机器语言的程序.a. 一定 b. 不一定1-27.编译程序生成的目标程序_ _是可执行的程序.a. 一定 b. 不一定1-28编译程序是一种 。A. 汇编程序 B. 翻译程序 C. 解释程序 D. 目标程序1-29按逻辑上划分，编译程序第二步工作是 。A. 语义分析 B. 词法分析 C. 语法分析 D. 代码优化1-30通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括_ _。A.模拟执行器 B.解释器 C.表格处理和出错处理 D.符号执行器2-06已知语言L= xnyyn | n=1，则下述文法中， 可以产生语言L。A 1.ZxZy|xAy|y B 1.AxAy2. AxAy|x 2.Ax C 1.ZAyB D 1.ZxAy 2.AxA|x 2.AxAy|y 3.ByB|y 2-07文法G所描述的语言是 的集合。A.文法G的字母表V中所有符号组成的符号串B.文法G的字母表V的闭包V*中的所有符号串C.由文法的开始符号推出的所有终极符串D.由文法的开始符号推出的所有符号串2-08乔姆斯基（Chomsky）把文法分为四种类型，即0型、1型、2型、3型。其中3型文法是 。A.短语文法 B.正则文法 C.上下文有关文法 D.上下文无关文法2-09.文法GN=（b，N，B，N，NbbB，BbN），该文法所描述的语言是 。A. L(GN)=bii0 B. L(GN)=b2ii0C. L(GN)=b2i+1i0 D. L(GN)=b2i+1i12-10一个句型中的最左 称为该句型的句柄。可选项有：A. 短语 B. 简单短语 C. 素短语 D. 终结符号2-11设G是一个给定的文法，S是文法的开始符号，如果Sx(其中xV*),则称x是文法G的一个 。A. 候选式 B. 句型 C. 单词 D. 产生式2-12一个上下文无关文法G包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 。A. 句子 B. 句型 C. 单词 D. 产生式2-13.文法GE：ETETTFTF Fa（E）该文法句型EF(ET)的简单短语是下列符号串中的 。（ET） ET F F(ET)可选项有：A) 和 B) 和 C) 和 D) 2-14若一个文法是递归的，则它所产生的语言的句子 。A.是无穷多个 B.是有穷多个 C.是可枚举的 D.个数是常量2-15文法的二义性和语言的二义性是两个 的概念。A 不同 B 相同 C 无法判断 D 不存在3-02词法分析器用于识别 。A. 句子 B. 句型 C. 单词 D. 产生式4-07.在语法分析处理中，FIRST集合、FOLLOW集合、SELECT集合均是 。A. 非终极符集 B.终极符集 C. 字母表 D. 状态集4-08.编译程序中语法分析器接收以 为单位的输入。A. 单词 B. 表达式 C. 产生式 D. 句子5-06在自底向上的语法分析方法中，分析的关键是 。A. 寻找句柄 B. 寻找句型 C. 消除递归 D. 选择候选式5-07. 在LR分析法中，分析栈中存放的状态是识别规范句型 的DFA状态。A.句柄 B. 前缀 C. 活前缀 D. LR(0)项目7-01.在使用高级语言编程时,首先可通过编译程序发现源程序的全部 错误和 部分错误.a.语法 b.语义 c.语用 d.运行三、是非题(下列各题，你认为正确的，请在题干的括号内打“ ”，错的打“”。)1-31.计算机高级语言翻译成低级语言只有解释一种方式。 （ ）1-32.在编译中进行语法检查的目的是为了发现程序中所有错误。 （ ）1-33.计算机高级语言翻译成低级语言只有解释一种方式。 （ ）2-15.正则文法其产生式为Aa,ABb, A、BVn，a、bVt。 （ ）4-09.每个文法都能改写为LL(1)文法。 （ ）4-10.递归下降法允许任一非终极符是直接左递归的。 （ ）5-08.算符优先关系表不一定存在对应的优先函数。 （ ）5-09.自底而上语法分析方法的主要问题是候选式的选择。 （ ）5-10.LR法是自顶向下语法分析方法。 （ ）5-11.简单优先文法允许任意两个产生式具有相同右部。 （ ）5-12.若一个句型中出现了某产生式的右部，则此右部一定是该句型的句柄。 （ ）5-13.一个句型的句柄一定是文法某产生式的右部。 （ ）7-02.数组元素的地址计算与数组的存储方式有关。 （ ）8-03.在程序中标识符的出现仅为使用性的。 （ ）9-04.对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。 （ ）9-05.寄存器分配是以程序为单位的。 （ ）9-06.在程序中标识符的出现仅为使用性的。 （ ）9-07.寄存器分配是以程序为单位的。 （ ）10-03.仅考虑一个基本块，不能确定一个赋值是否真是无用的。 （ ）10-04.削减运算强度破坏了临时变量在一基本块内仅被定义一次的特性。 （ ）10-05.在中间代码优化中循环上的优化主要有不变表达式外提和削减运算强度。 （ ）10-06.在中间代码优化中循环上的优化主要有不变表达式外提和削减运算强度。 （ ）四、名词解释：2-16.短语2-17.简单短语2-18.句柄2-19.规范推导2-21.语言4-11.语法分析4-12.选择符集合SELECT5-14.活前缀5-15.可归前缀5-16.LR(0)项目5-17.算符优先文法6-01.语义规则6-03.后缀式6-04.四元式6-05.语法制导翻译6-06.翻译方案9-08.活动9-09.活动记录9-10.活动的生存期10-02.基本块10-07.无环路有向图(DAG)五、简答题：2-19什么是句子？ 什么是语言?2-20.已知文法GE为：ET|E+T|E-TTF|T*F|T/FF（E）|i 该文法的开始符号（识别符号）是什么？请给出该文法的终结符号集合VT和非终结符号集合VN。 找出句型T+T*F+i的所有短语、简单短语和句柄。2-21.已知文法GS为：SdABAaA|aBBb| 试向GS是否为正规文法，为什么？ GS新产生的语言是什么？ GS能否改写为等价的正规文法？2-22.设有语言L(G)=adaR | a(a,b)*, aR 为a之逆，试构造产生此语言的上下文无关文法G。2-23.证明下面文法GN是二义性文法。 GN： N SEE S SDD E 0210D 0123-03简述DFA与NFA有何区别 ? 3-04.试给出非确定自动机的定义。3-05. 为正规式（a|b）*a(a|b) 构造一个等价的确定的有限自动机。其中：开始状态：0 终止状态：2123-07. 给定下列自动机：(1)把此自动机转换为确定自动机DFA。 (2)给出此DFA的正则表达式。4-13.消除下列文法GE的左递归。EE-TTTT/FFF( E )i4-14.在LL(1)分析法中,LL分别代表什么含义?4-15.自顶向下分析思想是什么？4-16.自顶向下的缺点是什么？4-17.LL（1）文法的定义是什么？4-18.什么是文法的左递归？4-19.递归下降法的主要思想是什么？5-19.自底向上分析法的原理是什么？5-20.简单优先方法基本思想是什么？5-21.三种优先关系的定义是什么？5-22.如何确定简单优先文法的句柄？5-23. 给定文法GZ：a) 构造此文法的LR(0)项目集规范族，并给出识别活前缀的DFA。b) 构造其SLR（1）分析表。5-24. 设有文法GS： 求识别该文法所有活前缀的DFA。6-07.语法制导翻译方法的基本思想是什么?6-09.在一个属性文法中，对应于每个产生式Aa都有一套与之相关联的语义规则，每条规则的形式为b：f（c1,c2，ck），其中对于b的要求是什么？6-10.给定文法及相应的翻译方案：SbTc print(“0”)Sa print(“1”)TR print(“2”)RR/S print(“3”)RS print(“4”)为该文法设计翻译方案，使句型bR/bTc/bSc/ac经该翻译方案翻译后,输出串：03420313206-10.给定文法及相应的翻译方案：)EE+T print(“5”)ET print(“4”)TT*F print(“3”)TF print(“2”)F( E ) print(“1”)Fi print(“0”)对于句型T+(T*(F+T)*i),处理完该句型后输出是什么？7-05.常用的中间语言种类有哪几种？7-06.给定下列中缀式，分别写出等价的逆波兰表示和抽象语法树(运算符优先级按常规理解)。(1)aba0b0 (2)a(a*bd)*(ab*d)/d(3)ab0a0(ab)2 (4)a*(b*ca)bcd7-07给定下列中缀式，分别写出等价的后缀式和四元式(运算符优先级按常规理解)。(1)(ab*c)/(ab)d(2)x+yza0(3)xy0 (xy)2(4)a:= (b*ca) * a8-04.符号表的组织方式有哪几种？8-05. 在整个编译期间，对于符号表的操作有哪些？8-06.符号表的作用有哪些？9-11.解释抽象地址的结构和出现的原因。9-12.描述活动记录的具体结构及display表的作用。9-13.参数传递有换名(call by name)、传值(call by value)、传地址(call by reference)和传结果(call by result)等方式，试叙编译程序处理“传值”和“传地址”方式时的要点，并指明处理“换名”与“传地址”，以及“传值”与“传结果”方式之间的主要差别。9-14运行时存储器的划分是怎样的？10-08.简述“循环中数组元素地址计算的优化”的主要思想，并举例说明。10-09. 简述优化的原则是什么？ 10-10简述常用的优化技术有哪些？10-11. 设有基本块：(1) a:=b-c(2) d:=a+4(3) e:=a-b(4) f:=a+4(5) b:=b+c(6) c:=b-f(7) b:=b-c(8) f:=b+f(9) a:=a-f(1) 画出DAG图；(2) 假设基本块出口时只有a，b还被引用，请写出优化后的三地址代码序列。10-12设有基本块 T1：2T2：10/T1T3：SRT4：SRA：T2 * T4B：AT5：SRT6：T3 * T5B：T6(1) 画出DAG图；(2) 假设基本块出口时只有A，B还被引用，请写出优化后的三地址代码序列。11-01.目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？11-02.什么是非活跃变量？什么是活跃变量？综合题：给定文法S及相应翻译方案为：40. 按chomsky分类法，文法G属于哪一型文法？ 41. 符号串bR/bRc/ac是不是该文法的一个句型，请证实。42. 若是句型，写出该句型的所有短语、简单短语，以及句柄。43. 构造识别该文法的活前缀的DFA。 44. 判断该文法是LR（0）还是SLR（1），并构造其相应的语法分析表。45. 对于bR/bRc/ac这个输入符号串，该翻译方案的输出是什么？