聲明

為提高教學(xué)質(zhì)量，我所在的學(xué)院正在籌劃編寫C語(yǔ)言教材?！?a target="_blank">用C語(yǔ)言寫解釋器》系列文章經(jīng)整理后將收入書(shū)中“綜合實(shí)驗(yàn)”一章。因此該系列的文章主要閱讀對(duì)象定為剛學(xué)完C語(yǔ)言的學(xué)生（不要求有數(shù)據(jù)結(jié)構(gòu)等其它知識(shí)），所以行文比較羅嗦，請(qǐng)勿見(jiàn)怪。本人水平有限，如有描寫敘述不恰當(dāng)或錯(cuò)誤之處請(qǐng)指教！特此聲明。

起因

近期，我們學(xué)院老師聯(lián)系我，希望我能提供一段用 C 語(yǔ)言編寫的 BASIC 解釋器，用于 C 語(yǔ)言課程設(shè)計(jì)教學(xué)。我前段時(shí)間也正好著迷于“語(yǔ)言”本身，本就有打算寫一個(gè)解釋器，這下正中我下懷，于是欣然接受。

曾經(jīng)在圖書(shū)館看過(guò)梁肇新的《編程高手箴言》，第四章“編程語(yǔ)言的運(yùn)行機(jī)理”中就包括了一段 C 語(yǔ)言編寫的 BASIC 解釋器代碼，但代碼好像并不完整（我翻了好幾遍，都沒(méi)發(fā)現(xiàn)函數(shù) get_token 的實(shí)現(xiàn)代碼）；再者，這次的代碼還有其它用處，不宜牽涉版權(quán)問(wèn)題；最后的原因是我有“想自己編碼”的沖動(dòng) ^_^。綜上所述，我要從零開(kāi)始用 C 語(yǔ)言來(lái)編寫一個(gè) BASIC 解釋器。

前置知識(shí)

1. 要編寫解釋器，首先就要明確什么是解釋器（具體的解釋請(qǐng)參看維基百科：http://zh./zh-cn/解釋器）。盜用《編程高手箴言》里的話：解釋程序就是一個(gè)字符串的解釋器（P165 解釋語(yǔ)言的原理）。所以，假設(shè)僅僅是為我個(gè)人編寫的話，我寧可會(huì)借助 lex & yacc 甚至 perl，而不會(huì)純粹用 C 語(yǔ)言來(lái)寫。

2. 在起因中已經(jīng)提過(guò)，這個(gè)程序會(huì)在學(xué)弟學(xué)妹們學(xué)完 C 語(yǔ)言后作為綜合實(shí)驗(yàn)。因此須要你熟悉 C 語(yǔ)言的語(yǔ)法、單鏈表加入/刪除節(jié)點(diǎn)等操作以及棧的概念（這些內(nèi)容大部分都能在 C 語(yǔ)言的教材中找到），一些相對(duì)冷僻的技術(shù)（比如 setjmp/longjmp）則不會(huì)出如今程序中。

關(guān)于語(yǔ)言

我在《編程和語(yǔ)言之我見(jiàn)》一文中提過(guò)，編程是一個(gè)非常寬泛的概念。從某種意義上來(lái)說(shuō)全部的軟件都是一種特定的語(yǔ)言，但依據(jù)程序本身的靈活性能夠分為“硬編碼”、“可配置”、“可控制”和“可編程”四類（詳見(jiàn)《四類程序》）。假設(shè)一個(gè)程序的靈活性達(dá)到了“可編程”，它的配置文件就能夠被看作一種“編程語(yǔ)言”，而該程序本身也就是一個(gè)“解釋器”。

要做到“可編程”，程序至少應(yīng)該具備“輸入/輸出”、“表達(dá)式運(yùn)算”、“內(nèi)存管理”和“按條件跳轉(zhuǎn)”四個(gè)功能（詳見(jiàn)《用DOS批處理來(lái)做數(shù)字圖像處理》）。這正好相應(yīng)了馮·諾依曼計(jì)算機(jī)的結(jié)構(gòu)：以運(yùn)算器和控制器為中心，輸入/輸出設(shè)備與存儲(chǔ)器之間的傳輸數(shù)據(jù)都要經(jīng)過(guò)運(yùn)算器。以下具體介紹各個(gè)部分。

我們的目標(biāo)

我們要編寫解釋器，自然也逃不出上面的條條例例。語(yǔ)法就參考 BASIC，但由于是設(shè)計(jì)我們自己的語(yǔ)言，當(dāng)然能夠依據(jù)個(gè)人興趣進(jìn)行“添油加醋”（比方表達(dá)式里提供神往已久的階乘運(yùn)算 ^_^）。以下是一段 BASIC 的演示樣例代碼（example.bas）：

