发表于 | 分类于

背景

时隔三年，这是相继 如何编写一个简单的 parser，

以及 如何编写一个简单的解释器，之后的 第三篇，

如何编写一个简单的 debugger。


众所周知，VSCode 通过 LSP 支持了不同的 语言特性，

而通过 DAP 实现了不同语言的 调试功能。


在前两篇文章中，我们基于 LISP 语法，

分别实现了 语法解析 parse（将字符串转换成有结构的数据），

以及 语义解释 eval（对结构化的数据进行求值） 两个过程。


但如果只有这些，对于了解语言技术而言还仍显不够。

市面上有太多资料介绍 parser 了，但其实这只是故事的开始罢了。


本文就从 语法设计、解析、解释、调试 整条链路，尝试写点不一样的内容。

重点写一写 debugger 的实现细节。



值得一提的是，有一类专门的工程师，称为编程语言工程师，

以下所述的内容，对于他们而言，可能太过班门弄斧了。

在这个语言领域中，我还只是一个小学徒。

有任何理解不当的地方，还请不吝指出，我也仍在不断的学习中。

语法设计

当我们萌生「让字符串跑起来」的想法之后，

首先应该考虑的是，如何设计一套无歧义的文法。


所谓文法，就是用来描述语言结构的规则集。

根据文法我们能够知道，哪些字符串是语言中合法的语句，哪些不是。

最常见的文法形式，就是 上下文无关文法。


上下文无关文法 由一堆产生式 构成（其次还有 终结符、非终结符），

举个例子，这就是一段有效的文法（取自 TypeScript 语言，略有删减），

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
SourceFile = StatementList
StatementList = Statement | Statement StatementList

Statement = VariableDeclaration | FunctionDeclaration

VariableDeclaration = 'let' Identifier '=' Value
Value = NUMBER | CallExpression

FunctionDeclaration = Identifier '(' Identifier ')' '{' FunctionBody '}'
FunctionBody = StatementList ReturnStatement
ReturnStatement = 'return' ReturnExpression

ReturnExpression = Identifier | PlusExpression

PlusExpression = Identifier '+' Identifier
CallExpression = Identifier '(' Identifier ')'

Identifier = [a-z]+
Number = [0-9]+
Keyword = 'let' | 'return'


其中，VariableDeclaration = 'let' Identifier '=' Value 这一行称为一个产生式，

左边 VariableDeclaration 是非终结符（它会被展开成右边），

右边 'let' '=' 称为终结符（它不能再被展开了），

右边 Identifier Value 仍为非终结符，可以根据其他相应的产生式规则，继续展开。


以上文法，可以用来描述下面这样的语言结构，

（类似 TypeScript 语言，只是去掉了 function 关键字）

1
2
3
4
5
6
7
8
9
10
11
12
13
let a = 1
let b = 2

f(x){
  let b = 3
  g(y){
    return y+b
  }
  return g
}

let c = f(a)
let d = c(b)



我们看到，不论是从语言还是从文法上，都能反映出一种递归结构。

最直观的感受是，函数定义里面还可以再嵌套一个函数，并可以无限嵌套下去（都是合法的）。

所以，这就对我们如何解析上下文无关语言，提供了启发 —— 递归处理。


解析过程，无非就是将字符串转成对象而已，

所以我们才需要 文法尽量的准确（无歧义），对于同一段字符串，有且仅有一种转换方式。

解析器

代码：thzt/dsl-parser


有不少文章，重点介绍了 parser 的实现过程，这里就不赘述了，

日常工作中，我们从零编写一个 parser 的情况很少，基本都用现成的。

即使有特殊情况，手写递归下降语法解析器，也能满足大多数场景了。


在 第一篇文章 如何编写一个简单的 parser中，

我们已经介绍了编写递归下降语法解析器的套路，

一个 parser 是由一些互递归的函数调用组成（每一个 非终结符/产生式 对应一个函数）。


