西电21秋编译原理与技术5答案
编译原理与技术模拟试题五一、填空（20分，每空2分）1.1高级语言被直接翻译成机器语言或汇编语言的过程称为 ；把汇编语言翻译成机器语言的过程称为 ；把汇编语言翻译成某种高级语言的过程称为 。
答案：编译，汇编，反编译
解释：根据定义。
1.2 语法分析方法分为自上而下和自下而上两类，递归下降分析属于 ，移进-归约方法属于 。
答案：自上而下，自下而上
解释：根据分析过程中分析树的构造方向。
1.3在预测分析器工作时，改变格局的动作中，除了接受（分析成功）和报错，还有
和 。
答案：展开，匹配
解释：预测分析器模拟最左推导的方式产生句子。
1.4 在散列表形式组织的符号表中，通常将每个符号挂在两个链上，其中散列链用来链接所有具有相同hash值的元素，而 链则用来链接所有在同一作用域内的元素。
答案：作用域
解释：根据定义。
1.5在过程（函数）调用中，引用调用传递的是实参的 ，过程内对参数的修改 。
答案：会影响作为实参的变量原来的值
解释：传值方式下，实参与形参各自有独立的存储单元，调用时将实参的值传递给形参，对形参进行的修改与实参无关。引用调用方式下，是将实参的地址传递给形参，对形参所作的修改最后会返回给实参。
二、单选题（10分，每空2分）
2.1程序设计语言可划分为低级语言和高级语言两大类。与高级语言相比，用低级语言开发的程序，其 。
A. 运行效率低，开发效率低 B. 运行效率低，开发效率高
C. 运行效率高，开发效率低 D. 运行效率高，开发效率高
答案：C
解释：在计算机中，低级语言指机器语言和汇编语言。机器语言是计算机可直接识别的二进制指令代码。用机器语言编制出来的程序可读性很差，也难以理解、修改和维护。因此，为了提高程序设计的效率，人们就用容易记忆的符号代替0、1序列来表示机器指令中的操作码和操作数，例如，用ADD表示加法，SUB表示减法等。因此，汇编语言可看作是用助记符表示的机器语言。用低级语言进行程序设计时，需要对机器结构有较多的了解，因此可以在时间上和空间上对程序进行最直接的优化处理，所以用低级语言开发的程序，其运行效率较高，但是开发程序的效率较低，在时间和空间上对程序有严格要求的场合，仍全部或部分地使用低级语言。
2.2 对于正规式(a|b)*abb，属于其所表示正规集的是 。
A. aaabbb B. abab C. bbbaaa D. ababb
答案：D
解释：正规式(a|b)*abb表示的正规集是以abb结尾的a、b构成的字符串。
2.3 已知有文法: G( VT ,VN ,E ,P )：
?P:??E → E + T | T T → T * F | F F → (E)| i
F*F+T是该文法的一个句型，其中， 是句柄。
A. F? B. F*F C. F+T D. F*F+T
答案：A
解释：
采用最左推导方法推导出句型F*F+T的过程及其分析树如下所示。
E => E1 + T1
=> T2 + T1
=> T3*F1 + T1
=> F2*F1 + T1如果在推导的任何一步(其中α、β是句型),都是对α中的最右（最左）非终结符进行替换，则称这种推导为最右（最左）推导。设是文法G的一个句型，即，且满足和，则称δ是句型相对于非终结符A的短语。特别地，如果有，则称δ是句型相对于产生式Ａ→δ的直接短语。一个句型的最左直接短语称为该句型的句柄。
以非终结符为根的子树中所有从左到右排列的叶子就是该非终结符号的短语；只有父子关系的树中所有从左到右排列的叶子为直接短语；树中最左边父子关系树中所有从左到右排列的叶子序列为句柄。
2.4为数组声明a:array中a分配的存储空间的首地址为base_a，且每个数组元素占据一个存储单元。若以行为主存放，数组元素a在存储空间中相对base_a的偏移量是 。
A. 8 B. 9 C. 10 D. 11
答案：B
解释：计算排列在a之前的元素个数即可。
2.5 不属于编译过程中所使用的中间代码形式。
A. 栈和队列 B. 树 C. 三地址码 D. 后缀式
答案：A
解释：常用的中间代码有三地址码（三元式、四元式）、后缀式、树和DAG图等。
三、简答题（40分，每小题10分）
3.1 简述从正规式构造词法分析器的一般方法和过程。
答案：有了正规式和有限自动机的理论基础后，就可以构造出编译程序的词法分析模块。构造词法分析器的一般步骤如下。
（1）用正规式描述语言中的单词构成规则。
（2）为每个正规式构造一个NFA，它识别正规式所表示的正规集。
（3）将构造出的NFA转换成等价的DFA。
（4）对DFA进行最小化处理，使其最简。
（5）从DFA构造词法分析器。
解释：同上。3.2 对于文法G: S→0S1 | 1S0 | 10，请给出句子101010的最左推导的分析树，并指明各句型的句柄。
答案：
S => 1S0 => 10S10 => 101010
分析树：
句型1S0的句柄为1S0，句型10S10的句柄为0S1，句型101010的句柄为10。
解释：对CFG G的句型，分析树被定义为具有下述性质的一棵树。
（1） 根由开始符号所标记；
（2） 每个叶子由一个终结符、非终结符、或ε标记；
（3） 每个内部结点由一个非终结符标记；
（4） 若A是某内部节点的标记，且X1，X2，...，Xn该节点从左到右所有孩子的标记，则A→X1X2...Xn是一个产生式。若A→ε，则标记为A的结点可以仅有一个标记为ε的孩子。
每一直接推导（每个产生式），对应一棵仅有父子关系的子树，即产生式左部非终结符“长出”右部的孩子；分析树的叶子，从左到右构成G的一个句型。若叶子仅由终结符标记，则构成一个句子。3.3 请分别写出在传值调用和引用调用方式下，下面代码的输出结果。
program main(input,output)
procedure f(a,b)
begin
a := a + 1;
b := a * 2 + 1;
end;
begin
x := 5; y := 10;
f(y, x);
print(x,y);
end.
答案：
传值调用：510
引用调用：2311
解释：
传值方式下，实参与形参各自有独立的存储单元，调用时将实参的值传递给形参，对形参进行的修改与实参无关。引用调用方式下，是将实参的地址传递给形参，对形参所作的修改最后会返回给实参。3.4 给定文法G：
S→cAdB A→aC B→b C→cC |ε
（1）计算所有非终结符的FIRST、FOLLOW集合；
（2）构造预测分析表。
答案：
（1）FIRST(C)={c,ε}FIRST(B)={b} FIRST(A)={a} FIRST(S)={c}
FOLLOW(C)={d} FOLLOW(B)={#}FOLLOW(A)={d}FOLLOW(S)={#}（2）预测分析表：a
b
c
d
#
S
cAdB
A
aC
B
b
C
cC
ε
解释：根据计算 FIRST集合和FOLLOW集合的算法进行计算。
通俗地讲，α的FIRST集合就是从α开始可以导出的序列中的开头终结符。而A的FOLLOW集合，就是从开始符号可以导出的所有含A序列中紧跟A之后的终结符。
根据FIRST集合与FOLLOW集合构造预测分析表。应用下述规则:
1. 加入#到FOLLOW(S)，其中，S是开始符号，#是输入结束标记。
2. 若有产生式A→αBβ，则除ε外，FIRST(β)的全体加入到FOLLOW(B)。
3. 若有产生式A→αB或A→αBβ而ε∈FIRST(β)，则FOLLOW(A)的全体加入到FOLLOW(B)。四、综合题（30分）
4.1（15分）某NFA的状态转换矩阵如下表所示（S0是初态，S4、S5是终态）a
b
c
ε
S0
S1
S1
S2,S3
S2
S3
S3
S4
S5
S2
S4
S3
S5
S3
（1）（5分）画出该NFA的状态转换图，列举两个该NFA可以识别的字符串；
（2）（6分）用“子集法”把该NFA确定化为DFA D（写出完整过程）；
（3）（4分）如果D不是最小DFA，请找出其最小DFA D’。答案：
（1）对应的NFA如下图所示：
该NFA可以识别的字符串： acab, abc
（2）确定化过程：
ε-闭包({S0}) = {S0} A
ε-闭包(smove(A, a)) = {S1,S2,S3} B
ε-闭包(smove(A, b)) = { } ε-闭包(smove(A, c)) = { }
ε-闭包(smove(B, a)) = {}
ε-闭包(smove(B, b)) ={S2,S3,S4} C
ε-闭包(smove(B, c)) ={S5} D
ε-闭包(smove(C, a)) = {S2,S3} E
ε-闭包(smove(C, b)) = {S2,S3,S4} = C
ε-闭包(smove(C, c)) = {S5}=D
ε-闭包(smove(D, a)) = {S2,S3} =E
ε-闭包(smove(D, b)) = { } ε-闭包(smove(D, c)) = { }
ε-闭包(smove(E, a)) = {}
ε-闭包(smove(E, b)) ={S2,S3,S4}=C
ε-闭包(smove(E, c)) ={S5}=D
对应的DFA如下图所示：
（3）最小化过程如下：
初始划分为：Π1 = {ABE, CD}
考查状态转移，由于：
m(A,a) = B m(A,b) = - m(B,c) = -
m(B,a) = - m(B,b) = C m(B,c) = D
m(E,a) = - m(E,b) = C m(E,c) = D
因此，B和E不可区分，用B代表{B,E}得到划分Π2 = {AB，CD}
再考查状态转移：
m(A,a) = B m(A,b) = - m(A,c) = -
m(B,a) = - m(B,b) = C m(B,c) = D
因此，A和B可区分，得到划分Π2 = {A，B，CD}
再考查状态转移：
m(C,a) = E m(C,b) = C m(C,c) = D
m(D,a) = E m(D,b) = - m(D,c) = -
因此，C、D是可区分的状态，因此得到最终划分：Πfinal={A，B，C，D}
最小DFA如下图所示：
解释：
用算法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→aA
A→Abc | c
（1）（9分）拓广该文法并构造基于LR(0)项目的、能识别其所有活前缀的DFA。
（2）（6分）该文法是否是LR（0）文法？是否为SLR(1)文法？为什么？答案：
（1） 拓广文法为 G’: S’->S S->aA A->Abc | c，DFA如下：
（2）不是LR（0）， 是SLR（1），因为加粗项目集中存在移进/归约冲突，且 Follow(S) 和 First(bc)不相交，即冲突可通过简单向前看一个终结符解决。解释：
用算法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]