南開(kāi)大學(xué)編譯原理第7章-資料下載頁(yè)
2025-01-18 17:39本頁(yè)面
【正文】 t3 := f(t1)。 t4 := f(t2)。 x := t3 + t4。 符號(hào)表 ?保存作用域和綁定信息 ?基本操作 ? 添加新標(biāo)識(shí)符 ——insert ? 查找標(biāo)識(shí)符 ——lookup ?符號(hào)表表項(xiàng) ——記錄 ? 一致性 ? 某些信息保存在外部，用指針指向 ? 兩個(gè)主要組成部分 ?名字：定長(zhǎng)字符串；統(tǒng)一保存，指針指向 ?屬性 實(shí)現(xiàn)方式一：線(xiàn)性表 ?數(shù)組方式 ? 固定大小，可能浪費(fèi)，也可能不足 ?鏈表方式 ? 動(dòng)態(tài)內(nèi)存分配，根據(jù)輸入大小確定 ?時(shí)間復(fù)雜度 ? 查找操作：與表大小線(xiàn)性關(guān)系 ? 插入操作 ?一個(gè)名字允許多個(gè)表項(xiàng)（不檢查）：常數(shù)時(shí)間 ?檢查重復(fù)表項(xiàng)：線(xiàn)性 ? n次插入， e次查找： (n+e)， O(n2) 實(shí)現(xiàn)方式二： hash表 ?開(kāi)地址法：“鏈表數(shù)組” ?長(zhǎng)度 m的數(shù)組，每個(gè)元素為指向一個(gè)符號(hào)表項(xiàng)鏈表的指針 ? hash函數(shù)： H(名字 )?{0, 1, …, m 1} ? H(名字 )=i?名字存入第 i個(gè)鏈表 ?若 hash函數(shù)設(shè)計(jì)良好，每個(gè)鏈表長(zhǎng)度 n/m ? n次插入， e次查找： (n+e)/m ? hash函數(shù)的計(jì)算應(yīng)該很高效 hash函數(shù)的選擇 ?原則 ? 計(jì)算簡(jiǎn)單 ? 使表項(xiàng)均勻分布 ?常用算法 ? 字符 ?整數(shù) ?名字 ?整數(shù)序列 c1, …, c k ? 對(duì)整數(shù)序列進(jìn)行數(shù)學(xué)運(yùn)算 ?單一整數(shù)結(jié)果 ? 對(duì) m取模 ?如： h0=0， hi=65599*hi1+ci， H=hk%m 作用域的處理 ?每個(gè)作用域一個(gè)符號(hào)表 ? 對(duì)應(yīng)活動(dòng)記錄，附著于語(yǔ)法樹(shù)結(jié)點(diǎn) ?處理作用域 ——為過(guò)程、塊編號(hào) ? 符號(hào)表項(xiàng) ——保存名字和過(guò)程號(hào) ? 名字匹配 ——名字字符串 amp。過(guò)程編號(hào) ? 符號(hào)表操作 ?lookup：查找最近創(chuàng)建的表項(xiàng) ?insert：創(chuàng)建新表項(xiàng) ?delete：刪除最近創(chuàng)建的表項(xiàng) 鏈表實(shí)現(xiàn)方式 ? front：最近創(chuàng)建的符號(hào)表項(xiàng) ? insert：創(chuàng)建表項(xiàng)，插入到 insert之前 ? lookup：從 front開(kāi)始遍歷鏈表 ? delete ? 無(wú)需保存過(guò)程編號(hào) ? 同一過(guò)程名字相鄰，保存每個(gè)過(guò)程位置即可 hash表實(shí)現(xiàn)方式 ?lookup：相同名字總是存入同一鏈表，在對(duì)應(yīng)鏈表搜索相同過(guò)程編號(hào)者即可 ?delete ?無(wú)需遍歷 hash表所有鏈表 ?作用域指針， scope link，相同作用域的所有表項(xiàng)串接起來(lái) ?指針設(shè)置問(wèn)題 高級(jí)語(yǔ)言的動(dòng)態(tài)內(nèi)存分配 ?堆 ?顯式方式： new, delete ?隱式方式：中間計(jì)算結(jié)果 ?垃圾內(nèi)存（ garbage） ? 已分配內(nèi)存未被任何指針引用 ? 垃圾收集， garbage collection ?空懸引用（ dangling reference） ? 指針指向無(wú)效區(qū)域 動(dòng)態(tài)內(nèi)存分配的處理 ?顯式方式，定長(zhǎng)塊分配 隱式方式的內(nèi)存釋放問(wèn)題 ? 記錄指向內(nèi)存塊的所有指針 ? 處理兩個(gè)問(wèn)題 1. 塊邊界 2. 辨別塊是否被使用 a) 引用計(jì)數(shù)法， reference count 記錄引用塊的指針數(shù)目 計(jì)數(shù) =0?可以釋放 性能影響較大 b) 標(biāo)記技術(shù)， marking technique 暫停程序，檢查所有指針 引用的內(nèi)存塊標(biāo)記為 used 未引用的內(nèi)存塊標(biāo)記未 unused，可釋放 lcc的運(yùn)行時(shí)環(huán)境處理 callee的幀 輸入?yún)?shù) 返回地址 存儲(chǔ) ebx 存儲(chǔ) esi 存儲(chǔ) edi 存儲(chǔ) ebp 局部變量和全局變量 caller的幀 esp ebp 0 4 8 12 16 20 lcc的運(yùn)行時(shí)環(huán)境處理 ?調(diào)用序列 print(“%s: \n”, f)。 print(“push ebx\n”)。 print(“push esi\n”)。 print(“push edi\n”)。 print(“push ebp\n”)。 print(“mov ebp,esp\n”)。 lcc的運(yùn)行時(shí)環(huán)境處理 ?處理參數(shù) offset = 16 + 4。 for (i = 0。 callee[i]。 i++) { Symbol p = callee[i]。 Symbol q = caller[i]。 p = q。 p = q = stringf(“%d”, p)。 psclass = qsclass = AUTO。 offset += roundup(qtypesize, 4)。 } lcc的運(yùn)行時(shí)環(huán)境處理 ?返回序列 print(“mov esp,ebp\n”)。 print(“pop ebp\n”)。 print(“pop edi\n”)。 print(“pop esi\n”)。 print(“pop ebx\n”)。 print(“ret\n”)。 lcc的運(yùn)行時(shí)環(huán)境處理 ?數(shù)據(jù)定義 ?靜態(tài)局部符號(hào)保證唯一名字 if (pscope = LOCAL amp。amp。 psclass == STATIC) p = stringf(“L%d”, genlabel(1))。 ?生成的符號(hào) ?合法匯編名 if (pgenerated) p = stringf(“L%s”, pname)。 ?全局符號(hào)加下劃線(xiàn)前綴 if (pscope == GLOBAL || psclass == EXTERN) p = stringf(“_%s”, pname)。 ... lcc的運(yùn)行時(shí)環(huán)境處理 ?數(shù)據(jù)定義 ?空間分配 case C: print(“db %d\n”, )。 return。 case S: print(“dw %d\n”, )。 return。 case I: print(“dd %d\n”, )。 return。 case U: print(“dd 0%xH\n”, )。 return。 case P: print(“dd 0%xH\n”, )。 return。 …
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1