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

【前言】

这是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）根据活性分析实现一个最优化的寄存器分配方案。

作答如下