第144集：数组访问的中间代码生成
核心知识点讲解
数组的存储方式
在内存中，数组通常采用连续存储的方式，即数组元素在内存中是连续排列的。对于一维数组和多维数组，它们的存储方式有所不同：
一维数组：元素按顺序连续存储。例如，数组
a[5]的元素在内存中的顺序是a[0],a[1],a[2],a[3],a[4]。多维数组：有两种存储方式：
- 行主序（Row-Major Order）：按行存储，先存储第一行的所有元素，然后存储第二行的所有元素，以此类推。C、C++、Java 等语言采用这种方式。
- 列主序（Column-Major Order）：按列存储，先存储第一列的所有元素，然后存储第二列的所有元素，以此类推。Fortran 等语言采用这种方式。
数组元素的地址计算
要访问数组元素，首先需要计算该元素在内存中的地址。地址计算的公式取决于数组的维度、存储方式和元素类型。
一维数组的地址计算
对于一维数组 a[n]，假设每个元素占用 w 个字节，数组的起始地址为 addr(a)，则元素 a[i] 的地址为：
addr(a[i]) = addr(a) + i * w二维数组的地址计算（行主序）
对于二维数组 a[m][n]，按行主序存储，元素 a[i][j] 的地址为：
addr(a[i][j]) = addr(a) + (i * n + j) * w三维数组的地址计算（行主序）
对于三维数组 a[m][n][p]，按行主序存储，元素 a[i][j][k] 的地址为：
addr(a[i][j][k]) = addr(a) + ((i * n + j) * p + k) * w数组访问的中间代码生成
生成数组访问的中间代码需要以下步骤：
计算数组元素的地址：根据数组的维度和索引，生成计算地址的中间代码。
生成访问指令：根据访问类型（读取或写入），生成相应的访问指令。
一维数组访问的中间代码生成
对于一维数组访问 a[i]，生成的中间代码如下：
- 计算偏移量：
t1 = i * w - 计算地址：
t2 = a + t1 - 读取值：
t3 = *t2（如果是读取操作）
或写入值：*t2 = x（如果是写入操作）
二维数组访问的中间代码生成
对于二维数组访问 a[i][j]（行主序），生成的中间代码如下：
- 计算
i * n：t1 = i * n - 计算
i * n + j：t2 = t1 + j - 计算偏移量：
t3 = t2 * w - 计算地址：
t4 = a + t3 - 读取值：
t5 = *t4（如果是读取操作）
或写入值：*t4 = x（如果是写入操作）
实用案例分析
案例1：一维数组的读取访问
示例代码
x = a[i];地址计算
假设 a 是一个整型数组，每个元素占4字节，则元素 a[i] 的地址为 addr(a) + i * 4。
生成的三地址码
t1 = i * 4 // 计算偏移量
t2 = a + t1 // 计算地址
t3 = *t2 // 读取值
x = t3 // 赋值给变量 x案例2：一维数组的写入访问
示例代码
a[i] = x;地址计算
同样，元素 a[i] 的地址为 addr(a) + i * 4。
生成的三地址码
t1 = i * 4 // 计算偏移量
t2 = a + t1 // 计算地址
*t2 = x // 写入值案例3：二维数组的读取访问
示例代码
x = a[i][j];地址计算
假设 a 是一个 m x n 的整型二维数组，按行主序存储，则元素 a[i][j] 的地址为 addr(a) + (i * n + j) * 4。
生成的三地址码
t1 = i * n // 计算 i * n（n 是数组的列数）
t2 = t1 + j // 计算 i * n + j
t3 = t2 * 4 // 计算偏移量
t4 = a + t3 // 计算地址
t5 = *t4 // 读取值
x = t5 // 赋值给变量 x案例4：二维数组的写入访问
示例代码
a[i][j] = x;地址计算
同样，元素 a[i][j] 的地址为 addr(a) + (i * n + j) * 4。
生成的三地址码
t1 = i * n // 计算 i * n
t2 = t1 + j // 计算 i * n + j
t3 = t2 * 4 // 计算偏移量
t4 = a + t3 // 计算地址
*t4 = x // 写入值案例5：三维数组的读取访问
示例代码
x = a[i][j][k];地址计算
假设 a 是一个 m x n x p 的整型三维数组，按行主序存储，则元素 a[i][j][k] 的地址为 addr(a) + ((i * n + j) * p + k) * 4。
生成的三地址码
t1 = i * n // 计算 i * n
t2 = t1 + j // 计算 i * n + j
t3 = t2 * p // 计算 (i * n + j) * p
t4 = t3 + k // 计算 (i * n + j) * p + k
t5 = t4 * 4 // 计算偏移量
t6 = a + t5 // 计算地址
t7 = *t6 // 读取值
x = t7 // 赋值给变量 x案例6：数组访问表达式
示例代码
x = a[i] + b[j];生成的三地址码
// 计算 a[i] 的地址并读取值
t1 = i * 4
t2 = a + t1
t3 = *t2
// 计算 b[j] 的地址并读取值
t4 = j * 4
t5 = b + t4
t6 = *t5
// 计算和并赋值
t7 = t3 + t6
x = t7案例7：数组作为函数参数
示例代码
void foo(int a[], int n) {
int x = a[0];
}
int main() {
int arr[5] = {1, 2, 3, 4, 5};
foo(arr, 5);
return 0;
}生成的三地址码
// foo 函数的中间代码
foo:
// 函数序言
// 计算 a[0] 的地址并读取值
t1 = 0 * 4
t2 = a + t1
t3 = *t2
x = t3
// 函数尾声
return
// main 函数的中间代码
main:
// 函数序言
// 调用 foo 函数
param arr
param 5
call foo, 2
// 返回
return 0代码实现
下面是一个简单的数组访问中间代码生成器的实现，使用 Python 语言：
class ArrayCodeGenerator:
def __init__(self):
self.temp_count = 0
self.instructions = []
def new_temp(self):
"""生成新的临时变量名"""
self.temp_count += 1
return f"t{self.temp_count}"
def generate_array_access(self, array_name, indices, element_size=4):
"""生成数组访问的中间代码
Args:
array_name: 数组名
indices: 索引列表，例如 [i, j] 表示二维数组
element_size: 每个元素的大小（字节）
Returns:
存储数组元素地址的临时变量名
"""
if not indices:
return array_name
# 一维数组
if len(indices) == 1:
index = indices[0]
# 计算偏移量
temp1 = self.new_temp()
self.instructions.append(f"{temp1} = {index} * {element_size}")
# 计算地址
temp2 = self.new_temp()
self.instructions.append(f"{temp2} = {array_name} + {temp1}")
return temp2
# 多维数组（行主序）
else:
# 计算第一个索引乘以第二个维度的大小
# 注意：这里假设我们知道每个维度的大小
# 在实际编译器中，这些信息会从符号表中获取
dim_sizes = [10, 5] # 假设是 10x5 的二维数组
# 计算 i * n
temp1 = self.new_temp()
self.instructions.append(f"{temp1} = {indices[0]} * {dim_sizes[1]}")
# 计算 i * n + j
temp2 = self.new_temp()
self.instructions.append(f"{temp2} = {temp1} + {indices[1]}")
# 递归处理剩余的索引
if len(indices) > 2:
# 对于三维及以上数组，继续递归计算
# 这里简化处理，只支持二维数组
pass
# 计算偏移量
temp3 = self.new_temp()
self.instructions.append(f"{temp3} = {temp2} * {element_size}")
# 计算地址
temp4 = self.new_temp()
self.instructions.append(f"{temp4} = {array_name} + {temp3}")
return temp4
def generate_array_read(self, array_name, indices, result_var, element_size=4):
"""生成数组读取的中间代码"""
addr_temp = self.generate_array_access(array_name, indices, element_size)
# 生成读取指令
self.instructions.append(f"{result_var} = *{addr_temp}")
def generate_array_write(self, array_name, indices, value_var, element_size=4):
"""生成数组写入的中间代码"""
addr_temp = self.generate_array_access(array_name, indices, element_size)
# 生成写入指令
self.instructions.append(f"*{addr_temp} = {value_var}")
def get_instructions(self):
"""获取生成的中间代码指令"""
return self.instructions
# 测试代码
generator = ArrayCodeGenerator()
# 测试一维数组读取
print("测试一维数组读取:")
generator.generate_array_read("a", ["i"], "x")
for instr in generator.get_instructions():
print(instr)
print()
# 测试二维数组读取
generator2 = ArrayCodeGenerator()
print("测试二维数组读取:")
generator2.generate_array_read("b", ["i", "j"], "y")
for instr in generator2.get_instructions():
print(instr)
print()
# 测试一维数组写入
generator3 = ArrayCodeGenerator()
print("测试一维数组写入:")
generator3.generate_array_write("c", ["k"], "z")
for instr in generator3.get_instructions():
print(instr)运行结果
测试一维数组读取:
t1 = i * 4
t2 = a + t1
x = *t2
测试二维数组读取:
t1 = i * 5
t2 = t1 + j
t3 = t2 * 4
t4 = b + t3
y = *t4
测试一维数组写入:
t1 = k * 4
t2 = c + t1
*t2 = z总结
数组访问的中间代码生成是编译器前端的重要组成部分，它涉及到数组元素的地址计算和访问指令的生成。对于一维数组和多维数组，它们的地址计算方式不同，需要根据数组的存储方式（行主序或列主序）来确定正确的地址计算公式。
在生成数组访问的中间代码时，需要注意以下几点：
元素大小：不同类型的数组元素占用的字节数不同，需要根据元素类型来确定。
维度大小：对于多维数组，需要知道每个维度的大小才能正确计算地址。
存储方式：行主序和列主序的地址计算方式不同。
地址计算优化：对于频繁访问的数组元素，可以考虑缓存地址计算的结果，以提高性能。
通过正确生成数组访问的中间代码，可以确保编译器能够正确处理数组操作，为后续的代码优化和目标代码生成做准备。