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

发布时间:2024年01月11日

【前言】

这是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)问当作独立的来做的,也就是说,我后面的活性分析,并没有在优化的基础上进行,还是用的原来的图和代码。但是对于这个有不同的理解,我的学霸同学(@段神)按照优化之后的来做的,并且是逐句分析,在这里,也可以参考:

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

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

文章来源:https://blog.csdn.net/qq_39480177/article/details/135529890
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。