c語言解釋器,用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》中我稱呼它為“算術運算”。但對于計算機來說，“算術運算”不僅包括諸如“四則運算”等算術運算，還包括“關系運算”和“邏輯運算”。為了避免歧義，在此就改稱它為“表達式運算”。“表達式運算”是整個程式的核心，地位相當于計算機的運算器。在我們的程式中，須要實作以下幾種運算符：符号名稱優先級結合性

(左括号17left2right

)右邊17left2right

+加12left2right

-減12left2right

*乘13left2right

/除13left2right

%取模13left2right

^求幂14left2right

+正号16right2left

-負号16right2left

!階乘16left2right

>大于10left2right

=等于9left2right

<>不等于9left2right

<=不大于10left2right

>=不小于10left2right

AND邏輯與5left2right

OR邏輯或4left2right

NOT邏輯非15right2left

記憶體管理

在我們這個迷你型的解釋器中，能夠不用考慮記憶體空間動态配置設定的問題，僅僅要實作簡單的變量管理。我們預設提供 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 THEN

sentence1

[ELSE

sentence2]

END IF

當中 sentence 是語句塊(下同)，包括一條或多條可運作語句。ELSE 為可選部分。

作用：分支結構。但表達式值為真(數字不等于0或者字元串不為空)時運作語句塊1；否則，有 ELSE 語句塊時運作 ELSE 語句塊。

比如：

IF 1=1 THEN

PRINT "TRUE"

ELSE

PRINT "FALSE"

END IF

3)

FOR var = expression TO expression [STEP expression]

sentence

NEXT

全部表達式均為數值表達式。STEP 為可選部分，為疊代器的步長。步長表達式的值不同意為 0。

作用：循環疊代結構

比如：

FOR I = 1 TO 10 STEP 3

PRINT I

NEXT

4)

WHILE expression

sentence

WEND

作用：疊代運作語句塊，直到表達式的值為假。

比如：

WHILE N < 10

N = N + 1

WEND

很多其它細節BASIC 的源代碼不區分大寫和小寫；

本程式在實作中沒有處理字元轉義，是以無法無法輸出雙引號。在介紹全然部源代碼後，假設你有興趣能夠嘗試自行完好；

本程式相同沒有考慮凝視(REM keyword)。事實上這非常easy，但這個問題相同留給你來處理 ^_^；

或許你也會有興趣加入 GOSUB 和 RETURN keyword，讓子程式功能從 GOTO 中解放出來。

總結

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

版權聲明

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