西电21秋编译原理与技术4满分
编译原理与技术模拟试题四一、填空题（20分，每空2分）
在以阶段划分的编译中， 阶段的主要工作是得到语言句子结构并以树的形式表示； 阶段的主要工作是对中间代码进行优化等价变换，以提高代码的执行效率。
答案：语法分析、中间代码优化
解释：编译过程包含词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成，以及符号表管理和出错处理。词法分析阶段是编译过程的第一阶段，这个阶段的任务是对源程序从前到后（从左到右）逐个字符地扫描，从中识别出一个个“单词”符号。词法分析阶段是编译过程的第一阶段，这个阶段的任务是对源程序从前到后（从左到右）逐个字符地扫描，从中识别出一个个“单词”符号。语法分析的任务是在词法分析的基础上，根据语言的语法规则将单词符号序列分解成各类语法单位，如“表达式”、“语句”和“程序”等。如果源程序中没有语法错误，语法分析后就能正确地构造出其语法树。语义分析阶段分析各语法结构的含义，检查源程序是否包含静态语义错误，并收集类型信息供后面的代码生成阶段使用。只有语法和语义都正确的源程序才能翻译成正确的目标代码。中间代码生成阶段的工作是根据语义分析的输出生成中间代码。“中间代码”是一种简单且含义明确的记号系统，可以有若干种形式，它们的共同特征是与具体的机器无关。语义分析和中间代码生成所依据的是语言的语义规则。由于中间代码不依赖于具体机器，此时所作的优化一般建立在对程序的控制流和数据流分析的基础之上，与具体的机器无关。优化所依据的原则是程序的等价变换规则。
可描述语言“每个x后面必然紧跟一个d的xd串”的正规式为 。
答案：(d|xd)*
解释：根据正规式的定义进行构造。
导致NFA不确定性的因素是存在ε转移和 。
答案: 同一状态下识别同一字符的下一状态转移多于一个
解释: 根据定义。
对于上下文无关文法，其终结符只能出现在产生式的 部。
答案: 左
解释: 根据定义。
给定文法G：E→E+T|T T→T*F|F F→-F|n，由该文法产生的句型E+-F*n的句柄为 。
答案：-F
解释：产生句型E+-F*n的分析树如下所示，其中，最左直接短语为句柄。 确定数组元素地址的两个要素为首地址和相对首地址的 ，在上述两个要素中，不同的内存映射方式（如以行为主或以列为主）会使得同一个数组元素的 不同。
答案：偏移量、偏移量（或地址）
解释：确定数组元素地址的两个因素是数组的首地址和相对于首地址的偏移量。
现有程序设计语言通常允许相同名字的变量出现在不同作用域中，编译器通常采用 原则确定程序中名字的作用域，为实现这一原则，当符号表中存在相同名字的符号信息时，符号表应使用 结构来保存符号信息，以确保能查找到正确的符号。
答案: 最近嵌套、栈
解释: 根据定义。二、单选题（10分，每空2分）
2.1 编译过程中 阶段不是必需的。
A. 语法分析 B. 语义分析 C. 代码优化 D. 目标代码生成
答案: C
解释:
编译过程中，代码优化不是必需的，优化是一个编译器的重要组成部分，由于编译器将源程序翻译成中间代码的工作是机械的、按固定模式进行的，因此，生成的中间代码往往在时间上和空间上有较大的浪费。当需要生成高效的目标代码时，就必须进行优化。优化过程可以在中间代码生成阶段进行，也可以在目标代码生成阶段进行。。
2.2不含子串100的所有0、1符号串的正规式是 。
A. 0* (1|10)* B. 1*|0*1 C. 0(01|10)*1 D. 1(10|01)*0
答案: A
解释: 根据正规式的定义进行构造。
2.3 给定文法A→bA|ca， 不是该文法的句子。
A. bbca B. cabb C. ca D. bca
答案: B
解释: 从A开始推导不出cabb。
2.4.源程序是句子的集合， 可以较好地反映句子的结构。
A. 数组 B. 树 C. 完全图 D. 堆栈
答案: B
解释: 句子中各语法成分的关系不是线性的，处理其语义时也有一定的顺序，树结构可以较好地反映句子的结构。
2.5识别上下文无关语言的自动机是 。
A. 下推自动机 B. NFA C. DFA D. 图灵机
答案: A
解释: 文法、语言语自动机的关系如下表所示。
文法
语言
自动机
0型（短语）文法
0型语言（短语结构语言，递归可枚举集）
图灵机
1型文法（CSG）
1型语言（CSL）
线性界线自动机
2型文法（CFG）
2型语言（CFL）
下推自动机
3型（正规）文法
3型语言（正规语言，正规集）
有限自动机
三、简答题（40分，每小题10 分）
1.简述编译器与解释器的主要共同点以及工作方式的差异。
答案：
共同点： 均完成对源程序的翻译。
工作方式的差异：编译器采用先翻译后执行，生成目标代码；解释器采用边翻译边执行，不生成目标代码。
解释：
编译和解释方式是翻译高级程序设计语言的两种基本方式。解释程序也称为解释器，它或者直接解释执行源程序，或者将源程序翻译成某种中间表示形式后再加以执行，运行过程中的控制权在解释器；而编译程序（编译器）则首先将源程序翻译成目标语言程序，然后在计算机上运行目标程序。编译过程包含词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成，以及符号表管理和出错处理。2. 说明 DFA 与 NFA的主要差异。
答案：
DFA为确定有限自动机的缩写，NFA为非确定有限自动机的缩写。DFA是NFA的特例。DFA上没有 ε转移；在DFA的任一状态下，对于任一字符，其下一状态最多仅有一个。
解释：
模式的描述采用正规式，记号的识别工具是有限自动机。不确定的有限自动机（Nondeterministic Finite Automaton, NFA）是一个五元组（5-tuple）：M =（S，∑，move，s0，F），其中
（1） S是有限个状态（state）的集合；
（2） ∑是有限个输入字符（包括ε）的集合；
（3） move是一个状态转移函数，move(si，ch)=sj表示，当前状态si下若遇到输入字符ch，则转移到状态sj；
（4） s0是唯一的初态（也称开始状态）；
（5） F是终态集（也称接受状态集），它是S的子集，包含了所有的终态。
确定的有限自动机（Deterministic Finite Automaton, DFA）是NFA的一个特例，其中：（1）DFA中没有状态具有ε状态转移（ε-transition），即状态转换图中没有标记ε的边； （2） 对每一个状态s和每一个字符a，最多只有一个下一状态。
3. 设&和%为二元运算，~为一元运算，其优先级从高到低依次为~、&、%，结合性为：&和%是左结合，~是右结合。请画出表达式“~a % b & ~c”的语法树，并给出其后缀式。
答案：语法树 后缀式a~bc~&%
解释：
根据前面的说明，对表达式“~a % b & ~c”进行求值时，先对“~a”进行计算，然后计算“~c”，之后是运算符“&”，最后是运算符“%”。
表达式的语法树被定义为具有下述性质的一棵树:
（1） 根与内部节点由表达式中的操作符标记；
（2） 叶子由表达式中的操作数标记；
（3） 用于改变运算优先级和结合性的括弧，被隐含在语法树的结构中。
4.简要说明编译过程中引入中间代码的好处，以及中间代码应具有的特点。
答案：
好处主要有两点，一是便于编译程序的开发和移植；二是便于对代码进行优化处理。
特点有：便于语法制导翻译；既与机器指令的结构相近，又与具体机器无关。
解释：
编译器各阶段的完整输出，均可以被认为是源程序的某种中间表示。本章讨论的是中间代码生成器输出的中间表示，称之为中间代码。
中间代码实际上应起一个编译器前端与后端分水岭的作用。为此要求中间代码具有如下特性，以便于编译器的开发移植和代码的优化。四、 综合题（30分）
4.1 （15分）给定正规式R = (0|1)*1(0|1)
（1）（5分）用Thompson算法构造识别L(R)的NFA N；
（2）（7分）用“子集法”把N确定化（写出完整过程），得到识别L(R)的DFA D；
（3）（3分）如果D不是最简DFA，请找出最简DFA。
答案：
（1）
（2）可详细写出每步的ε-闭包，亦可给出等价的状态转换矩阵。这里使用矩阵表示如下。
最开始计算ε-闭包({0}) = {0,1,2,4,7}，该状态集即为DFA的初态。0
1
{ 0,1,2,4,7 }
{ 3, 6,7,1,2,4 }
{ 5, 8 , 6,7,1,2,4,9, 11 }
{ 3, 6,7,1,2,4}
{ 3, 6,7,1,2,4 }
{ 5, 8 , 6,7,1,2,4,9, 11 }
{ 5, 8 , 6,7,1,2,4,9, 11 }
{ 3, 10, 6,7,1,2,4, 14}
{ 5, 8, 12, 6,7,1,2,4, 9, 11,14 }
{ 3, 10, 6,7,1,2,4, 14}
{ 3, 6,7,1,2,4 }
{ 5, 8 , 6,7,1,2,4,9, 11 }
{ 5, 8, 12, 6,7,1,2,4, 9, 11,14 }
{ 3, 10, 6,7,1,2,4, 14}
{ 5, 8, 12, 6,7,1,2,4, 9, 11,14 }
分别令 A={ 0,1,2,4,7 } , B={ 3, 6,7,1,2,4}, C={ 5, 8 , 6,7,1,2,4, 9, 11 },D={ 3, 10,6,7,1,2,4, 14},
E={ 5, 8, 12, 6,7,1,2,4, 9, 11,14 }，则上述矩阵如下，其中A为初态，D和E为终态：0
1
A
B
C
B
B
C
C
D
E
D
B
C
E
D
E
（3）构造初始划分 Π1 = { {A,B,C} , {D, E} }，
由于A和B不可区分，而C和A/B可区分，因此得到：
Π2 = { {A,B}, {C}, {D, E} }， 由于D和E可区分，得到最终划分：
Π = { {A,B}, {C}, {D}, {E} }
因此可得该DFA的状态转换矩阵为下，其中A为初态，D和E为终态。其状态图如下。
0
1
A
A
C
C
D
E
D
A
C
E
D
E
解释：用算法2.2 Thompson 算法从正规式构造出与其对应的NFA；用子集法（算法2.3）将NFA转换为DFA。其中需要用算法2.4计算状态集T的ε-闭包(T)。
利用状态可区分的概念球最小化DFA。
对于任何两个状态t和s，若从一状态出发接受输入字符串ω，而从另一状态出发不接受ω，或者从t出发和从s出发到达不同的接受状态，则称ω对状态t和s是可区分的。
反方向思考以上定义，设想任何输入序列ω对s和t均是不可区分的，则说明从s出发和从t出发，分析任何输入序列ω均得到相同结果。因此，s和t可以合并成一个状态。4.2（15分）已知某文法G如下所示，其中，S、A、B为非终结符且S为开始符号。
G?: S→AB
A→aAb |ab
B→c |Bc
（1）（10分）拓广该文法并构造其基于LR(0)项目的、识别活前缀的DFA；
（2）（5分）G是SLR(1)文法吗？为什么？
答案：
（1）拓广文法G' = G∪{S'→S}，构造的DFA如下，其中I0为初态，I1为终态：（2）G是SLR(1)的。在状态I4中存在移进/归约冲突，但是FOLLOW(S)={#}，FIRST(c)={c}，两个集合相交为空，故冲突可通过简单向前看一个终结符解决，因此该文法是SLR(1)的。解释：用算法3.9 计算文法基于LR(0)项目的识别活前缀的DFA。当DFA的一个项目集中同时存在：
1．A→β1.β2和B→β.：说明下一步既可以移进又可以归约，引起移进/归约冲突。
2．A→α.和B→β.：说明二者均可以指导下一步分析，引起归约/归约冲突。
解决冲突的方法是简单向前看一个终结符a：
1．对于移进/归约冲突：若FIRST(β2)∩FOLLOW(B)=Φ，冲突可以解决。
2．对于归约/归约冲突：若FOLLOW(A) ∩FOLLOW(B)=Φ，冲突可以解决。
若冲突可以解决，则称其为SLR(1)文法和SLR(1)分析表。否则需要寻求能力更强文法，即寻求新的项目集（LR(1)项目集）。
页:
[1]