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)
 
(function sayHello (name)
  (print
    "Hello, " name ". The meaning of life the universe and everything is " lifeUniverseAndEverything
  )
)

'let'是分配关键词，这里我说创建一个名为“LifeUniverseAndEverything”的变量，并将其值设置为42，只是对“sayHello”进行一个函数定义，并将它设置一个参数，然后发出一个消息。

要运行该函数：

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

这里有很多括号，原因是因为Lel像所有lisp派生语言一样使用S表达式（S-expression）。要解释什么是S表达式，首先要知道一个表达就是一段代码，当它运行时最终变成某种原始值。这里一个原始值可以是一个数字，一个字符串，或者稍微复杂的一个函数引用。然后，S表达式表示，它被包含在括号中，并且可以包含其他S表达式。

有趣的是，空格完全是无关紧要的。这意味着：

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

和

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

在Lel中都是有效的，但我绝对不会建议格式化代码。使用空格将逻辑部分组合在一起是最有意义的。

无论如何，来看看一个If判断语句：

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

这表示如果1<3，显示“1小于3”，否则显示“1不小于3”。这个 If判断语句的排序可能看起来有点奇怪，因为操作员会出现在它所运行的数字之前。这是因为<可以被理解为一个函数， 1和3是它的参数。所有比较函数也是如此，实际上Lel中的原理都是一样的。它的函数一直在减少。

现在，我就可以进行自制简易编程的第一步：将代码标记化。

标记化

让我从一个非常简单的计算多维数据集的程序开始。

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

我的目标是利用这个程序获得一系列标记，这些标记应该描述构建树所需的一切细节，这一过程也称为抽象语法树（abstract syntax tree，AST）。在标记化期间，Lel会识别8种标记类型：

SKIP - 空格和注释
LPAREN - 左括号
RPAREN - 右括号
NUMBER - 任何支持的数字（10，-23，1.0等）
STRING - 任何双引号（例如“你好”）
BOOLEAN - 真假
IDENTIFIER - 诸如语言关键字和变量名称
RANGE - 一个特殊的操作符，使生成列表更容易

这些标记类型中的每一个都与正则表达式或文字模式相关联，如果你不知道什么是正则表达式，那么最简单的解释就是它是描述文本模式的一种方式。

例如，空格匹配的是：

/^[sn]+$/

注释匹配的是：

/^;.+?n$/

解释器（tokeniser）一次只能读取一个字符，并检查它是否匹配任何模式。如果它找到一个匹配，它会不断添加字符，直到它不再匹配该模式。当停止匹配时，匹配失败之前的所有内容都是标记值。标记最终具有以下结构：

{
  type: 'NUMBER',
  value: 42
}

就这么简单吗？实际上它确实需要比这更复杂一些。例如，因为标识符可以是与正则表达式匹配的任何字符。

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

像-10这样的数字实际上将匹配负号作为标识符，然后才能匹配数字。所以要识别一个数字，至少需要2个字符才能找到正确的匹配。为了处理Lel中的这些类型所出现的歧义，首先要运行一组特殊的“歧义模式”。如果字符与“歧义模式”匹配，则会标记进入解析歧义的模式。例如，确保数字匹配正确的模式如下：

