南開大學(xué)編譯原理第7章-wenkub.com
2025-01-15 17:39 本頁面
【正文】 return。 return。 return。 psclass == STATIC) p = stringf(“L%d”, genlabel(1))。 print(“pop ebx\n”)。 } lcc的運行時環(huán)境處理 ?返回序列 print(“mov esp,ebp\n”)。 p = q。 for (i = 0。 print(“push edi\n”)。 符號表 ?保存作用域和綁定信息 ?基本操作 ? 添加新標(biāo)識符 ——insert ? 查找標(biāo)識符 ——lookup ?符號表表項 ——記錄 ? 一致性 ? 某些信息保存在外部，用指針指向 ? 兩個主要組成部分 ?名字：定長字符串；統(tǒng)一保存，指針指向 ?屬性 實現(xiàn)方式一：線性表 ?數(shù)組方式 ? 固定大小，可能浪費，也可能不足 ?鏈表方式 ? 動態(tài)內(nèi)存分配，根據(jù)輸入大小確定 ?時間復(fù)雜度 ? 查找操作：與表大小線性關(guān)系 ? 插入操作 ?一個名字允許多個表項（不檢查）：常數(shù)時間 ?檢查重復(fù)表項：線性 ? n次插入， e次查找： (n+e)， O(n2) 實現(xiàn)方式二： hash表 ?開地址法：“鏈表數(shù)組” ?長度 m的數(shù)組，每個元素為指向一個符號表項鏈表的指針 ? hash函數(shù)： H(名字 )?{0, 1, …, m 1} ? H(名字 )=i?名字存入第 i個鏈表 ?若 hash函數(shù)設(shè)計良好，每個鏈表長度 n/m ? n次插入， e次查找： (n+e)/m ? hash函數(shù)的計算應(yīng)該很高效 hash函數(shù)的選擇 ?原則 ? 計算簡單 ? 使表項均勻分布 ?常用算法 ? 字符 ?整數(shù) ?名字 ?整數(shù)序列 c1, …, c k ? 對整數(shù)序列進行數(shù)學(xué)運算 ?單一整數(shù)結(jié)果 ? 對 m取模 ?如： h0=0， hi=65599*hi1+ci， H=hk%m 作用域的處理 ?每個作用域一個符號表 ? 對應(yīng)活動記錄，附著于語法樹結(jié)點 ?處理作用域 ——為過程、塊編號 ? 符號表項 ——保存名字和過程號 ? 名字匹配 ——名字字符串 amp。 t2 := B。 i := a[i]。 unsafe(a)。 begin x := 2。另外，若實參有左值的話，還要求出左值 2. 當(dāng)調(diào)用返回時，將形參當(dāng)前的右值復(fù)制回實參左值指向位置。 swap(a, b)。 y := temp。 procedure swap(var x, y : integer)。a, amp。 *x = *y。 swap(a, b)。 temp = x。 show。 begin r := 。 procedure small。 begin c end. 過程作為參數(shù)的情況（續(xù)） ?當(dāng)過程作為參數(shù)傳遞時，對應(yīng)的訪問鏈接也一起傳遞 Display表 ?一維數(shù)組 d[i]：將嵌套深度為 i的過程的訪問鏈接串起來 Display表（續(xù)） display表的設(shè)置 ?當(dāng)設(shè)置嵌套深度為 i的過程的活動記錄 ?舊的 d[i]值保存入新的活動記錄 ?設(shè)置 d[i]指向新的活動記錄 ?正確性：假定嵌套深度 j的過程調(diào)用深度 i的過程 ? ji： ?i=j+1， d[1]~d[j]無需改變， d[i]指向新活動記錄，上面 (a)圖 ? j=i： ?包含兩個過程，嵌套深度 1,2,…,i 1的過程必然是相同的，將舊 d[i]保存到新活動記錄，并設(shè)置它指向新活動記錄即可，上面 (d)圖 動態(tài)作用域 ?嵌套關(guān)系，調(diào)用關(guān)系 決定名字綁定 program dynamic(input, output)。 function f(n : integer) : integer。 procedure b(function h(n : integer) : integer)。 begin …a… …v… end {partition}。 procedure quicksort(m, n : integer)。 procedure exchange(i, j : integer)。 x : integer。 b(f)。 begin g := m * n end。 var m : integer。 B0B1 int b = 1。 } printf(“%d %d\n”, a, b)。 { int a = 2。 } 堆分配策略 ? 棧分配策略的局限，不能處理下列情況 ? 局部名字的值在活動結(jié)束后能夠保持 ? 被調(diào)用函數(shù)的活動生存期比調(diào)用者長 ——可用活動樹表示控制流的語言無法實現(xiàn) ? 對小的（或大小已知的）活動記錄 1. 為若干可能大小，創(chuàng)建空閑塊鏈表（靜態(tài)） 2. 為大小為 s的活動記錄分配空間，盡量使用 s?的空閑塊表， s?為大于等于 s的最小值。 return amp。 quicksort(1, 9)。 quicksort(i + 1, n) end end。 過程定義 過程名 形式參數(shù) 函數(shù)定義 過程體 Pascal源碼示例（續(xù)） procedure quicksort(m, n : integer)。 end。 var a : array [0..10] of integer。 procedure readarray。 function partition(y, z : integer) : integer。 var i : integer。 調(diào)用 實際參數(shù) Pascal源碼示例（續(xù)） begin a[0] := 9999。 end. 活動樹（ activation tree） ?控制流 ? 順序性：程序的執(zhí)行 ?一組操作步驟序列，在每個步驟，控制流開始于程序的特定位置 ? 過程的執(zhí)行：起始于過程體開始，最終控制權(quán)返回到過程調(diào)用點之后 ?活動樹 表示 ?活動 ：一次 執(zhí)行 （ execution） ?過程 P的 生存期 ， lifetime：
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1