編譯方法導(dǎo)論

前言
教學(xué)建議
第1章　引論 1
1.1　編譯概述 1
1.2　編譯的過(guò)程 2
1.2.1　高級(jí)語(yǔ)言程序的處理過(guò)程 2
1.2.2　編譯的過(guò)程 3
1.3　編譯程序的生成 7
1.3.1　編譯程序的組合方式 7
1.3.2　編譯程序的生成方式 9
1.4　基本知識(shí) 11
1.4.1　形式語(yǔ)言 11
1.4.2　文法 14
1.5　練習(xí) 24
第2章　詞法分析 26
2.1　詞法分析概述 26
2.2　單詞的表示 27
2.2.1　單詞的種別 27
2.2.2　屬性 28
2.3　單詞的形式描述 29
2.3.1　正規(guī)式描述 30
2.3.2　正規(guī)文法描述 32
2.3.3　正規(guī)式與正規(guī)文法的等價(jià)性 33
2.4　有窮自動(dòng)機(jī) 38
2.4.1　不確定的有窮自動(dòng)機(jī) 38
2.4.2　確定的有窮自動(dòng)機(jī) 40
2.4.3　NFA與DFA的等價(jià)性 41
2.4.4　DFA的化簡(jiǎn) 45
2.4.5　正規(guī)式和FA的等價(jià)性 47
2.4.6　正規(guī)文法和FA的等價(jià)性 53
2.5　詞法分析程序的構(gòu)造 56
2.5.1　單詞識(shí)別程序的構(gòu)造 56
2.5.2　詞法分析程序的自動(dòng)生成工具LEX簡(jiǎn)介 59
2.6　練習(xí) 62
第3章　自頂向下的語(yǔ)法分析法 64
3.1　語(yǔ)法分析概述 64
3.2　自頂向下語(yǔ)法分析的實(shí)現(xiàn) 65
3.2.1　推導(dǎo)樹(shù)與語(yǔ)法樹(shù) 65
3.2.2　二義性 66
3.2.3　確定與不確定的自頂向下語(yǔ)法分析 67
3.3　確定的自頂向下的語(yǔ)法分析條件 70
3.3.1　LL(1)文法 70
3.3.2　非LL(1)文法到LL(1)文法的等價(jià)變換 75
3.4　自頂向下語(yǔ)法分析程序的構(gòu)造 80
3.4.1　預(yù)測(cè)分析法 80
3.4.2　遞歸下降分析法 83
3.5　練習(xí) 85
第4章　自底向上的語(yǔ)法分析法 88
4.1　自底向上語(yǔ)法分析的實(shí)現(xiàn) 88
4.1.1　歸約 88
4.1.2　短語(yǔ)和句柄 90
4.2　簡(jiǎn)單優(yōu)先分析法 92
4.2.1　簡(jiǎn)單優(yōu)先文法 92
4.2.2　簡(jiǎn)單優(yōu)先分析算法 94
4.3　算符優(yōu)先分析法 96
4.3.1　算符優(yōu)先文法 96
4.3.2　算符優(yōu)先分析算法 100
4.3.3　優(yōu)先函數(shù) 103
4.4　練習(xí) 105
第5章　LR分析法 108
5.1　LR分析法概述 108
5.2　LR(0)分析 110
5.2.1　LR(0)項(xiàng)目集規(guī)范族 110
5.2.2　LR(0)文法 116
5.2.3　LR(0)分析器的工作過(guò)程 119
5.3　SLR(1)分析 120
5.3.1　SLR(1)文法 120
5.3.2　SLR(1)分析表的構(gòu)造 121
5.4　LR(1)分析 123
5.4.1　LR(1)文法 123
5.4.2　LR(1)項(xiàng)目集規(guī)范族的構(gòu)造 125
5.4.3　LR(1)分析表的構(gòu)造 126
5.5　LALR(1)分析 127
5.5.1　LALR(1)文法 127
5.5.2　LALR(1)分析表的構(gòu)造 128
5.6　語(yǔ)法分析程序的自動(dòng)生成工具YACC簡(jiǎn)介 130
5.6.1　YACC對(duì)語(yǔ)言的要求 130
5.6.2　YACC的輸入輸出 130
5.6.3　YACC源程序 131
5.7　練習(xí) 132
第6章　語(yǔ)義分析 135
6.1　語(yǔ)義分析概述 135
6.2　語(yǔ)法制導(dǎo)的語(yǔ)義計(jì)算 135
6.2.1　屬性文法 136
6.2.2　語(yǔ)義計(jì)算 138
6.3　符號(hào)表 140
6.3.1　符號(hào)表的概述 140
6.3.2　符號(hào)表的定義 141
6.3.3　符號(hào)表的組織 145
6.3.4　符號(hào)表的管理 153
6.4　練習(xí) 154
第7章　中間代碼生成 156
7.1　中間代碼生成概述 156
7.2　中間代碼 156
7.2.1　逆波蘭式 156
7.2.2　樹(shù)代碼 158
7.2.3　三地址碼 159
7.3　自底向上的語(yǔ)法制導(dǎo)翻譯 161
7.3.1　說(shuō)明語(yǔ)句的翻譯 161
7.3.2　含簡(jiǎn)單變量的賦值語(yǔ)句的翻譯 164
7.3.3　含數(shù)組元素的賦值語(yǔ)句的翻譯 167
7.3.4　布爾表達(dá)式的翻譯 168
7.3.5　控制語(yǔ)句的翻譯 174
7.3.6　過(guò)程調(diào)用 182
7.4　練習(xí) 183
第8章　運(yùn)行時(shí)存儲(chǔ)空間的組織 185
8.1　運(yùn)行時(shí)存儲(chǔ)空間的劃分 185
8.2　數(shù)據(jù)空間的存儲(chǔ)分配策略 186
8.2.1　靜態(tài)存儲(chǔ)分配策略 186
8.2.2　動(dòng)態(tài)存儲(chǔ)分配策略 186
8.3　棧式存儲(chǔ)分配 190
8.3.1　簡(jiǎn)單程序設(shè)計(jì)語(yǔ)言的棧式存儲(chǔ)分配 190
8.3.2　嵌套過(guò)程語(yǔ)言的棧式存儲(chǔ)分配 193
8.4　練習(xí) 199
第9章　代碼優(yōu)化 201
9.1　代碼優(yōu)化概述 201
9.2　局部?jī)?yōu)化 201
9.2.1　基本塊及其劃分 202
9.2.2　基本塊的優(yōu)化技術(shù) 205
9.2.3　基本塊優(yōu)化技術(shù)的實(shí)現(xiàn) 207
9.3　循環(huán)優(yōu)化 212
9.3.1　程序中的循環(huán) 212
9.3.2　循環(huán)的優(yōu)化技術(shù)及其實(shí)現(xiàn) 217
9.4　練習(xí) 221
第10章　目標(biāo)代碼生成 224
10.1　目標(biāo)代碼生成概述 224
10.2　模型計(jì)算機(jī)的指令系統(tǒng) 225
10.2.1　尋址方式 225
10.2.2　指令系統(tǒng) 225
10.3　一種簡(jiǎn)單的代碼生成算法 226
10.3.1　寄存器的使用原則 226
10.3.2　待用信息和活躍信息 227
10.3.3　寄存器描述和變量地址描述 231
10.3.4　基本塊的代碼生成算法 231
10.4　DAG的目標(biāo)代碼生成 234
10.5　練習(xí) 235
參考文獻(xiàn) 237