step11 实验指导

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

int x[10];
int main() { int y[10]; return 0; }

词法语法分析

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

节点 成员 含义
IndexExpr 索引基底 base,索引下标 index 索引运算

语义分析

由于 step 11 里引入了数组,现在我们的变量类型不只是 int 型了,还包括 int 型数组。因此,为了保证所有表达式中变量的类型均合法,需要进行类型检查。

注意:引入数组后,左值不再一定是 identifier 了,还有可能是如 a[0][1] 这样的索引运算表达式,因此同学们可能需要仔细考虑一下如何处理赋值时对值类别的检查。

frontend/type/array.py 里实现了数组类型,同学们可以使用它完成实验,也可以自行对其进行修改。

有能力的同学可以考虑将原先 Namer 中类型检查的部分,以及 stage 5 需要增加的类型检查重构进 Typer 中,使实现更加模块化。

中间代码生成

数组和普通变量类似,可以分为局部数组和全局数组。

全局数组的处理与全局变量类似,由于是升级关卡,我们留给同学自行思考(和全局变量究竟有什么不同,是不是需要的内存空间更大?提示:1. 需要申请更大的 bss 段内存)。

针对局部数组,给出一种参考实现,实际上不只存在一种实现方法。实验文档给出一种参考实现方法,定义了一条中间代码指令 ALLOC 用于分配内存空间:

请注意,TAC 指令的名称只要在你的实现中是一致的即可,并不一定要和文档一致。

指令 参数 含义
ALLOC size 分配 size 字节的内存,并返回内存首地址

采用 ALLOC 指令,测试样例中的局部数组部分代码可以翻译为如下中间代码(忽略全局数组部分):

main:
    T0 = ALLOC 40 # 一个 int 类型为 4 个字节
    T1 = 0
    return T1

通过这种方式,我们实际上是把内存分配的锅甩给了目标代码生成,这大大提升了目标代码生成的自由度,属于合理分锅。

除了分配数组,我们还需要考虑如何访问数组元素。通过 ALLOC 指令我们得到了数组的首地址,那么任何一个数组元素的地址可以通过在首地址的基础上加上偏移量得到。于是,读取数组元素可以使用 Step10 中引入的 LOAD 指令来实现,我们还需要引入一条类似的 STORE 指令将值写入数组元素。

那么,如何将数组下标对应到偏移地址?对一维数组,下标的常数倍(int 型的大小为 4 个字节,倍数为4)即为偏移量。而对于高维数组,我们可以将其视为一个展开成一维的大数组。对于数组 a[d1][d2]...[dn],访问元素 a[i1][i2]...[in] 可以等价于访问 a[i1d2d3...dn + i2d3...*dn + ... + in]。在将数组索引翻译成 TAC 时,同学们需要自行将数组下标转换成地址计算指令。这个步骤并不困难,但可能比较繁琐,同学们在实现时要注意细节,避免错误。

目标代码生成

同中间代码生成,全局数组自行思考实现

对于局部数组的内存分配,推荐在栈上为局部数组分配所需的空间,实际上,Step5 栈帧中的局部变量区域,可以用于存储局部数组。因此,大家需要模仿新建栈帧的操作,对栈顶指针 sp 进行修改,在栈上开辟出一块连续内存,并将这块内存的首地址返回即可。后续如有对数组中元素的访问,基于首地址进行偏移操作即可。

思考题

  1. C 语言规范规定,允许局部变量是可变长度的数组(Variable Length Array,VLA),在我们的实验中为了简化,选择不支持它。请你简要回答,如果我们决定支持一维的可变长度的数组(即允许类似 int n = 5; int a[n]; 这种,但仍然不允许类似 int n = ...; int m = ...; int a[n][m]; 这种),而且要求数组仍然保存在栈上(即不允许用堆上的动态内存申请,如malloc等来实现它),应该在现有的实现基础上做出那些改动?

提示:不能再像现在这样,在进入函数时统一给局部变量分配内存,在离开函数时统一释放内存。

你可以认为可变长度的数组的长度不大于0是未定义行为,不需要处理。

results matching ""

    No results matching ""

    results matching ""

      No results matching ""