2022年编译原理自测题 .pdf

1 注：1、章节不完全按照陈意云教材的章节；2、不公布标准答案；3、 题目中标注的页码如P6 图 1.3均为陈意云教材的页码。第一章一填空题1编译程序的工作过程一般可以划分为_、_、_、_和_等几个基本阶段，同时还伴有_和 _。2若源程序是用高级语言编写的，目标程序是_或_，则其翻译程序称为编译程序。3编译方式与解释方式的根本区别在于_。4_是这样一种程序，它能将用甲种语言书写的程序转换成与其等价的乙种语言书写的程序。5对编译程序而言，输入数据是_，输出结果是_。6运行编译程序的计算机称宿主机，运行编译程序所产生目标代码的计算机称_。7当把编译程序划分成编译前端和编译后端时，_主要由与 _有关但与目标机无关的部分组成，编译后端包括编译程序中与目标机有关的部分，编译后端不依赖于源语言而仅仅依赖于_。8描述词法规则的有效工具是_，通常使用 _来描述语法规则，使用_描述语义规则。二 简答题1什么是编译程序2. 什么是解释程序3. 什么是翻译程序4. 以上 3 种程序的区别三 综合题1、编译过程的几个阶段的输入输出及相关技术（P6图 1.3）第二章一 综合题1构造与正规式(a|b)*a(a|b)等价的状态最少的确定有限自动机。2构造与正规式(0|1)*0(0|1) 等价的状态最少的确定有限自动机。3构造与正规式(a|ba)*等价的状态最少的确定有穷自动机。4构造与正规式(a|b)* aa 等价的状态最少的确定有穷自动机。5构造与正规式a (a|b)*b 等价的状态最少的确定有穷自动机。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 7 页 - - - - - - - - - 2 注意：以上4 题要分别写出构造NFA、NFA 确定化为 DFA（子集法）、DFA 的最小化过程二 简答题1、 当给出有限自动机的状态转换图时，写出有限自动机的五元式定义，并判断它能识别何种字符串。第三章一填空题1上下文无关文法包括以下四个组成部分：一组_符号，一组 _符号，一个 _符号，以及一组 _。2如果一个文法存在某个句子对应两棵不同的语法树，则这个文法是_文法。3消除文法的二义性的方法主要有：_二义文法为非二义文法；为文法符号规定_和_。二 简答题1有文法G： EE+E E*E (E) id （1）给出 (id* id)+ id的最左推导；（2）并给出该推导过程中的所有句型；（3）给出该文法的2 个句子；（4）这个文法产生的是什么语言。2. 有文法 G：SaSbS bSaS（1）为句子abab构造最左推导；（2）给出该推导过程中的所有句型；（3）证明该文法是二义文法；（4）这个文法产生的是什么语言。3. 什么是 LL （1）文法。4. 预测分析器模型由哪些部分组成。5. LR 分析器模型由哪些部分组成。第四章一填空题1 自上而下语法分析中存在的主要问题是由左递归引起的问题和左公共因子引起的问题。2LL （1）文法是即不含左递归，也没有左公共因子的文法。要避免回溯，第一，需要文法中每一个非终结符A 的各个产生式的候选首符集两两不相交，即，若 A1| 2| | n，则 ，(i j)；第二，若A 存在某个候选首符集包含，则= ，i=1,2,.,n。3自上而下语法分析的基本思想是，对任何输入串，从文法的符号，即根结点出发，自上而名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 7 页 - - - - - - - - - 3 下地为输入串建立一颗语法树。递归下降分析器采用的是自上而下语法分析方法，非递归的预测分析器采用的是语法分析方法，LR 分析器采用的是语法分析方法。4预测分析器模型是由输入、输出、，和组成。5自下而上语法分析的基本思想是，从开始，逐步进行，直至规约到文法的开始符号，即从语法树的开始，步步向上规约，直到。6LR 分析器模型包括输入、输出、和含有与两部分的分析表。二、简答题1将以下文法G（S）改写成 LL(1) 文法，该文法能识别哪一类语言。S (L) a L L，S S 2将以下表达式文法G（E）改写成 LL(1) （无左递归的）文法，该文法能识别哪一类语言。EE+T T TT*F F F (E) id 3将以下表达式文法G（L）改写成 LL(1) （无左递归的）的文法，该文法能识别哪一类语言。LE：LEE+T E-T T TT*F T/F T mod F F F (E) idnum 4将以下文法G(S)改写成 LL(1) （无左公共因子的）文法，该文法能识别哪一类语言。S iCtS | iCtSeS | a C b 三、综合题一完成分析以下文法G 的 LL（1）预测分析器（语法分析器）的构造。（1）L E;L|（2）E TE （3）E +TE|-TE| （4）T FT （5）T *FT|/FT|mod FT| （6）F (E)|id|num 1给出或画出预测分析器模型的组成；2构造预测分析表，FIRST（A）和 FOLLOW （A）如下：FIRST(F) = ( id num FIRST(T) = * / mod FIRST(T) = ( id num FIRST(E) = + - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 7 页 - - - - - - - - - 4 FIRST(E) = ( id num FIRST(L) = ( id num FOLLOW(L) = # FOLL0W(E) = ) ; FOLLOW(E) = ) ; FOLLOW(T) = + - ; ) FOLLOW(T) = + - ; ) FOLLOW(F) = + - * / mod ) ; 3给出驱动器算法的伪代码，令ip 指向 #中的第一个终结符，top 指向文法开始符号S; 4填表给出用此分析器分析句子id+id*id; # 的过程。5填表给出用此分析器分析句子id+id*;# 的过程。第三章 & 第五章一、综合题一有文法G：（1）EE+T （2）ET （3）TT*F （4）TF （5）F(E) （6）Fi 表 1是 LR 分析表，以下程序是驱动器算法，loop s := top; a := ip; case actions，a is shift s: push(a); push(s); next(ip); reduce by A: pop(2*|); s := top; push(A); push(goto(s，A); accept: return; others: error; end case; end loop1完成表 2 中 LR 分析器利用LR 分析表和驱动器对输入串i*i+i进行分析的过程：写出栈中的内容和动作类型（移进或归约，若为移进请指出转向状态，若为归约请指出归约采用的产生式），如步骤1步骤 3；2若在语法分析同时进行语义分析，请在有语义翻译动作的步骤中标出，无语义翻译动作的步骤中空白，如步骤1步骤 3。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 7 页 - - - - - - - - - 5 表 1 文法 G 的 LR 分析表ACTION GOTO i + * ( ) # E T F 0 s5 s4 1 2 3 1 s6 acc 2 r2 s7 r2 r2 3 r4 r4 r4 r4 4 s5 s4 8 2 3 5 r6 r6 r6 r6 6 s5 s4 9 3 7 s5 s4 10 8 s6 s11 9 r1 s7 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 解答：表 2 步骤栈内容当前输入移进 -规约动作翻译动作1 #0 i*i+i# 移进： s5 2 #0i5 *i+i# 规约： r6（Fi）有语义动作3 #0F3 *i+i# 规约： r4（TF）有语义动作4 5 6 7 8 9 10 11 12 13 14 第六章一填空题1、属性文法是在上下文无关文法的基础上，为每个文法符号配备若干相关的“值”，称为属性，属性与变量一样可以进行计算和传递，属性加工的过程即是语义处理的过程，对文法的每个产生式配备的一组属性的计算规则，叫_，语义分析和中间代码的产生就是根据该规则进行的，在自上而下或自下而上语法分析过程中，在适当的时候进行属性的_或其它语义动作（如查填符号表、_、发布出错信息）就可进行语法制导翻译得到中间代码，这就是_的基本思想。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 7 页 - - - - - - - - - 6 2、文法符号的属性分为两类，_属性用于“自下而上”传递信息，_属性用于“自上而下”传递信息。二 简答题1、简述语法制导翻译的基本思想第七章二、简答题一把下面表达式翻译成（a）语法树（b）有向无环图DAG （c）后缀表达式（d）三地址代码（1）-(a+b)*(b+c) （2）a*(b-c)+ (b-c)*d （3）(a+b)*(c+d)-(a+b+c) 二请根据以下翻译方案写出id1*id2+id3的三地址代码。结合第1 章，综合题的1、编译过程的几个阶段的输入输出及相关技术进行解答。产生式翻译方案（1）A id: =E p=lookup(id.lexeme); if(p!=nil) emit(p, = , E.place); else error; （2）EE1+E2 E.place=newtemp( ); emit(E.place, = ，E1. place, + ，E2. place；) （3）EE1*E2 E.place=newtemp( ); emit(E.place, = ，E1. place, * ，E2. place；) （4）Eid p=lookup(id.lexeme); if(p!=nil) E.place=p; else error; 第八章 -第九章一填空题1、不同的编译程序关于数据空间的存储分配策略会有所不同，_分配策略在编译是对所有数据对象分配固定的存储单元，且在运行是始终保持不变；另外还可采用的分配策略是_分配策略和_分配策略。2、过程一次执行所需局部信息用一块连续的存储区来管理，这块存储区叫_，它由临时数据、名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 7 页 - - - - - - - - - 7 局部数据、机器状态、访问链、控制链、参数和返回值等域构成，不同的语言及同一语言的不同编译器使用的域可能不同，这些域在其中的布局也可能不同，另外 _往往可以取代它们中的一个或多个域。3、编译过程中编译程序需要不断汇集和反复查证出现在源程序中各种名字的属性和特征等有关信息，这些信息通常记录在一张或几张_中。二、简答题：1、C 语言的编译系统应该采用哪种存储分配策略，并简述理由。1、Pascal语言的编译系统应该采用哪种存储分配策略，并简述理由。2、编译系统常见的存储分配策略有几种？它们都适合于什么性质的语言？三、综合题P172 例 6.4 第十章 -第十三章一填空题1、代码优化可在编译的各阶段进行，其中主要的一类是在_代码之前生成的，这类优化不依赖于具体的计算机。2、代码优化可在编译的各阶段进行，有一类是在生成_代码时进行的，这类优化在很大程度上依赖于具体的计算机。目标3、并行编译技术中两个最重要的内容是串行程序的_和_。二简答题：1、简述编译过程中代码优化必须遵循的原则2、对中间代码中基本块的优化和循环优化都是与机器无关的代码优化，请给出2-3 种对中间代码优化的方法。3、与机器无关的代码优化有哪些种类，与机器有关的代码优化有哪些种类，请举例说明。4、目标代码生成的任务是什么？5、目标代码一般有哪几种形式？名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 7 页 - - - - - - - - -