3个步骤实现简单语言解释器(自制简易编程语言)

xiaohui 技术 2017年8月21日发布

导语:前段时间,我用javascript重新编写了一个16位的虚拟机,用它实现了一个定制的CPU架构和汇编语言,汇编器和调试器。虽然从头编一个语言可以完全实现自己的自定义目标,但过程却及其复杂。为了使自己的编程过程更有效率,我决定使用Lel(布

1503082388443042.png

前段时间,我用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一些负面的报道,其原因就是它是一个共享空间。

15.png

当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上找到所有相关代码。最后鼓励大家看完本文后,利用学到的东西编写自己的编程语言。

本文翻译自:https://francisstokes.wordpress.com/2017/08/16/programming-language-from-scratch/ ,如若转载,请注明原文地址: http://www.4hou.com/technology/7328.html
点赞 4
  • 分享至
取消

感谢您的支持,我会继续努力的!

扫码支持

打开微信扫一扫后点击右上角即可分享哟

发表评论

    开发者头条 2017-08-22 09:36

    感谢分享!已推荐到《开发者头条》:https://toutiao.io/posts/sgmhas 欢迎点赞支持!
    欢迎订阅《嘶吼》https://toutiao.io/subjects/254086