编译原理与技术

课程编号：COM07017北京理工大学2016—2017学年第二学期计算机科学与技术类《编译原理与设计》试卷(2017.06)班级学号姓名成绩** 注意：各题均必须答在试卷上，书写不下可以写在试卷背面。

一．判断题（15分）在下面答题表中填上“√”或“×”。

1.符号串的前缀一定是此符号串的子串。

2.设正规式r对应的正规集合中有m个元素、正规式s对应的正规集合中有n个元素，则正规式rs对应的正规集合中有m×n个元素。

3.NFA的确定化是为了减少有限状态机的状态数。

4.DFA识别的语言一定是一个正规集。

5.一个LR(1)的项目集可以对多个句型的活前缀有效。

6.变量P在点d是活跃的是指P在点d被引用。

7.程序控制流图是无环路有向图。

8.若文法规则存在P P'a，则FIRST(P') = FIRST(P)。

9.C语言的符号表是在可执行程序运行过程中动态维护的。

10.实施循环不变代码外提之前需要进行活跃变量分析。

二、单项选择题 (在下面答题表中填上答案) （20分）1. 编译过程处理的遍数多的优点不包括（）A）编译程序逻辑结构清晰B）减少对主存容量的要求；C）优化准备充分D）便于移植2. 有G(S)={{S, T, F, X}, {a, b}, S, {S→XSX | T T→aFb | bFa F→XFX | X | εX→a | b}}，则下列符号串中不是该文法的句子的是（）A）babb B）aaaab C）aba D）bbbaa3. 不是文法的表示方法的是（）A）BNF B）语法树C）EBNF D）语法图4. 根据N. Chomsky分类法，则下列说法错误的是（）A）正则语言可以用上下文无关文法表示；B）短语文法语言可由图灵机识别；C）线性有界自动机识别的语言可以用上下文无关文法表示；D）下推自动机识别的语言可以用上下文无关文法表示。

5. 下列文法中，（）是算符优先文法。

反编译原理反编译（Decompilation）是指将已经编译的源代码或者机器码转换回人类可读的源代码的过程。

在软件开发和逆向工程的领域中，反编译是一种非常重要的技术，它提供了深入研究和理解现有软件的机会。

反编译器是用于执行反编译过程的工具，它使用一系列算法和技术来将机器代码转换回高级语言代码。

反编译原理包括以下几个关键步骤：1. 识别目标程序的架构：反编译器首先需要确定目标程序的架构，例如x86、ARM或者Java虚拟机等。

根据不同的架构，反编译器会采用不同的解析技术。

2. 分析符号信息：反编译器会尝试识别目标程序中的变量名、函数名以及其他符号信息。

这可以通过分析目标程序的符号表、反汇编代码以及其他元数据来实现。

3. 分析控制流和数据流：反编译器会尝试恢复目标程序中的控制流和数据流。

这可以通过分析源代码和调试信息来实现。

控制流分析可以帮助反编译器恢复函数的控制结构，例如条件语句和循环语句。

数据流分析可以帮助反编译器恢复关键变量的赋值和使用关系。

4. 生成源代码：根据前面的分析结果，反编译器会生成等效的高级语言源代码。

这可以是C、C++、Java等高级语言代码，也可以是类似于伪代码的中间表示形式。

反编译原理的参考内容可以从以下几个方面展开：1. 反汇编和静态分析技术：介绍反汇编和静态分析的基本原理和技术。

包括目标程序的内存布局、汇编语言指令的解析、控制流分析、数据流分析等。

相关参考内容可以包括书籍《反汇编逆向工程-应用的艺术》、论文《Static Control-Flow Analysis for Reverse Engineering》等。

2. 符号恢复技术：介绍如何根据反汇编代码和其他元数据来分析目标程序中的符号信息。

主要包括如何识别函数名、变量名以及其他符号信息。

相关参考内容可以包括书籍《反汇编逆向工程-应用的艺术》、论文《Recovering Symbolic Information from Executables》等。

北京语言大学智慧树知到“计算机科学与技术”《编译原理》网课测试题答案（图片大小可自由调整）第1卷一.综合考核(共10题)1.程序语言的语言处理程序是一种应用软件。

()A.错误B.正确2.语法分析器则可以发现源程序中的()。

A.语义错误B.语法和语义错误C.错误并校正D.语法错误3.数据空间的使用和管理方法分成()。

