用Go编写BASIC解释器

用Go编写BASIC解释器

Mon Jul 25, 2016

我以前用C写过一个简单的解释器，它接受类似BASIC的代码，并解释执行。一个解释器主要包含以下部分：

1. 词法分析器(lexer)，用来把代码分割成一连串记号(token)，如标识符、数字、运算符等，并且忽略空白和注释。
2. 语法分析器(parser)，用来分析代码的层次结构，并构造抽象语法树(AST)。
3. 后端(backend)，用来解释执行所生成的AST。

如果是编译器，那么后端的作用是生成机器代码，以便直接被CPU执行。

词法分析器可以手写也可以用lex自动生成。因为比较简单，所以往往采用手写的方式。语法分析器可以手写，通常采用递归下降(recursive-descent)算法；也可以用yacc自动生成，后者使用的是一种称为LALR(1)的技术。

最近发现Go的官方工具链自带了一个yacc工具(go tool yacc)，所以就试着用它写了一个类似的解释器。功能被进一步削减，只能算是一个demo。

能解释运行像这样的代码：

SUM = 0
I = 1
WHILE NOT I > 100 DO
	SUM = SUM + I
	I = I + 1
END WHILE
PRINT SUM

首先编写的是语法规则parse.y，它确定了整个语言的语法。编写完成后，补上词法分析器lex.go。在这里我为了偷懒，直接用了标准库中的text/scanner，这是一个比较通用的词法分析器。接下来定义AST中的节点，比如运算表达式可以用一个二叉树来表示，并在parse.y中增加构造AST的语句。

运行Go提供的yacc工具：

go tool yacc parse.y

这样就会生成真正的语法分析器y.go，以及它的状态图y.output，后者在调试语法分析器时有用。如果yacc报错，例如存在shift/reduce冲突等等，则需要修改parse.y使之符合要求。

最后是编写很无聊的后端，基本上就是把每个AST节点用代码表述一遍其语义。例如，如果节点代表加法运算，那么分别求值其左右子节点，然后计算它们之和。 这样一来，一个解释器就编写完毕了。

编写这些东西只花了很少的时间，Go的开发效率出乎意料地高，令我特别满意的有如下几点：

1. 不用编写头文件。C语言的程序需要把结构体的定义、extern变量和函数声明写入头文件中，这简直就是重复劳动。使用Go不需要编写头文件，函数的定义也不需要考虑先后次序。
2. 不用编写Makefile。C语言的程序为了高效地构建，需要编写Makefile，以便使用make命令替代复杂的编译器命令。对于大型的项目，可能还需要GNU Autotools来做一些自动化的工作。这些工具虽然目的都是为了减少工作量，但是配置起来非常麻烦。Go自带go build指令，无需任何配置，一步搞定。
3. 不会Segmentation fault。C语言的程序最大的痛苦就是程序莫名其妙地崩溃了。编写代码的时候一个不注意可能就发生了下标越界、解引用空指针/未初始化的指针、重复释放等内存错误，这样的错误需要花费大量的时间来调试。Go的运行时含有垃圾收集器，减少了手工的内存操作因此也就减少了潜在的错误。而且内建了边界检查，即便出现了下标越界的问题也会直接打印出调用栈以及出错的行号，便于迅速查错。

整个程序几乎是一遍写对的，通过了编译之后就基本上没有什么问题。

Go的yacc生成的语法分析器是可重入的(re-entrant)，它不使用任何全局变量。并且由于使用了垃圾收集器，也不会泄漏内存。基于C的语法分析器生成器很难做到这一点。