如何撸一个领域语言
DSL概述
DSL是一种抽象的概念，泛指用在特定领域的语言。例如在数据库管理系统中，使用SQL增删改查数据库内容，在C++编译中，Makefile也是一种DSL，它专用来描述各个编译单元的依赖关系以及编译参数，以此规则控制编译器和链接器。
从实现方法上来分类，DSL分为内部和外部DSL。内部与外部，指的是实现DSL的方式是否与宿主语言隔离。就是所谓内部DSL，就是用一种提供语言扩展功能的宿主语言来扩充的。比如Clojure支持暴露语法树给程序开发者（quote/unquote），用户可以以此来扩充原有语言的功能。而外部DSL则与源语言无关，重头写词法分析器、语法分析器以及解释执行器。
DSL的一大特点就是可以提高效率。从设计层面上来说，可以隔离两个系统之间的代码依赖，将其转变为可配置的数据，因此能够快速响应业务需求，对原系统的改动也比较小。从开发角度来说，DSL使得程序员可以专注某个领域的逻辑，从而不必关心相关原理与细节。这样对程序员来说，学习成本变低，代码量变少，程序出错的可能性也降低。例如，操作数据库只需要学会SQL语言就可以了，而并不需要掌握数据库底层的实现原理。
本文的应用场景在一些主流语言（Java，JavaScript，C++，C#，Objective-C等）他们很少支持语言扩展功能，因此着重谈一谈如何开发一个外部DSL。
编译原理基础
词法分析和语法分析
既然要开发一个外部DSL，那就免不了要涉及编译原理相关的知识了。不过放心，我们不需要自己造轮子，那是个大工程，是非常缓慢也容易出错的。本文主要介绍使用ANTLR工具来实现语言的解析。但是关于编译原理，我们还是得复习一下它的基本概念。
一个完整的编译器包括词法分析、语法分析、语义分析、源代码优化、代码生成、目标代码优化等步骤。词法分析和语法分析是编写一个外部DSL所必须涉及的部分。词法分析的输入是源程序字符串，其功能是一个一个字符地读取字符串，从中识别出标识符、关键字、常量等相对独立的记号（Token），形成记号流的过程。例如c,l,a,s,s五个字符构成了class关键字，2,3构成了整数23。词法分析器会过滤掉换行，空格，注释与程序处理无关的字符，并将记号（Token）归类。
语法分析是根据词法分析出的记号流，分析出源程序的语法结构，并按照语法结构生成语法树的过程。语法树的叶子节点就是词法分析得到的记号。例如，有下面源程序：
class T {
string Name;
object GetValue() {
}
}
经过词法分析之后的结果为：
class T { string Name ; object GetValue ( ) { } }
而语法分析之后的结果为：
文法
文法是描述语言规则的工具。文法最初是一些研究自然语言的科学家总结指定的，后来被应用到计算机语言中。下面这个例子定义了人类的语法规则。
语言 =>（句子）+
句子 => 主语 谓语
谓语 => 动词 宾语
主语 => 名词
宾语 => 名词
名词 =>‘张三’| ‘代码’
动词 =>‘编写’
如 ，‘张三编写代码’这句话在文法中按照LL的推导规则，其过程是：
语言 => 主语 谓语
=> 张三 动词宾语
=> 张三 编写名词
=> 张三 编写 代码
ANTLR
ANTLR是一种自动生成词法分析器、语法分析器的工具。利用它，我们不用关注词法分析和语法分析的细节。只需要描述语言的文法，将其作为输入传递给ANTLR，便可以自动生成词法分析器和语法分析器。ANTLR由Java语言写成，但是可以支持其它的目标语言，也就是，它可以生成C++、JavaScript等语言的词法分析和语法分析程序。
ANTLR有以下特点：
- Easy：自动完成词法分析和语法分析。应用程序所做的，仅仅是遍历解析树。
- 直观的文法描述：只要会写正则表达式，就能写文法。可维护性强。
- 强大的功能： LL(*)语法分析器。
- 目标代码的可读性与可扩展性：listener以及visitor遍历方式。
- 多语言target：支持大多数主流语言。
- 带有开发IDE： AntlrWorks。
- 被广泛使用： IDEA、Hibernate、Groovy、OpenJDK、Weblogic、Hive等语言都用到了它。
ANTLR的安装和使用
在ANTLR中，可以用一个jar包搞定以下事情：
- testRig测试工具
- 目标代码生成工具
- 解析程序依赖的库
testRig测试工具输入一段符合用户定义文法的代码，输出语法树。
ANTLR会自动帮我们生成词法分析器和语法分析器，但是这两个分析器均依赖于ANTLR-Runtime代码，在Java语言里，jar包包括了Runtime代码。如果是其它目标语言，需要下载对应的Runtime。
安装ANTLR很简单，只需要从官网下载一个jar包即可。然后设置相关的命令行参数。
ANTLR工作流程
ANTLR的工作流程可以由下图表示：
语言识别器（ANTLR库）在执行的过程中，输入用户的DSL字符串，然后经过词法分析，分割成独立的token单元，然后经过语法解析器生成解析树。解析树上包含了文法规则以及词法单元。
ANTLR文法定义
文法结构
ANTLR库输入文法（.g 或者 .g4 文件），然后将文法转换为目标语言的源代码。如下图所示，文法定义的结构按照下图线条形式转换为响应的目标语言代码：
一个示例文法
grammar Expr;
program: statement;
statement: expression NEWLINE;
expression : multExpr (('+' | '-') multExpr)* ;
multExpr : atom (('*' | '/') atom)* ;
atom: '(' expression ')' | INT;
ID : ('a'..'z' |'A'..'Z')+ ;
INT : '0'..'9' + ;
NEWLINE:'\r'? '\n' ;
WS : (' ' |'\t' |'\n' |'\r' )+ -> skip;
上面的代码是一个示例文法。开头的第一行使用grammar关键字定义了文法的名称为Expr，这个名称也必须跟文法文件（g4文件）一致。 文法由词法规则和语法规则组成，其格式为：规则名 : 规则内容 ; 规则名与规则内容用冒号分割，每一条规则以分号分隔。规则名可以用户自定义。文法规则要求规则名的第一个字符必须为大写，上述代码中，ID,INT,NEWLINE,WS均为文法规则。语法规则要求第一个字符必须小写。
在文法规则中，可以使用类似正则表达式的描述来表达重复。
例如，在ID词法规则中，用 “ .. ” 来描述了 a到z这26个字母。ID词法规则也使用 | 以及+号运算符来表达ID是由一个或者多个大写字母或者小写字母组成。其它的规则类似正则表达式。
在语法规则中，以空格来表示各个子规则之间的“并且”关系。例如 statement: expression NEWLINE; 这条规则规定了statement必须由expression语法单元和一个NEWLINE词法单元组成，并且expression的顺序在NEWLINE之前。
常见的规则表示：
- 空格连接符： 表示顺序连接
- | 选择符： 表示或者的关系
- 重复次数： + *
- 可选： ？
- 子规则： ( )
- 注释： // /* */
- 语法规则： 小写字母开头
- 词法规则： 大写字母开头
上述文法，如果输入“1+2*3/(4+5)”这段“DSL”，则会生成下图所示的解析树。
可以看出，叶子节点为词法单元的值，除了叶子节点，其它节点的内容都为语法名称。
避免左递归
由于ANTLR的语法分析器是LL型的，所以当它遇到左递归的文法时，会导致解析器无限递归，最终堆栈溢出，所以最好在文法层面使用 * + 等规则来表示重复。也可以将规则代入公式，算出等价的非左递归文法。
例如，有以下文法：
a : (a A) | B;
A : '3';
B : '4';
当输入为4333时，会造成解析器堆栈溢出。
解决方法：改写文法为：
a : Bc;
c : Ac | ;
又因为 c : Ac | ; 等价于 c: A*，所以目标文法可以改写成： a : BA*
生成解析程序
ANTLR生成解析程序很简单，只要以文法路径作为参数运行一下jar包即可。
java -jar antlr-4.5.2-complete.jar Expr.g4
这条命令会生成默认以Listener方式遍历解析树的代码。可以通过命令行参数来控制生成选项：
- -DLanguageName 生成LanguageName的目标处理程序，例如-DJavaScript
- -visitor 生成visitor模式遍历解析树的基类代码
- -listener 生成listener模式遍历解析树的基类代码
关于Listener与Visitor的区别，下文会介绍。
使用-visitor参数运行这条命令之后，ANTLR会帮我们生成下列文件：
- .tokens文件：按行分隔的词素列表及其类型。
- ExprListener：遍历解析树所需要的Listener接口。
- ExprBaseListener：实现Listener接口的具体类。 （Adapter模式（缺省适配器））
- ExprVisitor： 使用Visitor模式遍历解析树的接口。
- ExprBaseVisitor：实现Visitor接口的具体类。
- ExprLexer： 词法分析器。
- ExprParser：语法分析器。
解释执行DSL
Context
解释执行DSL的过程中一个重要的步骤就是遍历语法树。ANTLR会为我们在文法中写的每个语法规则生成一个对应的Context，如下图所示。
Context对象包含以下内容：
语法分析时生成
- 起始Token，终止Token
- 通过Token中的行号：列号可以在解释DSL出错的时候给用户提示
- 类型，text：通过类型和text可以获得Token匹配的内容。
- children： 可以得到子语法规则中的内容。
- 异常信息： 可以得到解析失败的信息。
ANTLR为每个子规则创建一个同名函数，因此可以方便地取到其子规则的context。例如我们的statement语法规则包含expression子规则，在上图中可以看到，生成了这样的同名函数，它返回的是expression的Context。
遍历解析树
遍历解析树有两种方式，一种是Listener，另一种是Visitor。对于Listener来说，ANTLR会生成以下结构的代码：
可以看出，它为每个语法规则都生成了匹配的enter/exit 方法，并且将Context作为参数传递进去。
Listener模式是一种被动遍历模式。遍历过程在ANTLR库中，用户调用开始遍历代码之后，ANTLR将会按照文法规则递归下降地遍历语法树，在遇到语法单元的前后分别调用enter和exit方法。遍历过程由下图所示。
Listener的遍历模式虽然简单，但是不可人为控制访问过程，并且逻辑分散在enter/exit两个方法中，对于编写遍历程序有所不便，因此有另一种Visitor模式可以选择。
Visitor模式为每个语法规则生成了一个visit方法，参数为对应的Context。其缺省实现为直接visitChildren。我们可以人为地控制visitChild的时间，并且在此前后做一些事情。
@Override
public T visitProgram(ProgramContext ctx) {
// before visit, doing something
T result = visitChildren(ctx);
// after visit, doing something
return result;
}
此外，Visitor类还提供一个泛型参数T，这个参数用来返回visit的结果。我们在下文中将会演示如何使用它。
示例
理解了上文所述的知识点之后，此时我们应该可以开发出上文的Expr文法对应的解析程序了。
在下面的例子中，我们继承了ExprBaseVisitor这个ANTLR生成的类，并重写了visitExpression, visitMultExpr,visitAtom这几个方法。从visitAtom看起，我们先通过使用自动生成的与语法规则同名的expression()来判断用户输入的DSL解析之后的语法节点中是否含有expression规则，如果没有，那么直接取词法单元的文本，并将其转化为Double。如果有expression，则调用visit方法递归地进行解析。
在visitExpression()中，我们通过ctx.children来获取词法规则expression : multExpr (('+' | '-') multExpr)* ;中*号匹配的多重子规则项，然后判断Context的类型是否为TerminalNode来得知child究竟是词法单元还是语法单元，如果是词法单元，则得到操作方法是加好还是减号，如果是语法单元，则递归下降地继续求值。
private static class MyVisitor extends ExprBaseVisitor<Double>{
@Override
public Double visitProgram(ExprParser.ProgramContext ctx) {
return super.visitProgram(ctx);
}
@Override
public Double visitStatement(ExprParser.StatementContext ctx) {
return super.visitStatement(ctx);
}
@Override
public Double visitExpression(ExprParser.ExpressionContext ctx) {
String lastOp = "+";
double result = 0;
for (ParseTree child : ctx.children){
if (child instanceof TerminalNode){
lastOp = child.getText();
continue;
}
ExprParser.MultExprContext context = (ExprParser.MultExprContext)child;
switch (lastOp) {
case "+":
result += visitMultExpr(context);
break;
case "-":
result -= visitMultExpr(context);
break;
default:
assert false : "invalid operation type";
break;
}
}
return result;
}
@Override
public Double visitMultExpr(ExprParser.MultExprContext ctx) {
double result = 1;
String lastOp = "*";
for (ParseTree child : ctx.children){
if (child instanceof TerminalNode){
lastOp = child.getText();
continue;
}
ExprParser.AtomContext atomContext = (ExprParser.AtomContext)child;
switch (lastOp) {
case "*":
result *= visitAtom(atomContext);
break;
case "/":
result /= visitAtom(atomContext);
break;
default:
assert false : "invalid operation type";
break;
}
}
return result;
}
@Override
public Double visitAtom(ExprParser.AtomContext ctx) {
if (ctx.expression() != null){
return visitExpression(ctx.expression());
}
else{
return Double.parseDouble(ctx.INT().getText());
}
}
}
调用ANTLR进行解析也很简单，首先将DSL文本作为构造函数参数传递给ANTLRInputStream，然后调用生成的ExprLexer进行词法分析，再把词法分析的结果（tokens）传递给ExprParser进行语法分析，然后调用语法分析的规则名称获取对应规则的解析树，接着对解析树进行遍历。
private static void antlrTest(){
String sentence = "1+2*3/(4+5)\n";
ExprLexer lexer = new ExprLexer(new ANTLRInputStream(sentence));
CommonTokenStream tokens = new CommonTokenStream(lexer);
ExprParser parser = new ExprParser(tokens);
ExprParser.ProgramContext context = parser.program();
MyVisitor visitor = new MyVisitor();
double result = visitor.visit(context);
System.out.println("result=" + result);
}
更多资料
- 关于Clojure/LISP提供的扩充自己语言，以实现内部DSL，可以参考这篇文章：https://zhuanlan.zhihu.com/p/20754002
- IBM的DeveloperWorks有一篇文章，介绍了ANTLR的一些高级用法，比如类型检查、代码生成。甚至实现了一个虚拟机来执行生成之后的代码，地址是：https://www.ibm.com/developerworks/cn/java/j-lo-antlr-fullapp/
知其所以然
关于ANTLR，如果想要了解更多，可以阅读《The Definitive ANTLR 4 Reference》，ANTLR的作者也写了另一本书描述ANTLR的原理，叫做《编程语言实现模式》。上面的两本书都比较侧重实践。如果想继续深入研究编译原理的理论知识，可以参考《编译原理》。前两本书如果读懂了，再读第三本书也不会太费力，因为此时你已经有了很多感性认识了。
转载自：ATA
作者：苏樽
