哈工大 2019 春编译原理考试总结

2019 年 5 月 18 日，记录一下今天的编译原理考试。

判断题（10 * 1 = 10 分）

三地址码之间是通过标识符相互联系的。【不会做，填的 ✖】
文法 $S \to aA, A \to Ab, A \to b$ 是否是 LR(0) 文法。【✖ 因为有移进规约冲突】
语法分析一定需要消除左递归。【✖ 自底向上并不需要】
语义子程序就是就是翻译方案。【✓】
编译的各个阶段都需要对符号表进行填充和查询。【✖ 语法分析无需符号表】
……

其他的真的记不起来了，只是对自己卡了的题目印象比较深刻，后面的填空选择也是，只有大题因为记在了草稿纸上所以能比较好地复原。这些问题只要复习的认真，基本上都可以答出来。

填空题（5 * 1 = 5 分）

有产生式 $A \to Ab$ ，那么 $aAbcBe$ 的直接短语是（），句柄是（）。【都是 $Ab$ 】
根据语句的功能，分为两种：（声明）语句和（控制）语句。【真的不会，随便填的】
如果某文法的预测分析表没有冲突，则该文法是（）文法。【LL(1)，预测分析法是自顶向下的，讲的只有 LL(1) 文法】
…

选择题（10 * 1 = 10 分）

词法分析阶段在符号表中填写（）【NAME 字段】
一个程序在运行之前需要进行（）【编写、编译、链接】
代码优化可以（）【提高速度、节省空间】
LR 的 DFA 状态对应的是规范句型的（）【活前缀】
…

大题

LL(1)

给出一个文法。

$S \to aSb \\ S \to P \\ P \to bQ|bc（这个产生式不太记得了，只知道是有公共前缀 b） \\ Q \to Qa|a$

(1) 首先改造文法为 LL(1) 文法，然后计算改造后的文法的 FIRST 集和 FOLLOW 集。

就是消除左递归，去回溯，然后计算，常规题。

这里自己有一个失误，看到 $Q \to Qa|a$ ，有两个一样的 $a$ ，自作聪明以为可以不用老师讲的 $T \to T\alpha|\beta$ 的去左递归公式，直接变为 $Q \to aQ|a$ ，然后做到第二问才发现是不对的，因为即使这样还要消除回溯……不过幸好前后要修改的地方不算太多，还是顺利做完了这道题，没有花太多的时间。

(2) 构造 LL(1) 分析表。

计算各个产生式的 SELECT 集，再填表，常规题。

(3) 推导句子 $abacb$ 。

推导过程，常规题。

LR(1)

对文法：

$A \to aAd \\ A \to aAb \\ A \to \epsilon$

计算 LR(1) 项目集，构造 LR(1) 分析表。

常规题，注意产生式 $A \to \epsilon$ 比较特殊，在项目中直接写为 $A \to \cdot$ （没有空符号）。

教学群里有人发了一个答案，如下图（感谢）：

LR(1) 答案

代码优化

给出了一个基本块的各个三地址码。

(1) 构造 DAG 图。

翻了一下陈鄞老师 MOOC 的课件，居然是原题（貌似只是常量的值改了一下）！见下图：

DAG 图的构造

(2) 假设只有 $M$ 在后续被使用到，对代码进行优化。

$M$ 是根节点，不可以删除，但是 $L$ 也在根节点，可以删掉。另外删除不活跃变量。

三地址码

写出下面程序的三地址码（无需进行代码优化）：

if (X > 0 or Y < 0)
then
    while (X > 0)
        X = A * 3
else
    Y = B + 3

(1)

第一遍不带标号：

1. if X > 0 goto _
2. if Y < 0 goto _
3. Y = B + 3
4. goto _
5. if X > 0 goto _
6. goto _
7. X = A * 3
8. goto _
9.

第二遍回填标号：

1. if X > 0 goto 5
2. if Y < 0 goto 5
3. Y = B + 3
4. goto 9
5. if X > 0 goto 7
6. goto 9
7. X = A * 3
8. goto 5
9.

这道题非常简单，关键是要懂得语义分析的【回填】操作，唯一的遗憾是我第一遍做错了没有判断 while 循环第一次进入的情况，在考试结束前 5 分钟才发现，虽然改对了，不过非常潦草。

(2) 画出程序流图。

常规题。参见下面的 PPT：

三地址码到程序流图

运行存储分配

介绍访问链和控制链的在存储分配中作用。

两者的区别要分清，访问链是指向直接外层的过程的活动记录的指针，控制链是前一个过程的 top_sp。

访问链

语义动作

语法制导定义：

$B \to B_10 \{ B.val = 2B_1.val \} \\ B \to B_11 \{ B.val = 2B_1.val+1 \} \\ B \to 1 \{ B.val = 1 \}$

改造成不含左递归的文法。

消除左递归。
改造语义动作。【新增一个 bits 属性】

我的答案如下：

$\begin{aligned} B \to 1B' &\quad \{B.bits = B'.bits+1, B.val = 2^{B'.bits} + B'.val\} \\ B' \to 0B_1' &\quad \{B'.bits = B_1'.bits+1, B'.val = B_1'.val\} \\ B' \to 1B_1' &\quad \{B'.bits = B_1'.bits+1, B'.val = 2^{B_1'.bits} + B_1'.val\} \\ B' \to \epsilon &\quad \{B'.bits = 0, B'.val = 0\} \\ \end{aligned}$

总结

这次考试总体还算顺利，没有出太大的岔子，不过也有不满意自己的地方。无论如何考试已经结束，结果如何不太重要了，需要给自己总结一些经验。

前期准备阶段：

厚积薄发，同学们一直问老师这儿考不考，那儿考不考，虽然有些得到了明确答复（这很好），但是大部分只是说『选择性复习』，我的选择是，尽量像准备高考一样，哪怕老师并不考这里，我也要准备，不要太贪图小便宜，毕竟相比于吃大亏来说，这点小努力还是值得的。
提前准备，这次大概提前了 2 周开始复习，准备的比较充分，很开心~

考试阶段：

快点做，多给自己一点压力，我坐在第一排，有很多人提前交卷（好像很多都是不会做了，不过也有大神），压力比较大，所以提前半小时完成了。
检查的时候一定要规划好时间，我在最后 5 分钟发现了一个错误，导致当时非常紧张没有写的很整洁。提前 5 分钟封笔是个不错的选择。