首页 > 业界 > 如何撸一个领域语言
2016
06-03

如何撸一个领域语言

  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 ( ) { } }

  而语法分析之后的结果为:
如何撸一个领域语言 - 同创卓越 - 1

  文法

  文法是描述语言规则的工具。文法最初是一些研究自然语言的科学家总结指定的,后来被应用到计算机语言中。下面这个例子定义了人类的语法规则。

语言 =>(句子)+
句子 => 主语谓语
谓语 => 动词宾语
主语 => 名词
宾语 => 名词
名词 =>‘张三’| ‘代码’
动词 =>‘编写’

  如 ,‘张三编写代码’这句话在文法中按照 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 包即可。然后设置相关的命令行参数。

如何撸一个领域语言 - 同创卓越 - 2

  ANTLR 工作流程

  ANTLR 的工作流程可以由下图表示:
如何撸一个领域语言 - 同创卓越 - 3

  语言识别器(ANTLR 库)在执行的过程中,输入用户的 DSL 字符串,然后经过词法分析,分割成独立的 token 单元,然后经过语法解析器生成解析树。解析树上包含了文法规则以及词法单元。

  ANTLR 文法定义

  文法结构

  ANTLR 库输入文法(.g 或者 .g4 文件),然后将文法转换为目标语言的源代码。如下图所示,文法定义的结构按照下图线条形式转换为响应的目标语言代码:

如何撸一个领域语言 - 同创卓越 - 4
如何撸一个领域语言 - 同创卓越 - 5

  一个示例文法

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”,则会生成下图所示的解析树。

如何撸一个领域语言 - 同创卓越 - 6

  可以看出,叶子节点为词法单元的值,除了叶子节点,其它节点的内容都为语法名称。

  避免左递归

  由于 ANTLR 的语法分析器是 LL 型的,所以当它遇到左递归的文法时,会导致解析器无限递归,最终堆栈溢出,所以最好在文法层面使用 * + 等规则来表示重复。也可以将规则代入公式,算出等价的非左递归文法。
如何撸一个领域语言 - 同创卓越 - 7

  例如,有以下文法:

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 会帮我们生成下列文件:

如何撸一个领域语言 - 同创卓越 - 8

  • .tokens 文件:按行分隔的词素列表及其类型。
  • ExprListener:遍历解析树所需要的 Listener 接口。
  • ExprBaseListener:实现 Listener 接口的具体类。 (Adapter 模式(缺省适配器))
  • ExprVisitor: 使用 Visitor 模式遍历解析树的接口。
  • ExprBaseVisitor:实现 Visitor 接口的具体类。
  • ExprLexer: 词法分析器。
  • ExprParser:语法分析器。

  解释执行 DSL

  Context

  解释执行 DSL 的过程中一个重要的步骤就是遍历语法树。ANTLR 会为我们在文法中写的每个语法规则生成一个对应的 Context,如下图所示。
如何撸一个领域语言 - 同创卓越 - 9

  Context 对象包含以下内容:

  语法分析时生成

  • 起始 Token,终止 Token
  • 通过 Token 中的行号:列号可以在解释 DSL 出错的时候给用户提示
  • 类型,text:通过类型和 text 可以获得 Token 匹配的内容。
  • children: 可以得到子语法规则中的内容。
  • 异常信息: 可以得到解析失败的信息。

如何撸一个领域语言 - 同创卓越 - 10

  ANTLR 为每个子规则创建一个同名函数,因此可以方便地取到其子规则的 context。例如我们的 statement 语法规则包含 expression 子规则,在上图中可以看到,生成了这样的同名函数,它返回的是 expression 的 Context。

  遍历解析树

  遍历解析树有两种方式,一种是 Listener,另一种是 Visitor。对于 Listener 来说,ANTLR 会生成以下结构的代码:

如何撸一个领域语言 - 同创卓越 - 11
  可以看出,它为每个语法规则都生成了匹配的 enter/exit 方法,并且将 Context 作为参数传递进去。

  Listener 模式是一种被动遍历模式。遍历过程在 ANTLR 库中,用户调用开始遍历代码之后,ANTLR 将会按照文法规则递归下降地遍历语法树,在遇到语法单元的前后分别调用 enter 和 exit 方法。遍历过程由下图所示。

如何撸一个领域语言 - 同创卓越 - 12

  Listener 的遍历模式虽然简单,但是不可人为控制访问过程,并且逻辑分散在 enter/exit 两个方法中,对于编写遍历程序有所不便,因此有另一种 Visitor 模式可以选择。

如何撸一个领域语言 - 同创卓越 - 13

  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 的结果。我们在下文中将会演示如何使用它。
如何撸一个领域语言 - 同创卓越 - 14

  示例

  理解了上文所述的知识点之后,此时我们应该可以开发出上文的 Expr 文法对应的解析程序了。

  在下面的例子中,我们继承了ExprBaseVisitor这个 ANTLR 生成的类,并重写了visitExpressionvisitMultExpr,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);
    }

  更多资料

  知其所以然

  关于 ANTLR,如果想要了解更多,可以阅读《The Definitive ANTLR 4 Reference》,ANTLR 的作者也写了另一本书描述 ANTLR 的原理,叫做《编程语言实现模式》。上面的两本书都比较侧重实践。如果想继续深入研究编译原理的理论知识,可以参考《编译原理》。前两本书如果读懂了,再读第三本书也不会太费力,因为此时你已经有了很多感性认识了。

  转载自:ATA

  作者:苏樽 

来自: ATA
 
最后编辑:
作者:同创卓越
这个作者貌似有点懒,什么都没有留下。

留下一个回复

你的email不会被公开。