minidecaf-tutorial

step11 实验指导

词法语法分析

如果你使用工具完成词法语法分析，修改你的语法规范以满足要求，自行修改词法规范，剩下的交给工具即可。

你可能注意到，虽然数组是一种类型，但我们没有把数组放到 type 中，而是只放在 declaration 里。这一方面是因为我们并不完全支持 C 的数组（例如我们没有指向数组的指针），另一方面 C 语言本身设计就如此。

对有兴趣的同学：C 的这个设计很麻烦…… 你能区分 int*[] 和 int(*)[] 哪个是指针的数组、哪个是数组的指针吗？加上函数指针就更麻烦了，例如声明 int (*(*vtable)[])(void*); 中变量 vtable 的类型是 int (*(*)[])(void*)，含义是

“是一个指针，指向一个数组，数组每个元素是函数指针，函数接受一个 void* 参数，函数返回 int”。

当然，实际中我们一般不会写出这样的代码，更好的方法是用 typedef 包装一下，例如上面的会写成 typedef int (*funcptr_t)(void*) ; typedef funcptr_t vtable_t[] ; vtable_t *vtable。

至于为什么 C 声明被设计成这样，有一个说法是设计者希望声明能够体现变量的用法。例如上面 vtable 的用法是 int v= (*(*vtable)[0])(voidptr_expr)，非常类似其声明。

当然这些都和我们 课程无关 ，我们更不用实现它们。

如果你是手写分析，参见这里。

名称解析

引入数组后，变量的大小不一定是 4 了，例如 int a[5][4] 大小是 80。因此变量的数据结构还需要增加一个 size 属性，并且变量的 frameaddr 不一定连续了（但每个变量所占的一片内存空间一定连续）。

例如，某种实现中 int main(){ int a[2][2]; int b[2]; int c; } 中， a 的 frameaddr 是 0，b 的是 4，c 的是 6。

另外，我们修改了左值的定义 12.9：

12.9 (更新 11.1）表达式是左值的必要条件是它能被下面几条规则构造出来

被声明过的变量，如果声明类型不是数组，那么它是左值；

如果 e 是左值，那么括号括起的 (e) 也是左值；

如果 e 是类型为 T* 的表达式，那么 *e 是类型为 T 的左值；

下标运算的结果，如果其类型不是数组类型，那么它是左值。

因为本质上，int a; 的 a 的值被存放在内存中，需要一次访存 load 它的frameaddr 才能取得。而局部变量 int a[2]; 中的 a 是一个编译期就确定的偏移量常数，它的值就是 fp 加上这个偏移量常数，无须访存。

全局变量 int a[2]; 也是类似的。

另外，数组各维长度必须是正整数，别忘实现对应的语义检查。

类型检查

除了 step12 的 IntegerType 和 PointerType，我们还需要增加数组类型 ArrayType(baseType, length)。

例如 int *a[10][20] 就是 ArrayType(ArrayType(PointerType(IntegerType()), 20), 10)，特别注意 20 和 10 的位置。

当然，就 MiniDecaf 而言，实现中你可以一口气把所有维长度都存起来，变成 ArrayType(baseType, lengthList)，如上就是 ArrayType(PointerType(IntegerType()), [10, 20])

如step12中所说，你也可以用不那么通用的方法来表示类型。因为我们不允许指向数组的指针，所以可以用一个(int, 整数列表)的二元组表示step11中任何表达式的类型。其中int部分表示数组的元素类型，它只可能是int的若干重指针，比如用 0 表示 int，3 表示 int***。 整数列表部分表示数组维度，如果为空，就是一个普通变量，否则就和上面的lengthList的含义一致。

不管你怎么表示类型，类型检查的规则是不会变的，int *a[10][20]可以表示成ArrayType(ArrayType(PointerType(IntegerType()), 20), 10)或者(1, [10, 20])，但是这只是同一个类型的两种的记录方式而已，不会影响到上层的逻辑。

并且相关类型规则是（语义规范 12.12, 12.13）

对于下标操作 e1[e2]，要求 e1 是指针类型或者数组类型，e2 是整数类型；结果类型是指针/数组的基类型。

注意，这里判断不要写 e1.type == PointerType, 而要写 e1.type instanceof PointerType（或者类似的手段）。可以写 e2.type == IntegerType() 或者 e2.type instanceof IntegerType。
对于加法操作，除了最基础的 int 加法还要支持指针加法：两个操作数中一个是指针、另一个是 int；结果类型和指针操作数的类型一致。
对于减法操作，除了 int 减法还可能有两种情况
1. 指针减整数：左操作数是指针类型、右操作数是 int；结果类型和第一个操作数的类型相同。（当然，MiniDecaf 禁止 int 减指针）
2. 指针减指针：左右操作数是相同的指针类型，结果类型是 int

IR 生成

无须新增 IR 指令。

数组声明 无需 IR 上特别处理，只要注意变量大小不一定是 4 即可。并且，数组中数据的内存空间是连续的，因此无论数组的原型是几维的，都可以看做是一个一维的大数组。对于一个数组 \(\mathtt{int}~a[d_1][d_2]\cdots[d_n]\)，可看做是 \(\mathtt{int}~a'[d_1d_2\cdots d_n]\)。访问 \(a[i_1][i_2]\cdots[i_n]\)，就是访问 \(a'[i_1d_2d_3\cdots d_n + i_2d_3d_4\cdots d_n + \cdots + i_n]\)。

例如，对于数组 int a[3][4][5]，有：

a[i] 的地址是 a + (i * 4 * 5) * sizeof(int)；

a[i][j] 的地址是 a + [(i * 4 * 5) + (j * 5)] * sizeof(int)；

a[i][j][k] 的地址是 a + [(i * 4 * 5) + (j * 5) + k] * sizeof(int)。

下标操作 e1[e2] 需要分数组和指针来说，并且需要类型检查阶段所计算出的表达式类型信息。

如果 e1 是数组：显然，e1[e2] 的地址是 e1 起始地址加上 e2 的值乘以 S，其中 S 为 e1 基类型的大小。
我们约定，任何数组类型类型表达式的 IR 执行后，栈顶正好多出一个元素，其为该数组的起始地址。因此，为了生成 e1[e2] 的 IR，先生成 e1 的 IR，再生成 e2 的 IR，再生成三条指令：push S ; mul ; add；这一步生成的是 e1[e2] 的地址，如果 e1[e2] 不是左值也不是数组，还需要一个 load。例如 int a[10][20];，设 a 的 frameaddr 为 20，则 a 的 IR 如 frameaddr 20。而 a[2+3] 的 IR 如下（其中 80 == 20 * sizeof(int)）
```
frameaddr 20
push 2 ; push 3 ; add
push 80
mul
add
```
而 a[2+3][17] 作为非左值的 IR 如（如果是左值，去掉最后 load 即可）
```
...（和上面一样）
push 17
push 4
mul
add
load
```
如果 e1 是指针：类似上面，e1[e2] 的地址是 e1 的值加上 e2 的值乘以 S，其中 S 为 e1 的基类型的大小。因此，为了生成 e1[e2] 的 IR，先生成 e1 的 IR（这里 e1 不是左值），然后生成 e2 的 IR，然后还是 push S ; mul ; add ; load。不过 e1[e2] 可能作为左值，如果作为左值，那么生成地址的 IR 和上面一样，但去掉最后的 load。

指针算术 也分两类

指针加整数：e1 + e2，其中 e1 是指针、e2 是整数。注意指针加整数的值是：指针的值，加上整数乘以 S，其中 S 为指针基类型的大小 ¹。 IR 生成类似上面，请自行设计。

例如 int *p;，设 p 的 frameaddr 是 20，那么 p+61 的 IR 如下（注意其中 push 4 ; mul） frameaddr 20 ; load ; push 61 ; push 4 ; mul ; add。整数加指针、指针减整数类似。
指针减指针：同上，指针数值相减后，要除以基类型的大小。

因此 int *p 那么 (p+10) - (&p[3]) 等于 7。

汇编生成

无需特别修改。

思考题

设有以下几个函数，其中局部变量 a 的起始地址都是 0x1000(4096)，请分别给出每个函数的返回值（用一个常量 minidecaf 表达式表示，例如函数 A 的返回值是 *(int*)(4096 + 23 * 4)）。

 int A() {
     int a[100];
     return a[23];
 }

 int B() {
     int *p = (int*) 4096;
     return p[23];
 }

 int C() {
     int a[10][10];
     return a[2][3];
 }

 int D() {
     int *a[10];
     return a[2][3];
 }

 int E() {
     int **p = (int**) 4096;
     return p[2][3];
 }

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

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

当同时存在>= 2个可变长度的数组时，至少有一个数组的起始地址不能在编译时决定。

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

总结

本节内容本身难度不大，但细节很多（尤其注意指针加整数时，整数要乘一个数），也有相当代码量。

备注

MiniDecaf 中指针基类型只能是 int、int*、int**……，所以这里 S 只可能等于 4。 ↩