/^-$/`

如果它匹配，它将会添加一个字符，并查看它是否匹配一个关联的歧义模式，那么在这种情况下只是常规数字模式。如果不匹配，则返回到第一个字符，并尝试使用正常模式进行匹配。

也许你会注意到，使用上面描述的匹配系统，会将单词“true”或“false”作为布尔值匹配。这是因为真正地匹配，必须是四个字符，字面上是“true”一词。在更新一般的识别符的匹配之前，会在解释器添加足够的字符以获得相应地匹配。所以必须有一组“精确”的模式。 解释器首先会检查这些模式，并准确读取需要获得该匹配的字符数。

实际地检查顺序是：

1.完全匹配（Exact matches）

2.歧义匹配（Ambiguous matches）

3.规则匹配（Regular matches）

这是简单的标记化，或者至少是Lel的解释器，不过有许多不同的方法可以解决这个问题。让我来看看代码，以了解它们真正的意义。因此，如果我回到原始示例的多维数据集代码，则标记化输出将如下所示：

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

在Lel解释器中，由空格和注释生成的SKIP标记甚至不会添加到标记列表中，因此这里只显示重要的信息。这是标记输入所需的最重要的信息，但是通常你会看到更多与标记相关联的信息，例如行编号和字符位置。当你执行不同的编码风格时，这种信息很重要，你可以看到它是否已正确缩进，或者是否已经使用了标准化的语言。

树形化

将标记解析成树形，主要涉及将标记匹配到语言中有效的序列。在Lel的情况下，这是一个相对简单的过程，因为语言只能表达一种事物，这是一种典型的函数执行。但并不总是每种语言都是这样，由于我要求的语言要对不同种类的特殊事物进行表达，所以解析就会变得越来越复杂，在大多数语言中，你会有一种特殊的处理分配方式，一种处理switch语句的特殊方法，一种特殊的方法来声明或执行一个函数。

不过本文所述的基本想法是，树形的“根”是一个空数组。每次我点一个左括号的标记，就表示在生成一个新的树形分支，即一个新的空数组出现在当前的分支。同理，当我点右括号标记时，就表示该分支的结尾。每一个其他的标记都将被添加到当时我碰巧进入的分支，当处理玩所有标记时，返回树形。

因此，使用上述过程转换这些标记将产生：

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

所以现在LPAREN和RPAREN标记都没有了，只有INDENTIFIERS和NUMBER仍然存在，所有这些都正确嵌套到一棵形成的树形中。在以上这些操作都完成后，就可以进行最后一步——评估了。

在进行第三步之前，我要说明的是，如果你想根据语言可以表达的事物种类来开始评估，那么解析器将会发挥更大的作用。我可能需要先看一到两个标记，看看我正在处理的是什么样的表达或陈述，而不是一个接一个地通过标记，再单独选择该信息。而且只要放入更深层次的数组也许不会对标记进行缩减，因为我需要一些信息来说明以下是一个赋值还是一个函数调用。但从根本上说，这几乎总是一个树形结构。

评估

这将是实现简单语言解释器的关键一步，在Lel中，有一个函数可以进行规则评估，即evaluateExpr（…）函数。

在程序开始时，整个树形结构都会被传递到这个函数中。通过这个函数可以看到该结构里是什么样的内容，并且设计出如何处理这些内容的方法。如果它是一个数组（即树的一个分支），那么该函数就会调用该分支中的每个表达式的evaluateExpr。如果这些分支还含有各种分支，那么该函数也会调用该分支中的每个表达式的evaluateExpr。所有这些对evaluateExpr的嵌套调用最终都将呈现在一个“原始值”上，原始值可以是一个数字，字符串，布尔，函数或列表引用。

显然并不是每个表达式都包含这么多表达式数组。通常情况下，表达式都类似于函数调用，变量，函数分配或对现有变量的引用。如下就是一个变量分配表达式：

(let a 42)

它将作为一个带有标记的数组从解释器和解析器中释放出来，在这种情况下，evaluateExpr函数将会看到该表达式是一个带有标记的数组，并且查看第一个标记。检查的顺序是：

1.是原始值吗？
2.是变量吗
3.是空块吗？
4.是一个非空块吗？
5.它是核心语言函数吗？
6.是定义函数吗？

所以在这种情况下，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)

evaluateExpr将会计算出这个表达式是一个“非空块”，并且一个接一个地在块内的每个项目上调用evaluateExpr。那么我得到的表达式，如下所示：

// This variable is just for illustration
const branch = [
  { type: 'IDENTIFIER', value: 'function'},
  { type: 'IDENTIFIER', value: 'cube'},
  [
    { type: 'IDENTIFIER', value: 'x'}
  ],
  [
    { type: 'IDENTIFIER', value: '*'},
    { type: 'IDENTIFIER', value: 'x'},
    { type: 'IDENTIFIER', value: 'x'},
    { type: 'IDENTIFIER', value: 'x'}
  ]
];
 
evaluateExpr(globalScope, branch)

现在，evaluateExpr将会看到该表达式中的第一个标记将该表达式识别为“核心语言函数”，其名称为“function”，这意味着需要调用与“function”关键字相关的函数。这将与当前SCOPE和当前表达式一起被调用，其最终结果是global scope现在包含一个称为“多维数据集”的表达式中，它是一个函数定义。该函数定义具有自己的SCOPE（为了说明的目的，我称它为cubeScope），它可以访问global scope。这就是这个树形分支的表达式，现在执行返回执行树的块。

// This variable is just for illustration
const branch = [
  { type: 'IDENTIFIER', value: 'let'},
  { type: 'IDENTIFIER', value: 'threeCubed'},
  [
    { type: 'IDENTIFIER', value: 'cube'},
    { type: 'NUMBER', value: 3}
  ]
];
 
evaluateExpr(globalScope, branch)

我的下一个分支是一个let，并将像以前一样被识别为“核心语言功能”。所有的信息将被传递给与let相关的函数。这非常有趣，因为这里创建的变量会运行我刚刚定义的函数的结果。不过，需要首先评估对多维数据集的内部函数调用，因此它调用evaluateExpr本身：

// This variable is just for illustration
const branch = [
  { type: 'IDENTIFIER', value: 'cube' },
  { type: 'NUMBER', value: 3 }
];
evaluateExpr(globalScope, branch)

这被解释为“定义的函数”。当遇到这种表达式时，首先通过在SCOPE内找到它来解析多维数据集的函数定义，然后将执行传递给处理调用定义函数的专门函数，这个函数就是callFunction。 callFunction将我的函数定义为cube，值为3，在我的函数定义中的cubeScope中创建一个cubeExecutionScope。通过执行SCOPE，可以将任何参数放置到此函数所在的位置，在这种情况下，值就是3.该值会与作为多维数据集参数的x匹配。

// This variable is just for illustration
const branch = [
  { type: 'IDENTIFIER', value: '*'},
  { type: 'IDENTIFIER', value: 'x'},
  { type: 'IDENTIFIER', value: 'x'},
  { type: 'IDENTIFIER', value: 'x'}
];
evaluateExpr(cubeExecutionScope, branch)

你会注意到，树形分支只是我的多维数据集函数的主体，我使用的是x = 3的SCOPE。最终，这个估计值会达到27，这个值会一直传递给我原来的let 。

所以现在要分配给它一个值，且使用名称为“threeCubed”，它会将它作为变量放在global scope中，值为27。控制会返回到我正在评估的原始块，下一个和最后的表达式是：

// This variable is just for illustration
const branch = [
  { type: 'IDENTIFIER', value: 'print'},
  { type: 'IDENTIFIER', value: 'threeCubed'}
];
evaluateExpr(globalScope, branch)

最终，print被识别为“核心语言函数”类型表达式，可将其参数的值写入stdout。这个值首先需要进行评估，所以我可以得到我的三个Cubed变量，这样另一个调用是：

// This variable is just for illustration
const branch = { type: 'IDENTIFIER', value: 'threeCubed'};
evaluateExpr(globalScope, branch)

其值当然是27，该值最终会被传回给print。至此为止，实现简单语言解释器的3个步骤就完成了。

总结

读完本文，首先你已经看到了标记化程序如何将源代码转换成标记流，其次解释器如何树化其接收的标记，最后评估者如何获取树形及其所有小分支，并得出一个可以解决专门问题的函数，而该函数会被不断地传递。如果你想尝试Lel，你可以通过npm安装它：

npm install -g lel-lang
lel # starts a Lel REPL

如果你想阅读代码或复制repo脚本，你可以在github上找到所有相关代码。最后鼓励大家看完本文后，利用学到的东西编写自己的编程语言。