使用Javascript实现DSL解析器:揭开DSL神秘面纱

9,220 阅读6分钟

前言

这篇文章在一个比较高的抽象层次,讨论了什么是DSL,DSL的分类以及实现一个DSL所需的理论知识和一些关键的技术点。让读者对实现DSL能有一个全局的认识,在后面的文章中再深入介绍各个技术点,最终会使用Javascript实现一个DSL的编译器生成器。

DSL 是什么

DSL(Domain Specific Language)是一种用来解决特定领域问题的计算机编程语言我们经常使用的CSS、SQL都属于DSL。还有其他的比如模版语言,从名字就可以知道他是一种领域特定语言,另外Docker的镜像描述文件Dockerfile也是一种DSL, 与领域特定语言相对的就是通用编程语言比如C#、Java等。

DSL的分类

Martin Fowler将DSL分为内部DSL和外部DSL,内部DSL一般是基于宿主语言封装的一个类库,提供领域表现力更强的API给使用方,比如jQuery的链式调用API可以认为是一种内部DSL实现。实现外部DSL相当于创造一个新的编程语言,根据领域表现力需求我们可以去定义它的词法规则、语法规则。我需要为外部DSL实现一个编译器,对它进行词法分析、语法法析、语义分析最后生成目标语言。实现外部DSL的理论基础是编译原理,在文章后面的部分提到的DSL指的是外部DSL。

为什么需要实现DSL

我们知道按照不同的抽象层次,计算机编程语言的抽象层次从高到低依次为,高级语言、汇编语言、机器语言。 抽象层次越高对人类越友好、表现力越强、执行性能也越差,与之相对的抽象层级越低对机器越友好、表现力越差、性能也越好。 而领域特定语言(DSL)在计算机编程语言的抽象层次中位于高级语言之上,实现DSL主要的目标是为了能够以更简单、更容易理解的方式完成我们的业务需求。为什么说抽象层次越高就越容易理解呢,就像这篇文章是站在一个比较高的层次讲DSL,并没有讨论过多的技术技术细节,所以理解起来也就不难。


理解Compiling(编译)和Transpiling(转译)

前后我们提到实现DSL的理论基础是编译原理,根据wikipedia的定义:编译器是将一种计算机语言编写的源程序转换成另一种计算机语言的计算机程序。通常编译器的主要任务就是将使用高级语言编写的源程序,编译成机器可识别的机器语言。要实现对源程序的编译,编译器需要经过以下的处理阶段,如图:


对于实现DSL来说有些不同,我们不需要关心底层的机器指令生成,一般做法先通过编译器前端将DSL解析为抽象语法树,再使用访问者模式和迭代器模式遍历抽象语法树生成目标代码,这里目标代码可能是另一种高级语言的源代码。Transpiling (转译)是一种特殊Compiling(编译), 用于将一种语言编写的源代码转换为另一种具有相同抽象层次的语言。比如使用babel将ES6 转换成ES5,使用tsc将typescript编译到javascript,


词法分析

词法分析器读入源语言字符流,生成token(单词)序列,token可以理解为一种数据结构,在token中包含了它在源程序中位置信息、类型信息(包含标识符、关键字,常量、操作符等)和Token对应的值。有穷自动机是词法分析的理论基础,对于给定的输入串如果能够从有穷自动的开始状态,经过状态转换器进行若干步骤状态状态,最终到达有穷自动机的终止状态。则说这个输入串能够被有穷自动机识别,有穷自动机每识别完成一个输入串会把它作为一个token加入到已经识别的token序列中。然后重新从开始状态继续识别后续的输入串,如果直到输入串的结尾都没有到达有穷自动的结束状态,则说明给定的源程序中包含词法错误


语法分析

语法分析的基本任务是读入词法分析产生的token序列,然后根据给定的文法构造语法分析树, 按照分析树构造方向分为自顶向下的语法分析和自底向上的语法分析。自顶向下的语法分析是从顶部根节点向底部叶节点构造分析树,自底向下的语法分析是从底部叶节点向顶部的根节点自底向上构造语法分析树。递归下降分析是最简单的自顶向下语法分析算法,根据文法的不同构造分析树的方法也不同,文法描述了语言的语法规则,一个文法G被定义为一个四元组,包含文法的开始符号用S表示, 终结符集用Vt表示,非终结符集用Vn表示,一组产生式用P表示,下面是一个文法的符号表示:


语法分析器生成器

我们可以根据编译原理手工实现一个DSL词法分析器和语法分析器,也可以使用一些语法分析器生成器工具自动成一个DSL词法分析和语法分析器。使用语法分析器生成器我们只需要定义DSL的词法规则和语法规则,然后调用编译器生成器的主程序即可以一个DSL语法分析器。词法法规则使用正则来定义,语法规则使用EBNF来定义,EBNF提供了一种定义上下文无关文法的一种方式。其中BISON是一个可以用来生成C++语言实现的语法分析器生成器,需要配合使用Flex生成的词法分析器,完成语法分析。其中ANTLR是一个能够生成Java、C++、Python等多中语言实现的语法分析器生成器,在前端领域也有一个类似的语法分析器生成器叫做JISON可以生成Javascript实现的语法分析器。在后面的文章中也会介绍一下如何使用JISON生成一个语法分析器