下载文档原格式
课程编号：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。
编译原理与技术
编译原理与技术是计算机科学领域的一门重要课程，它研究的是如
何将高级程序语言转化为目标机器能够执行的机器语言的过程。
本文
将介绍编译原理与技术的基本概念、主要原理和常见技术，并探讨其
在计算机科学领域的应用。
一、编译原理与技术的基本概念
编译原理与技术是计算机科学中研究如何将高级语言程序转换为机
器语言程序的一门学科。
它的主要任务是设计并实现一个编译器，将
高级语言程序转化为目标机器能够执行的机器语言程序。
编译器是由
词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代
码生成等阶段组成。
1. 词法分析
词法分析是编译器中的第一步，它将源程序中的字符序列转化为一
个个的单词符号。
单词符号是代码的最小单位，包括保留字、标识符、常量、运算符等。
2. 语法分析
语法分析是将词法分析得到的单词符号序列按照语法规则进行分析
和处理，生成语法树。
语法树表示了程序的结构和语义，便于后续的
语义分析和中间代码生成。
3. 语义分析
语义分析是在语法树的基础上进行类型检查和语义检查，确保程序在语义上是正确的。
它还包括符号表的管理和语义信息的传递。
4. 中间代码生成
中间代码生成是将源程序转化为一种中间表示形式的过程。
中间代码是一种抽象的低级语言，与源语言和目标语言无关，便于后续的代码优化。
5. 代码优化
代码优化是对中间代码进行优化和改进，使得执行效率更高、消耗更少的资源。
常见的优化技术包括常量传播、死代码消除、循环展开等。
6. 目标代码生成
目标代码生成是将优化后的中间代码转化为目标平台的机器代码。
目标代码依赖于目标平台的体系结构和指令集。
二、编译原理与技术的主要原理
编译原理与技术的主要原理包括自顶向下分析、自底向上分析和语法制导翻译。
1. 自顶向下分析
自顶向下分析是一种自上而下的语法分析方法，从开始符号开始展开，不断向下扩展，直到匹配输入符号串。
常见的自顶向下分析方法有LL(1)文法和递归下降分析。
2. 自底向上分析
自底向上分析是一种自下而上的语法分析方法，通过反复归约产生式，将输入符号串归约为开始符号。
常见的自底向上分析方法有LR(0)文法和LR(1)文法。
3. 语法制导翻译
语法制导翻译是一种将语义信息嵌入到语法定义中的翻译方法。
它通过语法规则的属性和继承传递机制来实现语义信息的传递和计算。
三、编译原理与技术的常见技术
编译原理与技术涉及的技术非常广泛，下面介绍其中的一些常见技术。
1. 正则表达式与有限自动机
正则表达式和有限自动机是词法分析的基础。
正则表达式描述了字符串匹配的规则，有限自动机通过有限状态和转移函数来描述字符串的有限状态。
2. 上下文无关文法与LR分析
上下文无关文法是语法分析的基础。
它用产生式来描述语言的句子结构，通过LR分析方法进行句子的分析和归约。
3. 语义分析与类型检查
语义分析和类型检查是确保程序语义正确的重要环节。
它们通过建立符号表、类型推导和语义规则的检查来保证程序的正确性。
4. 中间代码优化与生成
中间代码优化是提高程序执行效率和减少资源消耗的重要手段。
常
见的中间代码优化技术有常量传播、死代码消除、循环展开等。
中间
代码生成是将中间表示翻译为目标代码的过程。
四、编译原理与技术的应用
编译原理与技术在计算机科学领域有着广泛的应用。
下面列举一些
常见的应用领域。
1. 编程语言的设计与实现
编译原理与技术为编程语言的设计与实现提供了基础和指导。
它帮
助语言设计者定义语言的语法和语义，并实现相应的编译器和解释器。
2. 虚拟机和解释器的实现
编译原理与技术为虚拟机和解释器的实现提供了理论和方法。
通过
编译原理与技术的研究，可以设计和实现高效的虚拟机和解释器，提
高程序的执行效率。
3. 操作系统的开发
编译原理与技术在操作系统的开发中也起着重要的作用。
操作系统
的内核和驱动程序一般使用汇编语言或者C语言编写，需要通过编译
原理与技术来将高级语言转化为目标机器能够执行的机器语言。
4. 嵌入式系统和芯片设计
嵌入式系统和芯片设计也离不开编译原理与技术的支持。
通过编译
原理与技术的研究，可以设计和实现嵌入式系统和芯片的编译器和优
化器，提高系统的性能和资源利用率。
总结：
编译原理与技术是计算机科学中的一门重要课程，它研究的是如何
将高级程序语言转化为目标机器能够执行的机器语言的过程。
本文介
绍了编译原理与技术的基本概念、主要原理和常见技术，并探讨了其
在计算机科学领域的应用。
编译原理与技术在编程语言设计与实现、
虚拟机和解释器的实现、操作系统的开发以及嵌入式系统和芯片设计
等方面都有着广泛的应用。
通过不断深入研究和学习编译原理与技术，我们可以提高程序的执行效率和性能，为计算机科学的发展做出贡献。
