step6 实验指导

本实验指导使用的例子为：

int main() {
    int x = 1;
    {
        x = 2; 
        int x = 3;
    }
    x = 4;
    return x;
}

词法语法分析

针对块语句，我们需要设计 AST 节点来表示它，给出的参考定义如下：

节点	成员	含义
`Block`	子语句列表 `children`	语句块

语义分析

从 Step6 开始，我们需要考虑作用域和代码块。简而言之，一份代码中可能有多个代码块的嵌套，因此作用域开始出现了层次结构。例如，在示例中，尽管 main 函数里定义了变量 x，但随后我们开启了一个新的代码块。在这个代码块中，赋值语句 x = 2; 中的 x 就是指 main 作用域中定义的 x，而随后通过 int x = 3; 我们定义了另一个变量 x，这个 x 只在内部大括号括起的作用域内生效。

在 Step5 中，我们只维护了 main 的作用域，所有符号都在这个作用域的符号表中维护。现在，为了维护层次嵌套的作用域，我们引入了作用域栈（Scope Stack）这个数据结构。在进行符号表构建的扫描过程中，我们需要动态维护作用域栈，保存当前扫描结点所在的从内到外所有作用域。每次我们开启一个代码块时，要新建一个作用域并压栈；而当退出代码块时，要弹栈关闭此作用域。

接下来针对上述代码示例，讲述作用域栈的维护方式。首先，栈底有一个全局作用域，其符号表里只有 main 函数。由于目前不需要考虑函数和全局变量，可以暂时忽略全局作用域。进入 main 函数时，开启一个局部作用域，在扫描 int x = 1; 时定义变量符号 x，并将其加入栈顶作用域对应的符号表中。如下所示：

作用域栈	符号表
全局作用域（栈底）	函数 main（可忽略）
局部作用域（栈顶）	变量 x

接下来，扫描到一个局部代码块，由此建立一个局部作用域并压栈。在扫描 x = 2; 时，我们需要分析 x 这个变量对应着哪个作用域里的符号。此时的作用域栈是这样的：

作用域栈	符号表
全局作用域（栈底）	函数 main（可忽略）
局部作用域	变量 x
局部作用域（栈顶）	空

对变量x的查找从栈顶开始，由上向下依次查找对应的符号表，直至找到变量 x 为止。由于在栈顶作用域对应的符号表中不存在变量符号 x，于是向下继续查找。在 main 函数对应的作用域中，可以找到变量符号 x。因此，语句 x = 2; 中的 x 对应 main 函数作用域里定义的变量 x。

接下来，当扫描到语句 int x = 3; 时，定义了另一个变量 x。此时，只需要在栈顶作用域中查找该变量是否存在。若不存在，即在符号表中加入对应符号。此时的作用域栈如下：

作用域栈	符号表
全局作用域（栈底）	函数 main（可忽略）
局部作用域	变量 x
局部作用域（栈顶）	变量 x

请务必注意上表中的两个变量 x 是不同的变量。

接下来，退出代码块，将其对应的作用域弹出栈，此时的作用域栈如下：

作用域栈	符号表
全局作用域（栈底）	函数 main（可忽略）
局部作用域（栈顶）	变量 x

最后，扫描语句 x = 4; 时，从栈顶作用域符号表查找 x，所找到的变量 x 为 main 作用域定义的 x 变量。

中间代码生成

本步骤中无须新增新的 TAC 指令。

让我们来看看示例所对应的 TAC 代码：

main:
    _T1 = 1
    _T0 = _T1   # int x = 1;
    _T2 = 2
    _T0 = _T2   # x = 2
    _T4 = 3
    _T3 = _T4   # int x = 3;
    _T5 = 4
    _T0 = _T5   # x = 4;
    return _T0

显然，两个代码块里的变量 x 是不同的变量，因此它们分别对应着不同的临时变量。其中，_T0 对应着 main 作用域里的 x，而 _T3 则对应着内层代码块定义的变量 x。只要同学们在符号表构建阶段把每个变量和正确作用域的变量符号关联起来，这一步就非常简单了：找到对应变量符号，使用该符号对应的临时变量即可。

目标代码生成

不需要新增新的中间代码指令。

代码框架需要同学们对寄存器分配相关的 CFG 的内容进行细微修改。具体来说，需要在 backend/dataflow/cfg.py 中添加基本块是否可达的判断。在寄存器分配算法 backend/reg/bruteregalloc.py 的注释中，我们给出了提示，如果一个基本块不可达，那么无须为它分配寄存器。

实现提示

在 step5 中，namer/typer 遍历时的上下文信息(参数 ctx)是单一的作用域。到了 step 6，你需要按照实验指导书中描述，把上下文信息改成“作用域栈”。也即定义 class Namer(Visitor[Scope, None]) 应改为 class Namer(Visitor[YourType, None])，其中 YourType 是你的作用域栈类型，你可以任意命名它。我们推荐把这个类的定义放在 frontend/scope/ 下。class Typer 也需要如上改动。
之前 step5 的全局唯一的作用域可以被当作“函数作用域使用”，在 visitFunction 入栈。然后在新的 visitBlock 中，再进一步将局部作用域压栈。最后，在所有这些方法的末尾，不要忘了把对应作用域退栈。
当只有一个作用域时，“不可以定义新变量a”就意味着当前“可以获取变量a的值”，反之亦然，所以“定义变量”和“获取变量”的检查都可以用 Scope.lookup 实现。但有了多个作用域之后，就出现了“既可以拿到a的值，也可以重新定义一个a”的情况。这需要重新考虑 Typer / Namer 中的每一个 Scope.lookup ，看她们是否需要换成新函数。
后续 stage-4 时，你需要一个机制来检查 break/continue 语句是否在一个循环内。这可以通过修改 namer/typer 中的对应结点来实现。另外，别忘了循环本身也是一个作用域！
后续如果你选做“全局变量”部分，可以在 Namer 和 Typer 的 transform 方法中先将全局作用域加入栈底，再往上才是 visitFunction 的函数作用域。

思考题

请画出下面 MiniDecaf 代码的控制流图。

int main(){
 int a = 2;
 if (a < 3) {
     {
         int a = 3;
         return a;
     }
     return a;
 }
}

通过例子学习