用C語言寫解釋器（一）——我們的目標

聲明

為提高教學質量，我所在的學院正在籌劃編寫C語言教材。《用C語言寫解釋器》系列文章經整理后將收入書中“綜合實驗”一章。因此該系列的文章主要閱讀對象定為剛學完C語言的學生（不要求有數據結構等其它知識），所以行文比較羅嗦，請勿見怪。本人水平有限，如有描寫敘述不恰當或錯誤之處請指教！特此聲明。

起因

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

曾經在圖書館看過梁肇新的《編程高手箴言》，第四章“編程語言的運行機理”中就包括了一段 C 語言編寫的 BASIC 解釋器代碼，但代碼好像并不完整（我翻了好幾遍，都沒發現函數 get_token 的實現代碼）；再者，這次的代碼還有其它用處，不宜牽涉版權問題；最后的原因是我有“想自己編碼”的沖動 ^_^。綜上所述，我要從零開始用 C 語言來編寫一個 BASIC 解釋器。

前置知識

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

2. 在起因中已經提過，這個程序會在學弟學妹們學完 C 語言后作為綜合實驗。因此須要你熟悉 C 語言的語法、單鏈表加入/刪除節點等操作以及棧的概念（這些內容大部分都能在 C 語言的教材中找到），一些相對冷僻的技術（比如 setjmp/longjmp）則不會出如今程序中。

關于語言

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

要做到“可編程”，程序至少應該具備“輸入/輸出”、“表達式運算”、“內存管理”和“按條件跳轉”四個功能（詳見《用DOS批處理來做數字圖像處理》）。這正好相應了馮·諾依曼計算機的結構：以運算器和控制器為中心，輸入/輸出設備與存儲器之間的傳輸數據都要經過運算器。以下具體介紹各個部分。

我們的目標

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

0009 N = 0
0010 WHILE N < 1 OR N > 20
0011   PRINT "請輸入一個1-20之間的數"
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 語法要求行首提供一個 1->9999 之間的數字作為該行的行號（當前行的行號不小于上一行的行號），供 GOTO 語句跳轉時調用。BASIC 的語法比 C 嚴格，這不僅能夠減少代碼的復雜性還使語言本身更易學。上面的代碼差點兒相同涵蓋了我們須要實現的全部功能，假設能被正確解析，你將看到以下的運行效果：

以下來依次討論要實現的功能。

輸入/輸出（IO）

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

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

表達式運算

在《DOS》中我稱呼它為“算術運算”。但對于計算機來說，“算術運算”不僅包括諸如“四則運算”等算術運算，還包括“關系運算”和“邏輯運算”。為了避免歧義，在此就改稱它為“表達式運算”。“表達式運算”是整個程序的核心，地位相當于計算機的運算器。在我們的程序中，須要實現以下幾種運算符：

符號	名稱	優先級	結合性
(	左括號	17	left2right
)	右邊	17	left2right
+	加	12	left2right
-	減	12	left2right
*	乘	13	left2right
/	除	13	left2right
%	取模	13	left2right
^	求冪	14	left2right
+	正號	16	right2left
-	負號	16	right2left
!	階乘	16	left2right
>	大于	10	left2right
<	小于	10	left2right
=	等于	9	left2right
<>	不等于	9	left2right
<=	不大于	10	left2right
>=	不小于	10	left2right
AND	邏輯與	5	left2right
OR	邏輯或	4	left2right
NOT	邏輯非	15	right2left

內存管理

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

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

按條件跳轉

假設設計一門最簡潔的語言，那它的控制語句就僅僅需提供像匯編中的 JMP、JNZ 等依據條件跳轉的語句就可以，通過它們的組合就可以模擬出 IF、WHILE、FOR、GOTO 等控制語句。但 BASIC 作為一門高級語言，須要提供更高層、更抽象的語句。我們將會實現以下四條語句：

1)
GOTO expression當中 expression 是一個數值表達式，計算結果必須為可用的行號。由于它是一個表達式，通過動態計算就能模擬子程序調用。作用：無條件跳轉到指定行。比如：GOTO 120+10
2)
IF expression THENsentence1
[ELSEsentence2]
END IF當中 sentence 是語句塊（下同），包括一條或多條可運行語句。ELSE 為可選部分。作用：分支結構。但表達式值為真（數字不等于0或者字符串不為空）時運行語句塊1；否則，有 ELSE 語句塊時運行 ELSE 語句塊。比如：IF 1=1 THENPRINT "TRUE"ELSEPRINT "FALSE"END IF
3)
FOR var = expression TO expression [STEP expression]sentence
NEXT全部表達式均為數值表達式。STEP 為可選部分，為迭代器的步長。步長表達式的值不同意為 0。作用：循環迭代結構比如：FOR I = 1 TO 10 STEP 3PRINT INEXT
4)
WHILE expressionsentence
WEND作用：迭代運行語句塊，直到表達式的值為假。比如：WHILE N < 10N = N + 1WEND

很多其它細節

1. BASIC 的源代碼不區分大寫和小寫；
2. 本程序在實現中沒有處理字符轉義，因此無法無法輸出雙引號。在介紹全然部源代碼后，假設你有興趣能夠嘗試自行完好；
3. 本程序相同沒有考慮凝視（REM keyword）。事實上這非常easy，但這個問題相同留給你來處理 ^_^；
4. 或許你也會有興趣加入 GOSUB 和 RETURN keyword，讓子程序功能從 GOTO 中解放出來。

總結

這一篇主要介紹了我們編寫的解釋器要實現的功能，接下來會有一系列文章來逐步具體介紹解釋器的實現。在下一篇中會首先介紹解釋器的核心部分——表達式求值。請關注《用C語言寫解釋器（二）》。

---

版權聲明

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

聯系方式

我的郵箱，歡迎來信（redraiment@gmail.com）
我的Blogger（子清行）：http://redraiment.blogspot.com/
我的Google Sites（子清行）：https://sites.google.com/site/redraiment
我的CSDN博客（夢婷軒）：http://blog.csdn.net/redraiment
我的百度空間（夢婷軒）：http://hi.baidu.com/redraiment