3個步驟實現簡單語言解釋器（自製簡易編程語言）

前段時間，我用javascript重新編寫了一個16位的虛擬機，用它實現了一個定製的CPU架構和彙編語言，彙編器和調試器。雖然從頭編一個語言可以完全實現自己的自定義目標，但過程卻及其複雜。為了使自己的編程過程更有效率，我決定使用Lel（布局表達式語言，Layout Expression Language，LEL）。

本文將深入研究怎樣用一個簡單的方法來編寫一個編程語言解釋器，由於所有Lel的代碼都是開放的，可以在github上使用。

解釋器的組成

解釋器是什麼？簡單來說，它基本上是一個程序，讀取源代碼，並對其進行運行，而不必首先將該源代碼編譯成機器語言。雖然這實現起來容易，但是，在運行該源代碼之前，還必須執行3個步驟，才能實現簡單語言解釋器：

1.標記化(Tokenisation)技術

標記化你的源代碼，並將其轉換成許多標記，其中每個標記都表示一種類型（比如數字，變數名稱，括弧等）和一種特殊值（比如42，「你好」，真假等）。

2.解析（樹形化）

解析或樹形化（treeification），這會讓所有的標記都以列表的形式呈現出來，一目了然，結構清晰，就像樹形一樣。為什麼我非要進行解析或樹化處理呢？因為在進行編程時，往往是函數的層次嵌套結構，樹形數據結構可以表示數據表素之間一對多的關係。

3.評估

LEL

Lel或「Lisp-esque語言」是基於lisp的語法，它是一具有50多年的編程語言。

我會在這裡分配一個變數，並聲明一個函數。

(let lifeUniverseAndEverything 42)nn(function sayHello (name)n (printn "Hello, " name ". The meaning of life the universe and everything is " lifeUniverseAndEverythingn )n)n

let是分配關鍵詞，這裡我說創建一個名為「LifeUniverseAndEverything」的變數，並將其值設置為42，只是對「sayHello」進行一個函數定義，並將它設置一個參數，然後發出一個消息。

要運行該函數：

(sayHello "Francis Stokes")nn; -> "Hello, Francis Stokes. The meaning of life the universe and everything is 42"n

這裡有很多括弧，原因是因為Lel像所有lisp派生語言一樣使用S表達式（S-expression）。要解釋什麼是S表達式，首先要知道一個表達就是一段代碼，當它運行時最終變成某種原始值。這裡一個原始值可以是一個數字，一個字元串，或者稍微複雜的一個函數引用。然後，S表達式表示，它被包含在括弧中，並且可以包含其他S表達式。

有趣的是，空格完全是無關緊要的。這意味著：

(function sayHello (name) (print "Hello, " name ". The meaning of life the universe and everything is " lifeUniverseAndEverything))n

和

(functionnsayHellon(name)n(printn"Hello, "nnamen". The meaning of life the universe and everything is "nlifeUniverseAndEverythingn))n

在Lel中都是有效的，但我絕對不會建議格式化代碼。使用空格將邏輯部分組合在一起是最有意義的。

無論如何，來看看一個If判斷語句：

(if (< 1 3)n (print "1 is less than 3.")n (print "1 is NOT less than 3.")n)n

這表示如果1<3，顯示「1小於3」，否則顯示「1不小於3」。這個 If判斷語句的排序可能看起來有點奇怪，因為操作員會出現在它所運行的數字之前。這是因為<可以被理解為一個函數， 1和3是它的參數。所有比較函數也是如此，實際上Lel中的原理都是一樣的。它的函數一直在減少。

現在，我就可以進行自製簡易編程的第一步：將代碼標記化。

標記化

讓我從一個非常簡單的計算多維數據集的程序開始。

(function cube (x)n (* x x x)n)nn(let threeCubed (cube 3))nn(print threeCubed)n

我的目標是利用這個程序獲得一系列標記，這些標記應該描述構建樹所需的一切細節，這一過程也稱為抽象語法樹（abstract syntax tree，AST）。在標記化期間，Lel會識別8種標記類型：

SKIP - 空格和注釋nLPAREN - 左括弧nRPAREN - 右括弧nNUMBER - 任何支持的數字（10，-23，1.0等）nSTRING - 任何雙引號（例如「你好」）nBOOLEAN - 真假nIDENTIFIER - 諸如語言關鍵字和變數名稱nRANGE - 一個特殊的操作符，使生成列表更容易n

這些標記類型中的每一個都與正則表達式或文字模式相關聯，如果你不知道什麼是正則表達式，那麼最簡單的解釋就是它是描述文本模式的一種方式。