A.静态存储分配B.栈式动态存储分配C.堆式动态存储分配D.局部存储分配4.通常编译过程分成前端和后端，其中前端包括()，后端包括目标代码生成。

A.语法分析B.语义分析C.中间代码生成D.词法分析5.LR 法是自顶向下语法分析方法。

()A.错误B.正确6.代码外提是把产生的结果独立于循环执行次数的表达式，放到循环的前面。

()A.错误B.正确7.一个句型的句柄一定是文法某产生式的右部。

()A.错误B.正确8.DFA可以通过多条路径识别一个符号串。

()A.错误B.正确9.一个控制流程图可以表示成一个组，它包括()。

A.图中所有结点集B.图中所有有向边集C.首结点D.堆区10.程序设计语言中的布尔表达式只有一个作用，即用做改变控制流语句中的表达式。

()A.错误B.正确第1卷参考答案一.综合考核1.参考答案：A2.参考答案：D3.参考答案：ABC4.参考答案：ABCD5.参考答案：A6.参考答案：B7.参考答案：B8.参考答案：A9.参考答案：ABC10.参考答案：A。

《编译原理》习题参考答案（四）第四章4.1 根据表4.1的语法制导定义，为输入表达式5*（4*3+2）构造注释分析树。

Solution:LE.val =70 nT.val = 70T.val =5 * F.val =14F.val =5 ( E.val =14 )digit.lexval =5 E.val =12 + T.val =2T.val = 12 F.val = 2T.val =4 * F.val =3 digit.lexval =2F.val = 4 digit.lexval = 34.3 为文法→ ( L ) | aSL→ L , S | S( a )写一个语法制导定义，它输出括号的对数。

( b )写一个语法制导定义，它输出括号的最大深度。

Solution:( a ) :Sˊ→S n print ( S.val )S → ( L ) S.val = L .val + 1S → a S.val = 0L →L1 , S L.val = L1.val + S.valL → S L.val = S.val( b ) :Sˊ→S n print ( S.val )S → ( L ) S.val = L .val + 1S → a S.val = 0L →L1 , S L.val = max ( L1.val , S.val )L → S L.val = S.val4.5 给出对表达式求导数的语法制导定义，表达式由+和*作用于变量x和常数组成，如x * ( 3 * x + x * x )，并假定没有任何化简，例如将3 * x 翻译成3 * 1 + 0 * x。

Solution:exp为原表达式的字符串，s为求导后的字符串。

|| 为串联接符E′→ E n print ( E.s )E → E1 + T E.exp = E1.exp || " + " || T.expE.s = E1.s || " + " || T.sE → T E.exp = T.expE.s = T.s T → T1 * FT.exp = T1.exp || " * " || F.expT.s = " ( " || T1.s || " ) " || " * " || F.exp || " + " ||T.exp || " * " || F.s T → F T.exp =F.exp T.s = F. sF → ( E ) F.exp = " ( " || E.exp || " ) " F.s = " ( " || E.s || " ) " F → num F.exp =num.lexmeF.s = " 0 "F → x F.exp = " x "F.s = " 1 "4.6 给出把中缀表达式翻译成没有冗余括号的中缀表达式的语法制导定义。

第十章代码优化某些编译程序在中间代码或目标代码生成之后要对生成的代码进行优化。

所谓优化，实质上是对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加大或占用存储空间少，或两者都有。

优化可在编译的不同阶段进行，对同一阶段，涉及的程序范围也不同，在同一范围内，可进行多种优化。

一般，优化工作阶段可在中间代码生成之后和（或）目标代码生成之后进行。

中间代码的优化是对中间代码进行等价变换。

目标代码的优化是在目标代码生成之后进行的，因为生成的目标代码对应于具体的计算机，因此，这一类优化在很大程度上依赖于具体的机器，我们不做详细讨论。

另外依据优化所涉及的程序范围，又可分为局部优化、循环优化和全局优化三个不同的级别。

局部优化指的是在只有一个入口、一个出口的基本程序块上进行的优化。

循环优化对循环中的代码进行的优化。

全局优化是在整个程序范围内进行的优化。

本章重点：局部优化基本块的DAG表示第一节优化技术简介为了说明问题，我们来看下面这个例子，源程序是：P :=0For I :=1 to 20 doP :=P+A[I]*B[I];经过编译得到的中间代码如图10-1-1所示，这个程序段由B1和B2两个部分组成，B2是一个循环，假定机器按字节编址。

