說點閑話
工作已經(jīng)五年了素挽，自己從c++到php python的過程中，一直都是往高級編程語言的路子走著狸驳。學得越深预明，未知的越多，很多事務如今卻覺得知其然不知所以然锌历≈樱回想大學課程里的編譯原理，詞法分析究西、句法分析窗慎，計算機底程的東西一直覺得很難。以致于在算法設計卤材、架構(gòu)設計等高難度點的工作上就有點力不從心遮斥。我們一直都在學習的路上，卻更多時候是在重復的路上扇丛。千萬行代碼术吗，重復的比例自己心知肚明。曾以為自己很懂計算機帆精，卻連編譯较屿、解釋原理都沒深刻掌握隧魄。 于是，馬上動手準備出一個『閑來沒事』系列隘蝎，第一個出品的是代碼解釋器购啄。接下來可能是各種形態(tài)的代碼解釋器，各種形態(tài)的編譯器嘱么，然后算法等等狮含。涉及的語言不限，更新時間不限曼振，我會盡我所能几迄，還有網(wǎng)友們的意見。然后冰评，雖然都是些娛樂性的小項目映胁，僅供自己和大伙學習，但也會把項目代碼發(fā)布的GitHub上。這次的玩具是pyScheme
文章首發(fā)我的博客: 老白經(jīng)
什么是代碼解釋器
我們寫的代碼要在計算機中執(zhí)行，都需要翻譯成機器語言才能被計算機懂得去執(zhí)行厕氨。教程上對于編譯器和解釋器的明確定義及區(qū)別都很詳細抛蚁，只是能不能被讀者理解是另外一回事。我從來不喜歡羞澀難懂的定義，喜歡活潑明了的比喻。
老公老婆是兩個不同國家的人，老公只會阿拉伯語言娱据，老婆只會韓語。老公要怎么跟老婆講話盅惜？請一個中間人中剩。中間人有兩種，一種解釋型的抒寂，我們稱為解釋人结啼；一種編譯型的，我們稱為編譯人屈芜。
老公要逗老婆郊愧，說一段笑話給她聽，這時候解釋人和編譯人的處理方式不一樣井佑。
老公說完笑話属铁，解釋人就把口譯給老婆聽，老婆很開心躬翁。老婆還想再聽一次那個笑話焦蘑，老公再講一次，解釋人又要再口譯一次盒发。累例嘱！
編譯人聽完笑話狡逢，把翻譯結(jié)果用錄音機錄下來，給她老婆拼卵。老婆還想聽那個笑話的時候甚侣，聽錄音就好了。如果老公的笑話一直不換间学，顯然編譯人的做法是更有效率的。
OK印荔，所謂解釋和編譯就是有沒有錄音機的區(qū)別低葫。我們講的解釋器就是沒有錄音機的解釋人，它要把我們的話解釋給計算機聽仍律，即使我們說的話一樣的嘿悬，也還需要它解釋一次。
常見的編譯型語言有C水泉、C++善涨、Pascal等。 常見的解釋型語言有PHP草则、Python钢拧、JavaScript等。
詞法分析最簡單的語言 Scheme
這是本文的主角炕横，Scheme是Lisp語言的一個重要分支源内，它是極簡主義哲學在編譯語言里面的極品。Lisp的設計初衷是用來進行學校內(nèi)教學的份殿，誰知道會火膜钓。廢話少點... 當然我沒精力把Scheme所有的語法、功能都實現(xiàn)了卿嘲，都實現(xiàn)了你們也沒精力看吧颂斜。好吧，學習就應該從小麻雀開始拾枣，雖小五臟俱全沃疮。解釋型語言的步驟：詞法分析、句法分析梅肤、執(zhí)行忿磅。真的只有三步，一個解釋型語言很簡單的凭语。
我們繼續(xù)看我們的項目葱她，初學者別太難，所以我們雖然也是三步似扔，卻是：簡單詞法分析吨些、簡單句法分析搓谆、簡單執(zhí)行。簡單的錯誤提示和錯誤處理豪墅，簡單的類型泉手，簡單的操作。我希望我的文章和代碼會顯示簡單偶器，好明白斩萌。
我們的解釋器
上節(jié)講到Scheme，是的屏轰，我們要寫一個Scheme語言的解釋器颊郎，只是不會得Scheme那么強大，那沒有意義霎苗，我們的目的是學習怎么寫一個解釋器姆吭。
首先，明確我們的可以寫怎么樣的代碼唁盏。寫怎么樣的代碼是一個代碼設計人做的事情内狸，其中水是非常深的，比如有沒有Class厘擂、支持什么Types昆淡、怎么定義變量、怎么定義函數(shù)等刽严，你想得越復雜這個解釋器(編譯器)的詞法瘪撇、句法分析就越復雜。當然港庄，我是個挑軟柿子捏的人倔既，Scheme的詞法和句法法分析是最簡單的，所以我才拿它當例子鹏氧。我們來假設以下是一個解釋器的輸入輸出過程渤涌。>>代表輸入，<<代表輸出把还。
>> 3 ; 常量3
<< 3
>> (def a 5) ; 定義變量a
<< 5
>> a ; 變量a
<< 5
>> (+ a a 3) ; 基本運算 a+a+3
<< 13
>> (- a 1 2 3) ; 基本去處 a- 1-2-3
>> (and 0 2 3 4) ; 邏輯操作 1 and 2 and 3 and 4
<< False
>> (def mul (func (x y) (* x y))) ; 自定義乘法函數(shù): mul
<< (func (x y) (* x y))
>> (mul 7 5) ; 使用自定義函數(shù)mul
<< 35
>> (def mul7 (mul 7)) ; 自定義高階函數(shù)mul7
<< (func (x y) (* x y))
>> (mul7 5) ; 使用高階函數(shù)mul7
<< 35
>> (def alist (list 1 2 3 4)) ; 定義列表
<< (list 1 2 3 4)
先這樣子吧实蓬，已經(jīng)夠復雜了，復雜都是有簡單堆砌起來的吊履。我們來開始吧安皱！確定完語法，我們就可以進行分析和實現(xiàn)艇炎。語言不重要酌伊，重要的是你用你的思考把它實現(xiàn)了！我偏愛Python缀踪，所以就用Python居砖。當然虹脯，使用不同的語言的實現(xiàn)復雜度也不一樣，所需要的代碼量也不一樣奏候。我盡量偏理論一些循集，然后各位看觀可以用自己熟悉的語言來實現(xiàn)。然后分享出來蔗草，這是個有趣的過程咒彤。
這里我會實現(xiàn)一些簡單的概念：函數(shù)、列表咒精、作用域镶柱。不會實現(xiàn)變量類型，只支持數(shù)值運算狠轻，不支持字符串等。能簡化的都簡化掉彬犯。
我們進入一下章節(jié)向楼！
詞法分析
上節(jié)讓大家了解了一下Scheme語法，可能大家會說谐区，這語法太復雜了湖蜕，看不懂，比神馬語言的語法都復雜宋列，然后就開始賣樓主了昭抒。別急，它的語法就是這樣的一個格式(不用范式炼杖，太難理解了灭返！) (操作符/函數(shù)名等 參數(shù)1 參數(shù)2 參數(shù)3 ...) 操作符/函數(shù)名和參數(shù)都可以是上面的格式，你想多復雜就多寫幾個括號內(nèi)的東西坤邪。 例：
((func (x y z) (* x y z)) (def a 4) (def b (+ a 6)) (+ a b 9))
換成熟悉的語法大概如下
function afun(x, y, z) { return x*y*z}
var a = 4, b = a + 6
afun(a, b, a+b+9)
// 輸出920
懂了么熙含，不懂好好理解一下再往下看。 這樣看起來復雜的語法卻是語法分析中最簡單的艇纺。為什么呢怎静，因為它最接近語法樹的語法。也就是所謂的句法分析黔衡！
看下圖蚓聘，為什么語法樹這樣子的，因為我們拿到一個語句盟劫，要先知道是什么函數(shù)夜牡、什么操作符，然后才知道它需要多少個參數(shù)侣签。所以語法樹都是操作符在前氯材，參數(shù)在后渣锦。 我們舉的栗子是：
(def x (if (> a 1) a 1))
以上語法樹讓我很直觀的明白，我們要怎么去處理那復雜的代碼氢哮，而且scheme語法的括號讓我們無需去處理運算符的優(yōu)先順序袋毙，什么先乘除后加減，這里沒這玩意冗尤，想辦法把括號里的值求出來就好了听盖！
好的，看著這棵樹裂七，我們就想到遞歸皆看，遇到父結(jié)點就調(diào)用遞歸函數(shù)求值。好像好簡單啊背零，的確腰吟，問題就是這么簡單。然后想想怎么把作用域加進來徙瓶？操毛雇，好復雜！
哈侦镇，差不多分析完成灵疮！我們來想辦法完成吧！
一步一步寫解釋器
我盡量寫偽代碼壳繁，實際Python代碼到GitHub去看吧震捣。
詞法分析
詞法分析的目的是把代碼中所有的元素找出來，并按順序存好闹炉。元素包括函數(shù)蒿赢、運算符、操作符渣触、函數(shù)名诉植、變量名、數(shù)值等昵观。去掉寫代碼執(zhí)行無關的東西：如換行晾腔、空格、注釋(pyScheme沒考慮它)等啊犬。scheme語法灼擂，空格是關鍵。按空格切開字符串就可以找到所有元素了觉至。"(",")"前后是沒有空格的剔应，怎么辦，那就創(chuàng)造出空格來。
定義 詞法分析-tokenize(code)
list = code.replace("(", " ( ").replace(")", " ) ").split([" ","\n", "\t", "\r"])
ret_list = []
for i = 0; i < list.length; i++
if list[i].length > 0 then ret_list.append(list[i])
return ret_list
于是峻贮，運行"tokenize('(def x (if (> a 1) a 1))')"的結(jié)果是 ['(', 'def', 'x', '(', 'if', '(', '>', 'a', '1', ')', 'a', '1', ')', ')']席怪。 很簡單的完成了。
句法分析
句法分析的目的就是把詞法分析的結(jié)果變成語法樹纤控，然后程序根據(jù)語法樹去遍歷執(zhí)行挂捻。先不忙著定義句法分析函數(shù)，先想想這個語法樹怎么來實現(xiàn)船万。這個Node在代碼里叫SExpression
Struct 語法樹結(jié)點-Node
var value = ''
var parent = None
var children[]
定義 句法分析-parse(tokens)
var program = new Node()
var current = program
for i=0; i<tokens.length; i++
switch(tokens[i])
case '(':
var newNode = new Node()
newNode.value = '('
newNode.parent = current
current = newNode
case ')':
current = current.parent
default:
var newNode = new Node()
newNode.value = tokens[i]
newNode.parent = current
current.child.append(newNode)
return program.children[0]
OK, 句法分析也夠簡單的刻撒，謝謝scheme，如果是C++體系的語法耿导，寫三天代碼估計還有很大的bug声怔。anyway, 恭喜你，進入男生權利：擼一局舱呻！好吧醋火，順道做個廣告，鄙人在艾歐尼亞叫轉(zhuǎn)坑艾歐尼亞箱吕，挺坑的不怕死的加我芥驳。
執(zhí)行
句法分析完就可以執(zhí)行了，執(zhí)行過程中需要存儲一些過程變量殖氏，如自定義變量晚树、自定義函數(shù)等姻采。我們引入一個作用域的概念雅采。我們把它設計成一個單向鏈表，當前在末端慨亲，如果找不到就向上搜索婚瓜，直到根本，如果找不到就不存在了刑棵。
Struct 作用域-Scope:
var parent = None
var vars = {} //這是一個字典
Scope(parent) // 構(gòu)造函數(shù)巴刻，你的語言體系中沒有這個的話，就多寫幾行代碼吧
this.parent = parent
定義 找變量-find(scope, name)
current = scope
while current != null:
if is_exist(current[name])
return current[name]
current = current.parent
return null
OK有這個概念后蛉签，我們進入執(zhí)行的實現(xiàn)胡陪。
定義 求值-evaluate(expression, scope):
if expression.children.length <= 0
// 不是數(shù)值就是變量
if tryParse2Float(expression.value)
return tryParse2Float(expression.value)
return scope.find(name)
first = expression.children[0]
if first.value = '(':
// 遞歸的節(jié)奏啊
func = evaluate(first, new Scope(scope))
arguments = []
for i = 1; i < self.children.length;i++
argument.append(evaluate(self.children[i], scope))
return evaluate(func, scope)
// 內(nèi)置函數(shù)
// 這個解釋器好像沒什么功能啊，強大的功能都是在內(nèi)置函數(shù)里了碍舍。
// 我們設置一個全局變量柠座，就叫builtInFuncs吧, evluate
if is_exist(builtInFuncs[first.value])
return execute(builtInFuncs[first.value], self.childrens, scope)
OK，強大的語法樹求值片橡，搞定了妈经。善后善一下。
// 我們定義一個函數(shù)原型
定義 function (args, scope) {}
定義 執(zhí)行函數(shù)-execute(function, arguments, scope)
return evaluate(function, arguments, scope)
PS：寫到這里的時候，為了減少(mul7 5) = 35這個高階函數(shù)給大家?guī)淼睦斫饫щy吹泡，所以突然想簡化成不支持此類高階函數(shù)骤星。但是，思路有點混亂爆哑，感覺怪怪的洞难，卻還看不出哪里不對，先這樣子吧泪漂，想到了再發(fā)廊营。
OK：真的結(jié)束了么？還差一點萝勤，說好的內(nèi)置函數(shù)庫來了露筒。
內(nèi)置函數(shù)庫
前面，那么多功夫敌卓，都是沒有結(jié)果慎式，直接推出會被人扔火雞蛋的。操趟径，這是解釋器框架瘪吏，懂嗎？仍然有人表示不理解蜗巧。我也不廢話掌眠，先來定義個加法吧。 回顧一下加法的語法
（+ 1 2 3 4 5 6）
builtInFuncs["+"] = function(args, scope) {
var ret = 0
for i = 1; i < args.length; i++
ret += evaluate(args[i], scope)
return ret
}
builtInFuncs["if"] = function(args, scope) {
if evaluate(args[1], scope):
return evaluate(args[2])
else
return evaluate(args[3])
}
其他的操作幕屹，大家花飛自己的想像和碼代碼的能力自己添加蓝丙，實在搞不定吧，就看我的代碼吧望拖。還是有問題渺尘，而且代碼不是python，煩請你建一個gist或github倉庫说敏，把代碼鏈接發(fā)給我看看吧鸥跟。
最后怎么玩
main ()
var code
var scope = new Scope()
while(true)
cout<< "pySch>> "
cin>> code
if code and code != "quit"
cout<< "pySch>> "<< evaluate(parse(tokenize(code)), scope)
if code == 'quit'
break
寫在最后
好了，串完了盔沫。寫代碼容易医咨，碼字難，好像沒寫長文了架诞，保持這個沖勁拟淮，繼續(xù)加油～ 老感覺代碼寫不好就算了，文章也寫不好侈贷。 算了～
