微信小程序西安电子科技大学网络与继续教育学院
2020 学年上学期
《编译原理与技术》期末考试试题
（综合大作业）
题号 一 二 三 四 总分
题分 10 20 30 40
得分
考试说明：
1、大作业试题于 2020 年 4 月 23 日公布，2020 年 4 月 24 日至 2020 年 5 月 10 日在线上传大作业答卷（一张图片对应一张 A4 纸答题纸），要求拍照清晰、上传完整；
2、考试必须独立完成，如发现抄袭、雷同均按零分计；
3、答案须用《西安电子科技大学网络与继续教育学院标准答题纸》手写完成，要求字迹工整、卷面干净。
一、单选题（10 分，每空 2 分）
1. 从一个 C/C++源程序产生其可执行程序的过程中，需要经过 。
A. 编译-汇编-预处理-链接 B. 预处理-编译-链接-汇编
C. 预处理-编译-汇编-链接 D. 链接-预处理-编译-汇编
2. 对于正规式 0(1|10)*1， 是其正规集的元素。
A. 1010 B. 0101 C. 0011 D. 0110
3. 递归下降分析是一种 的语法分析方法。
A. 自上而下 B. 自下而上 C. 自左至右 D. 自右至左
4. 与逆波兰式 ab+c*d+对应的中缀表达式是 。
A. a+b+c*d B. (a+b)* c+d C. (a+b)* (c+d) D. a+b*c+d
5. 在表达式 t:=b+3*x 中， 作为左值出现(其中，“:=”表示赋值)。
A. b B. x C. 3 D. t
二、填空题（20 分，每空 2 分）
1. 编译程序的工作过程中，可划分为词法分析、语法分析、 、中间代码生
成、代码优化、 等阶段，以及出错处理和符号表管理。
2. 常用的动态存储分配中， 分配由系统进行管理， 分配由程序员根
据需要申请和释放。
第 1 页 （共 2 页）
3. 用 SLR 方法实现语法分析时，典型的操作有__________、__________、接受和报错。
4. 从一个上下文无关文法的开始符号出发，反复用其 的右部替换文法符号
序列最左边的非终结符，直到产生称为句子的终结符号序列，该过程称
为 。
5. 已知有二维数组 arr[0..4, 0..6]，其元素以行为主序存放（设每个元素占 2 个存储单元），
若第一个元素 arr[0,0]的地址为 arr，则元素 arr[1,4]的地址计算式是 ，最后
一个元素 arr[4,6]的地址计算式是 。
三、简答题（30 分，每小题 10 分）
1. 请分别写出传值调用、引用调用和传名调用时，下述代码的输出结果。
program main(input,output)
procedure f(a,b)
begin
a := a – b;
b := a * b + 1;
end;
begin
x := 1; y := 5;
f(y,x);
print(x,y);
end.
2. 请给出布尔表达式 A or B 和 A and B 短路计算的控制逻辑。
3. 给定文法如下，对于句型 T*-F+id，给出该句型对应的分析树，并指出句型中的所有短语、直接短语和句柄。
E→E+T | T T→T*F | F F→-F | id
四、综合题（40 分）
1.（12 分）已知一个 NFA 如下图所示。
a,b a,b
b b
0 1 2
<1>（4 分）写出两个该自动机可识别的字符串，以及该自动机等价的正规式 r；<2>（8 分）用子集法构造识别 r 的 DFA 及最小 DFA。
2.（10 分）设有文法 G[S]：S→aBc|bAB, A→aAb|b, B→b|ε，计算非终结符 S、A、B
的 FIRST 和 FOLLOW 集合。
3.（14 分）某表达式的语法制导翻译方案如下(运算符-,*,+的优先级依次递减)。
（1） M→ε { M.stat:=nextstat; }
（2） E→ E1 + M E2 { backpatch(E1.fc，M.stat)；
E.tc:=merge(E1.tc,E2.tc); E.fc := E2.fc; }
（3） E→ E1 * M E2 { backpatch(E1.tc, M.stat)；
E.fc:=merge( E1.fc , E2.fc); E.tc:=E2.tc; }
（4） E→ – E1 { E.tc:=E1.fc; E.fc:=E1.tc; }
（5） E→ id { E.tc:=mkchain(nextstat); E.fc:=mkchain(nextstat+1);
emit(‘if’ id.place ‘goto _’); emit(‘goto _’); } <1>（8 分）给出表达式 p*-a+b 的注释分析树；
<2>（6 分）根据上述翻译方案，生成表达式 p*(-a)+b 的三地址码序列(设 nextstat 的初始值为 1)。
第 2 页 （共 2 页）
请先 ！