系列文章戳這里👇

1. 什么是上下文無(wú)關(guān)文法、最左推導(dǎo)和最右推導(dǎo)
2. 如何判斷二義文法及消除文法二義性
3. 何時(shí)需要消除左遞歸
4. 什么是句柄、什么是自上而下、自下而上分析
5. 什么是LL(1)、LR(0)、LR(1)文法、LR分析表
6. LR(0)、SLR(1)、LR(1)、LALR(1)文法之間的關(guān)系
7. 編譯原理第三章習(xí)題
8. 詞法分析、構(gòu)建DFA、上下文無(wú)關(guān)文法、LL(1)分析、提取正規(guī)式
9. 證明LL(1)、SLR(1)、LALR(1)文法
10. 翻譯方案、屬性棧代碼
11. 【運(yùn)行時(shí)環(huán)境】什么是活動(dòng)記錄、 活動(dòng)記錄與匯編代碼的關(guān)系

什么是活動(dòng)記錄？

相信大家也和我一樣，覺(jué)得編譯原理在運(yùn)行環(huán)境這部分比較難理解，由于機(jī)器是棧式運(yùn)行的，所以里面很多操作并不利于我們理解，下面分享一下我自己對(duì)活動(dòng)記錄這一塊的部分理解，也有一些x86匯編的內(nèi)容

活動(dòng)記錄－AR （Activation Record）

• 是一連續(xù)存儲(chǔ)區(qū)域，用于管理與存放和程序單元執(zhí)行相關(guān)的重要信息。
• 下圖就是活動(dòng)記錄的內(nèi)容，簡(jiǎn)單來(lái)說(shuō)，活動(dòng)記錄是用來(lái)記錄一段函數(shù)信息的地方，
  • 很好理解，當(dāng)我們?cè)趯慍程序時(shí)，如果我們要用一個(gè)函數(shù)調(diào)用另一個(gè)函數(shù)，那么在調(diào)用結(jié)束后怎么回到原來(lái)的函數(shù)呢？
    • 就是活動(dòng)記錄在幫忙，他幫我們把調(diào)用者的地址記錄下來(lái)，并用控制鏈相連。
  • 而訪問(wèn)鏈?zhǔn)怯涗洰?dāng)前函數(shù)可以訪問(wèn)的函數(shù)地址，這個(gè)是可選擇的，意思就是活動(dòng)記錄中可以沒(méi)有它。
  • 返回值自然就是該函數(shù)return的值，實(shí)在參數(shù)其實(shí)就是函數(shù)的參數(shù)，也就是int fun(int a,int b)里面的a和b
  • 局部數(shù)據(jù)就是函數(shù)體里面定義的局部變量
  • 機(jī)器狀態(tài)就是活動(dòng)記錄的一個(gè)指針，它是活動(dòng)記錄的基地址，x86匯編中一般表示為%ebp，我們可以用它來(lái)找到活動(dòng)記錄里面參數(shù)的位置，比如8(%ebp)就是ebp+8，
• 
• 問(wèn)題來(lái)了，如何獲取活動(dòng)記錄里的內(nèi)容呢？上面說(shuō)了，可以通過(guò)%ebp，如下圖所示，bp進(jìn)行偏移就可以取得的對(duì)應(yīng)位置的值！

活動(dòng)記錄的內(nèi)容

• 下圖是棧式分配下的活動(dòng)記錄內(nèi)容布局，其中返回值往下即為高地址到低地址，所以我們要調(diào)用參數(shù)就需要用bp+xx去取，而局部參數(shù)就是bp-xx，還不懂也沒(méi)關(guān)系，后面會(huì)舉個(gè)栗子，應(yīng)該會(huì)更好理解

• 臨時(shí)區(qū)域。用以保存臨時(shí)計(jì)算結(jié)果

• 局部數(shù)據(jù)區(qū)。源程序中程序單元聲明的局部變量對(duì)應(yīng)在此區(qū)域。

• 機(jī)器狀態(tài)保存區(qū)。存有機(jī)器的寄存器，程序指令計(jì)數(shù)器 ip（返回地址）等。

• 訪問(wèn)鏈（靜態(tài)鏈）。當(dāng)前程序單元可以訪問(wèn)的（靜態(tài)程序中）外圍程序單元的活動(dòng)記錄鏈。