例如，空格匹配的是：

/^[sn]+$/n

注釋匹配的是：

/^;.+?n$/n

解釋器（tokeniser）一次只能讀取一個字元，並檢查它是否匹配任何模式。如果它找到一個匹配，它會不斷添加字元，直到它不再匹配該模式。當停止匹配時，匹配失敗之前的所有內容都是標記值。標記最終具有以下結構：

{n type: NUMBER,n value: 42n}n

就這麼簡單嗎？實際上它確實需要比這更複雜一些。例如，因為標識符可以是與正則表達式匹配的任何字元。

/^[a-zA-Z+-/*%_><=]*$/n

像-10這樣的數字實際上將匹配負號作為標識符，然後才能匹配數字。所以要識別一個數字，至少需要2個字元才能找到正確的匹配。為了處理Lel中的這些類型所出現的歧義，首先要運行一組特殊的「歧義模式」。如果字元與「歧義模式」匹配，則會標記進入解析歧義的模式。例如，確保數字匹配正確的模式如下：

/^-$/`n

如果它匹配，它將會添加一個字元，並查看它是否匹配一個關聯的歧義模式，那麼在這種情況下只是常規數字模式。如果不匹配，則返回到第一個字元，並嘗試使用正常模式進行匹配。

也許你會注意到，使用上面描述的匹配系統，會將單詞「true」或「false」作為布爾值匹配。這是因為真正地匹配，必須是四個字元，字面上是「true」一詞。在更新一般的識別符的匹配之前，會在解釋器添加足夠的字元以獲得相應地匹配。所以必須有一組「精確」的模式。 解釋器首先會檢查這些模式，並準確讀取需要獲得該匹配的字元數。

實際地檢查順序是：

1.完全匹配（Exact matches）

2.歧義匹配（Ambiguous matches）

3.規則匹配（Regular matches）

這是簡單的標記化，或者至少是Lel的解釋器，不過有許多不同的方法可以解決這個問題。讓我來看看代碼，以了解它們真正的意義。因此，如果我回到原始示例的多維數據集代碼，則標記化輸出將如下所示：

[n { type: LPAREN, value: (},n { type: IDENTIFIER, value: function},n { type: IDENTIFIER, value: cube},n { type: LPAREN, value: (},n { type: IDENTIFIER, value: x},n { type: RPAREN, value: )},n { type: LPAREN, value: (},n { type: IDENTIFIER, value: *},n { type: IDENTIFIER, value: x},n { type: IDENTIFIER, value: x},n { type: IDENTIFIER, value: x},n { type: RPAREN, value: )},n { type: LPAREN, value: (},n { type: IDENTIFIER, value: let},n { type: IDENTIFIER, value: threeCubed},n { type: LPAREN, value: ()},n { type: IDENTIFIER, value: cube},n { type: NUMBER, value: 3},n { type: RPAREN, value: )},n { type: RPAREN, value: )},n { type: LPAREN, value: (},n { type: IDENTIFIER, value: print},n { type: IDENTIFIER, value: threeCubed},n { type: RPAREN, value: )}n]n

在Lel解釋器中，由空格和注釋生成的SKIP標記甚至不會添加到標記列表中，因此這裡只顯示重要的信息。這是標記輸入所需的最重要的信息，但是通常你會看到更多與標記相關聯的信息，例如行編號和字元位置。當你執行不同的編碼風格時，這種信息很重要，你可以看到它是否已正確縮進，或者是否已經使用了標準化的語言。

樹形化

將標記解析成樹形，主要涉及將標記匹配到語言中有效的序列。在Lel的情況下，這是一個相對簡單的過程，因為語言只能表達一種事物，這是一種典型的函數執行。但並不總是每種語言都是這樣，由於我要求的語言要對不同種類的特殊事物進行表達，所以解析就會變得越來越複雜，在大多數語言中，你會有一種特殊的處理分配方式，一種處理switch語句的特殊方法，一種特殊的方法來聲明或執行一個函數。

不過本文所述的基本想法是，樹形的「根」是一個空數組。每次我點一個左括弧的標記，就表示在生成一個新的樹形分支，即一個新的空數組出現在當前的分支。同理，當我點右括弧標記時，就表示該分支的結尾。每一個其他的標記都將被添加到當時我碰巧進入的分支，當處理玩所有標記時，返回樹形。

因此，使用上述過程轉換這些標記將產生：

[n [n { type: IDENTIFIER, value: function},n { type: IDENTIFIER, value: cube},n [n { type: IDENTIFIER, value: x}n ],n [n { type: IDENTIFIER, value: *},n { type: IDENTIFIER, value: x},n { type: IDENTIFIER, value: x},n { type: IDENTIFIER, value: x}n ]n ],n [n { type: IDENTIFIER, value: let},n { type: IDENTIFIER, value: threeCubed},n [n { type: IDENTIFIER, value: cube},n { type: NUMBER, value: 3}n ]n ],n [n { type: IDENTIFIER, value: print},n { type: IDENTIFIER, value: threeCubed}n ]n]n

所以現在LPAREN和RPAREN標記都沒有了，只有INDENTIFIERS和NUMBER仍然存在，所有這些都正確嵌套到一棵形成的樹形中。在以上這些操作都完成後，就可以進行最後一步——評估了。

在進行第三步之前，我要說明的是，如果你想根據語言可以表達的事物種類來開始評估，那麼解析器將會發揮更大的作用。我可能需要先看一到兩個標記，看看我正在處理的是什麼樣的表達或陳述，而不是一個接一個地通過標記，再單獨選擇該信息。而且只要放入更深層次的數組也許不會對標記進行縮減，因為我需要一些信息來說明以下是一個賦值還是一個函數調用。但從根本上說，這幾乎總是一個樹形結構。

評估

這將是實現簡單語言解釋器的關鍵一步，在Lel中，有一個函數可以進行規則評估，即evaluateExpr（…）函數。

在程序開始時，整個樹形結構都會被傳遞到這個函數中。通過這個函數可以看到該結構里是什麼樣的內容，並且設計出如何處理這些內容的方法。如果它是一個數組（即樹的一個分支），那麼該函數就會調用該分支中的每個表達式的evaluateExpr。如果這些分支還含有各種分支，那麼該函數也會調用該分支中的每個表達式的evaluateExpr。所有這些對evaluateExpr的嵌套調用最終都將呈現在一個「原始值」上，原始值可以是一個數字，字元串，布爾，函數或列表引用。

顯然並不是每個表達式都包含這麼多表達式數組。通常情況下，表達式都類似於函數調用，變數，函數分配或對現有變數的引用。如下就是一個變數分配表達式：

(let a 42)n

它將作為一個帶有標記的數組從解釋器和解析器中釋放出來，在這種情況下，evaluateExpr函數將會看到該表達式是一個帶有標記的數組，並且查看第一個標記。檢查的順序是：

1.是原始值嗎？n2.是變數嗎n3.是空塊嗎？n4.是一個非空塊嗎？n5.它是核心語言函數嗎？n6.是定義函數嗎？n

所以在這種情況下，let被認為是一個核心語言函數，所以evaluateExpr將返回一個特定值，該值從傳遞表達式到處理let函數，幾乎無所不能。假設通過調用evaluateExpr本身將變數設置為兩個其他變數的總和，如果需要，let函數將執行進一步的評估，最終將返回新分配的值。從現在開始，在當前SCOPE內，有一個名為a的變數。

SCOPE

有可能你以前聽說過這個詞，如果你有javascript背景，特別是從ES5天開始，你可能已經對這個詞很了解了。我試圖找出這個「this」的SCOPE。那麼SCOPE究竟是一個什麼東西呢？簡單地說，就是你正在評估任何給定的表達式的上下文。根據上下文，就可以在一段代碼中可以完全訪問已經描述的所有變數和函數。

之所以要談論不同的SCOPE和上下文，是因為所聲明的每個函數都是自己的SCOPE。每次運行一個函數，它都是一個新的執行SCOPE。所有這些SCOPE都以父子類型的關係鏈接在一起，稱為數據結構，可以大致地定義為單鏈表。這是一個比較花哨的方式，這意味著SCOPE有著自己的東西，並會以某種方式來訪問其父級的SCOPE。

條條大路通羅馬，所有SCOPE最終都會導致所謂的global scope或root scope。你經常會聽到對 SCOPE一些負面的報道，其原因就是它是一個共享空間。

當evaluateExpr被調用時，就會完成如上所示的過程，它的簽名如下所示：evaluateExpr（scope，expr）。如果分配了一個變數，它將進入該SCOPE。如果一個函數被聲明，它就將獲取的新SCOPE與傳遞給evaluateExpr的SCOPE相關聯。

對樹形的評估

首先，我會創建一個global scope。它的父SCOPE是null，且它的變數和函數的列表是空的。整個樹形將被傳遞給evaluateExpr，如下所示：

evaluateExpr(globalScope, entireTree)n

evaluateExpr將會計算出這個表達式是一個「非空塊」，並且一個接一個地在塊內的每個項目上調用evaluateExpr。那麼我得到的表達式，如下所示：

// This variable is just for illustrationnconst branch = [n { type: IDENTIFIER, value: function},n { type: IDENTIFIER, value: cube},n [n { type: IDENTIFIER, value: x}n ],n [n { type: IDENTIFIER, value: *},n { type: IDENTIFIER, value: x},n { type: IDENTIFIER, value: x},n { type: IDENTIFIER, value: x}n ]n];nnevaluateExpr(globalScope, branch)n

現在，evaluateExpr將會看到該表達式中的第一個標記將該表達式識別為「核心語言函數」，其名稱為「function」，這意味著需要調用與「function」關鍵字相關的函數。這將與當前SCOPE和當前表達式一起被調用，其最終結果是global scope現在包含一個稱為「多維數據集」的表達式中，它是一個函數定義。該函數定義具有自己的SCOPE（為了說明的目的，我稱它為cubeScope），它可以訪問global scope。這就是這個樹形分支的表達式，現在執行返回執行樹的塊。

// This variable is just for illustrationnconst branch = [n { type: IDENTIFIER, value: let},n { type: IDENTIFIER, value: threeCubed},n [n { type: IDENTIFIER, value: cube},n { type: NUMBER, value: 3}n ]n];nnevaluateExpr(globalScope, branch)n

我的下一個分支是一個let，並將像以前一樣被識別為「核心語言功能」。所有的信息將被傳遞給與let相關的函數。這非常有趣，因為這裡創建的變數會運行我剛剛定義的函數的結果。不過，需要首先評估對多維數據集的內部函數調用，因此它調用evaluateExpr本身：

// This variable is just for illustrationnconst branch = [n { type: IDENTIFIER, value: cube },n { type: NUMBER, value: 3 }n];nevaluateExpr(globalScope, branch)n

這被解釋為「定義的函數」。當遇到這種表達式時，首先通過在SCOPE內找到它來解析多維數據集的函數定義，然後將執行傳遞給處理調用定義函數的專門函數，這個函數就是callFunction。 callFunction將我的函數定義為cube，值為3，在我的函數定義中的cubeScope中創建一個cubeExecutionScope。通過執行SCOPE，可以將任何參數放置到此函數所在的位置，在這種情況下，值就是3.該值會與作為多維數據集參數的x匹配。

// This variable is just for illustrationnconst branch = [n { type: IDENTIFIER, value: *},n { type: IDENTIFIER, value: x},n { type: IDENTIFIER, value: x},n { type: IDENTIFIER, value: x}n];nevaluateExpr(cubeExecutionScope, branch)n

你會注意到，樹形分支只是我的多維數據集函數的主體，我使用的是x = 3的SCOPE。最終，這個估計值會達到27，這個值會一直傳遞給我原來的let 。

所以現在要分配給它一個值，且使用名稱為「threeCubed」，它會將它作為變數放在global scope中，值為27。控制會返回到我正在評估的原始塊，下一個和最後的表達式是：

// This variable is just for illustrationnconst branch = [n { type: IDENTIFIER, value: print},n { type: IDENTIFIER, value: threeCubed}n];nevaluateExpr(globalScope, branch)n

最終，print被識別為「核心語言函數」類型表達式，可將其參數的值寫入stdout。這個值首先需要進行評估，所以我可以得到我的三個Cubed變數，這樣另一個調用是：

// This variable is just for illustrationnconst branch = { type: IDENTIFIER, value: threeCubed};nevaluateExpr(globalScope, branch)n

其值當然是27，該值最終會被傳回給print。至此為止，實現簡單語言解釋器的3個步驟就完成了。

總結

讀完本文，首先你已經看到了標記化程序如何將源代碼轉換成標記流，其次解釋器如何樹化其接收的標記，最後評估者如何獲取樹形及其所有小分支，並得出一個可以解決專門問題的函數，而該函數會被不斷地傳遞。如果你想嘗試Lel，你可以通過npm安裝它：

npm install -g lel-langnlel # starts a Lel REPLn

如果你想閱讀代碼或複製repo腳本，你可以在github上找到所有相關代碼。最後鼓勵大家看完本文後，利用學到的東西編寫自己的編程語言。

本文翻譯自：https://francisstokes.wordpress.com/2017/08/16/programming-language-from-scratch/ ，如若轉載，請註明原文地址： http://www.4hou.com/technology/7328.html 更多內容請關注「嘶吼專業版」——Pro4hou

推薦閱讀：