那么，对于这个中间代码段，可进行如下这些优化。

1、删除多余运算（删除公共子表达式）优化的目的在于使目标代码执行速度较快。

图10-1-1中间代码（3）和（6）中都有4＊I的运算，而从（3）到（6）没有对I赋值，显然，两次计算机的值是相等的。

所以，（6）的运算是多余的。

我们可以把（6）变换成：T4 :=T1。

这种优化称为删除多余运算或称为删除公共子表达式。

2、代码外提减少循环中代码总数的一个重要办法是代码外提。

这种变换把循环不变运算，即其结果独立于循环执行次数的表达式，提到循环的前面。

使之只在循环外计算一次，上例中，我们可以把（4）和（7）提到循环外。

经过删除多余运算和代码外提后，代码变成图10-1-2。

《编译原理》总复习-07级第一章编译程序的概述（一）内容本章介绍编译程序在计算机科学中的地位和作用，介绍编译技术的发展历史，讲解编译程序、解释程序的基本概念，概述编译过程，介绍编译程序的逻辑结构和编译程序的组织形式等。

（二）本章重点编译（程序），解释（程序），编译程序的逻辑结构。

（三）本章难点编译程序的生成。

（四）本章考点全部基本概念。

编译程序的逻辑结构。

（五）学习指导引论部分主要是解释什么是编译程序以及编译的总体过程。

因此学习时要对以下几个点进行重点学习：翻译、编译、目标语言和源语言这几个概念的理解；编译的总体过程：词法分析，语法分析、语义分析与中间代码的生成、代码优化、目标代码的生成，以及伴随着整个过程的表格管理与出错处理。

第三章文法和语言课外训练（一）内容本章是编译原理课程的理论基础，主要介绍与课程相关的形式语言的基本概念，包括符号串的基本概念和术语、文法和语言的形式定义、推导与归约、句子和句型、语法分析树和二义性文法等定义、文法和语言的Chomsky分类。

（二）本章重点上下文无关文法，推导，句子和句型，文法生成的语言，语法分析树和二义性文法。

（三）本章难点上下文无关文法，语法分析树，文法的分类。

（四）本章考点上下文无关文法的定义。

符号串的推导。

语法分析树的构造。

（五）学习指导要构造编译程序，就要把源语言用某种方式进行定义和描述。

学习高级语言的语法描述是学习编译原理的基础。

上下文无关文法及语法树是本章学习的重点。

语法与语义的概念；程序的在逻辑上的层次结构；文法的定义，文法是一个四元组：终结符号集，非终结符号集，开始符号、产生式集；与文法相关的概念，字符，正则闭包，积（连接），或，空集，产生式，推导，直接推导，句子，句型，语言，最左推导，最右推导（规范推导）；学会用文法来描述语言及通过文法能分析该文法所描述的语言；语法树及二义性的概念、能通过画语法树来分析一个文法描述的语言是否具有二义性；上下文无关文法的定义和正规文法的定义，能判断一个语言的文法是哪一类文法。

编译原理书籍推荐编译原理作为计算机科学与技术领域的重要基础课程，对于计算机专业的学生来说至关重要。

一本优秀的编译原理教材不仅可以帮助学生深入理解编译原理的基本概念和原理，还可以引导他们掌握编译器的设计与实现方法，提高编程能力和软件开发水平。

在众多编译原理教材中，有几本经典的书籍深受学生和教师的喜爱，下面我将向大家推荐几本优秀的编译原理书籍。

首先推荐《编译原理》（龙书），这是一本经典的编译原理教材，作者是Alfred V. Aho、Monica S. Lam、Ravi Sethi和Jeffrey D. Ullman。

这本书系统地介绍了编译原理的基本概念、词法分析、语法分析、语法制导翻译、运行时环境等内容，覆盖了编译器设计与实现的方方面面。

书中内容通俗易懂，适合初学者阅读，同时也深入浅出地介绍了一些高级的编译原理知识，适合深入学习。

这本书是编译原理领域的经典之作，是学习编译原理的不二选择。

其次，推荐《现代编译原理》（虎书），这是一本由Andrew W. Appel和Jens Palsberg合著的编译原理教材。

