? ? ? 乘著春節(jié)假期閑來(lái)無(wú)事，準(zhǔn)備挑戰(zhàn)一下有點(diǎn)難度的事情，試著寫一門腳本語(yǔ)言。沒(méi)有任何依據(jù)，要想憑空造一門腳本語(yǔ)言，那是幾乎不可能的事情，所以首先要解決的是參考資料的問(wèn)題——龍??（Compilers: Principles,Techniques,and Tools）、虎??（Modern Compiler Implementation in C）、鯨??（Advanced Compiler Design and Implementation）三書(shū)是編譯原理的三大經(jīng)典，可是看看這幾本書(shū)的個(gè)頭以及有限的假期，看來(lái)只能等以后再來(lái)啃他們了。到亞馬遜和京東上搜索“自制語(yǔ)言”，出來(lái)的結(jié)果全是圖靈出的：《兩周自制腳本語(yǔ)言》、《自制編程語(yǔ)言》、《自制編譯器》，而且與設(shè)計(jì)腳本語(yǔ)言有關(guān)的中文書(shū)似乎只此一本——《兩周自制腳本語(yǔ)言》
英文書(shū)里倒是也有一本2016年新出的關(guān)于自制腳本語(yǔ)言的書(shū)《Writing An Interpreter In Go》，粗看了一下覺(jué)得不錯(cuò)，也列為參考資料。
選好參考資料，以兩周做為時(shí)間參考坐標(biāo)，我的自制腳本之旅就開(kāi)始啟動(dòng)了：
第一天：來(lái)，我們一起做些什么吧?
? ? ? 翻開(kāi)之后，發(fā)現(xiàn)第一天的內(nèi)容好像少的讓我有些吃驚，只有9頁(yè)，真的要花一天才能讀完嗎??? 當(dāng)然內(nèi)容雖少卻是提綱挈領(lǐng)的一章，里面介紹了要設(shè)計(jì)一門腳本語(yǔ)言必備的基礎(chǔ)概念：什么是機(jī)器語(yǔ)言、什么是匯編語(yǔ)言、解釋器和編譯器有什么區(qū)別等等……最重要的是介紹了我們要設(shè)計(jì)一門編程語(yǔ)言必不可少的結(jié)構(gòu)—— 如下圖所示：
首先是源代碼，程序員每天都要打交道的東西。既然是“自制”，那么現(xiàn)在這個(gè)語(yǔ)言要靠自己設(shè)計(jì)了，這是語(yǔ)言設(shè)計(jì)師的天地，語(yǔ)法（風(fēng)格）任由我來(lái)設(shè)定，比如：
? ? ? ? ? ? ? ? ? ? ? 令 年齡 = 1;
? ? ? ? ? ? ? ? ? ? ? 令 名字 = "我的姓名";
? ? ? ? ? ? ? ? ? ? ? 令 運(yùn)算結(jié)果 = 10 乘以 (20除以2);
/*上面這三行看上去雖然和程序員們?nèi)粘４蚪坏赖母鞣N語(yǔ)言不那么一樣，但是應(yīng)該還是能看懂的吧??*/
第二步，是詞法分析（Lexing），我們需要實(shí)現(xiàn)一個(gè)詞法分析器（被稱為lexical analyzer 或 lexer ?也有叫scanner的），把上面這些語(yǔ)句進(jìn)一步拆分成特定的“符號(hào)”，比如把“令 年齡 = 1;” 拆分為“令”、“年齡”、“＝”、“1”、“;”，這個(gè)拆分的結(jié)果被稱為Token。
第三步，是語(yǔ)法分析（Parsing），我們需要實(shí)現(xiàn)一個(gè)語(yǔ)法分析器（即Parser），語(yǔ)法分析器的作用就是把前面一步詞法分析（Lexing）獲取的Token進(jìn)一步的解析并生成抽象語(yǔ)法樹(shù)（abstract syntax tree或者縮寫為AST），這是每個(gè)編程語(yǔ)言（不論是解釋型的還是編譯型的）都少不了的部分。
第四步，則是腳本語(yǔ)言與編譯型語(yǔ)言的分野處，通過(guò)Parser拿到抽象語(yǔ)法樹(shù)（AST）后，如果你要通過(guò)編譯器（Compiler）生成機(jī)器碼后再運(yùn)行，那么你搞的就是編譯型語(yǔ)言，如果你是要通過(guò)解釋器（Interpreter）直接執(zhí)行，那么你搞的就是腳本語(yǔ)言。如果我既搞了編譯器，又搞了解釋器，那算什么呢 —— 其實(shí)這真的沒(méi)有問(wèn)題，只要你手上已經(jīng)有了抽象語(yǔ)法樹(shù)（AST），那你可以同時(shí)把兩者都給實(shí)現(xiàn)了??。
第一章雖然只有短短9頁(yè)，但是把整本書(shū)的內(nèi)容做了高度的概括，并且在第7-9頁(yè)列出了按天（章）劃分的學(xué)習(xí)計(jì)劃，劇透一下，其實(shí)本書(shū)要完整看完并不是14天，最后還有5章（天）是用于自學(xué)的，按照作者建議的閱讀順序是：先讀完第 2~8 章，之后是第 15、16 章，若還有時(shí)間，再讀第 11 章和第 13 章。
第一步：設(shè)計(jì)語(yǔ)言風(fēng)格
既然是自制腳本語(yǔ)言，那么我并不打算完整的跟著本書(shū)作者后面亦步亦趨，而是從一開(kāi)始就確立了本次實(shí)戰(zhàn)的語(yǔ)言風(fēng)格：中文型——除了通用操作符（＋、－、*、/、=、;等）之外，關(guān)鍵字都用中文??：
變量賦值在上面已經(jīng)舉例了，下面就舉一些例子：
流程控制語(yǔ)句:
若(年齡>18){
? ? ?打印("年齡已經(jīng)符合要求");
}否則{
? ? 打印("歲數(shù)還小");
}
循環(huán)語(yǔ)句1：
令 總數(shù) = 0;
當(dāng)(總數(shù)<1000){
? ? ? ?打印(總數(shù));
? ? ? ?總數(shù)++;
}
循環(huán)語(yǔ)句2:
令 數(shù)組 = [1,2,3,4,5];
在 數(shù)組 遍歷 i,v {
? ? ? 打印("第" + i + "個(gè)數(shù)組元素是:" + v); ??
}
第二步：設(shè)計(jì)詞法分析器（Lexing）
? ? ? 在確定了語(yǔ)言風(fēng)格之后，其實(shí)詞法分析器就不是很困難了，說(shuō)起來(lái)就是把每一行里哪些是關(guān)鍵字（比如“令”、“遍歷”、“在”、“當(dāng)”、“若”、“否則”）、哪些是變量（如“i”、“v”、“年齡”等）、哪些是操作符（如“＋”、“－”、“*"、“/”、“＝”）、哪些是分隔符（如“{”、“｝”、“;”等）并且分門別類，這些被分析出來(lái)的元素統(tǒng)稱為Token。
至于如何找出Token，方法其實(shí)并不限定，這取決于第一步你的語(yǔ)言風(fēng)格是如何設(shè)計(jì)的，常見(jiàn)的分析方法：（1）用正則表達(dá)式分析，本書(shū)第三章用的是這個(gè)方法。
（2）正則表達(dá)式能夠表述非常復(fù)雜的字符串模式匹配邏輯，但它并非萬(wàn)能，所以本書(shū)又在第十五章提供了一個(gè)“手工詞法分析器”的方法，將正則表達(dá)式分析方法改寫為自動(dòng)機(jī)方法，具體流程見(jiàn)下圖
第三步：設(shè)計(jì)語(yǔ)法分析器（Parsing）
? ? ? 我們?cè)诘诙将@得Token之后，就要通過(guò)語(yǔ)法分析器（Parser）將Token解析為抽象語(yǔ)法樹(shù)（abstract syntax tree，即AST），如果學(xué)過(guò)編譯原理，那么你不會(huì)對(duì)AST感到陌生，如果不熟悉的話，應(yīng)該好好閱讀一下第4章：用于表示程序的對(duì)象。
? ? ? 在計(jì)算機(jī)科學(xué)中，抽象語(yǔ)法樹(shù)，是源代碼的抽象語(yǔ)法結(jié)構(gòu)的樹(shù)狀表現(xiàn)形式，這里特指編程語(yǔ)言的源代碼。樹(shù)上的每個(gè)節(jié)點(diǎn)都表示源代碼中的一種結(jié)構(gòu)。之所以說(shuō)語(yǔ)法是“抽象”的，是因?yàn)檫@里的語(yǔ)法并不會(huì)表示出真實(shí)語(yǔ)法中出現(xiàn)的每個(gè)細(xì)節(jié)。比如，嵌套括號(hào)被隱含在樹(shù)的結(jié)構(gòu)中，并沒(méi)有以節(jié)點(diǎn)的形式呈現(xiàn)；而類似于if-condition-then這樣的條件跳轉(zhuǎn)語(yǔ)句，可以使用帶有兩個(gè)分支的節(jié)點(diǎn)來(lái)表示。
例如我們要用一個(gè)抽象語(yǔ)法樹(shù)表示一個(gè)表達(dá)式： 13+x*2
會(huì)得到下面的??樹(shù)狀圖:
? ? ? ? 了解完抽象語(yǔ)法樹(shù)的概念后，我們將正式開(kāi)始語(yǔ)法分析器的設(shè)計(jì)。在第二步，我們已經(jīng)通過(guò)詞法分析器（Lexer）分解為了單詞序列。而語(yǔ)法分析器（Parser）的任務(wù)是將這些單詞序列與語(yǔ)法規(guī)則定義的模式進(jìn)行匹配，并構(gòu)造出如上圖那樣的抽象語(yǔ)法樹(shù)。
? ? ? ?在語(yǔ)法設(shè)計(jì)的時(shí)候，你設(shè)計(jì)的表達(dá)式越復(fù)雜，則在語(yǔ)法分析的時(shí)候，面臨的困難就越大，所以從語(yǔ)言使用者的角度來(lái)看，我還是喜歡設(shè)計(jì)簡(jiǎn)潔的語(yǔ)言。
? ? ? 其實(shí)對(duì)于搞出語(yǔ)法分析器還有另一種辦法，那就是借助語(yǔ)法分析器的生成器(Parser Generator)，例如yacc, bison 或者 ANTLR，這些都是比較完善的生成器，可以大大降低工作量以及減少bug。
? ? ? 當(dāng)然本著我們要自己搞一套的理念??，本書(shū)中仍然提供了手寫語(yǔ)法分析器的過(guò)程以及代碼。自己手寫語(yǔ)法分析器的過(guò)程，當(dāng)然是對(duì)語(yǔ)法分析的一次極有價(jià)值的實(shí)踐，所以嘛，從玩票的角度，我們?nèi)匀粦?yīng)該堅(jiān)持手寫Parser????。
第四步：設(shè)計(jì)解釋器并執(zhí)行程序（Evaluation）
? ? ? ? 如第一天教程所介紹的，我們拿到抽象語(yǔ)法樹(shù)（AST）之后，要編譯還是解釋就取決于我們的需求了，當(dāng)然，有興趣的話兩者都可以實(shí)現(xiàn)，編譯器的設(shè)計(jì)請(qǐng)參看圖靈的《自制編譯器》一書(shū)。
? ? ? 言歸正傳，從抽象語(yǔ)法樹(shù)（AST）到通過(guò)求值（Evaluate）得到結(jié)果，其實(shí)有很多種策略，根據(jù)策略的不同，執(zhí)行效率也會(huì)有較大的差別，最簡(jiǎn)單的策略就是本書(shū)中提到的遍歷抽象語(yǔ)法樹(shù)解釋法（A Tree-Walking Interpreter），即從抽象語(yǔ)法樹(shù)的根節(jié)點(diǎn)開(kāi)始遍歷該樹(shù)直至葉節(jié)點(diǎn)，并計(jì)算各節(jié)點(diǎn)的內(nèi)容。
? ? ? 我們的語(yǔ)法樹(shù)的每個(gè)節(jié)點(diǎn)都需要具備相應(yīng)的求值（eval）方法。eval方法將計(jì)算與以該節(jié)點(diǎn)為根的子樹(shù)對(duì)應(yīng)的語(yǔ)句、表達(dá)式及子表達(dá)式，并返回執(zhí)行結(jié)果。因此，只要調(diào)用抽象語(yǔ)法樹(shù)的根節(jié)點(diǎn)對(duì)象的eval方法，就能完整執(zhí)行該語(yǔ)法樹(shù)對(duì)應(yīng)的程序。eval方法將遞歸調(diào)用該節(jié)點(diǎn)的子節(jié)點(diǎn)的eval方法，并根據(jù)它們的返回值計(jì)算自身的返回值，最后將結(jié)果返回給調(diào)用者。
? ? 說(shuō)到關(guān)鍵之處，本書(shū)作者引入了一個(gè)其自己開(kāi)發(fā)的“GlounJ”的系統(tǒng)來(lái)實(shí)現(xiàn)解釋器。當(dāng)然，我們也完全可以拋開(kāi)“GlounJ”系統(tǒng)來(lái)完成自己的解釋器。
總結(jié)：
? ? ? 本書(shū)到第6章，其實(shí)已經(jīng)把一個(gè)初步的腳本語(yǔ)言設(shè)計(jì)完成，并且涉及到了開(kāi)發(fā)一門腳本語(yǔ)言所需要的基礎(chǔ)知識(shí)和概念，后面的7-10章則陸續(xù)介紹了如何引入函數(shù)、面向?qū)ο?、?shù)組的方法，進(jìn)一步的豐富了腳本語(yǔ)言，使其具有圖靈完備性。第11-14章則進(jìn)一步討論如何優(yōu)化解釋器的性能：優(yōu)化變量讀寫性能、優(yōu)化對(duì)象操作性能、設(shè)計(jì)中間代碼解釋器、添加靜態(tài)類型等等。第15-19章則從另一種角度出發(fā)，以不同的方式實(shí)現(xiàn)了腳本語(yǔ)言的第2、3、4步，反映了解決問(wèn)題的不同思路。?
? ? ?總的來(lái)說(shuō)，如果你要是想設(shè)計(jì)并實(shí)現(xiàn)一門腳本語(yǔ)言，而又需要中文教材的話，本書(shū)是你目前的唯一選擇??。至于缺點(diǎn)嘛，我覺(jué)得就是大段的代碼邊上沒(méi)有注釋，啃起來(lái)有點(diǎn)費(fèi)勁，要是能有一個(gè)帶注釋的版本會(huì)更好！
? ? 最后，感謝圖靈帶給我們的這本好書(shū)，下一次，我將挑戰(zhàn)《自制編程語(yǔ)言》和《自制編譯器》??
