西电21秋编译原理与技术2答案
编译原理与技术模拟试题二一、填空题（20分，每空2分）
1.1 LR(1)分析法中，L的含义是 ，R的含义是 。
答案：自左至右扫描输入串，最右推导的逆
解释：若为文法G构造的移进-归约分析表中不含多重定义的条目，则称G为LR(k)文法，分析器被称为是LR(k)分析器，它所识别的语言被称为LR(k)语言。L表示从左到右扫描输入序列，R表示逆序的最右推导，k表示为确定下一动作向前看的终结符个数，一般情况下k<=1。当k=1时，简称LR。
1.2源程序经过编译后产生的程序称为 。
答案：目标程序
解释：源程序经过编译后产生的程序称为目标程序。
1.3词法分析的输出由 和 两部分组成。
答案：单词种别，单词的值
解释：根据构词规则识别称为源程序的输入序列，称为词法分析。词法分析阶段是编译过程的第一阶段，这个阶段的任务是对源程序从前到后（从左到右）逐个字符地扫描，从中识别出一个个“单词”符号。“单词”符号是程序设计语言的基本语法单位，如关键字（或称保留字）、标识符、常数、运算符和分隔符（如标点符号、左右括号）等。词法分析程序输出的“单词”常以二元组的方式输出，即单词种别和单词自身的值。
1.4文法G：S→AB, A→aA|ε, B→bBc|bc描述的语言L(G)= 。
答案：｛ambkck | m>=1,k>=0｝
解释：通过推导进行分析。
1.5允许用户随意地动态申请与释放内存空间应采用 存储分配技术。
答案：堆
解释：编译器怎样对存储空间进行组织和采用什么样的存储分配策略，很大程度上取决于程序设计语言中所采用的机制。编译器具体实现时，根据语言机制的特性，采用静态分配策略、栈分配策略和堆分配策略三种方式的其中若干种。 静态分配策略是指编译时安排所有数据对象的存储，即绑定是静态确定的；栈分配策略是指按栈的方式管理运行时的存储；堆分配策略是指在运行时根据要求从堆数据区动态地分配和释放存储。
1.6一个文法产生的_______________________称为该文法的语言。
答案：句子的全体
解释：由CFG G所产生的语言L(G)被定义为: L(G) = { ω┃S=+>ω and ω∈T* }，
L(G)称为上下文无关语言（Context Free Language,CFL），ω称为句子。若S=*>α，α∈(N∪T)*，则称α为G的一个句型。一个文法产生的句子的全体称为该文法的语言。
1.7语义错误可分为静态语义错误和动态语义错误，“运算符与运算对象的类型不一致”属于______________错误，“无穷递归”属于______________错误。
答案：静态语义，动态语义
解释：源程序中可能出现的错误分为两类：语法错误和语义错误。语法错误是指语法结构出错，如少分号、begin/end不配对等；静态语义错误是编译时可发现的语义错误，如类型不一致、参数不匹配等；动态语义错误（逻辑错误）是运行时才能发现的语义错误，如无穷递归、变量为零时作除数等。大多数错误的诊断和恢复集中在语法分析阶段，一个原因是大多数错误是语法错误，另一个原因是语法分析方法的准确性，它们能以非常有效的方法诊断语法错误。在编译的时侯，想要准确地诊断语义或逻辑错误有时是很困难的。二、单选题（10分，每空2分）
2.1编译程序是对______。
A. 汇编语言的翻译 B. 高级语言的解释执行
C. 机器语言的执行 D. 高级语言的翻译
答案：D
解释：根据定义。
2.2一个文法产生的语言是指 。
A. 从开始符号出发推导的所有符号串的集合
B. 所有终结符和非终结符形成的集合
C. 所有短语构成的集合
D. 该文法产生的句子的集合
答案：D
解释：根据定义。
2.3函数（或过程）调用时， 。
A. 值调用方式下将实参的右值传递给形参，引用调用方式下将实参的左值传递给形参
B. 值调用方式下将实参的左值传递给形参，引用调用方式下将实参的右值传递给形参
C. 值调用方式下将形参的右值传递给实参，引用调用方式下将形参的左值传递给实参
D. 值调用方式下将形参的左值传递给实参，引用调用方式下将形参的右值传递给实参
答案：A
解释：根据程序语言提供的调用机制，值调用方式下将实参的右值传递给形参，引用调用方式下将实参变量的左值（地址）传递给形参。
2.4用来描述控制进入和离开活动方式的树结构被称为 。
A. 语法树 B. 分析树 C. 活动树 D. 嵌套关系树
答案：C
解释：用来描绘控制进入和离开活动方式的树结构被称为活动树，在活动树中：①每个结点代表过程的一个活动；②根代表主程序的活动；③结点a是结点b的父亲，当且仅当控制流从a的活动进入b的活动；④结点a处于结点b的左边，当且仅当a的生存期先于b的生存期。
2.5 是与规范归约（最左归约）互逆的一个过程。
A. 最左推导 B. 最右推导 C. 词法分析 D. 语义分析
答案：B
解释：最左归约的逆过程是一个最右推导，分别称最右推导和最左归约为规范推导和规范归约。三、简答题（40分，每小题10分）
3.1 （10分）对下述C++程序，(a) 指出各参数的传递方式； (b)给出程序的执行结果。
void f(int a, int &b, int &c){c=c+10; b=a*b+c;}
void main()
{ int x=10, y=25, z=0, t=0;
z=x+y*10;
f(x+y,x,z); cout << "1：" << x;
t=x+y;
f(t,x,z); cout << " 2：" << x << endl;
}
答案：
（a）参数a采用传值方式，参数b和c采用传引用方式
（b）1：620 2：400180
解释：根据程序语言提供的调用机制，值调用方式下将实参的右值传递给形参，被调用函数运行结束后，不会将形参变量的值再传回去；而在引用调用方式下将实参变量的左值（地址）传递给形参，在被调用函数中对通过间接方式，借助于形参变量实现对实参变量的修改。
3.2 （10分）请简要说明进行自上而下的语法分析时，文法中为什么不能有左递归和公共左因子。
答案：进行自上而下的语法分析时，若存在左递归，则可能在分析某些句子时陷入死循环；若存在公共左因子，则可能因为虚假匹配导致需要回溯，从而降低分析效率。
解释：自上而下分析从S开始，进行最左推导，直到得到一个合法的句子或发现一个非法结构。在推导的过程中试图用一切可能的方法，自上而下、从左到右为输入序列建立分析树。分析是一种试探的过程，是反复使用不同产生式谋求与输入序列匹配的过程。若存在左递归，则可能在分析某些句子时陷入死循环；若存在公共左因子，则可能因为虚假匹配导致需要回溯，从而降低分析效率。
3.3（10分）举例说明下述文法G是二义的。有哪些方法可以消除文法的二义性。
G：S→aA|Bb A→bA|ε B→a
答案：若文法G对同一个句子产生不止一棵分析树，则称G是二义的。
以句子“ab“为例，其分析树可有如下两种形式：
即句子“ab”存在不同的最左推导S => aA => abA => ab 和 S => Bb => ab，因此文法G是二义的。
消除文法二义性的方法主要有两种：一是改写文法为非二义的：二是规定优先级和结合性，限制分析的每一步仅有唯一选择。
解释：根据定义。
3.4（10分）
给出语句while (x<0) do if (x<y) then x:= y+z的中间代码序列。
答案：
101if x<0 goto 103
102goto 108
103if x<y goto105
104goto 101
105t1 = y + z
106x = t1
107goto 101
108
解释：根据循环语句和选择语句的语义处理。四、综合题（30分）
4.1（15分）设有正规式r=(a|ba)*，试：
（a）（5分）用自然语言简要叙述该自动机所识别的语言的特点，列举三个它可识别的串。
（b）（10分）构造识别该正规集的NFA和DFA（要有计算过程）。
答案：
（a）正规式r=(a|ba)*所表示语言的特点是b不能连续出现，即只要出现字符b，则其后必然出现至少一个a。
（b）识别正规式r=(a|ba)*所表示语言的NFA如下图所示：
ε_闭包({0}) = {0,3} 记为A
ε_闭包(smove(A,a)) = {1,3,0} 记为B
ε_闭包(smove(A,b)) = {2} 记为C
ε_闭包(smove(B,a)) = {0,1,3} = B
ε_闭包(smove(B,b)) = {2} = C
ε_闭包(smove(C,a)) = {3,0} 记为D
ε_闭包(smove(C,b)) = {}
ε_闭包(smove(D,a)) = {1,3,0}= B
ε_闭包(smove(D,b)) = {2}= C
DFA如下图所示
图中状态A，B，D是等价的，因此最小化DFA如下图所示：
解释：根据正规式的定义和运算符号的含义进行分析。
令Σ是一个有限字母表，则Σ上的正规式及其表示的集合递归定义如下:
1. ε是正规式，它表示集合L(ε)={ε}；
2. 若a是Σ上的字符，则a是正规式，它表示集合L(a)={a}。
3. 若正规式r和s分别表示集合L(r)和L(s)，则
（a） r|s是正规式，表示集合L(r)∪L(s)，
（b） rs是正规式，表示集合L(r)L(s)，
（c） r*是正规式，表示集合(L(r))*，
（d）(r)是正规式，表示的集合仍然是L(r)。 （加括弧改变优先级、结合性）
可用正规式描述的语言称为正规语言或正规集。
用算法2.2 Thompson 算法从正规式构造出与其对应的NFA；用子集法（算法2.3）将NFA转换为DFA。其中需要用算法2.4计算状态集T的ε-闭包(T)。
4.2 （15分）对于文法
S→SaA | bA
A→Ac | d | ε
(a)（4分）计算非终结符S和A的FIRST集和FOLLOW集；
(b)（6分）构造识别该文法活前缀的DFA；
(c)（5分）该文法是否为LR(0)文法？为什么？ 是否为SLR(1)文法，为什么？
答案：
(a)FIRST(S) = {b} FIRST(A) = {d, ε}
FOLLOW(S) = {a, #} FOLLOW(A) = {a,c,#}
(b) 识别该文法活前缀的DFA如下图所示
(c) 该文法不是LR(0)文法，存在移进－归约冲突；是SLR(1)，冲突可解决。
解释：
（a）根据计算 FIRST集合和FOLLOW集合的算法进行计算。通俗地讲，α的FIRST集合就是从α开始可以导出的序列中的开头终结符。而A的FOLLOW集合，就是从开始符号可以导出的所有含A序列中紧跟A之后的终结符。根据计算 FIRST集合和FOLLOW集合的算法进行计算。
（b）用算法3.9 计算文法基于LR(0)项目的识别活前缀的DFA。
（c）当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]