編譯原理

出版者的話<br>專家指導(dǎo)委員會(huì)<br>譯者序<br>前言<br>第1章   編譯簡(jiǎn)介 1<br>1.1   編譯器 1<br>1.1.1   編譯的分析-綜合模型 1<br>1.1.2   編譯器的前驅(qū)與后繼 3<br>1.2   源程序分析 3<br>1.2.1   詞法分析 3<br>1.2.2   語(yǔ)法分析 3<br>1.2.3   語(yǔ)義分析 5<br>1.2.4   文本格式器中的分析 5<br>1.3   編譯器的各階段 6<br>1.3.1   符號(hào)表管理 7<br>1.3.2   錯(cuò)誤檢測(cè)與報(bào)告 7<br>1.3.3   各分析階段 7<br>1.3.4   中間代碼生成 9<br>1.3.5   代碼優(yōu)化 9<br>1.3.6   代碼生成 10<br>1.4   編譯器的伙伴 10<br>1.4.1   預(yù)處理器 10<br>1.4.2   匯編器 11<br>1.4.3   兩遍匯編 12<br>1.4.4   裝配器和連接編輯器 12<br>1.5   編譯器各階段的分組 13<br>1.5.1   前端與后端 13<br>1.5.2   編譯器的遍 13<br>1.5.3   減少編譯的遍數(shù) 14<br>1.6   編譯器的構(gòu)造工具 14<br>參考文獻(xiàn)注釋 15<br>第2章   簡(jiǎn)單的一遍編譯器 17<br>2.1   概述 17<br>2.2   語(yǔ)法定義 17<br>2.2.1   分析樹(shù) 19<br>2.2.2   二義性 20<br>2.2.3   操作符的結(jié)合規(guī)則 20<br>2.2.4   操作符的優(yōu)先級(jí) 21<br>2.3   語(yǔ)法制導(dǎo)翻譯 22<br>2.3.1   后綴表示 22<br>2.3.2   語(yǔ)法制導(dǎo)定義 22<br>2.3.3   綜合屬性 23<br>2.3.4   深度優(yōu)先遍歷 24<br>2.3.5   翻譯模式 25<br>2.3.6   翻譯的輸出 25<br>2.4   語(yǔ)法分析 26<br>2.4.1   自頂向下語(yǔ)法分析 27<br>2.4.2   預(yù)測(cè)分析法 29<br>2.4.3   何時(shí)使用產(chǎn)生式 30<br>2.4.4   設(shè)計(jì)一個(gè)預(yù)測(cè)語(yǔ)法分析器 30<br>2.4.5   左遞歸 31<br>2.5   簡(jiǎn)單表達(dá)式的翻譯器 32<br>2.5.1   抽象語(yǔ)法和具體語(yǔ)法 32<br>2.5.2   調(diào)整翻譯模式 33<br>2.5.3   非終結(jié)符expr. term 和rest 的過(guò)程 33<br>2.5.4   翻譯器的優(yōu)化 35<br>2.5.5   完整程序 35<br>2.6   詞法分析 37<br>2.6.1   剔除空白符和注釋 37<br>2.6.2   常數(shù) 37<br>2.6.3   識(shí)別標(biāo)識(shí)符和關(guān)鍵字 37<br>2.6.4   詞法分析器的接口 38<br>2.6.5   詞法分析器 38<br>2.7   符號(hào)表 40<br>2.7.1   符號(hào)表接口 40<br>2.7.2   處理保留的關(guān)鍵字 41<br>2.7.3   符號(hào)表的實(shí)現(xiàn)方法 41<br>2.8   抽象堆棧機(jī) 42<br>2.8.1   算術(shù)指令 42<br>2.8.2   左值和右值 43<br>2.8.3   堆棧操作 43<br>2.8.4   表達(dá)式的翻譯 43<br>2.8.5   控制流 44<br>2.8.6   語(yǔ)句的翻譯 44<br>2.8.7   輸出一個(gè)翻譯 45<br>2.9   技術(shù)的綜合 46<br>2.9.1   翻譯器的描述 46<br>2.9.2   詞法分析器模塊lexer.c 47<br>2.9.3   語(yǔ)法分析器模塊parser.c 48<br>2.9.4   輸出模塊emitter.c 48<br>2.9.5   符號(hào)表模塊symbol.c和init.c 48<br>2.9.6   錯(cuò)誤處理模塊error.c 48<br>2.9.7   編譯器的建立 48<br>2.9.8   程序清單 49<br>練習(xí) 53<br>編程練習(xí) 54<br>參考文獻(xiàn)注釋 55<br>第3章   詞法分析 57<br>3.1   詞法分析器的作用 57<br>3.1.1   詞法分析中的問(wèn)題 58<br>3.1.2   記號(hào). 模式. 詞素 58<br>3.1.3   記號(hào)的屬性 59<br>3.1.4   詞法錯(cuò)誤 60<br>3.2   輸入緩沖 60<br>3.2.1   雙緩沖區(qū) 61<br>3.2.2   標(biāo)志 62<br>3.3   記號(hào)的描述 62<br>3.3.1   串和語(yǔ)言 62<br>3.3.2   語(yǔ)言上的運(yùn)算 63<br>3.3.3   正規(guī)表達(dá)式 64<br>3.3.4   正規(guī)定義 65<br>3.3.5   縮寫表示法 66<br>3.3.6   非正規(guī)集 66<br>3.4   記號(hào)的識(shí)別 67<br>3.4.1   狀態(tài)轉(zhuǎn)換圖 68<br>3.4.2   狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn) 70<br>3.5  詞法分析器描述語(yǔ)言 72<br>3.5.1   Lex說(shuō)明 72<br>3.5.2   超前掃描操作 75<br>3.6   有窮自動(dòng)機(jī) 76<br>3.6.1   不確定的有窮自動(dòng)機(jī) 77<br>3.6.2   確定的有窮自動(dòng)機(jī) 78<br>3.6.3   從NFA到DFA的變換 79<br>3.7  從正規(guī)表達(dá)式到NFA 81<br>3.7.1   從正規(guī)表達(dá)式構(gòu)造NFA 81<br>3.7.2   NFA的雙堆棧模擬 84<br>3.7.3   時(shí)間空間的權(quán)衡 85<br>3.8   設(shè)計(jì)詞法分析器的生成器 85<br>3.8.1   基于NFA的模式匹配 86<br>3.8.2   詞法分析器的DFA 88<br>3.8.3   實(shí)現(xiàn)超前掃描操作 88<br>3.9   基于DFA的模式匹配器的優(yōu)化 89<br>3.9.1   NFA的重要狀態(tài) 89<br>3.9.2   從正規(guī)表達(dá)式到DFA 89<br>3.9.3   最小化DFA的狀態(tài)數(shù) 93<br>3.9.4   詞法分析器的狀態(tài)最小化 95<br>3.9.5   表壓縮方法 95<br>練習(xí) 97<br>編程練習(xí) 103<br>參考文獻(xiàn)注釋 103<br>第4章   語(yǔ)法分析 105<br>4.1   語(yǔ)法分析器的作用 105<br>4.1.1   語(yǔ)法錯(cuò)誤的處理 106<br>4.1.2   錯(cuò)誤恢復(fù)策略 108<br>4.2   上下文無(wú)關(guān)文法 109<br>4.2.1   符號(hào)的使用約定 110<br>4.2.2   推導(dǎo) 110<br>4.2.3   分析樹(shù)和推導(dǎo) 112<br>4.2.4   二義性 113<br>4.3   文法的編寫 113<br>4.3.1   正規(guī)表達(dá)式和上下文無(wú)關(guān)文法的<br>比較 114<br>4.3.2   驗(yàn)證文法所產(chǎn)生的語(yǔ)言 114<br>4.3.3   消除二義性 115<br>4.3.4   消除左遞歸 116<br>4.3.5   提取左因子 117<br>4.3.6   非上下文無(wú)關(guān)語(yǔ)言的結(jié)構(gòu) 118<br>4.4   自頂向下語(yǔ)法分析 120<br>4.4.1   遞歸下降語(yǔ)法分析法 120<br>4.4.2   預(yù)測(cè)語(yǔ)法分析器 121<br>4.4.3   預(yù)測(cè)語(yǔ)法分析器的狀態(tài)轉(zhuǎn)換圖 121<br>4.4.4   非遞歸的預(yù)測(cè)分析 123<br>4.4.5   FIRST和FOLLOW 124<br>4.4.6   預(yù)測(cè)分析表的構(gòu)造 125<br>4.4.7   LL(1)文法 126<br>4.4.8   預(yù)測(cè)分析的錯(cuò)誤恢復(fù) 127<br>4.5   自底向上語(yǔ)法分析 128<br>4.5.1   句柄 129<br>4.5.2   句柄裁剪 130<br>4.5.3   用棧實(shí)現(xiàn)移動(dòng)歸約分析 131<br>4.5.4   活前綴 133<br>4.5.5   移動(dòng)歸約分析過(guò)程中的沖突 133<br>4.6   算符優(yōu)先分析法 134<br>4.6.1   使用算符優(yōu)先關(guān)系 135<br>4.6.2   從結(jié)合律和優(yōu)先級(jí)獲得算符優(yōu)先<br>關(guān)系 136<br>4.6.3   處理一元操作符 137<br>4.6.4   優(yōu)先函數(shù) 137<br>4.6.5   算符優(yōu)先分析中的錯(cuò)誤恢復(fù) 139<br>4.7   LR語(yǔ)法分析器 142<br>4.7.1   LR語(yǔ)法分析算法 142<br>4.7.2   LR文法 145<br>4.7.3   構(gòu)造SLR語(yǔ)法分析表 146<br>4.7.4   構(gòu)造規(guī)范LR語(yǔ)法分析表 151<br>4.7.5   構(gòu)造LALR語(yǔ)法分析表 155<br>4.7.6   LALR語(yǔ)法分析表的有效構(gòu)造<br>方法 158<br>4.7.7   LR語(yǔ)法分析表的壓縮 161<br>4.8   二義文法的應(yīng)用 163<br>4.8.1   使用優(yōu)先級(jí)和結(jié)合規(guī)則來(lái)解決分析<br>動(dòng)作的沖突 163<br>4.8.2   懸空else的二義性 164<br>4.8.3   特例產(chǎn)生式引起的二義性 165<br>4.8.4    LR語(yǔ)法分析中的錯(cuò)誤恢復(fù) 167<br>4.9   語(yǔ)法分析器的生成器 168<br>4.9.1   語(yǔ)法分析器的生成器Yacc 169<br>4.9.2   用Yacc處理二義文法 171<br>4.9.3   用Lex建立Yacc的詞法分析器 173<br>4.9.4   Yacc的錯(cuò)誤恢復(fù) 174<br>練習(xí) 174<br>參考文獻(xiàn)注釋 182<br>第5章   語(yǔ)法制導(dǎo)翻譯 185<br>5.1   語(yǔ)法制導(dǎo)定義 185<br>5.1.1   語(yǔ)法制導(dǎo)定義的形式 186<br>5.1.2   綜合屬性 186<br>5.1.3   繼承屬性 187<br>5.1.4   依賴圖 187<br>5.1.5   計(jì)算順序 189<br>5.2   語(yǔ)法樹(shù)的構(gòu)造 189<br>5.2.1   語(yǔ)法樹(shù) 190<br>5.2.2   構(gòu)造表達(dá)式的語(yǔ)法樹(shù) 190<br>5.2.3   構(gòu)造語(yǔ)法樹(shù)的語(yǔ)法制導(dǎo)定義 191<br>5.2.4   表達(dá)式的無(wú)環(huán)有向圖 192<br>5.3   自底向上計(jì)算S屬性定義 194<br>5.4   L屬性定義 195<br>5.4.1   L屬性定義 196<br>5.4.2   翻譯模式 196<br>5.5   自頂向下翻譯 198<br>5.5.1   從翻譯模式中消除左遞歸 198<br>5.5.2   預(yù)測(cè)翻譯器的設(shè)計(jì) 201<br>5.6   自底向上計(jì)算繼承屬性 202<br>5.6.1   刪除嵌入在翻譯模式中的動(dòng)作 202<br>5.6.2   分析棧中的繼承屬性 203<br>5.6.3   模擬繼承屬性的計(jì)算 204<br>5.6.4   用綜合屬性代替繼承屬性 206<br>5.6.5   一個(gè)難計(jì)算的語(yǔ)法制導(dǎo)定義 207<br>5.7   遞歸計(jì)算 207<br>5.7.1   從左到右遍歷 207<br>5.7.2   其他遍歷方法 208<br>5.8   編譯時(shí)屬性值的空間分配 209<br>5.8.1   在編譯時(shí)為屬性分配空間 209<br>5.8.2   避免復(fù)制 211<br>5.9   編譯器構(gòu)造時(shí)的空間分配 211<br>5.9.1   從文法中預(yù)知生存期 212<br>5.9.2   不相重疊的生存期 214<br>5.10   語(yǔ)法制導(dǎo)定義的分析 215<br>5.10.1   屬性的遞歸計(jì)算 216<br>5.10.2   強(qiáng)無(wú)環(huán)的語(yǔ)法制導(dǎo)定義 216<br>5.10.3   環(huán)形檢測(cè) 217<br>練習(xí) 219<br>參考文獻(xiàn)注釋 221<br>第6章   類型檢查 223<br>6.1   類型系統(tǒng) 224<br>6.1.1   類型表達(dá)式 224<br>6.1.2   類型系統(tǒng) 225<br>6.1.3   靜態(tài)和動(dòng)態(tài)類型檢查 226<br>6.1.4   錯(cuò)誤恢復(fù) 226<br>6.2   一個(gè)簡(jiǎn)單的類型檢查器的說(shuō)明 226<br>6.2.1   一種簡(jiǎn)單語(yǔ)言 226<br>6.2.2   表達(dá)式的類型檢查 227<br>6.2.3   語(yǔ)句的類型檢查 228<br>6.2.4   函數(shù)的類型檢查 228<br>6.3   類型表達(dá)式的等價(jià) 229<br>6.3.1   類型表達(dá)式的結(jié)構(gòu)等價(jià) 229<br>6.3.2   類型表達(dá)式的名字 231<br>6.3.3   類型表示中的環(huán) 232<br>6.4   類型轉(zhuǎn)換 233<br>6.5   函數(shù)和運(yùn)算符的重載 234<br>6.5.1   子表達(dá)式的可能類型的集合 235<br>6.5.2   縮小可能類型的集合 236<br>6.6   多態(tài)函數(shù) 237<br>6.6.1   為什么要使用多態(tài)函數(shù) 237<br>6.6.2   類型變量 238<br>6.6.3   包含多態(tài)函數(shù)的語(yǔ)言 239<br>6.6.4   代換. 實(shí)例和合一 240<br>6.6.5   多態(tài)函數(shù)的檢查 241<br>6.7   合一算法 244<br>練習(xí) 247<br>參考文獻(xiàn)注釋 251<br>第7章   運(yùn)行時(shí)環(huán)境 253<br>7.1   源語(yǔ)言問(wèn)題 253<br>7.1.1   過(guò)程 253<br>7.1.2   活動(dòng)樹(shù) 253<br>7.1.3   控制棧 255<br>7.1.4   聲明的作用域 256<br>7.1.5   名字的綁定 256<br>7.1.6   一些問(wèn)題 257<br>7.2   存儲(chǔ)組織 257<br>7.2.1   運(yùn)行時(shí)內(nèi)存的劃分 257<br>7.2.2   活動(dòng)記錄 258<br>7.2.3   編譯時(shí)的局部數(shù)據(jù)布局 259<br>7.3   存儲(chǔ)分配策略 260<br>7.3.1   靜態(tài)存儲(chǔ)分配 260<br>7.3.2   棧式存儲(chǔ)分配 262<br>7.3.3   懸空引用 265<br>7.3.4   堆式存儲(chǔ)分配 265<br>7.4   對(duì)非局部名字的訪問(wèn) 266<br>7.4.1   程序塊 267<br>7.4.2   無(wú)嵌套過(guò)程的詞法作用域 268<br>7.4.3   包含嵌套過(guò)程的詞法作用域 269<br>7.4.4   動(dòng)態(tài)作用域 274<br>7.5   參數(shù)傳遞 275<br>7.5.1   傳值調(diào)用 275<br>7.5.2   引用調(diào)用 276<br>7.5.3   復(fù)制-恢復(fù) 277<br>7.5.4   傳名調(diào)用 277<br>7.6   符號(hào)表 278<br>7.6.1   符號(hào)表表項(xiàng) 278<br>7.6.2   名字中的字符 279<br>7.6.3   存儲(chǔ)分配信息 280<br>7.6.4   符號(hào)表的線性表數(shù)據(jù)結(jié)構(gòu) 280<br>7.6.5   散列表 281<br>7.6.6   表示作用域的信息 283<br>7.7   支持動(dòng)態(tài)存儲(chǔ)分配的語(yǔ)言措施 285<br>7.7.1   垃圾單元 285<br>7.7.2   懸空引用 286<br>7.8   動(dòng)態(tài)存儲(chǔ)分配技術(shù) 287<br>7.8.1   固定塊的顯式分配 287<br>7.8.2   變長(zhǎng)塊的顯式分配 287<br>7.8.3   隱式存儲(chǔ)釋放 288<br>7.9   Fortran語(yǔ)言的存儲(chǔ)分配 288<br>7.9.1   COMMON區(qū)域中的數(shù)據(jù) 289<br>7.9.2   一個(gè)簡(jiǎn)單的等價(jià)算法 290<br>7.9.3   Fortran語(yǔ)言的等價(jià)算法 292<br>7.9.4   映射數(shù)據(jù)區(qū) 294<br>練習(xí) 294<br>參考文獻(xiàn)注釋 298<br>第8章   中間代碼生成 299<br>8.1   中間語(yǔ)言 299<br>8.1.1   圖表示 299<br>8.1.2   三地址碼 300<br>8.1.3   三地址語(yǔ)句的類型 301<br>8.1.4   語(yǔ)法制導(dǎo)翻譯生成三地址碼 302<br>8.1.5   三地址語(yǔ)句的實(shí)現(xiàn) 303<br>8.1.6   表示方法比較：間址的使用 305<br>8.2   聲明語(yǔ)句 305<br>8.2.1   過(guò)程中的聲明語(yǔ)句 305<br>8.2.2   跟蹤作用域信息 306<br>8.2.3   記錄中的域名 308<br>8.3   賦值語(yǔ)句 309<br>8.3.1   符號(hào)表中的名字 309<br>8.3.2   臨時(shí)名字的重用 310<br>8.3.3   尋址數(shù)組元素 311<br>8.3.4   數(shù)組元素尋址的翻譯模式 312<br>8.3.5   賦值語(yǔ)句中的類型轉(zhuǎn)換 314<br>8.3.6   記錄域的訪問(wèn) 315<br>8.4   布爾表達(dá)式 315<br>8.4.1   翻譯布爾表達(dá)式的方法 316<br>8.4.2   數(shù)值表示 316<br>8.4.3   短路代碼 317<br>8.4.4   控制流語(yǔ)句 317<br>8.4.5   布爾表達(dá)式的控制流翻譯 319<br>8.4.6   混合模式的布爾表達(dá)式 321<br>8.5   case語(yǔ)句 321<br>8.6   回填 323<br>8.6.1   布爾表達(dá)式 323<br>8.6.2   控制流語(yǔ)句 326<br>8.6.3   翻譯的實(shí)現(xiàn)方案 326<br>8.6.4   標(biāo)號(hào)和goto 327<br>8.7   過(guò)程調(diào)用 328<br>8.7.1   調(diào)用序列 328<br>8.7.2   一個(gè)簡(jiǎn)單的例子 328<br>練習(xí) 329<br>參考文獻(xiàn)注釋 331<br>第9章   代碼生成 333<br>9.1   代碼生成器設(shè)計(jì)中的問(wèn)題 333<br>9.1.1   代碼生成器的輸入 333<br>9.1.2   目標(biāo)程序 334<br>9.1.3   存儲(chǔ)管理 334<br>9.1.4   指令選擇 334<br>9.1.5   寄存器分配 335<br>9.1.6   計(jì)算次序的選擇 336<br>9.1.7   代碼生成方法 336<br>9.2   目標(biāo)機(jī)器 336<br>9.3   運(yùn)行時(shí)存儲(chǔ)管理 338<br>9.3.1   靜態(tài)分配 339<br>9.3.2   棧式分配 340<br>9.3.3   名字的運(yùn)行地址 342<br>9.4   基本塊和流圖 343<br>9.4.1   基本塊 343<br>9.4.2   基本塊的變換 344<br>9.4.3   保結(jié)構(gòu)變換 344<br>9.4.4   代數(shù)變換 345<br>9.4.5   流圖 345<br>9.4.6   基本塊的表示 345<br>9.4.7   循環(huán) 346<br>9.5   下次引用信息 346<br>9.5.1   計(jì)算下次引用信息 346<br>9.5.2   臨時(shí)名字的存儲(chǔ)分配 347<br>9.6   一個(gè)簡(jiǎn)單的代碼生成器 347<br>9.6.1   寄存器描述符和地址描述符 348<br>9.6.2   代碼生成算法 348<br>9.6.3   函數(shù)getreg 349<br>9.6.4   為其他類型的語(yǔ)句生成代碼 350<br>9.6.5   條件語(yǔ)句 351<br>9.7   寄存器分配與指派 351<br>9.7.1   全局寄存器分配 352<br>9.7.2   引用計(jì)數(shù) 352<br>9.7.3  外層循環(huán)的寄存器指派 353<br>9.7.4   圖染色法寄存器分配 354<br>9.8   基本塊的dag表示法 354<br>9.8.1   dag的構(gòu)造 355<br>9.8.2   dag的應(yīng)用 357<br>9.8.3   數(shù)組. 指針和過(guò)程調(diào)用 358<br>9.9   窺孔優(yōu)化 359<br>9.9.1   冗余加載與保存 360<br>9.9.2   不可達(dá)代碼 360<br>9.9.3   控制流優(yōu)化 361<br>9.9.4   代數(shù)化簡(jiǎn) 361<br>9.9.5   強(qiáng)度削弱 361<br>9.9.6   機(jī)器語(yǔ)言的使用 362<br>9.10   從dag生成代碼 362<br>9.10.1   重排序 362<br>9.10.2   對(duì)dag的啟發(fā)式排序 362<br>9.10.3   樹(shù)的最優(yōu)排序 363<br>9.10.4   標(biāo)記算法 364<br>9.10.5   從標(biāo)記樹(shù)中產(chǎn)生代碼 364<br>9.10.6   多寄存器操作 367<br>9.10.7   代數(shù)性質(zhì) 367<br>9.10.8   公共子表達(dá)式 368<br>9.11   動(dòng)態(tài)規(guī)劃代碼生成算法 368<br>9.11.1   一種寄存器計(jì)算機(jī) 368<br>9.11.2   動(dòng)態(tài)規(guī)劃的原理 369<br>9.11.3   鄰近計(jì)算 369<br>9.11.4   動(dòng)態(tài)規(guī)劃算法 369<br>9.12   代碼生成器的生成器 371<br>9.12.1   采用重寫樹(shù)技術(shù)的代碼生成 371<br>9.12.2   借助語(yǔ)法分析的模式匹配 375<br>9.12.3   用于語(yǔ)義檢查的例程 376<br>練習(xí) 376<br>參考文獻(xiàn)注釋 378<br>第10章   代碼優(yōu)化 381<br>10.1   引言 381<br>10.1.1   代碼改進(jìn)變換的準(zhǔn)則 381<br>10.1.2   性能的提高 382<br>10.1.3   優(yōu)化編譯器的組織 383<br>10.2   優(yōu)化的主要種類 384<br>10.2.1   保持功能變換 385<br>10.2.2   公共子表達(dá)式 386<br>10.2.3   復(fù)制傳播 387<br>10.2.4   無(wú)用代碼刪除 387<br>10.2.5   循環(huán)優(yōu)化 388<br>10.2.6   代碼外提 388<br>10.2.7   歸納變量和強(qiáng)度削弱 388<br>10.3   基本塊的優(yōu)化 390<br>10.4   流圖中的循環(huán) 392<br>10.4.1   支配節(jié)點(diǎn) 392<br>10.4.2   自然循環(huán) 393<br>10.4.3   內(nèi)循環(huán) 393<br>10.4.4   前置首節(jié)點(diǎn) 394<br>10.4.5   可約流圖 394<br>10.5   全局?jǐn)?shù)據(jù)流分析介紹 395<br>10.5.1   點(diǎn)和路徑 396<br>10.5.2   到達(dá)定義 396<br>10.5.3   結(jié)構(gòu)化程序的數(shù)據(jù)流分析 397<br>10.5.4   對(duì)數(shù)據(jù)流信息的保守估計(jì) 399<br>10.5.5   in 和 out 的計(jì)算 400<br>10.5.6   處理循環(huán) 401<br>10.5.7   集合的表示 402<br>10.5.8   局部到達(dá)定義 403<br>10.5.9   引用-定義鏈 404<br>10.5.10   計(jì)算順序 404<br>10.5.11   一般控制流 404<br>10.6   數(shù)據(jù)流方程的迭代解 405<br>10.6.1   到達(dá)定義的迭代算法 406<br>10.6.2   可用表達(dá)式 408<br>10.6.3   活躍變量分析 410<br>10.6.4   定義-引用鏈 411<br>10.7   代碼改進(jìn)變換 412<br>10.7.1   全局公共子表達(dá)式刪除 412<br>10.7.2   復(fù)制傳播 413<br>10.7.3   循環(huán)不變計(jì)算的檢測(cè) 415<br>10.7.4   代碼外提 415<br>10.7.5   可選的代碼外提方案 417<br>10.7.6   代碼外提后對(duì)數(shù)據(jù)流信息的<br>維護(hù) 418<br>10.7.7   歸納變量刪除 418<br>10.7.8   帶有循環(huán)不變表達(dá)式的歸納<br>變量 421<br>10.8   處理別名 422<br>10.8.1   一種簡(jiǎn)單的指針語(yǔ)言 422<br>10.8.2   指針賦值的作用 422<br>10.8.3   利用指針信息 424<br>10.8.4   過(guò)程間的數(shù)據(jù)流分析 425<br>10.8.5   帶有過(guò)程調(diào)用的代碼模型 425<br>10.8.6   別名的計(jì)算 426<br>10.8.7   存在過(guò)程調(diào)用時(shí)的數(shù)據(jù)流分析 427<br>10.8.8   change信息的用途 428<br>10.9   結(jié)構(gòu)化流圖的數(shù)據(jù)流分析 429<br>10.9.1   深度優(yōu)先搜索 429<br>10.9.2   流圖的深度優(yōu)先表示中的邊 431<br>10.9.3   流圖的深度 431<br>10.9.4   區(qū)間 432<br>10.9.5   區(qū)間劃分 432<br>10.9.6   區(qū)間圖 433<br>10.9.7   節(jié)點(diǎn)分裂 433<br>10.9.8   T1-T2 分析 434<br>10.9.9   區(qū)域 434<br>10.9.10   尋找支配節(jié)點(diǎn) 435<br>10.10   高效數(shù)據(jù)流算法 436<br>10.10.1   迭代算法中的深度優(yōu)先順序 436<br>10.10.2   基于結(jié)構(gòu)的數(shù)據(jù)流分析 437<br>10.10.3   對(duì)基于結(jié)構(gòu)的算法的一些速度上<br>的改進(jìn) 440<br>10.10.4   處理不可約流圖 441<br>10.11   一個(gè)數(shù)據(jù)流分析工具 441<br>10.11.1   數(shù)據(jù)流分析框架 442<br>10.11.2   數(shù)據(jù)流分析框架的公理 443<br>10.11.3   單調(diào)性和分配性 444<br>10.11.4   數(shù)據(jù)流問(wèn)題的聚合路徑解 447<br>10.11.5   流問(wèn)題的保守解 447<br>10.11.6   通用框架的迭代算法 448<br>10.11.7   一個(gè)數(shù)據(jù)流分析工具 448<br>10.11.8   算法10.18的性質(zhì) 449<br>10.11.9   算法10.18的收斂性 449<br>10.11.10   初始化的修正 450<br>10.12   類型估計(jì) 450<br>10.12.1   處理無(wú)窮類型集 451<br>10.12.2   一個(gè)簡(jiǎn)單的類型系統(tǒng) 452<br>10.12.3   前向方案 452<br>10.12.4   后向方案 453<br>10.13   優(yōu)化代碼的符號(hào)調(diào)試 455<br>10.13.1   基本塊中變量值的推斷 456<br>10.13.2   全局優(yōu)化的影響 459<br>10.13.3   歸納變量刪除 459<br>10.13.4   全局公共子表達(dá)式刪除 459<br>10.13.5   代碼外提 459<br>練習(xí) 460<br>參考文獻(xiàn)注釋 465<br>第11章   編寫一個(gè)編譯器 469<br>11.1   編譯器設(shè)計(jì) 469<br>11.1.1   源語(yǔ)言問(wèn)題 469<br>11.1.2   目標(biāo)語(yǔ)言問(wèn)題 469<br>11.1.3   性能標(biāo)準(zhǔn) 469<br>11.2   編譯器開(kāi)發(fā)方法 470<br>11.3   編譯器開(kāi)發(fā)環(huán)境 472<br>11.4   測(cè)試與維護(hù) 474<br>第12章   編譯器實(shí)例 475<br>12.1   數(shù)學(xué)排版預(yù)處理器EQN 475<br>12.2   Pascal編譯器 475<br>12.3   C編譯器 476<br>12.4   Fortran H編譯器 477<br>12.4.1   Fortran H中的代碼優(yōu)化 478<br>12.4.2   代數(shù)優(yōu)化 478<br>12.4.3   寄存器優(yōu)化 478<br>12.5   BLISS/11編譯器 479<br>12.6   Modula-2優(yōu)化編譯器 480<br>附錄   一個(gè)程序設(shè)計(jì)項(xiàng)目 483<br>參考文獻(xiàn) 489<br>索引 511