0009 N = 0
0010 WHILE N < 1 OR N > 20
0011   PRINT "請(qǐng)輸入一個(gè)1-20之間的數(shù)"
0012   INPUT N
0013 WEND
0020 FOR I = 1 TO N
0030   L = "*"
0040   FOR J = 1 TO N - I
0050     L = " " + L
0060   NEXT
0070   FOR J = 2 TO 2 * I - 1 STEP 2
0080     L = L + "**"
0090   NEXT
0100   PRINT L
0110 NEXT
0120 I = N - 1
0130 L = ""
0140 FOR J = 1 TO N - I
0150   L = L + " "
0160 NEXT
0170 FOR J = 1 TO ((2*I) - 1)
0180   L = L + "*"
0190 NEXT
0200 PRINT L
0210 I = I - 1
0220 IF I > 0 THEN
0230   GOTO 130
0240 ELSE
0250   PRINT "By redraiment"
0260 END IF

BASIC 語(yǔ)法要求行首提供一個(gè) 1->9999 之間的數(shù)字作為該行的行號(hào)（當(dāng)前行的行號(hào)不小于上一行的行號(hào)），供 GOTO 語(yǔ)句跳轉(zhuǎn)時(shí)調(diào)用。BASIC 的語(yǔ)法比 C 嚴(yán)格，這不僅能夠減少代碼的復(fù)雜性還使語(yǔ)言本身更易學(xué)。上面的代碼差點(diǎn)兒相同涵蓋了我們須要實(shí)現(xiàn)的全部功能，假設(shè)能被正確解析，你將看到以下的運(yùn)行效果：

以下來(lái)依次討論要實(shí)現(xiàn)的功能。

輸入/輸出（IO）

通過(guò)輸入/輸出來(lái)和外部程序或人交互，這是脫離“硬編碼”的最基本要求。輸入/輸出也是非常抽象的概念，它并不局限于標(biāo)準(zhǔn)輸入輸出端（鍵盤、顯示器等），也能夠通過(guò)文件、互聯(lián)網(wǎng)等方式獲得數(shù)據(jù)（因此 C 語(yǔ)言中除了 scanf、printf 等，事實(shí)上 #include 指令也算是一種 IO 操作）。我們這個(gè)程序并不強(qiáng)調(diào) IO，因此僅僅要求實(shí)現(xiàn) INPUT 和 PRINT 兩條指令，分別用于從鍵盤輸入數(shù)據(jù)和打印到屏幕。指令的格式例如以下：

INPUT var[, var ...]
　　當(dāng)中 var 代表變量名(下同)，變量之間用逗號(hào)隔開(kāi)。
　　作用：從鍵盤獲得一個(gè)或多個(gè)值，并賦值到相應(yīng)的變量。同一時(shí)候輸入多個(gè)變量時(shí)，輸入的每一個(gè)數(shù)之間用空格、回車或制表符隔開(kāi)。
　　比如：INPUT A, B, C
PRINT expression[, expression ...]
　　當(dāng)中 expression 為表達(dá)式（下同），表達(dá)式之間用逗號(hào)隔開(kāi)。
　　作用：對(duì)表達(dá)式求值，將結(jié)果輸出到屏幕并換行。假設(shè)有多個(gè)表達(dá)式，表達(dá)式之間用制表符（/t）隔開(kāi)。
　　比如：PRINT I * 3 + 1, (A + B)*(C + D)

表達(dá)式運(yùn)算

在《DOS》中我稱呼它為“算術(shù)運(yùn)算”。但對(duì)于計(jì)算機(jī)來(lái)說(shuō)，“算術(shù)運(yùn)算”不僅包括諸如“四則運(yùn)算”等算術(shù)運(yùn)算，還包括“關(guān)系運(yùn)算”和“邏輯運(yùn)算”。為了避免歧義，在此就改稱它為“表達(dá)式運(yùn)算”。“表達(dá)式運(yùn)算”是整個(gè)程序的核心，地位相當(dāng)于計(jì)算機(jī)的運(yùn)算器。在我們的程序中，須要實(shí)現(xiàn)以下幾種運(yùn)算符：

內(nèi)存管理

在我們這個(gè)迷你型的解釋器中，能夠不用考慮內(nèi)存空間動(dòng)態(tài)分配的問(wèn)題，僅僅要實(shí)現(xiàn)簡(jiǎn)單的變量管理。我們默認(rèn)提供 A-Z 26個(gè)可用的弱類型變量（能夠任意賦值為整數(shù)、浮點(diǎn)數(shù)或字符串）。變量要求先賦值才干使用，否則就會(huì)提示變量不可用（因此演示樣例代碼中第一行就是給 N 賦值為 0）。賦值語(yǔ)句的格式為