这本书在介绍编译原理的基本概念的同时，还特别关注了一些现代编译技术和研究领域的最新进展，如SSA形式、中间代码优化、JIT编译等内容。

书中还通过大量的案例和实例，帮助学生理解和掌握编译器设计与实现的方法和技巧。

这本书在教学实践中被广泛应用，受到了学生和教师的一致好评。

最后，推荐《编译原理及实践》（虎书），这是一本由Keith D. Cooper和Linda Torczon合著的编译原理教材。

这本书在介绍编译原理的基本理论的同时，还特别关注了编译器实现的实践技巧和方法，如词法分析器和语法分析器的设计、符号表管理、类型检查等内容。

书中还通过大量的实例和项目，引导学生动手实践，提高他们的编程能力和软件开发水平。

这本书在教学中被广泛应用，对于培养学生的实际动手能力有着重要的作用。

总的来说，以上这几本书都是编译原理领域的经典之作，无论是在编译原理的理论研究还是在编译器的实际开发中都具有重要的参考价值。

北京语言大学智慧树知到“计算机科学与技术”《编译原理》网课测试题答案（图片大小可自由调整）第1卷一.综合考核(共15题)1.非终结符可以有综合属性，但不能有继承属性。

()A.错误B.正确2.栈式存储分配策略是指运行时每当进入一个过程，就在栈顶为该过程分配所需的数据空间，当一个过程工作完毕返回时，它在栈顶的数据空间也释放。

()A.错误B.正确3.与正规表达式(0|1)*000等价的正规文法是G[Z]:Z→0Z|IZ|0A，A→0B，B→0。

()A.错误B.正确4.通常编译过程分成前端和后端，后端是由这样一些阶段组成这些阶段的工作主要依赖于源语言而与目标机无关。

()A.错误B.正确5.DFA可以通过多条路径识别一个符号串。

()A.错误B.正确6.一个句型的句柄一定是文法某产生式的右部。

()A.错误B.正确7.全局优化是在整个程序范围内进行的优化。

()A.错误B.正确8.综合属性是用于“自上而下”传递信息。

()A.错误B.正确9.自顶向下分析包括请确定分析和不确定分析。

()A.错误B.正确10.逆波兰表示法表示表达式时无需使用括号。

()A.错误B.正确11.一个多遍的编译程序可以较之一遍的编译程序少占内存。

()A.错误B.正确12.静态数据区用于可变数据以及管理过程活动的控制信息。

()A.错误B.正确13.出口语句是一种结构化的方式跳出循环而设置的语句，它的作用是引起外层循环的终止。

()A.错误B.正确14.在编译过程中，语法分析器的任务是()。

A.分析单词是怎样构成的B.分析单词串是如何构成语句和说明的C.分析语句和说明是如何构成程序的D.分析程序的结构15.符号表中的信息栏中登记了每个名字的属性和特征等有关信息，如类型、种属、所占单元大小、地址等等。

()A.错误B.正确第2卷一.综合考核(共15题)1.语法分析器则可以发现源程序中的()。

A.语义错误B.语法和语义错误C.错误并校正D.语法错误2.若一个文法中存在某个句子，它有两个不同的最左(最右)推导，则这个文法是二义。

北京语言大学智慧树知到“计算机科学与技术”《编译原理》网课测试题答案（图片大小可自由调整）第1卷一.综合考核(共15题)1.一个LR分析器由3个部分组成，其中分析表或分析函数，也可以称为驱动程序。

()A.错误B.正确2.递归下降分析法是自顶向下分析方法。

()A.错误B.正确3.循环优化的重要技术有()。

A.代码外提B.删除归纳变量C.强度削弱D.局部优化4.出口语句是一种结构化的方式跳出循环而设置的语句，它的作用是引起外层循环的终止。

()A.错误B.正确5.所谓数据空间的分配，本质上看，是将程序中的每个名字与一个存储位置关联起来，该存储位置用以容纳名字的值。

()A.错误B.正确6.堆栈区用以存放编译时能确定所占用空间的数据。

()A.错误B.正确7.逆波兰表示法表示表达式时无需使用括号。

()A.错误B.正确8.一个LR分析器由()组成。

A.驱动程序B.分析函数C.分析栈D.向前搜索符集合9.通常编译过程分成前端和后端，后端是由这样一些阶段组成这些阶段的工作主要依赖于源语言而与目标机无关。

