文章目录
  1. 1. 关于各种「器」的废话
  2. 2. 实现语法分析器
  3. 3. 后续路线图

动手之后才发现,造一个编译器轮子的难度其实并没有很多人所想的那么大。所以还是用 Learn By Doing 的方式,一点点地构建出自己的编译器吧。而为了实现全平台通用的野心,这里就选用了活在浏览器里的 JavaScript 来造这个轮子

关于各种「器」的废话

编译器、翻译器、解释器、词法分析器、语法分析器……先对这些概念做一点小总结吧。

A compiler is a computer program (or set of programs) that transforms source code written in a programming language (the source language) into another computer language (the target language, often having a binary form known as object code)

编译器就是把源代码翻译到目标代码的工具。广义上说,实现了各种编程语言代码之间转换的程序,都可以称为编译器。不过,最早编译器是把高级语言的代码转换成机器语言的,而今天显然不是所有代码都通过这种方式来执行,于是也就细分出了几种不同的「器」,比如翻译器把一种高级语言代码翻译到另一种高级语言;解释器一边读入代码,一边把代码转换成另一种语言来执行,等等。至于把低级语言翻译到高级语言,这就似乎没什么必要了……

上面的这些「器」,每种实现起来都是个大工程,实现上会被分成一个个模块,每个模块负责过程的一部分。要让自己的编译器跑起来,至少需要实现的几个过程依次是词法分析(Lexial Analysis)、语法分析(Grammar Analysis)和语义分析(Semantic Analysis)。

  • 词法分析过程把代码流分成一个个 Token,然而程序并不明白每个 Token 的意义。它的实现就称为词法分析器。
  • 语法分析过程把顺序输入的一个个 Token 按照文法,组合成一棵语法树。
  • 语义分析过程遍历这棵树,执行每个节点相应的语义动作。简单的理解,就是在由 Token 组成的语法树上的每个节点,在 JS 里都执行一下相应的 eval()

语法分析和语义分析虽然在概念上是独立的步骤,但实现时可以在建立语法树时一起执行。所以这里建立的语法分析器在后面就可以直接加上语义分析的功能,成为一个完整的编译器。

实现语法分析器

实践中实现语法分析器的过程大体上分为两种:自底向上与自顶向下。

  • 自顶向下方法,相当于从根节点(顶部)向下构造语法树,有种流行的实现称为递归下降的预测分析器。看到递归了吗,这就是在偷偷告诉你直接手写构造它的难度低啊。
  • 自底向上方法,先根据文法生成一张分析表,然后一个个吃进符号,从叶子结点开始来建立语法树。这个东西的难度在于造表的流程比较复杂,而好处就是想要修改文法,不需要修改分析器的代码,只要改文法本身就行。

说了半天,还没提到现在要实现的语法分析器本身呢。由于一点小小的野心,这个分析器的分析方式被设计为自底向上的。也就是说,只要换一套文法,就能执行对不同语言的分析任务,感觉是不是很通用呢。

自底向上做语法分析的过程可以粗略地分为造表和按表跑这两步。而实现时首先需要做的是造表。这大致又可以分为下面的这几步:

  1. 计算所有文法符号的 FIRST 集合。
  2. 计算所有非终结符的 FOLLOW 集合。
  3. 根据闭包运算求出每个状态所对应的项集。
  4. 建 STATE 表记录下所有的状态。
  5. 根据 STATE 表填 ACTION 表和 GOTO 表。

而 ACTION 和 GOTO 是可以合并的(差别仅仅在于,ACTION 表的列名是终结符,而 GOTO 表的列名是非终结符)。这样一来,整个建表过程就可以十分过程化地像下面这样执行(代码里确实也是这么写的):

buildFirstTable();

buildFollowTable();

buildStateTable();

buildActionTable();

这样就完成了造表的过程。后面的分析过程中,只要通过查 ACTION 和 GOTO 表来执行状态间的转移就行了。

实现时,STATE 和 ACTION 对应了 JS 的数组(状态的序号对于数组的偏移),而 FIRST 和 FOLLOW 集合则很适合用字典来表示(根据读入的字符直接对应相应的集合)。

最有意思的地方,是 JavaScript 可以用 JSON 的对象来表示文法。这有个好处,就是特殊符号不能作为变量名,但是可以作为 JSON 对象的键名,从而在实现上会比较统一。

后续路线图

现在的语法分析器已经实现了分析表的构建,下面的需要做的可以归结成这几件事:

  • 按表执行语法树的构建。
  • 语义动作的附加。
  • 一些实用文法的构造,现在所能想到的就是通过加入自定义的文法,在浏览器里实现这些东西:
    • JSON 的解析器。
    • HTML 的解析器。
    • SQL 的解释器,各种查表的语义动作可以最终转对 CSV 格式数据的查询。
    • jQuery 到原生 JavaScript 的翻译器。

限于时间和我弱渣的 debug driven development 水平,感觉这些东西最后能实现一两个就很不错啦,毕竟就好像执行力比好 idea 重要一样,重点总是不在于开坑,而在于填坑……

文章目录
  1. 1. 关于各种「器」的废话
  2. 2. 实现语法分析器
  3. 3. 后续路线图