小型編譯器設計實踐

第一篇 PIC16Fxxxx編譯器(cc16e.exe)的設計
第1章 工具準備和系統設置............................................................................................2
1.1 GNU C/C++編譯工具的選擇..................................................................................2
1.1.1 MinGW ........................................................................................................ 2
1.1.2 DJGPP .......................................................................................................... 2
1.1.3 Cygwin ......................................................................................................... 2
1.2 解析工具構造器 ...................................................................................................... 3
1.3 工具的安裝 .............................................................................................................. 3
1.4 目標編譯器運行前的系統設置 .............................................................................. 4
第2章 預處理器的設計...................................................................................................5
2.1 預處理器(C/C++版) ........................................................................................... 6
2.1.1 項目文件及其設置......................................................................................6
2.1.2 任務和算法.................................................................................................. 7
2.2 源程序預處理器(flex 版) ................................................................................. 11
2.2.1 正規表達式簡介........................................................................................12
2.2.2 預處理器設計實戰....................................................................................14
2.3 本章小結 ................................................................................................................ 20
第3章 編譯器設計初步實踐..........................................................................................21
3.1 設計簡介 ................................................................................................................ 21
3.2 一個簡單的 C 語言關鍵字識別器........................................................................22
3.2.1 工程項目文件............................................................................................22 3.2.2 項目運行主程序........................................................................................23
小型編譯器設計實踐
3.2.3 詞法解析自動機部分................................................................................23
3.2.4 詞法解析 C 語言部分 ............................................................................... 24
3.3 編譯器雛形(flex 和 bison 的使用) .................................................................. 25
3.3.1 問題的提出和任務....................................................................................25
3.3.2 工程文件 makefile.....................................................................................26
3.3.3 詞法解析規則部分....................................................................................26
3.3.4 詞法解析的啟動........................................................................................27
3.3.5 語法解析器文本及其基本格式 ................................................................ 27
3.3.6 語法解析器文本各區域的內容 ................................................................ 28
3.4 語法解析和詞法解析之間的數值傳遞 ................................................................ 30
3.4.1 語法解析器文本的定義部分 .................................................................... 31
3.4.2 語法解析器識別規則部分 ........................................................................ 32
3.4.3 詞法解析器解析規則部分 ........................................................................ 33
3.5 編譯樹的構建 ........................................................................................................ 34
3.5.1 編譯樹中的數據類型和結構 .................................................................... 34
3.5.2 節點生成和處理函數................................................................................35
3.5.3 語法解析器文本的定義部分 .................................................................... 36
3.5.4 語法解析器文本的語法解析識別規則部分 ............................................ 36
3.6 源程序語句代碼的截取和嵌入 ............................................................................ 38
3.6.1 緩沖區與相關函數....................................................................................38
3.6.2 截取源程序代碼並送入緩沖區中 ............................................................ 38
3.6.3 讀取源代碼緩沖內容................................................................................39
3.6.4 增加新定義並擴充 node 數據結構 .......................................................... 39
3.6.5 支持函數和程序........................................................................................40
3.6.6 在源程序片段中嵌入節點 ........................................................................ 41
3.7 編譯樹的顯示 ........................................................................................................ 41
3.7.1 用於顯示編譯樹的函數 ............................................................................ 42 3.7.2 編譯樹的顯示操作....................................................................................42
第4章 編譯器設計實戰.................................................................................................44 4.1 對 C 語言的詞法解析............................................................................................44
VIII

4.1.1 詞法解析宏定義部分................................................................................44
4.1.2 各種常數解析識別....................................................................................45
4.1.3 C 語言關鍵字和標識符解析 .................................................................... 46
4.1.4 C 語言各種操作運算符識別 .................................................................... 46
4.1.5 關於字符和字符串常數的處理 ................................................................ 47
4.2 對 C 語言的語法解析............................................................................................ 47
4.2.1 描述特徵的 attrib 完整結構 ..................................................................... 48
4.2.2 各類 node 數據結構的完善 ...................................................................... 48
4.2.3 語法解析定義部分的完善 ........................................................................ 49
4.2.4 函數聲明/定義的完善............................................................................... 51
4.2.5 運算語法和運算符優先確定 .................................................................... 52
4.2.6 變量定義語法規則的完善 ........................................................................ 53
4.3 支持預處理等語句的語法解析 ............................................................................ 56
4.3.1 用於預處理語句的新增變量 .................................................................... 56
4.3.2 用於預處理語句的新增解析狀態 ............................................................ 57
4.3.3 用於預處理語句的解析 ............................................................................ 57
4.3.4 用於預處理語句的節點和數據類型 ........................................................ 58
4.4 支持結構化數據的語法解析 ................................................................................ 61
4.5 支持對 typedef 的語法解析 .................................................................................. 63
4.5.1 支持 typedef 的新變量 .............................................................................. 63
4.5.2 判斷標識符的性質....................................................................................64
4.5.3 typedef 語法解析.......................................................................................64
4.5.4 識別結構化數據定義中出現的新類型名 ................................................ 65
4.5.5 使用新類型名............................................................................................66
4.6 本章小結 ................................................................................................................ 66
第5章 編譯樹的預掃描.................................................................................................67
5.1 符號表的基本數據結構和應用 ............................................................................68
5.1.1 符號表基本數據結構 Nnode .................................................................... 69
5.1.2 符號表鏈數據結構 Nlist...........................................................................69
5.2 符號的鏈表操作 .................................................................................................... 71
目錄
IX

