[books] - 自己动手写编译器、链接器

古人學問無遺力，少壯功夫老始成。

賽巴看來很正吧! 不過我不是要介紹賽巴, 那不是我的專業, 網路上一堆開箱文照片都拍的很好, 我要介紹賽巴後面的那本書。

讀了《Orange's 一個作業系統的實現》讓我完成 simple os。

讀了《SICP 2nd edition 》讓我完成 simple scheme。

讀了《事件驅動程式設計》讓我完成 simple gui。

在電腦的本質技術上我還少了什麼? 很多很多, 這本自己动手写编译器、链接器可以彌補我編譯器/連結器這塊拼圖。

20150618 透過林兄從中國帶回三本, 160*3 + 20; 2 本從三民書局購得, 222*2 - 20, 20150710 拿到, 總共買了 5 本, 4 本送人, 你就知道我有多喜歡這本書了。而 3 本不到 500 新臺幣的價錢讓我為作者抱屈, 我都要替作者掉眼淚了, 這樣等級的書賣 500 新臺幣一點也不過份, 只好多幫他買一點書了。

為了學習 compiler 技術, 我曾經買過很多書籍 (fig 2), 不過一樣成效不彰, 我自己比較想要寫出類似 c 語言的 compiler, 而不是那些教學用的什麼簡易版的 pascal, 或是為了教學而設計的語言, 完全不能和現實生活接上軌道。

本書的作者和我有相同的想法, 因此對 c 做了一些縮減, 就是針對這個縮減版的 c 來寫 compiler, 所以稱做 simple c compiler。這樣就夠了嗎? 當然不夠, 還有 linker 要寫, 還有組譯器也要寫, 而我買的這些書中有些把這個難題交給了 nasm, 只處理到組合語言這部份, 不是不行, 只是這樣就沒有完整的學習到, 神功只練了一半, 豈不可惜, 你不想搞定那些 machine code 嗎? 不管是 arm 還是 x86, machine code 這些充滿魔法般的東西, 我想搞懂他們, 當然還有執行檔格式, elf 或是 pe, 這些都要一起學起來, 就是要一條鞭的學習, 才不會遺漏了某塊技術拼圖。

simple os, simple gui, simple scheme 都是從無到有實作過一次, 這樣的學習會讓我有深刻的印象, 而不是只停留在「理解」的狀態。我不要說的一口好 os, 說的一口好 mvc 架構, 說的一口好 interperter, 我要做出這樣的東西來, 儘管是最最簡單的玩具版本, 都能讓我有深度的學習體驗。

官網 (書中程式碼下載點): http://www.tup.tsinghua.edu.cn/booksCenter/book_05928401.html http://www.tup.tsinghua.edu.cn/wap/tsxqy.aspx?id=05928402, 本書的程式是用 c 開發, 以 vc6 為開發環境, 而造出來的執行檔也是以 coff/pe windows 平台為主, 對習慣 linux 的我來說, 有些遺憾, 不過不要緊, 人家已經開好路, 柏油我就自己鋪上吧!

目前把一部份程式移植到 linux, 我使用了 ncurses 來作終端機顏色處理。有個麻煩點就是 getch(), 因為 ncurses 也有一個 getch(), 所以我把 getch() 改為 fgetch(), 因為範例程式碼的 getch() 其實就是去抓檔案的一個 char。

另外把 GB 編碼轉成 utf8。

fig 2

目录

