警告⚠️:这将是一个又臭又长的系列教程,教程结束的时候,你将拥有一个除了性能差劲、扩展性差、标准库不完善之外,其他方面都和官方相差无几的 Lua 语言解释器。说白了,这个系列的教程实现的是一个玩具语言,仅供学习,无实用性。请谨慎 Follow,请谨慎 Follow,请谨慎 Follow。
前言
编译原理是计算机科学的一个重要且复杂的知识体系。这个系列教程也只是你入门前的垫脚石。但即使如此,也并不代表这个教程就很简单,如果决定开始,请坚持到底。这是一个认真严肃的教程(咳咳),它不像网络上的其他类似教程,要么实现一个“高级计算器”就完事了,要么语法分析还没讲完,就太监了。也不像其他的 Lua 源码阅读类的指导教程,去教你怎么阅读并理解官方实现的 Lua 解释器的源码。但我相信完成本教程后再去读官方实现的源代码,也会轻松很多。
本教程将从零开始,一砖一瓦的构建出一个完整的解释器。不使用任何自动化的工具,也不使用任何第三方库,从词法分析到虚拟机,全部亲力亲为。我们将要实现的语言起名为 SLua,意思是 Simple Lua。
前置要求
本教程并不是面向编程初学者的,你至少需要满足以下要求才可以继续阅读:
本教程使用的编程语言为 Google 出品的 Go 语言。Go 语言上手非常容易,如果你有过其他任何语言的编程经验,请花几个小时阅读这篇教程:墙外多语言版、墙内中文版。
本教程的定位不是教科书,因此不会过多的提及关于编译原理的理论性的内容,而更加注重实践。所以,这要求你至少要知道编译过程流水线的基本步骤以及每个步骤的作用,比如:词法分析、语法分析、虚拟机等。
既然要实现 Lua 语言的解释器,自然要求你熟悉 Lua 语言,即使没有用它写过项目,至少要熟悉 Lua 语言的语法及语言特性。
面向人群
- 如果你很想知道脚本语言的解释器的工作原理,请继续阅读。
- 如果你不仅想知道工作原理,还想亲自实现一个,请继续阅读。
- 如果你学完学校开设的编译原理课程,除了学会了 LEX 和 YACC,其余的还是一无所知,请继续阅读。
开发方式
我们不准备从一开始就着手实现一个完完整整的解释器,支持所有的 Feature,这样无疑会顾此失彼,也会极大的拉高教程的阅读门槛。所以我们会先抽取 Lua 中一些最最基本的特性,实现一个可以工作的原型。在原型之上,我们再不断添加特性,直到完成为止。
在第一个版本中,我们会将一些比较重要的 Feature 都砍掉,将目光集中在整个流程的实现上。
所以,第一个版本将:
- 不支持 Table
- 不支持函数和闭包
- 不支持 for 循环语句
- 不支持 repeat...until 循环语句
- 不支持多行注释和多行字符串
阉割的差不多了,看看还剩下什么:
- 变量的声明及赋值(全局变量和局部变量)
- do ... end 代码块
- if ... elseif ... else ... end 分支语句
- while 循环语句
- 单行注释
- 单行形式的字符串
- 各种单目和双目的运算符
编译流程
SLua 的编译共分为以下几个阶段:
- 词法分析:将用户输入的文本形式的源代码分解为一个 Token 列表
- 语法分析:将词法分析的输出作为输入,生成无语义信息的抽象语法树(AST)
- 语义分析:完善 AST 中的语义相关的信息
- 代码生成:根据 AST 生成字节码
- 虚拟机:解释并执行字节码
- 标准库:提供系统级的实用函数
教程的章节安排也和编译流程保持一致。
获取源代码
代码已托管到 Github 上:SLua,每一个阶段的代码我都会创建一个 release,你可以直接下载作为参照。虽然提供了源代码,但并不建议直接复制粘贴,因为这样学到的知识会很容易忘记。
刚开始玩 Github 和简书,所以没有任何粉丝和关注量(哭),如果你觉得这篇教程有帮助,请不要吝啬给文章点个喜欢,给 Github 上的项目点个 Star。如果能 Follow 一下简书和 Github 的账号就更好啦,我也会更加有动力将这个系列写下去。:)