神刀安全网

如何撸一个领域语言

如何撸一个领域语言

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生成的类,并重写了 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

作者: 苏樽

【云栖快讯】直播预告:节省90%代码量,21天快速搭建推荐系统!  详情请点击

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » 如何撸一个领域语言

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址