第1章引言1 1.1HelloWorld编译过程分析1 1.1.1HelloWorld程序源文件1 1.1.2词法分析2 1.1.3语法分析3 1.1.4语义分析3 1.1.5链接器4 1.2SCC编译器简介7 1.2.1SCC编译器架构7 1.2.2SCC编译器开发环境7 1.2.3SCC编译器运行环境8 第2章文法知识10 2.1语言概述10 2.2形式语言11 2.2.1字母表和符号串11 2.2.2文法与语言的形式定义12 2.2.3文法与语言的类型13 2.2.4程序设计语言描述工具15 2.3词法分析方法16 2.3.1词法定义例举17 2.3.2状态转换图17 2.3.3词法分析程序流程图17 2.4语法分析方法18 2.4.1LL分析器18 2.4.2LL（k）文法19 2.4.3LL(1)文法19 2.4.4递归子程序法21 2.4.5文法的等价变换24 第3章SC语言定义26 3.1SC语言的蓝本选择26 3.1.1K&R C 26 3.1.2C8926 3.1.3C9927 3.2SC语言对C89简化原则27 3.3SC语言的字符集27 3.3.1基本字符集28 3.3.2扩展字符集28 3.4SC语言词法定义29 3.4.1关键字29 3.4.2标识符30 3.4.3整数常量31 3.4.4字符常量31 3.4.5字符串常量32 3.4.6运算符及分隔符32 3.4.7注释33 3.5SC语言语法定义33 3.5.1外部定义33 3.5.2语句35 3.5.3表达式39 3.6SC语言与C语言功能对比46 3.6.1关键字46 3.6.2数据类型46 3.6.3存储类型47 3.6.4常量47 3.6.5变量47 3.6.6函数48 3.6.7语句48 3.6.8表达式50 第4章SC语言词法分析52 4.1词法分析任务的官方说法52 4.2单词编码53 4.3词法分析用到的数据结构55 4.3.1动态字符串56 4.3.2动态数组58 4.3.3哈希表61 4.3.4单词表62 4.4错误处理，未雨绸缪67 4.5词法分析过程72 4.5.1词法分析主程序72 4.5.2预处理76 4.5.3解析标识符79 4.5.4解析整数80 4.5.5解析字符串80 4.5.6词法分析流程图82 4.6词法着色84 4.7控制程序85 4.8词法分析成果展示86 第5章SC语言语法分析87 5.1外部定义87 5.1.1翻译单元87 5.1.2外部声明88 5.1.3类型区分符90 5.1.4结构区分符92 5.1.5函数调用约定95 5.1.6结构成员对齐95 5.1.7声明符96 5.1.8初值符100 5.2语句101 5.2.1复合语句102 5.2.2表达式语句103 5.2.3选择语句104 5.2.4循环语句104 5.2.5跳转语句105 5.3表达式107 5.3.1赋值表达式108 5.3.2相等类表达式109 5.3.3关系表达式109 5.3.4加减类表达式110 5.3.5乘除类表达式111 5.3.6一元表达式112 5.3.7后缀表达式113 5.3.8初值表达式114 5.4语法缩进116 5.4.1用到的全局变量及枚举116 5.4.2语法缩进程序117 5.5总控程序118 5.6成果展示119 第6章符号表120 6.1符号表简介121 6.1.1收集符号属性121 6.1.2语义的合法性检查122 6.2符号表用到的主要数据结构123 6.2.1栈结构123 6.2.2符号表结构127 6.2.3数据类型结构132 6.2.4存储类型133 6.3符号表的构造过程134 6.3.1外部声明134 6.3.2类型区分符137 6.3.3结构区分符138

6.3.4声明符144 6.3.5变量初始化149 6.3.6复合语句150 6.3.7sizeof表达式150 6.3.8初等表达式152 6.4控制程序153 6.5成果展示155 第7章生成COFF目标文件157 7.1COFF文件结构157 7.1.1基本概念157 7.1.2总体结构158 7.1.3COFF文件头158 7.1.4节头表161 7.1.5代码节内容168 7.1.6数据节与导入节内容168 7.1.7COFF符号表169 7.1.8COFF字符串表173 7.1.9COFF重定位信息173 7.2生成COFF目标文件175 7.2.1生成节表176 7.2.2生成符号表178 7.2.3生成重定位信息182 7.2.4生成目标文件183 7.3成果展示185 第8章x86机器语言187 8.1x86机器语言简介187 8.2通用指令格式188 8.2.1指令前缀188 8.2.2操作码190 8.2.3ModR/M字节190 8.2.4SIB字节191 8.2.5偏移量与立即数193 8.3x86寄存器193 8.3.1数据寄存器193 8.3.2变址寄存器193 8.3.3指针寄存器194 8.3.4段寄存器194 8.3.5指令指针寄存器194 8.3.6标志寄存器195 8.4指令参考196 8.4.1符号说明196 8.4.2数据传送指令198 8.4.3算术运算指令200 8.4.4逻辑运算指令203 8.4.5控制转移指令205 8.4.6串操作指令208 8.4.7处理器控制指令208 8.5生成x86机器语言208 8.5.1操作数栈209 8.5.2生成通用指令210 8.5.3生成数据传送指令213 8.5.4生成算术与逻辑运算指令217 8.5.5生成控制转移指令221 8.5.6寄存器使用224 8.5.7本章用到的全局变量227 8.6成果展示227 第9章SCC语义分析229 9.1外部定义229 9.1.1声明与函数定义229 9.1.2初值符232 9.1.3函数体234 9.2语句237 9.2.1表达式语句237 9.2.2选择语句 238 9.2.3循环语句 239 9.2.4跳转语句241 9.3表达式 244 9.3.1赋值表达式244 9.3.2相等类表达式245 9.3.3关系表达式246 9.3.4加减类表达248 9.3.5乘除类表达式249 9.3.6一元表达式250 9.3.7后缀表达式253 9.3.8初值表达式257 9.4成果展示259 第10章链接器261 10.1链接方式与库文件261 10.2PE文件格式263 10.2.1总体结构263 10.2.2DOS部分264 10.2.3NT头265 10.2.4节头表272 10.2.5代码节272 10.2.6数据节274 10.2.7导入节274 10.3链接器代码实现278 10.3.1生成PE文件头278 10.3.2加载目标文件281 10.3.3加载引入库文件282 10.3.4解析外部符号285 10.3.5计算节区的RVA地址288 10.3.6重定位符号地址291 10.3.7修正需要重定位的地址292 10.3.8写PE文件293 10.3.9生成EXE文件295 10.4SCC编译器、链接器总控程序297 10.5成果展示301 10.6全书代码架构302 第11章SC语言程序开发304 11.1SC语言程序开发流程304 11.2SCC编译器测试程序304 11.2.1表达式测试304 11.2.2语句测试308 11.2.3结构体测试310 11.2.4函数参数传递测试312 11.2.5字符串测试314 11.2.6全局变量测试315 11.3语言举例316 11.3.1可接收命令行参数的控制台程序316 11.3.2可接收命令行参数的Win32应用程序317 11.3.3HelloWindows窗口程序318 11.3.4文件复制程序323 11.3.5九九乘法表325 11.3.6打印菱形326 11.3.7屏幕捕捉程序328 参考文献336 附录ASC语言文法定义中英文对照表337

數學對於程式設計的用途一直是討論區上的熱門話題, 我當然不是指使用到數學的那種程式 (ex: 影像處理, 方程式計算), 那種程式沒有爭議, 一定要用到數學, 大部分想討論數學對於程式的用途也不是指這些程式。那寫 compiler 需要用到數學嗎? 其實是有的, 但有趣的是, 就算你不會該門學科, 還是可以寫出編譯器來, 所以到底數學對於程式設計到底有什麼樣的影響呢? 我也不清楚, 我把這問題放在心中, 還在找答案。

第二章便是在談論這個數學, 是集合論, 相信很多人應該都忘記了, 畢竟只用來考試的東西, 誰會真正去喜愛它呢? 真是可惜了這門學問, 第二章的描述很理論很枯燥, 重點是很難看得懂, 一堆符號和式子只靠書上的描述看的很吃力。消去左遞迴的方式實在太公式了, 有看沒有懂。其實我覺得只是單純的學數學, 在哪邊算式子, 而沒把他和工程上的問題做結合, 那當然有人會問學這個要幹嘛, 但很多人答不出來可以幹嘛, 只好跟你說很重要, 要學。

《一個A/D 的系統應用問題》是一個例子, 如果學校老師可以提到這個, 相信比起單純的計算, 一定更有趣, 我們學這個又不是只用來考試, 如果這門學問只在考試時有用, 那真是太可惜了。

2.2.4 介紹 BNF, EBNF, 他們很簡單, 不簡單的是用他們來描述語言的話, 要想很久才能知道是怎麼一回事, 尤其又涉及了 recursive 的想法, 真的是會把腦袋打好幾個結。



以下就是拿 bnf/ebnf 來定義有符號的整數。



學習 compiler 的朋友一定聽過 Recursive descent parser, 為什麼是這樣的名稱呢?

fig 3

看過 fig 3 之後, 你是不是有點聯想? fig 3 列出來語法分析的幾個方法, 本書用的就是遞迴子程序那條路, 所以才稱做 Recursive descent parser。Recursive descent parser 很好實作 (就是程式很好寫), 難的是什麼? 怎麼把語法規則寫出來, 並且還要需要符合 LL(1)。LL 分析器是由上到下的一個分析方法, 所以 Recursive descent parser 可以用, 但文法規則要符合 LL(1), 所以你的文法規則不符合 LL(1) 的話要改寫規則使其符合 LL(1), 想到就很難吧! 這是困難之二。

那什麼是 LL(1)? 就是在解析文法時, 要多讀一個 token 來判斷, 多讀兩個來判度就是 LL(2), 以此類推。想也知道, 多讀一個最簡單, 所以就挑這個來實作了。

我一直以來都把 yacc/bison 和 LL(1) 的語法搞混了, 原來 yacc 產生的是 LALR 的 parser, 而有趣的是 LL(1) 適合用手工來寫, LALR 則適合用程式來產生。

本書程式碼解說的不是很清楚, 需要靠自己去看去理解, 也沒有行號, 排版不算專業, 沒有行號的程式碼書籍, 被我歸為是很不專業的排版, 出版人員功力不夠。

chapter 3 介紹 sc 語言的定義, 把詞法分析的 token 和語法分析的 EBNF 仔細的介紹, 不能算是很好看, 是很枯燥的一章。

chapter 4 的詞法分析程式完成後, 又在進一步展示詞法分析可以幹嘛, 現在的編輯器不是都有關鍵字上色的功能嗎? 就是靠這個能力完成的, 所以只要你會寫詞法分析, 就可以做到這個功能。

我覺得就算是詞法分析, 也不是很容易寫的程式, 這是練功的好方法。這是 compiler 的困難之一。

chapter 5 就是語法分析了, 這很難, 不用我贅述了, 但這只是 compiler 的困難之二, 最後同樣示範一個程式, 展示語法分析可以拿來做什麼, 就是 auto identify, 你可以把

語法分析的能力

 1 if (x>2) { 1+2 } else { 2*3 }
 2
 3 變成
 4
 5 if (x>2)
 6 {
 7   1+2
 8 }
 9 else
10 {
11   2*3
12 }

本書沒有產生 AST, 而是直接將程式轉成 machine code, 這是我覺得很可惜的地方, 我自己想要學習的是轉成 AST 的方法, 《两周自制脚本语言》有介紹這樣的方式。

chapter 7 介紹 coff 格式, 這是很自然的, 要不然你要怎麼轉成 coff obj 檔。這只是 compiler 的困難之三。

chapter 8 介紹 x86 machine code, 這也是很自然的, 要不然你的 coff obj 檔的內容怎麼產生出來。這只是 compiler 的困難之四。

困難之五是 linker, chapter 10 在講這個。

如果是轉成類似 java 虛擬機器的 machine code, 你還要寫個 vm, 這是困難之其六。

只有這六點困難度嗎? 當然不是, 我只是把大項寫出來, 讓大家對其困難度有個蓋略的認識, 事實上會更難。

不過後來在 20160129 發現這系列文章《手把手教你构建 C 语言编译器》, 這個系列我覺得是比較好的學習方式, lexer, parser, virtual machine (後文用 vm 來代替) 都是由手工自己完成, 不會有任何的黑箱是你無法理解的, 而轉成這個 vm 的 machine code 比起 x86 容易多了, 這個 vm 只有 4 個暫存器, 很難想像這樣就可以將 c 語言的功能轉譯對應到這個 vm 上, 總共只有 10 篇文章。對於這種大題目, 我一向不喜歡看網路上的教學, 那一定會少了很多東西, 找本好書來學習是我偏愛的方式。

不過若以本書來學習的話, 我大概又需要一個魯蛇模式才能搞懂了, 而這個系列文則可以讓我用片斷的時間來學習, 在冗長的工作時間之中, 應該是有機會學成的。化繁為簡是一個很好的學習方式, 精髓學到了, 那就足夠, 你應該不是做 compiler 的吧, 應該只是和我一樣是因為興趣而學習, 我們沒那麼多時間可以鍛鍊這個技能, 只能學習最精髓的地方。《實作一個簡單的 virtual machine》是我目前的學習心得。

這篇的 vm 寫的比 sicp chapter 5 還好, 我很容易就理解了, 而 sicp 我卡在 scheme 的語法與思維上, 很難有快速的學習, 還是 c/c++ 好阿, 讓我很容易就理解程式碼的內容。

後來中國又出版了不少編譯器相關書籍, 我從其它書中找到我想要的部份, 這本的參考性就沒那麼重要了。

這裡有個有趣的討論:
如何看待《自己動手寫編譯器、鏈接器》一書大量抄襲開源編譯器 TCC？

課程:
编译实战课程 - 王博俊

ref:

• 作者 blog
• 這裡有一些短文 (簡體中文翻譯) 系列:
• 【深入淺出教你寫編譯器（Compiler）】一、簡介 by Dukeland
• 自己手动编写一个简单的解释器 Part 1
• 【深入淺出教你寫編譯器（Compiler）】三

原文版本:

• Let’s Build A Simple Interpreter. Part 1.
• Let’s Build A Simple Interpreter. Part 2.