小型編譯器設計實踐
5.2.1 符號表節點和表鏈的初始化 .................................................................... 71
5.2.2 對符號表鏈的搜索....................................................................................72
5.2.3 對符號表鏈添加符號定義 ........................................................................ 72
5.2.4 對符號表鏈刪除一個節點 ........................................................................ 73
5.2.5 介紹一組輔助函數....................................................................................73
5.2.6 關於 enum 枚舉成員的取值和等價長度 ................................................. 74
5.3 對編譯樹的預掃描 ................................................................................................ 75
5.3.1 預掃描操作的類........................................................................................75
5.3.2 預掃描的啟動運行....................................................................................76
5.3.3 編譯樹的基本構造和周游掃描 ................................................................ 76
5.3.4 對 idNode_t 節點的掃描 ........................................................................... 77
5.3.5 對復合語句操作的掃描處理 .................................................................... 79
5.3.6 對宏定義語句#define 和#undef 的掃描處理 ........................................... 79
5.3.7 對#ifdef 和#ifndef 語句的掃描處理 ......................................................... 80
5.3.8 對#if ... #else ... #endif 語句的掃描處理 ................................................ 80
5.3.9 對函數調用 CALL 操作的掃描處理 ....................................................... 81
5.3.10 對函數定義 FUNC_DECL 操作的掃描處理 ......................................... 81
5.3.11 對 enum 語句操作的掃描處理 ............................................................... 82
5.3.12 對變量定義操作的掃描處理 .................................................................. 83
5.3.13 對 typedef 語句的掃描處理 .................................................................... 86
5.3.14 對 sizeof()函數記號的掃描處理............................................................. 88
5.3.15 對類型強制轉換操作的掃描處理 .......................................................... 89
5.3.16 對寄存器位定義操作的掃描處理 .......................................................... 89
5.3.17 對#pragma 操作的掃描處理 ................................................................... 90
5.3.18 對其他操作類型的處理和對常數運算的歸並 ...................................... 91
5.4 本章小結 ................................................................................................................ 91
第6章 P-代碼與虛擬機.................................................................................................92 6.1 基本數據結構 ........................................................................................................ 93
6.1.1 操作項 Item 數據結構 ..............................................................................93
6.1.2 代碼片段 Pnode 數據結構........................................................................95
X

6.1.3 編譯棧和操作項的移入與歸約 ................................................................ 95
6.2 變量表和函數表 .................................................................................................... 98
6.2.1 變量表數據節點 Dnode 和鏈表 Dlink 的結構 ........................................ 99
6.2.2 Dlink 的應用操作和表示........................................................................100
6.2.3 函數表數據節點 Fnode 和鏈表 Flink 的結構 .......................................102
6.2.4 函數內部的標號(label)和臨時變量的命名 ...................................... 103
6.3 P-代碼生成基礎................................................................................................... 103
6.3.1 生成器類.................................................................................................. 104
6.3.2 生成器類的構建和運行啟動 .................................................................. 105
6.4 P-代碼生成過程................................................................................................... 107
6.4.1 6.4.2 6.4.3 6.4.4 6.4.5 6.4.6 6.4.7 6.4.8 6.4.9 6.4.10 6.4.11 6.4.12 6.4.13 6.4.14 6.4.15 6.4.16 6.4.17 6.4.18 6.4.19 6.4.20
語句行終結和復合語句 .......................................................................... 107 變量聲明和定義......................................................................................108 普通函數的聲明和定義 .......................................................................... 111 賦值操作語句.......................................................................................... 113 變量地址 ADDR_OF .............................................................................. 114 變量地址 POS_OF .................................................................................. 115 表達式中數組偏址計算 .......................................................................... 117 調試顯示工具的擴充..............................................................................120 結構實體變量的成員偏移尋址 .............................................................. 122
變量的成員間接偏移尋址 .................................................................... 124 預先遞增和預先遞減 ............................................................................ 126 滯後遞增和滯後遞減 ............................................................................ 127 sizeof()函數 ........................................................................................... 129 標號語句 LABEL 和 GOTO 語句 ........................................................ 130 單目運算語句........................................................................................130 類型強制轉換........................................................................................132 SBIT 類型操作項..................................................................................133 復合賦值運算 ADD_ASSIGN 和 SUB_ASSIGN................................133 算術運算“+”和“-”........................................................................ 135 邏輯運算“＆”、“|”和“^” .............................................................. 136
目錄
XI

小型編譯器設計實踐
6.4.21 其他復合賦值運算................................................................................137
6.4.22 算術運算“*”、“/”和“%”，以及“移位”運算............................ 138
6.4.23 算術比較運算........................................................................................139
6.4.24 邏輯“與關聯”操作 ............................................................................ 140
6.4.25 邏輯“或關聯”操作 ............................................................................ 141
6.4.26 增加新函數及其相應的數據變量 ........................................................ 143
6.4.27 if 語句 .................................................................................................... 144
6.4.28 while 語句..............................................................................................145
6.4.29 do ... while 語句 ..................................................................................... 146
6.4.30 for 語句 .................................................................................................. 147
6.4.31 break 和 continue 語句 .......................................................................... 148
6.4.32 switch 語句 ............................................................................................ 149
6.4.33 call 語句 ................................................................................................. 153
6.4.34 條件運算符“?”語句 .......................................................................... 156
6.4.35 連續運算符“,”語句 ........................................................................... 158
6.4.36 函數返回 return 語句 ............................................................................ 159
6.4.37 匯編語言插入語句 AASM ................................................................... 160
6.4.38 編譯設置語句 PRAGMA...................................................................... 160
6.5 本章總結 .............................................................................................................. 160
第7章 P-代碼的優化..................................................................................................162
7.1 清除冗餘的代碼 .................................................................................................. 164
7.1.1 刪除冗餘的標號......................................................................................164
7.1.2 清除與無條件跳轉語句有關的冗餘 ...................................................... 166
7.1.3 常數與地址運算的合並 .......................................................................... 168
7.2 代碼的合並簡化 .................................................................................................. 169
7.2.1 地址與常數運算的合並 .......................................................................... 169
7.2.2 合並間接偏址計算..................................................................................170
7.2.3 簡化和重組雙目運算..............................................................................171
7.2.4 省略臨時變量.......................................................................................... 171
7.2.5 變換運算順序.......................................................................................... 172
XII

7.2.6 合並連續常數運算..................................................................................172
7.2.7 簡化運算類型.......................................................................................... 173
7.3 條件跳轉操作的優化 .......................................................................................... 173
7.3.1 簡單的跳轉類型變換..............................................................................173
7.3.2 使用位檢測進行跳轉類型的變換 .......................................................... 174
7.3.3 清除與常數 0 的等值比較 ...................................................................... 174
7.3.4 合並簡單遞減(遞加)並跳轉操作 ...................................................... 175
7.4 關於特殊常數操作運算的優化 .......................................................................... 175 7.4.1 簡化算術邏輯運算..................................................................................175
7.4.2 簡化常數為 2 的冪次方運算..................................................................177
7.5 關於臨時變量使用的優化 .................................................................................. 178
7.5.1 清除賦值後未被使用的臨時變量 .......................................................... 178
7.5.2 臨時變量的重復使用..............................................................................179
7.5.3 臨時變量長度最小化..............................................................................180
7.6 其他種類的優化 .................................................................................................. 181
7.6.1 清除 ACC 與臨時變量之間的賦值........................................................181
7.6.2 對數據結構成員偏址尋址過程進行優化 .............................................. 182
7.7 本章小結 .............................................................................................................. 184
第8章 匯編語言輸出..................................................................................................185
8.1 PIC16Fxxxx 處理器簡介 ..................................................................................... 185
8.1.1 加強版 PIC16Fxxxx 指令系統和偽指令 ...............................................186
8.1.2 加強版 PIC16Fxxxx 編譯器對 RAM 公用區域的用途劃分...................187
8.1.3 匯編器設計的基本結構 .......................................................................... 188
8.2 編譯器的匯編語言輸出 ...................................................................................... 190
8.2.1 匯編語言輸出的起始..............................................................................190
8.2.2 匯編語言輸出全局 RAM 變量...............................................................192 8.3 運行代碼的匯編語言輸出 .................................................................................. 193
8.3.1 函數起始 P_FUNC_BEG 的匯編語言輸出 ........................................... 194
8.3.2 函數結束 P_FUNC_END 的匯編語言輸出 ........................................... 199
8.3.3 註釋和標號行的匯編語言輸出 .............................................................. 200
目錄
XIII

小型編譯器設計實踐
8.3.4 函數調用 CALL 的匯編語言輸出 ......................................................... 200
8.3.5 無條件跳轉 GOTO 的匯編語言輸出 ..................................................... 200
8.3.6 “=”和 P_MOV 賦值操作的匯編語言輸出 ........................................ 201
8.3.7 INC_OP 和 DEC_OP 運算的匯編語言輸出 .......................................... 205
8.3.8 NEG_OF 運算的匯編語言輸出 ............................................................. 206
8.3.9 “~”運算的匯編語言輸出.................................................................... 208
8.3.10 “!”運算的匯編語言輸出 ..................................................................208
8.3.11 算術復合賦值運算 ADD_ASSIGN 和 SUB_ASSIGN........................209
8.3.12 邏輯復合賦值運算 AND_ASSIGN、OR_ASSIGN 和
XOR_ASSIGN....................................................................................... 211
8.3.13 P_JZ 和 P_JNZ 的匯編語言輸出 ......................................................... 213
8.3.14 P_JBZ 和 P_JBNZ 的匯編語言輸出 .................................................... 214
8.3.15 P_ARG_PASS 的匯編語言輸出 ........................................................... 215
8.3.16 P_CALL 的匯編語言輸出 .................................................................... 215
8.3.17 P_JZ_INC、P_JZ_DEC、P_JNZ_INC 和 P_JNZ_DEC 的匯編
語言輸出................................................................................................216
8.3.18 “+”和“-”運算的匯編語言輸出.................................................... 217
8.3.19 P_JEQ 和 P_JNE 的匯編語言輸出....................................................... 221
8.3.20 “位”變量的比較和跳轉匯編語言輸出 ............................................ 222
8.3.21 P_JLT、P_JLE、P_JGT 和 P_JGE 的匯編語言輸出 .......................... 224
8.3.22 關於確定比較結果的 cmpJump()函數.................................................226
8.3.23 復合型左移位 LEFT_ASSIGN 的匯編語言輸出 ................................ 230
8.3.24 復合型右移位 RIGHT_ASSIGN 的匯編語言輸出 ............................. 233
8.3.25 左移位 LEFT_OP 的匯編語言輸出 ..................................................... 235
8.3.26 右移位 RIGHT_OP 的匯編語言輸出................................................... 238
8.3.27 復合乘法 MUL_ASSIGN 的匯編語言輸出......................................... 241
8.3.28 乘法的匯編語言輸出 ............................................................................ 242
8.3.29 復合除法 DIV_ASSIGN 和復合取模 MOD_ASSIGN 的匯編
語言輸出 ...............................................................................................243
8.3.30 除法和取模的匯編語言輸出 ................................................................ 244
XIV

8.3.31 PRAGMA(#pragma)的匯編語言輸出 ............................................. 245
8.3.32 函數型匯編插入....................................................................................246
8.3.33 P_DJNZ/P_IJNZ 的匯編語言輸出 ....................................................... 247
8.3.34 邏輯運算的匯編語言輸出 .................................................................... 247
8.3.35 AASM 的匯編語言輸出 ....................................................................... 251
8.4 非運行代碼的匯編語言輸出 .............................................................................. 251
8.4.1 RAM 變量初始化的匯編語言輸出........................................................252
8.4.2 ROM 常數的匯編語言輸出....................................................................253
8.4.3 ROM 字符串的匯編語言輸出................................................................254
第9章 PIC16Fxxxx編譯器最後的完善.......................................................................257
9.1 為編譯器增加編譯運行的編譯選項 ..................................................................257
9.1.1 增加編譯選項.......................................................................................... 258
9.1.2 搜索/獲取編譯選項................................................................................. 260
9.1.3 使用編譯選項.......................................................................................... 260
9.2 編譯器庫函數的設計 .......................................................................................... 262
9.2.1 編譯器基本庫函數的設計 ...................................................................... 262
9.2.2 編譯器擴充型庫函數的設計 .................................................................. 263
9.3 支持超強型 PIC16Fxxxx 處理器的思考和對策................................................264
第二篇 PIC16Fxxxx匯編器(as16e.exe)的設計
第10章 PIC16Fxxxx匯編器的詞法解析器..................................................................268
10.1 10.2
10.3
數據結構的設計 ................................................................................................ 268
匯編器的詞法解析設計 .................................................................................... 271
10.2.1 起始狀態................................................................................................ 272
10.2.2 操作碼狀態............................................................................................ 273
10.2.3 操作數狀態............................................................................................ 273
匯編器的語法解析設計 .................................................................................... 274
10.3.1 文件語句行的語法規則和處理 ............................................................ 275
10.3.2 匯編語句行的語法規則和處理 ............................................................ 275
10.3.3 匯編語句操作數處理 ............................................................................ 276
目錄
XV

小型編譯器設計實踐
10.4
10.5
10.6
10.3.4 匯編器的產生........................................................................................278 匯編器對輸入文件的掃描 ................................................................................ 279
10.4.1 匯編器的 P16E_asm 類的啟動.............................................................280
10.4.2 匯編器的 P16E_asm 對指令序列的兩次掃描.....................................282
匯編器的代碼轉換輸出 .................................................................................... 282
10.5.1 .obj 文件格式......................................................................................... 282
10.5.2 .obj 和.lst 文件輸出啟動的偽指令部分 ............................................... 283
10.5.3 .obj 和.lst 文件輸出啟動的常規指令部分 ........................................... 285
匯編器的最後完善 ............................................................................................ 289
10.6.1 啟動運行選項的設計 ............................................................................ 289
10.6.2 支持超強型 PIC16Fxxxx 的代碼輸出 .................................................290
第三篇 PIC16Fxxxx連接器(lk16e.exe)的設計
第11章 PIC16Fxxxx連接器基本設計.........................................................................294
11.1
11.2 11.3 11.4
11.5
11.6
.obj 文件的讀入和語法掃描 .............................................................................294
11.1.1 輸入文件和數據結構 ............................................................................ 295
11.1.2 連接器輸入文件的詞法解析 ................................................................ 296
11.1.3 連接器輸入文件的語法解析 ................................................................ 298
分段類型及其數據結構 ....................................................................................300 連接器起始和運行模式 ....................................................................................301 內存類型和模式的建立 ....................................................................................303
11.4.1 內存類及其相關的服務函數 ................................................................ 304
11.4.2 內存空間分配函數和內存地址空間轉換選擇 .................................... 305
符號數據結構 ....................................................................................................306
11.5.1 Symbol 類的數據結構和啟用...............................................................306
11.5.2 Memory 和 Symbol 類在連接中的應用...............................................307
連接操作 ............................................................................................................ 309
11.6.1 連接類 P16link ...................................................................................... 310
11.6.2 連接類 P16link 的啟用 ......................................................................... 310
11.6.3 搜索被使用的分段並舍棄未被使用的分段 ........................................ 311
11.6.4 表達式取值函數 .................................................................................... 312
XVI

11.6.5 對各分段的內存空間進行分配和定位 ................................................ 314
11.6.6 連接後的結果文件輸出 ........................................................................ 316
第12章 PIC16Fxxxx連接器的加強與深入..................................................................319
12.1 12.2
12.3
12.4
13.1
13.2
問題的提出和應對 ............................................................................................ 319
函數活躍狀態的判斷原則 ................................................................................ 320 12.2.1 基本判斷原則........................................................................................320 12.2.2 進程類型互斥原則................................................................................321
函數內部變量空間共享的實現和設計 ............................................................322
12.3.1 功能的嵌入............................................................................................ 323
12.3.2 算法的實現............................................................................................ 324
12.3.3 函數內部變量共享群的生成 ................................................................ 326
本章小結 ............................................................................................................ 327 第13章 PIC16Fxxxx編譯器設計的總結和應用實例...................................................328
應用實例 1:基於 si47xx 模塊的收音機.........................................................329 13.1.1 設計選材................................................................................................ 329 13.1.2 應用程序設計........................................................................................330
應用實例 2:USB/UART 轉接器.....................................................................333
13.2.1 設計選材................................................................................................ 333
13.2.2 設計考慮................................................................................................ 333