• 控制鏈（動(dòng)態(tài)鏈）。程序單元的活動(dòng)記錄按它們的生成（或調(diào)用）次序串成鏈。

• 實(shí)在參數(shù)

• 返回值

舉個(gè)栗子

• 
• 那么這個(gè)C程序的活動(dòng)記錄安排你能畫出來(lái)嗎？試試看？
• 函數(shù)g被調(diào)用時(shí)，活動(dòng)記錄棧的（大致）內(nèi)容如下：
• 可以看到主函數(shù)中調(diào)用了h，而h調(diào)用了g，他們的old bp就是控制鏈，分別指向調(diào)用者，他們都有一個(gè)局部變量a，并且此時(shí)bp在函數(shù)g的活動(dòng)記錄中，sp是棧頂指針(始終指向棧頂)

再舉個(gè)栗子

• 

• 這是一個(gè)非常簡(jiǎn)單的c函數(shù)程序，你能畫出它的活動(dòng)記錄圖，并標(biāo)明各個(gè)參數(shù)對(duì)應(yīng)bp的偏移嗎？如果我們要取參數(shù)則上移，要取局部變量則下移，這里是int，占4個(gè)字節(jié)，所以分別是bp+8和bp-4

• 更深一步，讓我們一起看一看這段程序的匯編代碼是怎么樣的吧！x86匯編是典型的棧式機(jī)，首先pushl %ebp將當(dāng)前bp壓棧，movl %esp,%ebp將這個(gè)位置作為活動(dòng)記錄的基址，即把esp送入ebp，subl $8, %esp為局部數(shù)據(jù)分配空間，有兩個(gè)整型變量，所以esp-8，movl 8(%ebp), %eax取參數(shù)a的值放入寄存器%eax，再movl %eax,-4(%ebp)將其賦給局部變量，后兩句同理將b賦給d，最后leave和ret回收活動(dòng)記錄，恢復(fù)原先保存的機(jī)器狀態(tài)，leave相當(dāng)于mov bp,sp ;pop bp //恢復(fù)調(diào)用者的bp

• 

再再舉個(gè)栗子

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

(1)準(zhǔn)確畫出該函數(shù)的活動(dòng)記錄內(nèi)容安排。

• 同理，也很簡(jiǎn)單就能畫出來(lái)

(2)補(bǔ)全 5 處帶有下劃線的匯編代碼。

那么這里的匯編代碼怎么填呢？

• 可以看到參數(shù)分別為(int** &a,int b, int c,int &d)，如果你不清楚指針引用的話，可以先看一下這篇文章《C語(yǔ)言指針、引用》，那么其中a是一個(gè)引用，它是指向某一個(gè)指針的指針的引用，也就是有一個(gè)指針x，它指向另一個(gè)指針y，而a就是指針x的引用，也就是x的另一個(gè)名字。知道這個(gè)以后就可以補(bǔ)充匯編代碼了！
• movl 8(%ebp), %eax顯然是將參數(shù)a送入%eax，那么前面說(shuō)了a是一個(gè)指針的指針的引用，也就是說(shuō)此時(shí)的a是一個(gè)地址，那么①就應(yīng)該是movl (%eax)，%ebx，(%eax)相當(dāng)于取指針a指向的地址，可以作為一個(gè)數(shù)組的首地址，然后把a(bǔ)這個(gè)地址先放到一個(gè)寄存器%ebx里面
• %12(ebp)對(duì)應(yīng)的就是參數(shù)b了，那接下來(lái)就應(yīng)該計(jì)算a[b]的值了，數(shù)組地址的計(jì)算也很簡(jiǎn)單，a+b*4對(duì)應(yīng)匯編就是(%ebx,%eax,4)，再把它送入%ebx就得到了a[b]的地址
• 然后取d的值20(%ebp)，送入%eax，再存到寄存器%edx中
• 然后再計(jì)算a[b][c]的地址，前面已經(jīng)計(jì)算了a[b]為(%ebx,%eax,4)，所以a[b]+c*4=(%ebx, %eax ,4)，那么最后將d送入這個(gè)地址就可以了movl %edx,(%ebx,%eax,4)
• 最后return 0即對(duì)應(yīng) xorl %eax, %eax：按位異或，相同的位置為0，不同的位置為1，eax和eax的每一位都相同，所以相當(dāng)于清零。
• 最終結(jié)果如下: