21CTO导读：

各位，一位资深程序员分享了他们周末从零开始构建完整编译器的项目，创建了一个名为 toybasic 的简化 BASIC 变体，可以将其转换为 Go 代码。

该实现包含三个阶段：使用 nex 构建的词法分析器用于标记化，使用 goyacc 构建的解析器用于语法树生成，以及一个自定义的 Go 编译器。

现在，我们一块来看正文。

我拥有计算机科学学位。我参加了一整套关于编译器的课程（因此对“红龙书”颇有好感）。然而，直到上周末的一个下雨天，我才真正从头到尾写过一个编译器。没错，这只是我的爱好。

我想为一种真正的语言编写一个编译器，但要简单一些，这样我就能用几个小时完成这个项目。我一直对 BASIC 情有独钟——它是我小时候学的第一门编程语言。幸运的是，现在有一个实用的版本叫做 TinyBASIC（感谢维基百科提供的提示）。我的版本比 TinyBASIC 更简单（没有INPUT语句）。因此我把它命名为toybasic。所有代码都可以在 GitHub 上找到。

它是用 Go 编写的，并从 BASIC 生成 Go 代码。

演示代码

示例程序代码如下：example/hello.bas

PRINT "Hello, world."LET x = (3 * 2) + 3LET x = x + 1IF x == 10 THEN PRINT "Ten!"PRINT xIF x >= 15 THEN GOTO 70GOTO 30END

该代码实例会输出如下的结果：

$ ./toybasic $ go run out.goHello, world.Ten!101112131415

编译器之结构

我编写的编译器一共有3个阶段：

词法分析器- 将源代码中的字符序列转换为具有含义的标记序列，可以传递给如下。

解析器- 根据标记构建一棵树（Tree）。这为我们提供了程序的结构表示，以便在下一阶段轻松遍历。它还会检查所提供程序的结构是否符合语法要求，如果语法不正确，则会生成有用的错误消息。

编译器——遍历解析后的语法树并写出与原始 BASIC 等效的 Go 代码。

完全手工编写词法分析器和解析器是可能的，但市面上也有一些现成的工具可以简化这一过程。

值得尊敬的lex和yacc自1975年以来一直在用C语言帮助解决这个问题。yacc的原作者是迈克·沙因(Mike Lesk)和艾瑞克·史密特（Eric Schmidt）——没错，就是后来成为谷歌首席执行官的Eric Schmidt。

Go有很多lex可用的克隆版本。我决定用它们nex来编写我的词法分析器。Nex 的awk语法直观易懂，而且 README 文件也非常易懂。

Go 在其默认工具中内置了一个yacc名为的变体goyacc，这是解析器的最优选择项。

解析器

这是处理代码的第二步，但解析器是编写或解释编译器的最佳起点，因为它包含toybasic 的语法。我在语法处理上受到了 Bogdan Kravtsov 的tinybasic的启发，我对其进行了修改，加入了字符串并删除了INPUT。

我们来看一小段摘录：

statement:    PRINT expr_list                                 { $$ = opr(PRINT, 1, $2); }    | IF expression relop expression THEN statement { $$ = opr(IF, 4, $2, $3, $4, $6); }    | GOTO expression                               { $$ = opr(GOTO, 1, $2); }    | LET v '=' expression                          { $$ = opr(LET, 2, $2, $4); }    | END                                           { $$ = opr(END, 0);  }    ;

我们用一种特殊的语法来定义该语言的语法，并给出goyacc一小段 Go 代码，以便在解析相关符号时运行，从而生成解析树。这里你可以看到语法的一部分，它解析了我的 BASIC 所支持的所有语句。该opr函数在我的编译器代码中定义，用于为我们的语法树生成正确类型和形状的对象。

最终结果，是如下一行 BASIC 代码：

10 PRINT "Look!", (2 + 3) * 3

解析为如下对象树：

PrintOp    |  ListOp --------.    |            |  StringOp      *Op --------.                 |          |              GroupOp      INTEGER                 |                    InfixOp              |  |  |        INTEGER  +  INTEGER

语法旁边还定义了一个非常重要的小表，您可以在其中定义树中每个节点需要填充的属性：

%union {    v string    /* Variable */    s string    /* String */    num int     /* Integer constant */    dec float64 /* Decimal constant */    node Node   /* Node in the AST */};

词法分析器

nex使用一系列确定性有限自动机生成对语言进行标记化所需的 Go 代码。以下是它为 toybasic 生成的 1000 多行代码中的一小部分——不用手写这些代码真是太好了。

...var dfas = []dfa{// LET	{[]bool{false, false, false, true}, []func(rune) int{ // Transitionsfunc(r rune) int {switch r {case 69:return -1case 76:return 1case 84:return -1			}return -1		},...	}, []int{ /* Start-of-input transitions */ -1, -1, -1, -1}, []int{ /* End-of-input transitions */ -1, -1, -1, -1}, nil},...

相反，nex需要一个配置文件，在其中指定一组正则表达式，用于捕获语言的所有关键字和标识符。以下是一些代码示例：

/PRINT/ {return PRINT}/==/ {return EQ}/[0-9]+/                {lval.num, _ = strconv.Atoi(yylex.Text()); return INTEGER}/[0-9]+\.[0-9]*/        {lval.dec, _ = strconv.ParseFloat(yylex.Text(), 64);return DECIMAL}/"[^"]*"/               {lval.s = yylex.Text(); return STRING}

上面代码里，左侧/字符之间是正则表达式。

你可以按优先级顺序提供它们。这段代码最终与语法紧密耦合yacc。每个正则表达式匹配都会运行右侧花括号中的 Go 代码，该代码必须返回一个 token 类型，并填充树中所有叶节点的每个类型属性。

编译器

这是我唯一需要直接用 Go 编写的代码。它为语法树中每个可能的节点定义了类型，并且每个Node类型都有一个Generate对应的函数，该函数知道如何将该节点转换为 Go 代码（同时调用Generate任何相关的子节点）。

type Node interface {	Generate()}...type PrintOp struct {	expression Node}func (op PrintOp) Generate() {	fmt.Fprint(writer, "fmt.Println(")	op.expression.Generate()	fmt.Fprintln(writer, ")")}

看起来就是这样PrintOp——它知道如何用fmt.Println([whatever code my children generate])的Go 代码编写。

总结

就这样，我们终于搞定了——一个 BASIC 到 Go 的编译器玩具。

接着为了测试它，我编写了一个 BASIC 小程序，用到了 BASIC 语言的每一个结构，确保它能正常工作并生成预期的输出。虽然我对整个过程的每个步骤都有一定的了解，但实际操作起来却非常有趣，也让我豁然开朗。这绝对是度过阴雨绵绵的周六下午的好方法。

现在可以验证我编写的第一个 BASIC 程序是否仍按预期运行。

10 PRINT "David is cool"20 GOTO 10

作者：David

相关资源：

https://github.com/dps/toybasic/blob/main/parser.y

https://blog.singleton.io/posts/2021-01-31-i-wrote-a-compiler/