本文有兩個(gè)目的: 一是講述實(shí)現(xiàn)計(jì)算機(jī)語(yǔ)言解釋器的通用方法，另外一點(diǎn)，著重展示如何使用Python來(lái)實(shí)現(xiàn)Lisp方言Scheme的一個(gè)子集。我將我的解釋器稱(chēng)之為L(zhǎng)ispy (lis.py)。幾年前，我介紹過(guò)如何使用Java編寫(xiě)一個(gè)Scheme解釋器，同時(shí)我還使用Common Lisp語(yǔ)言編寫(xiě)過(guò)一個(gè)版本。這一次，我的目的是盡可能簡(jiǎn)單明了地演示一下Alan Kay所說(shuō)的“軟件的麥克斯韋方程組” (Maxwell's Equations of Software)。

Lispy支持的Scheme子集的語(yǔ)法和語(yǔ)義

大多數(shù)計(jì)算機(jī)語(yǔ)言都有許多語(yǔ)法規(guī)約 (例如關(guān)鍵字、中綴操作符、括號(hào)、操作符優(yōu)先級(jí)、點(diǎn)標(biāo)記、分號(hào)等等)，但是，作為L(zhǎng)isp語(yǔ)言家族中的一員，Scheme所有的語(yǔ)法都是基于包含在括號(hào)中的、采用前綴表示的列表的。這種表示看起來(lái)似乎有些陌生，但是它具有簡(jiǎn)單一致的優(yōu)點(diǎn)。 (一些人戲稱(chēng)”Lisp”是”Lots of Irritating Silly Parentheses“——“大量惱人、愚蠢的括號(hào)“——的縮寫(xiě)；我認(rèn)為它是”Lisp Is Syntactically Pure“——“Lisp語(yǔ)法純粹”的縮寫(xiě)。) 考慮下面這個(gè)例子：
 

/* Java */if(x.val() > 0) { z = f(a*x.val() + b);}/* Scheme */(if (> (val x) 0) (set! z (f (+ (* a (val x)) b))))

注意上面的驚嘆號(hào)在Scheme中并不是一個(gè)特殊字符；它只是”set!“這個(gè)名字的一部分。(在Scheme中)只有括號(hào)是特殊字符。類(lèi)似于(set! x y)這樣以特殊關(guān)鍵字開(kāi)頭的列表在Scheme中被稱(chēng)為一個(gè)特殊形式 (special form)；Scheme的優(yōu)美之處就在于我們只需要六種特殊形式，以及另外的三種語(yǔ)法構(gòu)造——變量、常量和過(guò)程調(diào)用。

在該表中，var必須是一個(gè)符號(hào)——一個(gè)類(lèi)似于x或者square這樣的標(biāo)識(shí)符——number必須是一個(gè)整型或者浮點(diǎn)型數(shù)字，其余用斜體標(biāo)識(shí)的單詞可以是任何表達(dá)式。exp…表示exp的0次或者多次重復(fù)。

更多關(guān)于Scheme的內(nèi)容，可以參考一些優(yōu)秀的書(shū)籍 (如Friedman和Fellesein, Dybvig,Queinnec, Harvey和Wright或者Sussman和Abelson)、視頻 (Abelson和Sussman)、教程 (Dorai、PLT或者Neller)、或者參考手冊(cè)。

語(yǔ)言解釋器的職責(zé)
一個(gè)語(yǔ)言解釋器包括兩部分：

1、解析 (Parsing)：解析部分接受一個(gè)使用字符序列表示的輸入程序，根據(jù)語(yǔ)言的語(yǔ)法規(guī)則對(duì)輸入程序進(jìn)行驗(yàn)證，然后將程序翻譯成一種中間表示。在一個(gè)簡(jiǎn)單的解釋器中，中間表示是一種樹(shù)結(jié)構(gòu)，緊密地反映了源程序中語(yǔ)句或表達(dá)式的嵌套結(jié)構(gòu)。在一種稱(chēng)為編譯器的語(yǔ)言翻譯器中，內(nèi)部表示是一系列可以直接由計(jì)算機(jī) (作者的原意是想說(shuō)運(yùn)行時(shí)系統(tǒng)——譯者注) 執(zhí)行的指令。正如Steve Yegge所說(shuō)，“如果你不明白編譯器的工作方式，那么你不會(huì)明白計(jì)算機(jī)的工作方式。”Yegge介紹了編譯器可以解決的8種問(wèn)題 (或者解釋器，又或者采用Yegge的典型的反諷式的解決方案)。 Lispy的解析器由parse函數(shù)實(shí)現(xiàn)。