[LET] var = expression
　　當(dāng)中 LET 是可選的keyword。BASIC 中不同意出現(xiàn) var1 = var2 = expression 這種賦值語(yǔ)句，
　　由于在表達(dá)式中“=”被翻譯為“等于”，所以賦值符合沒(méi)有出如今上面的表格中。
　　作用：計(jì)算表達(dá)式的值，并將結(jié)果賦值給變量 var。
　　比如：I = (123 + 456) * 0.09

按條件跳轉(zhuǎn)

假設(shè)設(shè)計(jì)一門最簡(jiǎn)潔的語(yǔ)言，那它的控制語(yǔ)句就僅僅需提供像匯編中的 JMP、JNZ 等依據(jù)條件跳轉(zhuǎn)的語(yǔ)句就可以，通過(guò)它們的組合就可以模擬出 IF、WHILE、FOR、GOTO 等控制語(yǔ)句。但 BASIC 作為一門高級(jí)語(yǔ)言，須要提供更高層、更抽象的語(yǔ)句。我們將會(huì)實(shí)現(xiàn)以下四條語(yǔ)句：

1)
GOTO expression
　　當(dāng)中 expression 是一個(gè)數(shù)值表達(dá)式，計(jì)算結(jié)果必須為可用的行號(hào)。由于它是一個(gè)表達(dá)式，通過(guò)動(dòng)態(tài)計(jì)算就能模擬子程序調(diào)用。
　　作用：無(wú)條件跳轉(zhuǎn)到指定行。
　　比如：GOTO 120+10
2)
IF expression THEN
  sentence1
[ELSE
  sentence2]
END IF
　　當(dāng)中 sentence 是語(yǔ)句塊（下同），包括一條或多條可運(yùn)行語(yǔ)句。ELSE 為可選部分。
　　作用：分支結(jié)構(gòu)。但表達(dá)式值為真（數(shù)字不等于0或者字符串不為空）時(shí)運(yùn)行語(yǔ)句塊1；否則，有 ELSE 語(yǔ)句塊時(shí)運(yùn)行 ELSE 語(yǔ)句塊。
　　比如：
        IF 1=1 THEN
           PRINT "TRUE"
        ELSE
           PRINT "FALSE"
        END IF
3)
FOR var = expression TO expression [STEP expression]
  sentence
NEXT
　　全部表達(dá)式均為數(shù)值表達(dá)式。STEP 為可選部分，為迭代器的步長(zhǎng)。步長(zhǎng)表達(dá)式的值不同意為 0。
　　作用：循環(huán)迭代結(jié)構(gòu)
　　比如：
        FOR I = 1 TO 10 STEP 3
          PRINT I
        NEXT
4)
WHILE expression
  sentence
WEND
　　作用：迭代運(yùn)行語(yǔ)句塊，直到表達(dá)式的值為假。
　　比如：
        WHILE N < 10
          N = N + 1
        WEND

很多其它細(xì)節(jié)

1. BASIC 的源代碼不區(qū)分大寫和小寫；

2. 本程序在實(shí)現(xiàn)中沒(méi)有處理字符轉(zhuǎn)義，因此無(wú)法無(wú)法輸出雙引號(hào)。在介紹全然部源代碼后，假設(shè)你有興趣能夠嘗試自行完好；

3. 本程序相同沒(méi)有考慮凝視（REM keyword）。事實(shí)上這非常easy，但這個(gè)問(wèn)題相同留給你來(lái)處理 ^_^；

4. 或許你也會(huì)有興趣加入 GOSUB 和 RETURN keyword，讓子程序功能從 GOTO 中解放出來(lái)。

總結(jié)

這一篇主要介紹了我們編寫的解釋器要實(shí)現(xiàn)的功能，接下來(lái)會(huì)有一系列文章來(lái)逐步具體介紹解釋器的實(shí)現(xiàn)。在下一篇中會(huì)首先介紹解釋器的核心部分——表達(dá)式求值。請(qǐng)關(guān)注《用C語(yǔ)言寫解釋器（二）》。

版權(quán)聲明

請(qǐng)尊重原創(chuàng)作品。轉(zhuǎn)載請(qǐng)保持文章完整性，并以超鏈接形式注明原始作者“redraiment”和主網(wǎng)站地址，方便其它朋友提問(wèn)和指正。