编译原理【运行时环境】—什么是活动记录、 活动记录与汇编代码的关系

系列文章戳这里👇

1. 什么是上下文无关文法、最左推导和最右推导
2. 如何判断二义文法及消除文法二义性
3. 何时需要消除左递归
4. 什么是句柄、什么是自上而下、自下而上分析
5. 什么是LL(1)、LR(0)、LR(1)文法、LR分析表
6. LR(0)、SLR(1)、LR(1)、LALR(1)文法之间的关系
7. 编译原理第三章习题
8. 词法分析、构建DFA、上下文无关文法、LL(1)分析、提取正规式
9. 证明LL(1)、SLR(1)、LALR(1)文法
10. 翻译方案、属性栈代码
11. 【运行时环境】什么是活动记录、 活动记录与汇编代码的关系

什么是活动记录？

相信大家也和我一样，觉得编译原理在运行环境这部分比较难理解，由于机器是栈式运行的，所以里面很多操作并不利于我们理解，下面分享一下我自己对活动记录这一块的部分理解，也有一些x86汇编的内容

活动记录－AR （Activation Record）

• 是一连续存储区域，用于管理与存放和程序单元执行相关的重要信息。
• 下图就是活动记录的内容，简单来说，活动记录是用来记录一段函数信息的地方，
  • 很好理解，当我们在写C程序时，如果我们要用一个函数调用另一个函数，那么在调用结束后怎么回到原来的函数呢？
    • 就是活动记录在帮忙，他帮我们把调用者的地址记录下来，并用控制链相连。
  • 而访问链是记录当前函数可以访问的函数地址，这个是可选择的，意思就是活动记录中可以没有它。
  • 返回值自然就是该函数return的值，实在参数其实就是函数的参数，也就是int fun(int a,int b)里面的a和b
  • 局部数据就是函数体里面定义的局部变量
  • 机器状态就是活动记录的一个指针，它是活动记录的基地址，x86汇编中一般表示为%ebp，我们可以用它来找到活动记录里面参数的位置，比如8(%ebp)就是ebp+8，
• 
• 问题来了，如何获取活动记录里的内容呢？上面说了，可以通过%ebp，如下图所示，bp进行偏移就可以取得的对应位置的值！

活动记录的内容

• 下图是栈式分配下的活动记录内容布局，其中返回值往下即为高地址到低地址，所以我们要调用参数就需要用bp+xx去取，而局部参数就是bp-xx，还不懂也没关系，后面会举个栗子，应该会更好理解

• 临时区域。用以保存临时计算结果

• 局部数据区。源程序中程序单元声明的局部变量对应在此区域。

• 机器状态保存区。存有机器的寄存器，程序指令计数器 ip（返回地址）等。

• 访问链（静态链）。当前程序单元可以访问的（静态程序中）外围程序单元的活动记录链。

• 控制链（动态链）。程序单元的活动记录按它们的生成（或调用）次序串成链。

• 实在参数

• 返回值

举个栗子

• 
• 那么这个C程序的活动记录安排你能画出来吗？试试看？
• 函数g被调用时，活动记录栈的（大致）内容如下：
• 可以看到主函数中调用了h，而h调用了g，他们的old bp就是控制链，分别指向调用者，他们都有一个局部变量a，并且此时bp在函数g的活动记录中，sp是栈顶指针(始终指向栈顶)

再举个栗子

• 

• 这是一个非常简单的c函数程序，你能画出它的活动记录图，并标明各个参数对应bp的偏移吗？如果我们要取参数则上移，要取局部变量则下移，这里是int，占4个字节，所以分别是bp+8和bp-4

• 更深一步，让我们一起看一看这段程序的汇编代码是怎么样的吧！x86汇编是典型的栈式机，首先pushl %ebp将当前bp压栈，movl %esp,%ebp将这个位置作为活动记录的基址，即把esp送入ebp，subl $8, %esp为局部数据分配空间，有两个整型变量，所以esp-8，movl 8(%ebp), %eax取参数a的值放入寄存器%eax，再movl %eax,-4(%ebp)将其赋给局部变量，后两句同理将b赋给d，最后leave和ret回收活动记录，恢复原先保存的机器状态，leave相当于mov bp,sp ;pop bp //恢复调用者的bp

• 

再再举个栗子

int punc(int** &a,int b, int c,int &d)
{
a[b][c] = d;return 0;
}//C/C++程序，int 变量占 4 字节。

(1)准确画出该函数的活动记录内容安排。

• 同理，也很简单就能画出来

(2)补全 5 处带有下划线的汇编代码。

那么这里的汇编代码怎么填呢？

• 可以看到参数分别为(int** &a,int b, int c,int &d)，如果你不清楚指针引用的话，可以先看一下这篇文章《C语言指针、引用》，那么其中a是一个引用，它是指向某一个指针的指针的引用，也就是有一个指针x，它指向另一个指针y，而a就是指针x的引用，也就是x的另一个名字。知道这个以后就可以补充汇编代码了！
• movl 8(%ebp), %eax显然是将参数a送入%eax，那么前面说了a是一个指针的指针的引用，也就是说此时的a是一个地址，那么①就应该是movl (%eax)，%ebx，(%eax)相当于取指针a指向的地址，可以作为一个数组的首地址，然后把a这个地址先放到一个寄存器%ebx里面
• %12(ebp)对应的就是参数b了，那接下来就应该计算a[b]的值了，数组地址的计算也很简单，a+b*4对应汇编就是(%ebx,%eax,4)，再把它送入%ebx就得到了a[b]的地址
• 然后取d的值20(%ebp)，送入%eax，再存到寄存器%edx中
• 然后再计算a[b][c]的地址，前面已经计算了a[b]为(%ebx,%eax,4)，所以a[b]+c*4=(%ebx, %eax ,4)，那么最后将d送入这个地址就可以了movl %edx,(%ebx,%eax,4)
• 最后return 0即对应 xorl %eax, %eax：按位异或，相同的位置为0，不同的位置为1，eax和eax的每一位都相同，所以相当于清零。
• 最终结果如下: