最近在看基于DSL的熱更新框架叛氨，瞬間對(duì)編譯器原理產(chǎn)生了濃厚的興趣躲因。百度蔑祟、知乎了很久趁耗，給自己定了一套學(xué)習(xí)路徑(??)。龍書(shū)疆虚，虎書(shū)苛败，鯨書(shū)這些是必看的，但是書(shū)還在路上径簿“涨《Engineering a Compiler》和《游戲腳本高級(jí)編程》看起來(lái)口碑也不錯(cuò)。不過(guò)我的入門(mén)篇亭，從一本叫《兩周自制腳本語(yǔ)言》開(kāi)始（以下簡(jiǎn)稱(chēng)《兩周》）缠捌。希望這個(gè)主題會(huì)有第二篇、第三篇....吧译蒂。
0x01.前言
在計(jì)算機(jī)的世界里曼月，計(jì)算機(jī)的底層執(zhí)行邏輯一定是通過(guò)二進(jìn)制的命令結(jié)合硬件電路實(shí)現(xiàn)的谊却。硬件看不懂我們的代碼，它們只知道把高電壓當(dāng)成1哑芹，低電壓當(dāng)成0炎辨，執(zhí)行過(guò)程就是一次次放電過(guò)程。所以程序本質(zhì)上是一串很長(zhǎng)很長(zhǎng)的的二進(jìn)制數(shù)字聪姿，由于不易閱讀碴萧，人們常通過(guò)匯編語(yǔ)言程序來(lái)表達(dá)這個(gè)巨大的數(shù)字。程序只有載入內(nèi)存后才能通過(guò)硬件執(zhí)行末购。因此破喻，用戶(hù)在實(shí)際使用的時(shí)候，必須先通過(guò)軟件從磁盤(pán)文件中讀取機(jī)器語(yǔ)言程序招盲，再將復(fù)制到內(nèi)存中低缩，這類(lèi)程序稱(chēng)不上時(shí)語(yǔ)言處理器，通常稱(chēng)為操作系統(tǒng)曹货。
而計(jì)算機(jī)是如何將高級(jí)語(yǔ)言變成機(jī)器語(yǔ)言的呢咆繁？這里就需要用到語(yǔ)言處理器，其實(shí)語(yǔ)言處理器在我們的工作中時(shí)時(shí)刻刻都在接觸顶籽。這之中大致分兩種:
編譯器：將某種語(yǔ)言寫(xiě)成的程序轉(zhuǎn)換成另一種語(yǔ)言的程序玩般。通常會(huì)將源程序轉(zhuǎn)化為機(jī)器語(yǔ)言程序。編譯器轉(zhuǎn)化程序的行為稱(chēng)為編譯礼饱。
解釋器：根據(jù)程序中的算法執(zhí)行運(yùn)算坏为。簡(jiǎn)單來(lái)講，它時(shí)一種用于執(zhí)行程序的軟件镊绪。如果執(zhí)行的程序由虛擬機(jī)器語(yǔ)言或類(lèi)似于機(jī)器語(yǔ)言的程序設(shè)計(jì)語(yǔ)言寫(xiě)成匀伏，這種軟件也能稱(chēng)為虛擬機(jī)，例如JS蝴韭，Python等腳本語(yǔ)言够颠。
Java語(yǔ)言會(huì)特殊一些，首先會(huì)通過(guò)編譯器把源代碼轉(zhuǎn)化成Java字節(jié)碼榄鉴，并將這種虛擬的機(jī)器語(yǔ)言保存在文件中履磨。之后,Java虛擬機(jī)的解釋器將執(zhí)行這些代碼。大多數(shù)Java虛擬機(jī)為了提高性能庆尘，會(huì)在執(zhí)行過(guò)程中通過(guò)編譯器將一部分Java字節(jié)碼直接轉(zhuǎn)化為機(jī)器代碼使用剃诅，執(zhí)行過(guò)程中進(jìn)行搞得機(jī)器語(yǔ)言轉(zhuǎn)化稱(chēng)為動(dòng)態(tài)編譯或JIT編譯，轉(zhuǎn)化后得到的機(jī)器語(yǔ)言將被載入內(nèi)存驶忌，由硬件執(zhí)行矛辕，無(wú)需使用解釋器。
過(guò)去人們提到編譯器時(shí)，首先會(huì)聯(lián)想編譯過(guò)程非常耗時(shí)如筛。不過(guò)由于編譯后實(shí)際執(zhí)行的是機(jī)器語(yǔ)言堡牡，因此執(zhí)行速度很快。而對(duì)于解釋器杨刨，人們通常認(rèn)為它會(huì)在程序輸入的同時(shí)立即執(zhí)行晤柄，執(zhí)行速度較慢。這就是兩者的基本區(qū)別⊙停現(xiàn)代的解釋器內(nèi)部常采用各種類(lèi)型的編譯器芥颈，已經(jīng)越來(lái)越?jīng)]必要將解釋器與編譯器區(qū)分看待。
0x02.詞法分析
語(yǔ)言處理器的第一個(gè)組成部分是詞法分析赚抡。程序的源代碼本質(zhì)只是一長(zhǎng)串字符串爬坑，這樣的字符串很難處理，語(yǔ)言處理器通常會(huì)首先將字符串中的字符以單詞為單位分組涂臣，切割成多個(gè)子字符串盾计。這就是詞法分析
token對(duì)象
下面是某個(gè)程序中的一行代碼
while i < 10 {
詞法分析會(huì)把它拆分為下面這樣的字符串
"while" "i" "<" "10" "{"
這句代碼被分割為了5個(gè)字符串。通常把詞法分析的結(jié)果稱(chēng)為單詞（token）赁遗，當(dāng)然可能你的換行會(huì)變成一個(gè)"\n"的token署辉，注釋標(biāo)志也可能會(huì)變成一個(gè)"/*"、"*/" 兩個(gè)token岩四，這都是有可能的哭尝，具體看編譯器是如何工作的。當(dāng)然具體是怎么切的剖煌，《兩周》這本書(shū)用的是正則匹配:
- 用
[0-9]+來(lái)匹配整型材鹦。 - 用
[A-Z_a-z][A-Z_a-z0-9]*(以字母、下劃線(xiàn)開(kāi)頭耕姊，之后僅包含有字母桶唐、數(shù)字、下劃線(xiàn))來(lái)匹配標(biāo)識(shí)符茉兰，（是不是很像我們平時(shí)定義變量?莽红，不可以用數(shù)字開(kāi)頭） - ...
執(zhí)行詞法分析時(shí)，語(yǔ)言處理器會(huì)逐行讀取源代碼邦邦，從各行開(kāi)頭起檢查內(nèi)容是否與該正則表達(dá)式匹配，并在檢查完后獲取與正則表達(dá)式括號(hào)內(nèi)的模式相匹配的字符串醉蚁。
在這一步中燃辖，空格、換行网棍、注釋這些都會(huì)被分析器所忽略黔龟。編譯器會(huì)事先獲知之后取得的單詞，一邊獲取一邊構(gòu)造抽象語(yǔ)法樹(shù)，在中途發(fā)現(xiàn)構(gòu)造有誤時(shí)氏身，需要退回若干單詞巍棱，重新構(gòu)造語(yǔ)法樹(shù)，稱(chēng)之為回溯蛋欣。
0x03.語(yǔ)法分析/AST(抽象語(yǔ)法樹(shù))
語(yǔ)言處理器在詞法分析階段將程序分割為單詞后航徙，將開(kāi)始構(gòu)造抽象語(yǔ)法樹(shù)。抽象語(yǔ)法樹(shù)（AST陷虎，Abstract Syntax Tree）是一種用于表示程序結(jié)構(gòu)的樹(shù)形結(jié)構(gòu)到踏。語(yǔ)法分析的主要任務(wù)是分析單詞之間的關(guān)系，如判斷哪些單詞屬于同一個(gè)表達(dá)式或語(yǔ)句尚猿，以及處理左右括號(hào)（單詞）的配對(duì)等問(wèn)題窝稿。這一階段還會(huì)檢查程序中是否含有語(yǔ)法錯(cuò)誤。
13 + x * 2
我們對(duì)上面這條語(yǔ)句進(jìn)行詞法分析凿掂。我們通過(guò)上面的分析可以得出伴榔，編譯器大致會(huì)分割成 13 、+ 庄萎、x 踪少、* 、2惨恭，這幾個(gè)token秉馏。
然后我們將這些token進(jìn)行重新排列，變成一個(gè)抽象語(yǔ)法樹(shù)脱羡，每個(gè)葉節(jié)點(diǎn)存儲(chǔ)著具體的值和值的類(lèi)型萝究。
那么像+和*，在進(jìn)行語(yǔ)法樹(shù)構(gòu)建的過(guò)程中锉罐，符號(hào)其實(shí)是有優(yōu)先級(jí)以及左右結(jié)合順序的帆竹，后面會(huì)提到。
0x04.BNF
什么是BNF脓规？總的來(lái)說(shuō)BNF是一個(gè)描述語(yǔ)法規(guī)則的語(yǔ)言栽连。
初次理解BNF會(huì)覺(jué)得很難懂，至少我是理解了好久侨舆。如果看文字實(shí)在太繞秒紧，建議看視頻，https://www.bilibili.com/video/BV1Us411h72K?from=search&seid=14895223797156770591 我是看了這個(gè)視頻之后開(kāi)竅了（我居然可以在bilibli學(xué)技術(shù)）挨下。
BNF中常用的元字符及其表示的意義如下：
在雙引號(hào)中的字 "word" 代表著這些字符本身熔恢。而double_quote用來(lái)代表雙引號(hào)；
在雙引號(hào)外的字（有可能有下劃線(xiàn)）代表著語(yǔ)法部分臭笆；
尖括號(hào) < > 內(nèi)包含的為必選項(xiàng)叙淌；
方括號(hào) [ ] 內(nèi)包含的為可選項(xiàng)秤掌；
大括號(hào) { } 內(nèi)包含的為可重復(fù)0至無(wú)數(shù)次的項(xiàng)；
圓括號(hào) ( ) 內(nèi)包含的所有項(xiàng)為一組鹰霍，用來(lái)控制表達(dá)式的優(yōu)先級(jí)闻鉴；
豎線(xiàn) | 表示在其左右兩邊任選一項(xiàng)，相當(dāng)于"OR"的意思茂洒；
::= 是“被定義為”的意思孟岛；
... 表示術(shù)語(yǔ)符號(hào)；
理解了上面這些符號(hào)的規(guī)則获黔，可以來(lái)看看書(shū)中對(duì)自制語(yǔ)言的規(guī)則描述:
primary ::= "(" expr ")" | NUMBER | IDENTIFIER | STRING
factor ::= "-" primary | primary
expr ::= factor { OP factor }
block ::= "{" [ statement ] { (";" | EOL) [ statement ]} "}"
simple ::= expr
statement ::= "if" expr block [ "else" block ] | "while" expr block | simple
program ::= [ statement ] (";" | EOL)
非終結(jié)符factor（因子）或表示一個(gè)primary蚀苛，或表示primary之前再添加一個(gè)-號(hào)的組合
expr（表達(dá)式）用于表示兩個(gè)factor之間夾有一個(gè)雙目運(yùn)算符的組合
block（代碼塊）指的是由{括起來(lái)的statement（語(yǔ)句）序列
statement之間需要用分號(hào)或換行符（EOL）分隔。由于Stone 語(yǔ)言支持空語(yǔ)句玷氏，因此規(guī)則中的statement兩側(cè)寫(xiě)有中括號(hào)[]堵未。可以看到盏触，它的結(jié)構(gòu)大致與expr類(lèi)似渗蟹。它們都由其他的非終結(jié)符（statement或factor）與一些用于分隔的符號(hào)組合而成
statement可以是if語(yǔ)句、while語(yǔ)句或僅僅是簡(jiǎn)單表達(dá)式語(yǔ)句（simp1e）赞辩。簡(jiǎn)單表達(dá)式語(yǔ)句是僅由表達(dá)式（expr）構(gòu)成的語(yǔ)句雌芽。
最后的program（程序）是一個(gè)非終結(jié)符，它可以包含分號(hào)或換行符辨嗽，用于表示一句完整的語(yǔ)句世落。其中，statement可以省略糟需，因此program還能用來(lái)表示空行屉佳。代碼塊中最后一句能夠省略句尾分號(hào)與換行符。
想要徹底理解BNF洲押，遞歸的思想是必不可少的
假如以上BNF規(guī)定了語(yǔ)言語(yǔ)法的時(shí)候武花，在進(jìn)行抽象語(yǔ)法樹(shù)組合的時(shí)候，如果不符合以上制定的這些規(guī)則時(shí)杈帐，編譯器就會(huì)拋出異常体箕。
例如:最后聲明的program（程序），你只能用分號(hào)或者換行符作為結(jié)束符挑童，你想用用句號(hào)（累铅。）作為結(jié)束符，是不被允許的站叼。
0x04.解釋器執(zhí)行
語(yǔ)法分析將從詞法分析器逐一讀取非終結(jié)符program娃兽。即，以語(yǔ)句為單位讀取單詞大年，并進(jìn)行語(yǔ)法分析换薄，執(zhí)行語(yǔ)法分析后得到的抽象語(yǔ)法樹(shù)。只要通過(guò)語(yǔ)法分析得到抽象語(yǔ)法樹(shù)翔试，剩下的就簡(jiǎn)單了轻要，只要從根結(jié)點(diǎn)開(kāi)始遍歷至葉節(jié)點(diǎn)，并計(jì)算各節(jié)點(diǎn)的內(nèi)容即可垦缅，這就是解釋器的基本實(shí)現(xiàn)原理冲泥。
要根據(jù)得到的抽象語(yǔ)法樹(shù)來(lái)執(zhí)行程序，各個(gè)語(yǔ)法樹(shù)節(jié)點(diǎn)對(duì)象的類(lèi)都需要具備eval方法壁涎。eval是evaluate（求值）的縮寫(xiě)凡恍。eval方法將計(jì)算與以該節(jié)點(diǎn)為根的子樹(shù)對(duì)應(yīng)的語(yǔ)句、表達(dá)式及子表達(dá)式怔球，并返回執(zhí)行結(jié)果嚼酝。一直執(zhí)行，執(zhí)行到根節(jié)點(diǎn)為止竟坛。
其實(shí)這同樣是一種遞歸過(guò)程闽巩，
0x05.編譯器
在使用中間代碼解釋器時(shí)，我們要事先將抽象語(yǔ)法樹(shù)轉(zhuǎn)換為中間代碼担汤。簡(jiǎn)單來(lái)說(shuō)涎跨，中間代碼是一種虛擬的機(jī)器語(yǔ)言，因此崭歧，中間代碼的轉(zhuǎn)換方法隅很，其實(shí)與編譯器將抽象語(yǔ)法樹(shù)轉(zhuǎn)換為真正的機(jī)器語(yǔ)言時(shí)采用的方法大體相同。
中間代碼與機(jī)器語(yǔ)言
之間利用抽象語(yǔ)法樹(shù)率碾，語(yǔ)言處理器需要在節(jié)點(diǎn)之間往返操作叔营，這是一件費(fèi)時(shí)的工作。因此播掷，如果語(yǔ)言處理器能夠?qū)崿F(xiàn)計(jì)算遍歷順序审编，并以此重新排列節(jié)點(diǎn)，執(zhí)行開(kāi)銷(xiāo)就可能有所降低
通常歧匈，語(yǔ)言處理器不會(huì)直接將重新排列的抽象語(yǔ)法樹(shù)節(jié)點(diǎn)作為中間代碼使用垒酬。如果直接保存抽象語(yǔ)法樹(shù)的節(jié)點(diǎn)，多余的無(wú)用信息是一種空間上的浪費(fèi)件炉，因此勘究，我們需要設(shè)計(jì)一種虛擬的機(jī)器語(yǔ)言，并將各個(gè)節(jié)點(diǎn)轉(zhuǎn)換為與該節(jié)點(diǎn)運(yùn)算邏輯對(duì)應(yīng)的機(jī)器語(yǔ)言斟冕。大多數(shù)語(yǔ)言處理器使用的中間語(yǔ)言都是這種轉(zhuǎn)換后的代碼（見(jiàn)下圖）
虛擬機(jī)由若干個(gè)通用寄存器與內(nèi)存組成口糕。內(nèi)存分為四個(gè)區(qū)域，分別是棧（stack）區(qū)磕蛇、堆（heap）區(qū)景描、程序代碼區(qū)與文字常量區(qū)十办。虛擬機(jī)器語(yǔ)言保存于程序代碼區(qū)，字符串字面量保存干文字常量區(qū)超棺。
本書(shū)作者自己實(shí)現(xiàn)了一個(gè)自制的虛擬機(jī)向族，在程序啟動(dòng)過(guò)程中同時(shí)啟動(dòng)虛擬機(jī)，對(duì)于抽象語(yǔ)法樹(shù)的操作不再是簡(jiǎn)單的執(zhí)行棠绘，而是首先將語(yǔ)言轉(zhuǎn)為虛擬機(jī)語(yǔ)言件相，再通過(guò)匯編執(zhí)行函數(shù)的思路進(jìn)行執(zhí)行。不過(guò)本書(shū)中的程序?yàn)榱搜菔咎摂M機(jī)的工作原理并沒(méi)有給程序性能帶來(lái)提升氧苍，因?yàn)樽灾频恼Z(yǔ)言是程序啟動(dòng)過(guò)程中進(jìn)行編譯夜矗，執(zhí)行。不如直接執(zhí)行抽象語(yǔ)法樹(shù)來(lái)的直接让虐。
0x06.總結(jié)
其實(shí)書(shū)中的細(xì)節(jié)還有很多紊撕，作者對(duì)自制的語(yǔ)言也加入很多功能，比如函數(shù)澄干，靜態(tài)變量逛揩、閉包等等。在實(shí)現(xiàn)局部和全部變量時(shí)麸俘，居然討巧的用了一個(gè)hashmap + namespace來(lái)實(shí)現(xiàn)辩稽，來(lái)確保變量的作用域，這真的非常有意思从媚。
看了這本書(shū)逞泄，算是對(duì)編譯原理有一個(gè)入門(mén)級(jí)的認(rèn)識(shí)吧， 取名（1）拜效，希望鞭策自己這個(gè)主題會(huì)有第二篇喷众、第三篇....吧。
眾所周知紧憾，目前程序的編譯器基本都是C++實(shí)現(xiàn)的到千，但是第一個(gè)C++程序又是誰(shuí)給編譯的呢？都知道蛋是雞生的赴穗，那么第一只雞是哪來(lái)的呢憔四？
所謂C語(yǔ)言編譯器，就是把編程得到的文件般眉，比方.c,.h的文件了赵，進(jìn)行讀取，并對(duì)內(nèi)容進(jìn)行剖析甸赃，按照C語(yǔ)言的規(guī)則柿汛，將其轉(zhuǎn)換成體系能夠履行的二進(jìn)制文件。
其本質(zhì)在于對(duì)文件的讀入埠对，剖析络断，及處理裁替。這些操作，C言語(yǔ)都是能夠完成的貌笨。所以用C言語(yǔ)來(lái)做C言語(yǔ)的編譯器是徹底可行的胯究。
可是，歷史上的第一個(gè)C言語(yǔ)編譯器躁绸，必定不是C言語(yǔ)寫(xiě)的，因?yàn)樵跊](méi)有編譯器時(shí)臣嚣，無(wú)法把C言語(yǔ)轉(zhuǎn)換成可履行文件净刮。
只需有了第一版其它言語(yǔ)的編譯器，就能夠用C言語(yǔ)寫(xiě)編譯器了硅则。事實(shí)上淹父，現(xiàn)在大多數(shù)的C言語(yǔ)編譯器，都是用C言語(yǔ)寫(xiě)的怎虫。
首要你要理解編譯的意思暑认，它是指把高檔言語(yǔ)翻譯成計(jì)算機(jī) 能讀懂的低級(jí)言語(yǔ)（二進(jìn)制代碼），這樣計(jì)算機(jī)才會(huì)履行你 的指令大审，
編譯器就相當(dāng)于一個(gè)翻譯蘸际，在翻譯的過(guò)程中還會(huì)檢 查你語(yǔ)法上有沒(méi)有錯(cuò)誤 C言語(yǔ)編譯器自然是把用C言語(yǔ)寫(xiě)的程序翻譯成二進(jìn)制代碼咯。
0x07.參考
兩周自制腳本語(yǔ)言/提取碼: t8qm
