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

大学的考试所剩不多,而现在的自己也懂得了凡事做笔记的好处,不仅能促进自己做得更好,还能记录自己所做过的事情,不做过后即忘之人。记录一下今天的编译原理考试。

考试科目 考试时间 考试教室
编译原理 2019 年 5 月 18 日
15:45 - 17:45
正心 12

判断题(10 * 1 = 10 分)

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

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

填空题(5 * 1 = 5 分)

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

选择题(10 * 1 = 10 分)

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

大题

LL(1)

给出一个文法。

SaSbSPPbQbcbQQaaS \to aSb \\ S \to P \\ P \to bQ|bc(这个产生式不太记得了,只知道是有公共前缀 b) \\ Q \to Qa|a

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

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

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

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

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

(3) 推导句子 abacbabacb

推导过程,常规题。

LR(1)

对文法:

AaAdAaAbAϵA \to aAd \\ A \to aAb \\ A \to \epsilon

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

常规题,注意产生式 AϵA \to \epsilon 比较特殊,在项目中直接写为 AA \to \cdot(没有空符号)。

教学群里有人发了一个答案,如下图(感谢):

LR(1) 答案

代码优化

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

(1) 构造 DAG 图。

翻了一下陈鄞老师 MOOC 的课件,居然是原题(貌似只是常量的值改了一下)!见下图:

DAG 图的构造

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

MM 是根节点,不可以删除,但是 LL 也在根节点,可以删掉。另外删除不活跃变量。

三地址码

写出下面程序的三地址码(无需进行代码优化):

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

访问链

语义动作

语法制导定义:

BB10{B.val=2B1.val}BB11{B.val=2B1.val+1}B1{B.val=1}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 \}

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

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

我的答案如下:

B1B{B.bits=B.bits+1,B.val=2B.bits+B.val}B0B1{B.bits=B1.bits+1,B.val=B1.val}B1B1{B.bits=B1.bits+1,B.val=2B1.bits+B1.val}Bϵ{B.bits=0,B.val=0}\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}

总结

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

前期准备阶段:

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

考试阶段:

  1. 快点做,多给自己一点压力,我坐在第一排,有很多人提前交卷(好像很多都是不会做了,不过也有大神),压力比较大,所以提前半小时完成了。
  2. 检查的时候一定要规划好时间,我在最后 5 分钟发现了一个错误,导致当时非常紧张没有写的很整洁。提前 5 分钟封笔是个不错的选择。
文章作者: upupming
文章链接: https://upupming.site/2019/05/18/hit-compilers-exam-2019/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 upupming 的博客