西电21秋编译原理与技术3
编译原理与技术模拟试题三一、填空题（20分，每空2分）
1.1 和 是编译程序各阶段都涉及到的工作。
答案: 出错处理，符号表管理
解释: 编译过程包含词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成，以及符号表管理和出错处理。其中，符号表管理和出错处理是编译程序各阶段都涉及到的工作。
1.2用LR方法实现语法分析时，典型的操作有__________、__________、接受和报错。
答案: 移进，归约
解释: 移进-归约是实现LR分析的一般方法，典型的操作有移进、归约、接受和报错。
1.3一个上下文无关文法（N，T，P，S）的四个组成部分是终结符集合N、非终结符集合T、 和 。
答案: 产生式集合，开始符号
解释:根据定义。
1.4已知数组M以行为主序存放，如果每个元素占4个存储单元，且起始地址为a，则元素M的地址是__________。数组元素的地址计算公式由两部分组成，一部分是不变部分，它在_________时确定；另一部分是可变部分，它在________时确定。
答案: a+120，编译，运行
解释: 计算排列在M之前的元素个数即可。计算数组元素的地址时，计算公式由两部分组成，一部分是不变部分，与数组的维数和每维的大小有关，编译时即可确定其值；另一部分是可变部分，与下表变量的值有关，在程序运行时才能确定。
1.5 表达式(a+b)*c-d的逆波兰(后缀)表达式为 ___________________________。
答案: ab+c*d-
解释：从表达式的求值过程考虑。逆波兰式中，操作符在前，操作数紧随其后，无需用括号限制运算的优先级和结合性。运算符的书写顺序就是处理顺序，中缀表达式要根据运算符的优先级和结合性进行处理。二、单选题（10分，每空2分）
2.1 生成中间代码所依据的是__________。
A. 语法规则 B. 词法规则 C. 语义规则 D. 等价变换规则
答案：D
解释：中间代码实际上应起一个编译器前端与后端分水岭的作用。为此要求中间代码具有便于语法制导翻译、既与机器指令的结构相近又与具体机器无关的特性，以便于编译器的开发移植和代码的优化。生成中间代码依据的是等价变换规则。
2.2 一个句型中的最左________称为该句型的句柄。
A. 短语 B. 直接短语 C. 非终结符号 D. 终结符号
答案：B
解释：根据定义。
2.3 给定文法A→bA|cc，________是该文法的句子。
A. ccbc B. bcbc C. cbcb D. bbcc
答案：D
解释：根据句子的定义和推导进行判断。
2.4 程序设计语言中大多数的语法现象可用Chomsky的________文法表示。
A. 0型（短语结构文法） B. 1型（上下文有关文法）
C. 2型（上下文无关文法） D. 3型（正规文法）
答案：C
解释：根据定义。
2.5 有限状态自动机可以识别的语言为________。
A. 上下文有关语言 B. 上下文无关语言
C. 短语文法定义的语言 D. 正规文法定义的语言
答案：D
解释：文法、语言语自动机的关系如下表所示。
文法
语言
自动机
0型（短语）文法
0型语言（短语结构语言，递归可枚举集）
图灵机
1型文法（CSG）
1型语言（CSL）
线性界线自动机
2型文法（CFG）
2型语言（CFL）
下推自动机
3型（正规）文法
3型语言（正规语言，正规集）
有限自动机
三、简答题（40分，每小题10分）
3.1 请列举三种常用的中间代码？采用中间代码有什么好处？
答案： 常用的中间代码：三地址码，后缀式，DAG图。 中间代码的特点是与具体机器（指令系统）无关； 采用中间代码可以明确区分前端与后端；便于优化和移植。
解释：编译器各阶段的完整输出，均可以被认为是源程序的某种中间表示。本章讨论的是中间代码生成器输出的中间表示，称之为中间代码。中间代码实际上应起一个编译器前端与后端分水岭的作用。为此要求中间代码具有如下特性，以便于编译器的开发移植和代码的优化：（1）便于语法制导翻译；（2）既与机器指令的结构相近，又与具体机器无关。3.2对下述C/C++程序，(a) 指出调用函数testfunc 时各参数的传递方式；(b) 给出程序的执行结果。
void testfunc(int &a, int &b, int c){a = b - c; c = c+10; b = a*b+c;}
int main()
{ int x = 1, y = 2, z = 3;
testfunc(y,x,z);
cout << "x = " << x << "y = " << y << "z = " << z << endl;
return 0;
}
答案：调用函数testfunc 时，y和x与a和b间传引用，z和c间传值
x = 11 y = -2 z = 3
解释：传值方式下，实参与形参各自有独立的存储单元，调用时将实参的值传递给形参，对形参进行的修改与实参无关。引用调用方式下，是将实参的地址传递给形参，对形参所作的修改最后会返回给实参。3.3 简述拉链与回填技术的基本思想。
答案：拉链与回填技术的基本思想是在转移地址未确定时，将所有转向相同地址的三地址码拉链；当转移地址确定后，沿所拉的链将确定的地址回填到每个三地址码中。从而达到一遍分析确定所有转移地址的目的。
解释：翻译方案需要解决的两个问题：① 如何实现表达式的真、假出口；② 如何在语法分析的同时正确生成三地址码序列，即所有的转向均可确定。换句话讲，设计一种什么样的翻译方案，使得仅对分析树进行一次遍历（LR分析中就是对分析树的一次自下而上的遍历）即可生成所需的中间代码序列。解决这两个问题的方法就是拉链与回填。3.4设有文法G：S→aBc|bAB,A→aAb|b, B→b|ε。
(a) 计算非终结符S、A、B的FIRST和FOLLOW集合；
(b) 该文法能否推导出baabbb，若能，写出其分析树，否则说明原因。
答案：
(a) FIRST(B) = {b, ε} FIRST(A) = {a, b} FIRST(S) = {a, b}
FOLLOW(S) = {#} FOLLOW(A) = {b} FOLLOW(B) = {c, #}
(b) 可以推导出baabbb
解释：根据计算 FIRST集合和FOLLOW集合的算法进行计算。通俗地讲，α的FIRST集合就是从α开始可以导出的序列中的开头终结符。而A的FOLLOW集合，就是从开始符号可以导出的所有含A序列中紧跟A之后的终结符。
最左推导baabbb的过程为S => bAB => baAbB => baaAbbB => baabbbB =>baabbb四、综合题（30分）
4.1（15分）有NFA N如下图所示。
(a) 求出N的最小DFA D； (b) 给出N所识别语言的正规式r。
答案：
(a) 确定化：
{1} 记为A，初态
smove(A, a) = {2} 记为B
smove(B, a) = {3，4} 记为C，终态
smove(B, b) = {2}
smove(C, a) = {2}
如下图所示：
它已经是最小DFA。
(b) r=a(b|aa)*a，它所描述的语言是由a开始和结尾的、偶数个a组成的a、b串。
解释：
用用子集法（算法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和语法制导翻译如下：
(1) V → id {var_no:=var_no+1;}
(2) |id(E) {arr_no:=arr_no+1;}
(3) E → E + V {exp_no:=exp_no+1;}
(4) | V {exp_no:=exp_no+1;}
(a) 给出识别该文法活前缀的DFA；
(b) 若语义变量var_no、arr_no和exp_no的初值均为0，请给出分析句子id(id+id(id))之后它们各自的值；答案：
(a) 识别该文法活前缀的DFA如下图所示
(b) 句子id(id+id(id))分析树
var_no = 2 arr_no = 2 exp_no = 3
解释：
（a）用算法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)项目集）。
（b）根据分析树和语法制导翻译方案计算。
语义变量var_no、arr_no和exp_no的初值均为1。
第1次归约：V → id，语义处理为var_no:=var_no+1；var_no的值变为1。
第2次归约：E → V，语义处理为exp_no:=exp_no+1；exp_no的值变为1。
第3次归约：V → id，语义处理为var_no:=var_no+1；var_no的值变为2。
第4次归约：E → V，语义处理为exp_no:=exp_no+1；exp_no的值变为2。
第5次归约：V → id(E)，语义处理为arr_no:=arr_no+1；arr_no的值变为1。
第6次归约：E → E + V，语义处理为exp_no:=exp_no+1；exp_no的值变为3。
第7次归约：V → id(E)，语义处理为arr_no:=arr_no+1；arr_no的值变为2。
页:
[1]