step7 实验指导

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

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

词法语法分析

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

对于Python:

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

对于C++:

节点 成员 含义
CompStmt 子语句列表 stmts 语句块

语义分析

从 Step7 开始,我们需要考虑作用域和代码块。简而言之,一份代码中可能有多个代码块的嵌套,因此作用域开始出现了层次结构。例如,在示例中,尽管 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。只要同学们在符号表构建阶段把每个变量和正确作用域的变量符号关联起来,这一步就非常简单了:找到对应变量符号,使用该符号对应的临时变量即可。

目标代码生成

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

Python 框架

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

思考题

  1. 请画出下面 MiniDecaf 代码的控制流图。
    int main(){
     int a = 2;
     if (a < 3) {
         {
             int a = 3;
             return a;
         }
         return a;
     }
    }
    

results matching ""

    No results matching ""

    results matching ""

      No results matching ""