编译原理-2022期末考试解析

【前言】

一、词法分析（15 分）

(1) 为下列正则表达式构造一个NFA。

( aa | b )*?( a | cc )*?

(2) 将下图中的 NFA 转换为相应的正则表达式。

(3) 将下图中的 NFA 转换为 DFA。

作答如下：

（1）

（2）

( aa | v )*?( a | bb?)*?

（3）

使用子集构造法

最后获得DFA

二、语法分析（25 分）

考虑下列文法 G:

A → ( S ) | ( B ]

B → S | ( B

S → ( S ) | ?

A, B, S 为非终结符，A 为开始符号，(、)、]是终结符。

(1) 给出 4 个文法 G 的语句, 尽可能多的用到不同的产生式, 并分别加以说明。

(2) 构建 A, B, S 的 FIRST 集和 FOLLOW 集， 𝜖 参与使用(无需解释, 只给出结果即可)。

(3) 画出文法 G 的 LR(0)有限自动机(LR(0)-DFA)。

(4) 从 0 开始依次命名每个状态，考虑所有的状态并且简述哪些状态有着至少一个 LR(0)冲突? 其中的哪些状态同时也有 SLR(1)冲突? 文法 G 是 SLR(1)文法吗?

(5) 构造文法 G 的 SLR（1）分析表。若文法 G 非 SLR（1），标出表中的冲突项。

我的作答：

三、语法制导翻译（15 分）

考虑以下语法制导定义 SDD，

?为该 SDD 写出一个翻译模式。

我的作答：

四、优化（45 分）

考虑下面这个三地址码程序：

1 a := input
2 b := input
3 t1 := a + b
4 t2 := a * 2
5 c := t1 + t2
6 if a < c goto 8
7 t2 := a + b
8 b := 25
9 c := b + c
10 d := a - b
11 if t2 = 0 goto 17
12 d := a + b
13 t1 := b - c
14 c := d – t1
15 if c < d goto 3
16 c := a + b
17 output c
18 output d

（1）指出每个基本块从哪一行开始，并给出每一个基本块的第一条指令的行号。
（2）用 B 1 ，B 2 ，…来依次命名每个基本块，并用这样的表示画出这些基本块的控制流图。
（3）检查是否有可以进行的优化手段, 写出优化后的代码。
（4）对每个基本块做出活性分析。
（5）根据活性分析实现一个最优化的寄存器分配方案。

?

?作答如下

另外，根据第5题分配寄存器的意思，这道题我感觉是需要进行逐句分析的。（不同班组教的不一样，我们老师教的按块分析，另一个班组的老师教的逐句分析，这里按照实际情况我觉得逐句分析会更好一些），下面我写出了逐句分析的，红字是迭代一次之后变更的。

关于本题，我是把第（3）问当作独立的来做的，也就是说，我后面的活性分析，并没有在优化的基础上进行，还是用的原来的图和代码。但是对于这个有不同的理解，我的学霸同学（@段神）按照优化之后的来做的，并且是逐句分析，在这里，也可以参考：

?另一位同学（@郑神）使用按块分析做的，也放在这里，供参考。

感觉主要是考察一个对于活性分析的方法，这道题没有太明确具体的做法。但是方法要掌握。