大家好悴了，我是微微笑的蝸牛搏恤，??。
這個(gè)系列的文章湃交，我們將來(lái)動(dòng)手實(shí)現(xiàn)一個(gè)小型的 Lisp 解釋器熟空，使用 Swift 編寫(xiě)。至于寫(xiě)解釋器的緣由呢搞莺，是因?yàn)榍靶┨炜吹揭黄?a target="_blank">國(guó)外的文章息罗，里面比較詳細(xì)的介紹了如何編寫(xiě)自己的 Lisp 解釋器。以前也沒(méi)有弄過(guò)這方面的東西才沧，出于學(xué)習(xí)的目的迈喉，讀完文章后，動(dòng)手實(shí)踐了一番温圆。
說(shuō)起來(lái)挨摸，只讀文章和動(dòng)手寫(xiě)的差別還是相當(dāng)大的。在讀文章時(shí)岁歉，你會(huì)發(fā)現(xiàn)大概思路我都懂了得运，但是細(xì)細(xì)一想，對(duì)有些小細(xì)節(jié)如何實(shí)現(xiàn)還是有點(diǎn)疑惑刨裆；而在實(shí)踐過(guò)程中澈圈，必須得去弄清楚每個(gè)細(xì)節(jié)（不然就是照抄代碼了??），從中會(huì)發(fā)現(xiàn)一些意外并令人驚喜的點(diǎn)帆啃，甚至突然有種熱血沸騰的感覺(jué)瞬女。
比如 lambda 的實(shí)現(xiàn)，它是一個(gè)匿名函數(shù)努潘，那如何實(shí)現(xiàn)在聲明后就立即調(diào)用的呢诽偷？這個(gè)點(diǎn)其實(shí)有點(diǎn)困擾我坤学，因?yàn)槲以趯?shí)現(xiàn)代碼中并沒(méi)有看到直接調(diào)用。后來(lái)仔細(xì)一調(diào)試报慕，才發(fā)現(xiàn)其精妙之處深浮。
下面，就讓我們開(kāi)始這段旅程吧~
LISP 簡(jiǎn)介
Lisp 是一種古老的語(yǔ)言眠冈，其全稱為 List Processor飞苇，它是一種函數(shù)式編程語(yǔ)言，該語(yǔ)言的主要數(shù)據(jù)結(jié)構(gòu)就是 list∥贤纾現(xiàn)在由它也衍生出了很多變種布卡，比如 Common Lisp、Scheme 等雇盖。
Lisp 中開(kāi)創(chuàng)了一些先驅(qū)概念忿等，比如 REPL，讀取-求值-循環(huán)輸出崔挖。我們的解釋器就構(gòu)建在該模型之上贸街。
Lisp 的代碼組成很簡(jiǎn)單，只包括 (狸相、)薛匪、字符三種類型。它由原子 atom 或者列表 list 組成脓鹃。
- 原子：包括符號(hào)和數(shù)值蛋辈，比如
"hello"，2将谊。 - 列表：用
()表示冷溶，內(nèi)部可有 0~n 個(gè)表達(dá)式，也可以嵌套列表尊浓，比如"(a b c)"逞频，"(a b (c d))"，表達(dá)式之間用空格隔開(kāi)栋齿。
另外苗胀，函數(shù)調(diào)用也是列表形式：
// f 是函數(shù)名，a, b, c 分別是三個(gè)參數(shù)
(f a b c)
接下來(lái)瓦堵，我們會(huì)根據(jù) MicroManual-LISP 的定義來(lái)實(shí)現(xiàn)它基协。不過(guò)，也不是全部菇用。先來(lái)看看 Lisp 中定義的操作符澜驮。
操作符
quote
- 定義：
// 返回 x
(quote x)
- 說(shuō)明：取出數(shù)據(jù) x。如果 x 是表達(dá)式惋鸥，x 的值無(wú)需計(jì)算杂穷，原樣返回悍缠。
atom
- 定義：
// 當(dāng) x 是 atom 或者是空 list 時(shí)返回 true；否則返回空表 ()
(atom x)
- 說(shuō)明：判斷表達(dá)式是否是原子耐量。若是
atom或者是空列表()飞蚓，則返回true；否則返回空列表（）廊蜒。
equal
- 定義：
// 判斷 x趴拧，y 是否相等
(equal x y)
- 說(shuō)明：判斷兩個(gè)表達(dá)式是否相等。如果相等山叮，則返回
true八堡；若不等，則返回空列表()聘芜。 - 舉例：
// true
(equal a a)
// ()
(equal a ())
car
- 定義：
// x 是一個(gè)列表，返回第一個(gè)元素
(car x)
- 說(shuō)明：取出列表中的第一個(gè)元素缝龄，x 必須是
列表汰现。 - 舉例：
// 結(jié)果：x
(car (x y))
cdr
- 定義
// x 是一個(gè)列表，返回除第一個(gè)元素外叔壤，其余的元素組成的列表瞎饲。也就是剔除掉第一個(gè)元素
(car x)
- 說(shuō)明：返回列表中除第一個(gè)元素外，其余的元素組成的列表炼绘。注意參數(shù)必須是
列表嗅战。 - 舉例：
// 結(jié)果：(y z)
(car (x y z))
cons
- 定義：
(cons e list)
- 說(shuō)明：將元素
e和list組合起來(lái)返回新的列表。注意：第二個(gè)參數(shù)必須是列表俺亮。 - 舉例：
// (x y z)
(cons (x) (y z))
cond
- 定義
// p驮捍、e 為表達(dá)式
(cond (p1 e1) ...(pn en))
- 說(shuō)明：對(duì)參數(shù)中的 p 逐個(gè)求值，直至返回 true脚曾，此時(shí)計(jì)算 e 的值后返回东且。
具體操作為：
- 首先對(duì) p1 求值，如果為 true本讥，則計(jì)算 e1 的值返回珊泳；否則繼續(xù)求值 p2。
- 若 p2 的值不為 true拷沸，繼續(xù)求值 p3色查，以此類推，直至到 pn撞芍。
- 若沒(méi)有滿足條件的 p秧了，則返回空列表 ()。
- 舉例
// second
(cond ((equal a b) (quote first)) ((atom a) (quote second)))
計(jì)算步驟如下：
- 首先對(duì)
p0 = (equal a b)求值序无，兩者不相等示惊，返回()好港。 - 然后繼續(xù)對(duì)
p1 = (atom a)求值，此時(shí)返回true米罚。那么計(jì)算對(duì)應(yīng)表達(dá)式e1 = (quote second)的值钧汹，結(jié)果是second，然后將其返回录择。
lambda
- 定義
// v1~vn 是參數(shù)拔莱，它的值會(huì)被 e1~en 替換，e 是函數(shù)體表達(dá)式
((lambda (v1 ... vn) e) e1 ... en)
- 說(shuō)明：lambda 用于定義匿名函數(shù)隘竭，注意匿名函數(shù)是會(huì)立即執(zhí)行的塘秦。
(v1 ... vn) 是參數(shù)，e 是函數(shù)體表達(dá)式动看，e1 ... en 的對(duì)應(yīng)參數(shù)的值尊剔。
在計(jì)算 e 表達(dá)式時(shí)，參數(shù)會(huì)被替換為具體的值菱皆，也就是 v1 = e1须误，...，vn = en仇轻。
- 舉例：
比如下面這個(gè)函數(shù)：參數(shù)為 x京痢，函數(shù)體為 (car x)，傳入?yún)?shù)值為 (c a b)篷店。
// 結(jié)果 c
((lambda (x) (car x)) (c a b))
將參數(shù)值 (c a b) 帶入 x祭椰，那么最終計(jì)算的表達(dá)式為：(car (c a b))，結(jié)果為 c疲陕。
defun
- 定義：
// v1~vn 是參數(shù)方淤，e 是函數(shù)體表達(dá)式
(defun test(v1 ... vn) e)
- 說(shuō)明：表示方法定義，跟
lambda很類似蹄殃。只不過(guò)它有方法名臣淤，需主動(dòng)調(diào)用。 - 舉例：
定義 test 方法窃爷，帶有一個(gè)參數(shù) x：
(defun test (x) (car x))
調(diào)用 test 方法邑蒋，傳入 (a b)：
(test (a b))
REPL
全稱是 Read - Evaluate - Print Loop，讀取-計(jì)算-打印循環(huán)按厘。
其模型如下圖所示：
我們將按照這個(gè)模型進(jìn)行實(shí)現(xiàn)医吊，其中最重要的兩步為：
-
Read：讀取輸入的代碼，提取 Token逮京，然后解析為抽象語(yǔ)法樹(shù) AST卿堂。 -
Evaluate：計(jì)算表達(dá)式，返回結(jié)果。
這篇文章草描，我們主要來(lái)介紹 Read 的實(shí)現(xiàn)览绿。
Read 又分為兩步：
-
詞法分析：
Tokenize，也稱之為「Token 化」穗慕。將代碼解析為一個(gè)個(gè)的 Token饿敲，輸出 「Token 列表」。由于 Lisp 中只有三種符號(hào)：
(逛绵、)怀各、字符串（字母+數(shù)字），那么 Token 的取值也很簡(jiǎn)單术浪，只包含這三種瓢对。 語(yǔ)法分析：Parse，將上一步得到的 「Token 列表」進(jìn)行結(jié)構(gòu)化胰苏，輸出 AST硕蛹。
數(shù)據(jù)結(jié)構(gòu)定義
由于 Lisp 代碼就是各種表達(dá)式，而它僅僅只有 atom 和 list 兩種類型硕并，且 list 內(nèi)部可嵌套法焰。那么它的數(shù)據(jù)結(jié)構(gòu)相對(duì)簡(jiǎn)單：
// 表達(dá)式定義
public enum SExpr {
// 原子
case Atom(String)
// 列表，可嵌套
case List([SExpr])
}
Tokenize
識(shí)別輸入代碼鲤孵，將其分割為一個(gè)個(gè)的有效 token。上面我們說(shuō)過(guò)辰如，token 只有三種類型普监，可用枚舉來(lái)進(jìn)行定義。
enum Token {
// 左括號(hào)
case pOpen
// 右括號(hào)
case pClose
// 字符串
case text(String)
}
而解析 token 的過(guò)程琉兜，只需逐個(gè)遍歷每個(gè)字符進(jìn)行處理凯正。
遍歷過(guò)程中，只會(huì)有如下幾種情形：
-
'('豌蟋，此時(shí)添加pOpen到 token 列表廊散。但要注意
(前面還可能存在字符串，比如cons(B C)梧疲，此時(shí)需將字符串cons作為一個(gè)字符串token添加到列表允睹。// "cons(B C)"，當(dāng)遍歷到 ( 時(shí)幌氮，cons 需作為一個(gè) token if tmpText != "" { res.append(.text(tmpText)) tmpText = "" } res.append(.pOpen) -
')'缭受，此時(shí)添加pClose到 token 列表。同樣注意字符串處理该互，比如
(B)米者，當(dāng)遇到)時(shí)，需添加字符串B到列表。// "(B)"蔓搞，遍歷到 )胰丁，B 作為一個(gè) token if tmpText != "" { res.append(.text(tmpText)) tmpText = "" } res.append(.pClose) -
' '，空格是分隔 token 的標(biāo)記喂分，多個(gè)空格只會(huì)被看成一個(gè)锦庸。當(dāng)遇到空格時(shí)，說(shuō)明可能有 token 定義結(jié)束妻顶。這里主要用于處理字符串 token酸员。
// "A B"，遍歷到到 A 后面的空格讳嘱，A 作為一個(gè) token if tmpText != "" { res.append(.text(tmpText)) tmpText = "" } -
其他就是字符了幔嗦，逐個(gè)累加字符。在上面三種情況中沥潭，將其添加到 token 列表邀泉。
tmpText.append(c)
經(jīng)過(guò)這幾種情況的處理，我們可以得到一個(gè) token 列表钝鸽。
舉個(gè)例子："(a b c)"汇恤，得到的 token 列表為：
[.pOpen, .text(a), .text(b), .text(c), .pClose]
Parse
接下來(lái)是進(jìn)行 token 列表的解析，將其結(jié)構(gòu)化為 AST拔恰，其實(shí)也就是轉(zhuǎn)換為上面定義的 SExpr 的結(jié)構(gòu)因谎。
最主要的就是列表左右括號(hào)配對(duì)處理，內(nèi)嵌列表的遞歸處理颜懊。
舉一個(gè)簡(jiǎn)單的例子财岔，比如代碼："(a b c)"，轉(zhuǎn)換為 AST 后河爹，應(yīng)是如下結(jié)構(gòu)：
.List([.Atom(a), .Atom(b), .Atom(c)])
如下圖所示：
再看一個(gè)嵌套的例子匠璧，比如代碼："(a (b c))"，轉(zhuǎn)換為 AST 后咸这，結(jié)構(gòu)如下：
.List([.Atom(a), .List([.Atom(b), .Atom(c)])])
如下圖所示：
那么看起來(lái)規(guī)則挺簡(jiǎn)單的夷恍，遇到 list，將其變?yōu)?.List媳维；遇到 atom酿雪，將其變?yōu)?.Atom。正所謂是侄刽，逢山開(kāi)山执虹，遇水淌水。
總結(jié)一下轉(zhuǎn)換規(guī)則：
- 對(duì)于列表
list唠梨，轉(zhuǎn)換為.List(xx)袋励； - 對(duì)于原子
atom，轉(zhuǎn)換為.Atom(xx)。
那么如何實(shí)現(xiàn)呢茬故？
在遍歷 token 時(shí)盖灸，只有如下三種情形：
當(dāng)遇到
.pOpen，也就是(時(shí)磺芭，說(shuō)明是列表的開(kāi)始赁炎，初始化一個(gè)空列表.List([])作為父節(jié)點(diǎn)，繼續(xù)遞歸處理其后的token列表钾腺。-
當(dāng)遇到
.pClose徙垫，也就是)時(shí)，說(shuō)明是列表的結(jié)束放棒，返回配對(duì)()組成的表達(dá)式姻报。此時(shí)會(huì)回到
.pOpen后續(xù)邏輯的處理，因?yàn)槭?strong>遞歸函數(shù)的返回间螟。將表達(dá)式添加到「當(dāng)前上下文的父節(jié)點(diǎn)」中吴旋，然后繼續(xù)往后遍歷剩余token。 當(dāng)遇到
text時(shí)厢破，轉(zhuǎn)換成.Atom(text)荣瑟，添加到當(dāng)前父節(jié)點(diǎn)即可。
解析過(guò)程如下所示摩泪，其中 parser 表示解析函數(shù)笆焰。
// 入?yún)ⅲ簍oken 列表，父節(jié)點(diǎn)
// 返回參數(shù)：剩余 token 列表见坑，子節(jié)點(diǎn)
parser(tokens, parentNode) -> (remainTokens, node)
舉個(gè)例子嚷掠，比方說(shuō)："(a (b))"，tokenize 之后的結(jié)果為：
[.pOpen, .text(a), .pOpen, .text(b), .pClose]
其解析過(guò)程如下圖所示鳄梅。PS：為了表示方便叠国，圖中直接使用了字符串未檩，而非 token戴尸。
這樣我們就得到了 SExpr 的結(jié)構(gòu)，圖示如下：
到此冤狡，Read 的過(guò)程就結(jié)束啦孙蒙，相關(guān)代碼可查看 github 。
總結(jié)
這篇文章主要介紹了如何通過(guò)詞法分析生成 token 列表悲雳、解析 token 生成 ast挎峦，最終得到 SExpr 的結(jié)構(gòu)。
下一篇文章我們將介紹如何利用 SExpr 結(jié)構(gòu)進(jìn)行計(jì)算合瓢，也就是 evaluation 的過(guò)程坦胶，敬請(qǐng)期待~
