《编译原理》第三版期末复习

期末复习总结《编译原理》第一章：绪论一、填空问题①由于计算机只能认识机器语言，所以需要翻译程序将高级语言翻译成计算机可以识别的机器语言。②编译程序的工作过程一般主要划分为词法分析，语法分析，中间代码生成，代码优化，目标代码生成等几个基本阶段，同时还会伴有表格管理和出错处理。③如果编译程序生成的目标程序是机器代码程序，则源程序的执行分为两个阶段：编译阶段和运行阶段。如果编译程序生成的目标程序是汇编语言的程序，则源程序的执行分为三个阶段：编译阶段，汇编阶段和运行阶段。1-02.若源程序是用高级语言编写的,目标程序是机器语言程序或汇编程序,则其翻译程序称为编译程序.1-03.编译方式与解释方式的根本区别在于是否生成目标代码.1-05.对编译程序而言,输入数据是源程序,输出结果是目标程序.1-10.一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括(1)c.其中,(2)b和代码优化部分不是每个编译程序都必需的.词法分析器用于识别(3)c,语法分析器则可以发现源程序中的(4)d.(1)a.模拟执行器b.解释器c.表格处理和出错处理d.符号执行器(2)a.语法分析b.中间代码生成c.词法分析d.目标代码生成(3)a.字符串b.语句c.单词d.标识符(4)a.语义错误b.语法和语义错误c.错误并校正d.语法错误1-11.程序语言的语言处理程序是一种(1)a.(2)b是两类程序语言处理程序,他们的主要区别在于(3)d.(1)a.系统软件b.应用软件c.实时系统d.分布式系统(2)a.高级语言程序和低级语言程序b.解释程序和编译程序c.编译程序和操作系统d.系统程序和应用程序(3)a.单用户与多用户的差别b.对用户程序的查错能力c.机器执行效率d.是否生成目标代码1-12.汇编程序是将a翻译成b,编译程序是将c翻译成d.a.汇编语言程序b.机器语言程序c.高级语言程序d.a或者be.a或者cf.b或者c1-13.下面关于解释程序的描述正确的是b.(1)解释程序的特点是处理程序时不产生目标代码(2)解释程序适用于COBOL和FORTRAN语言(3)解释程序是为打开编译程序技术的僵局而开发的a.(1)(2)b.(1)c.(1)(2)(3)d.(2)(3)1-14.高级语言的语言处理程序分为解释程序和编译程序两种.编译程序有五个阶段，而解释程序通常缺少(1)e和(1)b.其中，(1)e的目的是使最后阶段产生的目标代码更为高效.与编译系统相比，解释系统(2)d.解释程序处理语言时,大多数采用的是(3)b方法.(1):a.中间代码生成b.目标代码生成c.词法分析d.语法分析e.代码优化(2):a.比较简单,可移植性好,执行速度快b.比较复杂,可移植性好,执行速度快c.比较简单,可移植性差,执行速度慢d.比较简单,可移植性好,执行速度慢(3):a.源程序命令被逐个直接解释执行b.先将源程序转化为之间代码,再解释执行c.先将源程序解释转化为目标程序,在执行d.以上方法都可以1-15.用高级语言编写的程序经编译后产生的程序叫b.用不同语言编写的程序产生a后,可用g连接在一起生成机器可执行的程序.在机器中真正执行的是e.a.源程序b.目标程序c.函数d.过程e.机器指令代码f.模块g.连接程序h.程序库1-16.要在某一台机器上为某种语言构造一个编译程序,必须掌握下述三方面的内容:c,d,f.a.汇编语言b.高级语言c.源语言d.目标语言e.程序设计方法f.编译方法g.测试方法h.机器语言1-17.由于受到具体机器主存容量的限制,编译程序几个不同阶段的工作往往被组合成(1)d,诸阶段的工作往往是(2)d进行的.(1)a.过程b.程序c.批量d.遍(2)a.顺序b.并行c.成批d.穿插1-18.编译程序与具体的机器a,与具体的语言a.a.有关b.无关1-19.使用解释程序时,在程序未执行完的情况下，a重新执行已执行过的部分.a.也能b.不可能1-20.编译过程中,语法分析器的任务就是b.(1)分析单词是怎样构成的(2)分析单词串是如何构成语句和说明的(3)分析语句和说明是如何构成程序的(4)分析程序的结构a.(2)(3)b.(2)(3)(4)c.(1)(2)(3)d.(1)(2)(3)(4)1-21.编译程序是一种常用的b软件.a.应用b.系统1-22.编写一个计算机高级语言的源程序后,到正式上机运行之前，一般要经过b这几步.(1)编辑(2)编译(3)连接(4)运行a.(1)(2)(3)(4)b.(1)(2)(3)c.(1)(3)d.(1)(4)1-23.编译程序必须完成的工作有a.(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.a.不正确b.正确1-25.把汇编语言程序翻译成机器可执行的目标程序的工作是由b完成的.a.编译器b.汇编器c.解释器d.预处理器1-26.编译程序生成的目标程序b是机器语言的程序.a.一定b.不一定1-27.编译程序生成的目标程序b是可执行的程序.a.一定b.不一定1-28．编译程序是一种B。A.汇编程序B.翻译程序C.解释程序D.目标程序1-29．按逻辑上划分，编译程序第二步工作是C。A.语义分析B.词法分析C.语法分析D.代码优化1-30．通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括C。A.模拟执行器B.解释器C.表格处理和出错处理D.符号执行器1)把汇编语言程序翻译成机器可执行的目标程序的工作是由什么完成的？解答:由汇编器（汇编程序）完成的。19）编译程序是一种解释程序吗？还是什么程序？解答:编译程序是一种翻译程序。二、判断问题①高级语言程序必须经过编译程序的翻译才被计算机识别和执行。（错）答：对高级语言的翻译，还有解释程序。②编译程序的输入是高级语言，输出是机器语言程序。（错）答：输出还有汇编语言程序。③具有优化功能的编译程序的工作效率高。（错）答：优化是编译程序的的一部分，优化的目的，是提高目标程序的质量和运行效率。④有的编译程序可以没有目标代码生成部分。（错）答：编译程序必须生成目标代码，所以目标代码生成部分是不可缺少的。1-31.计算机高级语言翻译成低级语言只有解释一种方式。（×）1-32.在编译中进行语法检查的目的是为了发现程序中所有错误。（×）第二章：词法分析一、填空题1、编译过程中扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位—单词。2、高级程序设计语言的单词通常分为五类，它们是关键字、标识符、常数、运算符以及界限符。3、确定的有限自动机是一个五元组，通常表示为DFAM=（SS0，F）。4、词法分析的任务是输入源程序，输出单词符号。5、确定有限自动机DFA是NFA的一种特例。6、若二个正规式所表示的正规集相同，则认为二者是等价的。8-01.符号表中的信息栏中登记了每个名字的属性和特征等有关信息，如类型、种属、所占单元大小、地址等等。6-04.终结符只有综合属性，它们由词法分析器提供。二、判断题1、一些语言，它们能被确定的有限自动机识别，但不能用正规表达式表示。（错）答：用正规式表示的语言，都能被确定的有限自动机识别。2、每一个NFAM都对应有唯一的一个最小化的DFAM。（对）答：每一个NFAM都可以构造一个DFAM，而DFAM又可以构造一个最小化的DFAM。3、一个有限自动机，仅有一个唯一的终态。（错）答：有限自动机的终态可以有多个。4、确定的有限自动机以及不确定的有限自动机都能正确识别正规集。（对）答：一个有限自动机能识别该正规式，所描述的语言（正规集）。5、对任意一个正规文法G，都存在一个DFAM，满足L（G）=L（M）。（对）答：对每一个正规文法G，都存在一个DFAM，使得L（G）=L（M）。1、正规文法一定不是二义性的。（错）答：文法的二义性问题是不可避免和不可判定的，正规文法也可能存在二义性的问题。2、文法的二义性和语言的二义性是两个不同的概念。（对）答：可能有两个不同的文法G和G`，其中G是二义性的，但是却有L（G）=L（G`）。3、一个句型对应的一棵语法树，包括了该句型的所有推导。（错）答：一棵语法树，只能对应一个推导，所以不能包括该句型的所有推导。三、选择题1、在词法分析中能识别出a，c，e。a、关键字b、四元式c、运算符d、逆波兰式e、常数2、令Σ={a，b}，则Σ上所有以b开头，后跟若干个ab的字的全体对应的正规式b，d。a、b（ab）*b、b（ab）+c、（ba）*bd、（ba）+be、b（ba）*3、词法分析所依据的是b。a、语义规则b、词法规则c、语法规则d、等价变换规则4、正规式V1和V2等价是指c。a、V1和V2的状态数相等b、V1和V2的有向弧条数相等c、V1和V2所识别的语言集相等d、V1和V2状态数和有向弧条数相等5、令Σ={a，b}，正规式abc代表的正规集b。a、{ａ}b、｛ａ，ｂ，ｃ｝c、｛ａｂｃ｝d、｛ｂ，ｃ｝6、有限状态自动机能识别正规文法。三、简答题1、什么是扫描器？扫描器的功能是什么？扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析使用。2)DFA与NFA有何区别?解答:DFA与NFA的区别表现为两个方面:一是NFA可以有若干个开始状态，而DFA仅只有一个开始状态。另一方面，DFA的映象M是从K×∑到K，而NFA的映象M是从K×∑到K的子集，即映象M将产生一个状态集合（可能为空集），而不是单个状态。3)词法分析器是用于做什么的？解答:词法分析器是用于识别单词的。15)词法分析的主要任务是什么？解答:词法分析器的任务是对构成源程序的字符串从左到右逐个字符逐个字符地进行扫描，依次把它们识别为一个一个具有独立意义的单词，并确定其属性，再转换为长度统一的属性字并输出。*第三章：语法分析6)句柄答：句柄——给定句型中的最左简单短语就是句柄。7)句型答：句型——设G是一个给定的文法，S是文法的开始符号，如果Sx(其中x∈V*),则称x是文法的一个句型。8)句子答：句子——设G是一个给定的文法，S是文法的开始符号，如果Sx（其中x∈VT*），则称x是文法的一个句子。9)非终结符答：非终结符—出现在文法产生式的左部且能派生出符号或符号串的那些符号称为非终结符号。10)终结符*答：终结符——出现在文法产生式的右部且不能派生出符号或符号串的那些符号称为终结符号。11）属性文法答：一个属性文法形式的定义为一个三元组AG，AG=（G，V，E）。其中G为一个上下文无关文法；V为属性的有穷集；E为一组语义规则。二．简答题：1)什么是句子？什么是语言?解答：句子——设G是一个给定的文法，S是文法的开始符号，如果Sx（其中x∈VT*），则称x是文法的一个句子。语言——语言是句子的集合。或——设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为：L(G)＝{x│Sx,x∈VT*}。2)自顶向下的语法分析方法的基本思想是什么?解答:从文法的开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导，试图推导出文法的句子，使之与给定的输入串匹配。3)自底向上的语法分析方法的基本思想是什么?解答:从给定的输入串（终结符串）开始，根据文法的规则一步一步的向上进行直接归约，试图归约到文法的开始符号。4)一个上下文无关文法G包括哪四个组成部分？解答:一组非终结符号，一组终结符号，一个开始符号，以及一组产生式。5)在自底向上的语法分析方法中，分析的关键是什么？解答:关键是寻找句柄。6)在自顶向下的语法分析方法中，分析的关键是什么？解答:关键是选择候选式。7)若一个文