()A.错误B.正确10.一个确定有穷自动机有且只有一个终态。

()A.错误B.正确11.综合属性是用于“自上而下”传递信息。

()A.错误B.正确12.对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。

()A.错误B.正确13.过程调用的实质是把程序控制转移到子程序(过程段)。

()A.错误B.正确14.非终结符可以有综合属性，但不能有继承属性。

()A.错误B.正确15.若项目集Ik含有A-α·，则在状态k时，仅当面临的输入符号a∈FOLLOW(A)时，才采取“A-α·”动作的一定是()。

LR文法B.LR(0)文法C.LR(1)文法D.SLR(1)文法第2卷一.综合考核(共15题)1.语法分析器则可以发现源程序中的()。

A.语义错误B.语法和语义错误C.错误并校正D.语法错误2.数据空间的使用和管理方法分成()。

长风破浪会有时，直挂云帆济沧海。

住在富人区的她
全文为Word 可编辑，若为PDF 皆为盗版，请谨慎购买！
北京语言大学智慧树知到“计算机科学与技术”《编译原
理》网课测试题答案
（图片大小可自由调整） 第1卷
一.综合考核(共10题)
1.自底而上语法分析方法的主要问题是候选式的选择。

()
A.错误
B.正确
2.自顶向下分析包括请确定分析和不确定分析。

() A.错误 B.正确
3.编译和运行是两个独立分开的阶段。

() A.错误 B.正确
4.所有的编译程序都需要生成中间代码。

() A.错误 B.正确
5.正则文法其产生式为A-a ，A-Bb ，A ，B∈VN，a 、b∈VT。

() A.错误 B.正确
6.非终结符可以有综合属性，但不能有继承属性。

() A.错误 B.正确
7.代码外提是把产生的结果独立于循环执行次数的表达式，放到循环的前面。

() A.错误 B.正确
8.编译程序是对高级语言程序的解释执行。

()
A.错误
B.正确
9.在编译方式下执行源程序，易于查错，在程序执行中可以修改程序，但执行效率低。

() A.错误 B.正确
10.两个正规集相等的必要条件是他们对应的正规式等价。

() A.错误
B.正确
第1卷参考答案
一.综合考核
1.参考答案：A
2.参考答案：A
3.参考答案：B
4.参考答案：A
5.参考答案：A
6.参考答案：A
7.参考答案：B
8.参考答案：A
9.参考答案：A
10.参考答案：A。

编译原理》课程设计一、教学目标本课程旨在让学生了解编译原理的基本概念、方法和技巧，掌握源程序转换为目标程序的基本过程，包括词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等。

通过本课程的学习，学生应能理解并应用编译原理的基本知识解决实际问题，培养分析问题和解决问题的能力。

具体的教学目标如下：1.知识目标：（1）了解编译原理的基本概念和任务。

（2）掌握源程序转换为目标程序的基本过程，包括词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成。

（3）熟悉各种编译器设计和实现技术。

2.技能目标：（1）能够使用编译原理的基本方法分析并解决实际问题。

（2）具备编写简单编译器的能力。

3.情感态度价值观目标：（1）培养学生对编译原理的兴趣，认识到编译原理在计算机科学中的重要性。

（2）培养学生团队合作、创新和持续学习的精神。

二、教学内容本课程的教学内容主要包括以下几个部分：1.编译原理的基本概念和任务。

2.源程序转换为目标程序的基本过程，包括词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成。

3.各种编译器设计和实现技术。

4.编译原理在实际应用中的案例分析。

5.编译原理相关的研究动态和发展趋势。

三、教学方法为了提高教学效果，本课程将采用多种教学方法，包括：1.讲授法：教师讲解编译原理的基本概念、方法和技巧，引导学生掌握知识要点。

2.讨论法：学生针对编译原理中的关键问题进行讨论，培养学生的思考和表达能力。

3.案例分析法：分析编译原理在实际应用中的案例，帮助学生更好地理解编译原理的应用价值。

4.实验法：安排学生进行编译器设计的实验，提高学生的实际操作能力和创新能力。

四、教学资源为了支持本课程的教学，我们将准备以下教学资源：1.教材：《编译原理》，为学生提供系统、全面的学习资料。

2.参考书：提供相关领域的经典著作和最新研究成果，供学生拓展阅读。

3.多媒体资料：制作课件、教学视频等，丰富教学手段，提高教学效果。