parser 内部会包含一个 nextToken 词法分析器，

把单个字符组装成带有类型标识的 token 单词，再进行处理。



具体处理的时候后，这些互递归函数，会读取当前 token（或者之后的 token），

来判定 按照哪个产生式进行解析。

最终会得到一个树形结构 —— AST（树是递归结构的真实写照），

这个树形结构的节点，就是文法中的非终结符。


解释器

代码：thzt/dsl-interpreter


解释器也比较简单，就是一个在递归结构中，进行递归求值的过程。

解释器的实现套路在 第二篇 如何编写一个简单的解释器 中有过介绍，

每一个 AST 节点，对应一个 evalXXX 函数，然后递归调用。



稍微有些复杂的是词法作用域的实现，

需要在解释的过程中，遇到函数定义（FunctionDeclaration），先将求值环境与函数关联起来。

然后等到函数调用（CallExpression）的时候，再取出当时的环境进行求值。


函数+环境就是闭包了，希望这次把它讲清楚了。

调试器

yield

终于可以介绍调试器了。首先应该考虑的是，用什么工具对语言进行调试。

最常见的调试方式有命令行方式（例如 GDB），还有 IDE 集成方式。

本文选择较为直观的方式，通过 DAP 借用 VSCode 进行调试。



第一步，我们需要对解释器进行改造，让它可以停下来。

常见的办法是将函数改造为 generator，将递归调用改成 yield*，

然后在特定阶段（需要停下来的时候），通过 yield 把内部状态返回出来。



然后，就可以实现步进了，

只有我们手动调用 next 的时候，解释器才会继续向下执行。


更有甚者，我们还可以写一个 runtime，把控制逻辑包一层。

如下图，模拟我们在 VSCode 中启动调试后，按 Step Over（下一步）所发生的事情，


vscode extension

代码：thzt/vscode-dsl-debugger


第二步，就是实现一个 VSCode 插件了， 它实现了 DAP 协议。


例如，生命周期事件

  • 初始化 initializeRequest

  • 启动调试 launchRequest

  • 获取调用栈里面的进程 threadsRequest

  • 获取给定进程的调用栈帧 stackTraceRequest

  • 获取给定栈帧的作用域分类 scopesRequest

  • 获取不同栈帧分类的变量 variablesRequest


还有 操作按钮事件

  • Step Over（单行执行）：nextRequest

  • Step In（单步执行）：stepInRequest



我们需要做的事情是，如何驱动解释器，按照我们指定的方式执行。

比如，我们总是可以将复杂操作封装到 runtime 中去。

需要注意的是 VSCode 所需要的一些 Event（this.sendEvent）和 Response（this.sendResponse）。


最终效果


至此，我们实现了上述语言的调试功能，

借助了解释器的能力，语言本身支持词法作用域。

  • f 返回一个函数 g，并把它赋值给了 c

  • c 调用的时候，就会调用内层函数 g，并且 g 的变量 b 取自词法作用域 b=3，而不是最外层的 2

  • 而 y 的值是 c 的入参 2，因此 d 的返回值为 5

结语

上文我们编写了一个简单的 debugger，它可以对所设计的语言进行调试。

有了这些能力之后，我们就可以 debug everything 了（只要世界可以停下来）。


在自己实现 debugger 之前，会认为这些技术蕴含着难以理解的理论知识，

实际写完之后却发现，主要还是对「树」结构数据进行的处理，

只要了解 递归、封装、会调用 API、有工程思想，都能把它写出来。

比较困难的时，如何对现有实现进行优化，这些往往是某些文章、资料、书籍重点介绍的内容。


我们知道，软件领域正在经历翻天覆地的变革，

但不论怎样变革，知识本身并没有太多变化。


以上介绍的内容，可能颇为小众。

然而这些小众知识，反而能让我们在实际工作中 如虎添翼、立竿见影。


再接再厉。