标签 DSL 下的文章

手把手教你使用ANTLR和Go实现一门DSL语言(第一部分):设计DSL语法与文法

本文永久链接 – https://tonybai.com/2022/05/24/an-example-of-implement-dsl-using-antlr-and-go-part1

《使用ANTLR和Go实现DSL入门》一文中,我们了解了DSL与通用编程语言(GPL)的差异、DSL解析器生成工具选择以及ANTLR文法的简要书写规则,并和大家一起完成了一个CSV解析器的例子。看完上述文章后,你是不是有了打造属于自己的DSL的冲动了呢!

那么究竟该如何设计和实现一门自己的DSL呢?在这个系列文章中,我将“手把手”地和大家一起看看设计和实现一门DSL(这里主要指外部DSL)的全流程。

结合Martin Fowler在《领域特定语言》一书中的建议,我将设计与实现一门外部DSL的过程分为如下几个步骤:


图:外部DSL设计与实现的步骤

本文是系列文章的第一篇,在这一篇中,我将先来说说前三个步骤,即为某一特定领域设计一门DSL的语法(syntax)、并编写可以解析该DSL的ANTLR文法(grammar),生成该DSL语法的解析器并验证ANTLR文法的正确性。

到这里有朋友可能会问:“一会儿文法,一会儿又语法,它们到底有啥区别?”,别急!在设计这门DSL语法之前,我先来和大家一起简单理解一下文法与语法的区别。

一. 文法(grammar)和语法(syntax)


图:文法与语法的比较

如上图所示,语法是面向使用该编程语言的应用开发者的,就像Go语法面向的是Gopher;而文法则是面向这门编程语言的编译器或解释器(Interpreter)的核心开发者的

我们通常用自然语言描述编程语言的语法,这样的文档一般被称为该编程语言的语言规范(language specification),比如用于描述Go语法的Go语言规范

但自然语言通常是不精确的,有时带有歧义。为了给出更为精确的语法描述,编程语言规范通常也会有采用某种形式语言(比如:EBNF)表示的关于这门语言语法所对应的文法,比如在Go语言规范中,我们就能看到用EBNF所描述的文法:

SourceFile       = PackageClause ";" { ImportDecl ";" } { TopLevelDecl ";" } .
PackageClause    = "package" PackageName .
PackageName      = identifier .
ImportDecl       = "import" ( ImportSpec | "(" { ImportSpec ";" } ")" ) .
ImportSpec       = [ "." | PackageName ] ImportPath .
ImportPath       = string_lit .
... ...

通常应用开发人员是不会关心这些夹带在语言规范文档中的文法描述的,只有当规范中的说明有歧义时,开发人员才会根据文法中的产生式规则去推导语法的合规形式的,当然了这一推导过程是比较“痛苦”的。

到这里,结合我们在《使用ANTLR和Go实现DSL入门》一文中的说明,我们进一步明确了文法就是一组规则,这组规则告诉我们如何将文本流转换为语法树。如果转换失败,说明文本流中存在不符合编程语言语法的地方。

此外,用于描述一门编程语言语法的文法可以不止一种,每种形式语言工具都有自己的表示形式,比如针对Go语言语法,我们可以使用EBNF给出形式化的文法,也可以使用ANTLR专用的形式化文法。

到这里,你对文法与语法的概念是不是更深刻一些了呢!不过这时可能会有朋友站出来提问:设计一门编程语言或DSL,是先设计语法还是先设计文法呢

在语言设计伊始,语法和文法设计的边界其实并非那么清晰。讨论语法是为了确定文法做准备,而一旦确定了一版文法,语法的使用形式又被进一步精确了。在编程语言/DSL设计过程中,语法与文法是交替螺旋上升的。简单的DSL语言,可能一轮迭代就完成了全部设计。复杂的通用编程语言可能要反复针对语法讨论多次,确定下来后,才会编写出新一版本的文法,依次反复迭代。

不过通常来说我们会先确定一版语言的语法,写出一些采用此版语言语法的样例源文件,供后续文法以及生成的解析器(Parser)验证使用。回顾Go语言的历史,我们会发现Go语言创世团队当初也是这么做的。Robert Griesemer、Rob Pike和Ken Thompson这三位大佬在Google总部的一间会议室里首先进行了一场有关Go具体设计的会议。会后的第二天,Robert Griesemer发出了一封题为“prog lang discussion”的电邮,这封电邮便成为了这门新语言的第一版设计稿,三位大佬在这门语言的一些基础语法特性与形式上达成了初步一致:

Date: Sun, 23 Sep 2007 23:33:41 -0700
From: "Robert Griesemer" <gri@google.com>
To: "Rob 'Commander' Pike" <r@google.com>, ken@google.com
Subject: prog lang discussion
...
*** General:
Starting point: C, fix some obvious flaws, remove crud, add a few missing features
  - no includes, instead: import
  - no macros (do we need something instead?)
  - ideally only one file instead of a .h and .c file, module interface
should be extracted automatically
  - statements: like in C, though should fix 'switch' statement
  - expressions: like in C, though with caveats (do we need ',' expressions?)
  - essentially strongly typed, but probably w/ support for runtime types
  - want arrays with bounds checking on always (except perhaps in 'unsafe mode'-see section on GC)
  - mechanism to hook up GC (I think that most code can live w/ GC, but for a true systems
    programming language there should be mode w/ full control over memory allocation)
  - support for interfaces (differentiate between concrete, or implementation types, and abstract,
    or interface types)
  - support for nested and anonymous functions/closures (don't pay if not used)
  - a simple compiler should be able to generate decent code
  - the various language mechanisms should result in predictable code
...

基于这版设计,2008年初,Unix之父Ken Thompson实现了第一版Go编译器(文法相关),用于验证之前的语法设计。

好了,在理解了文法与语法的区别后,接下来,我们就来为某一特定领域创建一门DSL语言,我们先来介绍一下这门DSL的背景与语法设计。

注:以上提到的对文法与语法的理解仅限于计算机编程语言领域,并不一定适合自然语言领域(自然语言领域也有文法与语法的概念)。

二. 为《后天》中的气象学家设计一门DSL

注:下面只是一个虚构的领域例子,大家无需在其合理性、可行性、科学性与严谨性上产生质疑:)。

如果你看过灾难片专业户罗兰·艾默里奇指导的美国灾难题材电影《后天》,你肯定会对电影里发生的威胁人类文明的灾难情节记忆犹新。不过《后天》里的情节其实离我们并不“遥远”,尤其是进入二十一世纪以来,极端异常天气在全球各个地区屡屡发生:两极高温冰川消融、北美陆地飓风以及我国2021年华北地区的极端降水等等。各国的气象学家、地球物理科学家们都在努力破解这些极端天气背后的原因,并预测全球气候的走势。他们在全球设置了诸多气象数据的采集装置,就像《后天》中部署在大西洋上的浮标那样,7×24小时地监视着“地球的生命体征”。

像浮标这样的采集装置内置采集程序,按照设定的规则定期向中心上报数据或发送异常事件信息。不过浮标一般都是无人值守的,一旦投放,便很难维护。一旦要进行程序升级,比如更新采集数据与上报事件的规则,就比较麻烦了。

如果我们为像浮标这样的采集装置设计一门DSL,让这些装置内置某种DSL引擎,这样变更采集和报警规则只需给装置远程传送一个极小数据量的规则文件即可完成升级,采集装置将按照新规则上报数据和事件。

好了,领域背景介绍完了,下面我们就来为气象学家们分忧,帮助他们设计一门DSL语言,用于“指挥”像浮标这样的数据收集装置按照气象学家们设定的规则上报数据与事件。

三. DSL语言的语法样例

我们先来构思一下这门DSL的语法。什么样的DSL是好DSL?没有固定的评价标准。

  • 自然语言 vs. 编程语言

有人说DSL是给领域专家用的,应该更贴近自然语言一些,但实际情况是DSL更多还是开发人员/测试人员去写,或有开发经验的领域专家使用。所以在《领域特定语言》一书的第二章末尾,Martin Fowler给出关于DSL的特别警示:不要试图让DSL读起来像自然语言。牢记,DSL是一种程序设计语言

使用DSL更像是在编程,而不是写小说。同自然语言相比,像DSL这样的程序设计语言的目标是简洁、清晰与精确

  • 一门大的DSL vs. 多门小的DSL

DSL正如其名,是领域相关的。绝大多数DSL都是非常简单、非常小的“编程语言”,比如一个算术表达式求值语言,再比如DSL一书中格兰特小姐的控制器状态机等。

但DSL始终存在演化成庞然大物-一门图灵完备的通用编程语言的风险,这个是要极力避免的。那么怎么识别这种风险呢?Martin Fowler告诉我们:如果一个系统整体都是用一门DSL实现的,那么这门DSL就成为了事实上的通用编程语言了。更佳的作法是切分领域,为不同领域构建不同的DSL,而不要构建一门DSL用于所有领域

好了,到这里我们先了解一下虚构例子的领域需求,我们需要为这样的一个无人值守的海洋浮标设备设计一门DSL,DSL可用于描述采集设备数据采集与上报的规则。

科学家们对设备的采集能力描述如下:

  • 可通过传感器周期性(默认间隔一分钟)获取所在坐标位置的大气温度、水温、水流速、盐度、….等物理指标;
  • 可对传感器实时获取到的各种物理指标信息进行一元运算(向下取整、向上取整、绝对值)、算术运算(加减乘除取模)、关系运算(大于、小于…)、逻辑运算(与、或) ,构造混合这些运算的条件,当条件为真时,上报指定的物理指标信息;
  • 可结合采集设备缓存的历史时刻数据(缓存能力有限,最大300分钟,即300条数据)进行综合条件判定,这里将其定义为窗口计算,判定策略包括:都不满足、全部满足和至少一项满足。

面对这样的需求,我们怎么定义DSL的语法呢?外部DSL的语法设计往往会受到设计者对以往的编程语言的使用经验的影响。很多开发人员都会从自己熟悉的编程语言的语法中“借鉴”一些语法元素来构成自己的DSL。下面是我设计的一组语法样例:

r0001: Each { || $speed > 30 } => ("speed", "temperature", "salinity");

r0002: None { |,30| $temperature > 5 } => ("speed", "temperature", "salinity");

r0003: None { |3,| $temperature > 10 } => ("speed", "temperature", "salinity");

r0004: Any { |11,30| ($speed < 5) and ($temperature < 2) and (roundUp($salinity) < 600) } => ("speed", "temperature", "salinity");

r0005: Each { |,| (($speed < 5) and (($temperature + 1) < 10)) or ((roundDown($speed) <= 10) and (roundUp($salinity) >= 500))} => ();

到这里,一些童鞋会惊讶到DSL的简单,没错!就像前面所说的,DSL就应该简单、清晰和表意精确

下面我来对上面的语法样例做个简单说明:

  • 一条规则占用一行,以ruleID开头,以分号结尾;
  • ruleID与rule body之间通过冒号分隔;
  • rule body借鉴了Ruby语言中的迭代器语法:
#!/usr/bin/ruby

a = [1,2,3,4,5]
b = Array.new
b = a.collect{ |x| x <= 4 }
puts b

输出:

true
true
true
true
false

在上面ruby的这种迭代器语法中,collect迭代器会将迭代数组a中每个元素,并针对每个元素进行x <= 4的求值,求值结果存储在b中对应的元素位置上。我借鉴了这种形式的语法,形成支持窗口计算和表达式求值的语法。以下面语法为例:

r0001: Each { |1,5| $speed > 30 } => ("speed", "temperature", "salinity");

这个规则的含义是:当窗口数据,从第1项到第5项数据中的speed指标都大于30时,输出并上报当前最新的speed、temperature和salinity指标数据。

Each是对窗口满足策略的判定,Each表示窗口数据中每一项都符合后面的条件表达式;其他两个判定词是None和Any,None表示窗口数据中没有一项满足后面的条件表达式;Any表示窗口数据中有一项满足后面的条件表达式即可。

Each后面的大括号中放置了窗口范围以及条件表达式。

两个竖线表示要参与求值的窗口数据,窗口表示的标准形式为|low, high|,low和high是下标值(下标从1开始),表示的窗口范围为:[low, high]。当省略low时,比如:|, high|表示的窗口范围为|1, high|;当low与high相同时,比如:|n, n|表示只有下标为n这一个元素参与后续求值;当省略high时,比如:|low, |表示窗口范围为|low, max|,其中max为默认设置的窗口的大小;当low与high都省略,但保留逗号时,比如:|,|,表示窗口中所有数据;当low与high都省略,逗号也省略时,比如:||,则表示|1,1|,即窗口中最新的那条数据。这种设计也部分借鉴了Go的切片下标的语法。

窗口后面条件表达式的求值结果要么为true,要么为false。其支持的运算符可以参考r0005规则。物理指标用$+指标名字表示,比如$speed。

当整个规则求值结果为真时,输出窗口中最新数据的speed、temperature和salinity这三个指标。如果最后输出指标的元组为空,则代表输出所有指标。

好了,大致确定了DSL语法后,我们就来根据语法样例编写对应ANTLR文法。

四. 为DSL编写ANTLR文法

在之前的文章中,我们也提到过,ANTLR文法规则存储在以.g4为后缀的文件中,文件名要与文件内的grammar关键字后面的名字保持一致,比如我们的文件名为Tdat.g4,那么该文件中grammar后面也必须是Tdat:

// the grammar for tdat RuleEngine
grammar Tdat;

注意:如果生成的解析器的目标语言为Go,那么ANTLR文法文件名必须要大写,否则生成的一些重要的结构无法被导出。

每个ANTLR文法文件都需要一个起始语法解析规则(parser rule),在Tdat.g4中,我们的起始规则为prog:

// the first parser rule, also the first rule of RuleEngine grammar
// prog is a sequence of rule lines.

prog
    : ruleLine+
    ;

正如prog规则的注释那样,一个采集装置的完整规则文件是由一组(至少包含一条)规则行(ruleLine)组成。而每个ruleLine的组成模式也非常固定:

ruleLine
    : ruleID ':' enumerableFunc '{' windowsRange conditionExpr '}' '=>' result ';'
    ;

大家可以对照着前面语法样例来理解ruleLine这个规则。接下来我们自顶向下(从左向右)的将各个组成部分的规则逐一定义就好了。先来看ruleID这个最简单的规则:

  • ruleID就是以字母开头,由数字与数字组成的文本:
ruleID
    : ID
    ;

// the first char of ID must be a letter
ID
    : ID_LETTER (ID_LETTER | DIGIT)*
    ;

fragment
ID_LETTER
    : 'a'..'z'|'A'..'Z'|'_'  // [a-zA-Z_]
    ;

fragment
DIGIT
    : [0-9]  // match single digit
    ;

像ID这样的词法规则,大家其实无需自己去从头编写,《ANTLR 4权威指南》antlr/grammar-v4中有大量样例可供参考。

  • enumerableFunc就是窗口判定策略,这里直接将Each、None和Any定为语言的关键字了:
enumerableFunc
    : 'Each'
    | 'None'
    | 'Any'
    ;
  • windowsRange是窗口规则,它有两个候选产生式:
windowsRange
    : '|' INT? '|'          #WindowsWithSingleOrZeroIndex
    | '|' INT? ',' INT? '|' #WindowsWithLowAndHighIndex
    ;

为了便于后续解析,这里用#为每个产生式起了一个名字,这样后续ANTLR在基于Tdat.g4生成Parser代码时,就会单独针对每个名字生成一对EnterXXX和ExitXXX(以listener模式下为例),便于我们解析。当然这里你还可以拆分的更细碎一些以进一步减少在处理Parser规则时自己写代码做判断的工作量。

  • conditionExpr是这里最复杂的parser规则,它的求值结果永远是true或false,因此我将其产生式规则定义如下:
conditionExpr
    : conditionExpr logicalOp conditionExpr
    | '(' conditionExpr ')'
    | primaryExpr comparisonOp primaryExpr
    ;

我们看到:conditionExpr规则有三个候选产生式,它可以是带括号的自身,支持自身通过逻辑操作符(and和or)的运算,也可以是经由比较操作符计算(比如>、<等)的普通表达式(primaryExpr)。

而普通表达式(primaryExpr)同样可以是带括号的自身,可以是经由算术运算符(比如:加减乘除等)计算的普通表达式,可以是单一的指标(METRIC),可以是经由一元内置函数(比如:roundUp、abs等)计算的普通表达式,当然也可以仅仅是一个字面值(literal)。literal字面值支持整型、浮点(非科学记数法表示形式)和字符串(双引号括起的文本):

primaryExpr
    : '(' primaryExpr ')'                  #BracketExprInPrimaryExpr
    | primaryExpr arithmeticOp primaryExpr #ArithmeticExprInPrimaryExpr
    | METRIC                               #MetricInPrimaryExpr
    | builtin '(' primaryExpr ')'          #BuildinExprInPrimaryExpr
    | literal                              #RightLiteralInPrimaryExpr
    ;

arithmeticOp
    : '+'
    | '-'
    | '*'
    | '/'
    | '%'
    ;

builtin
    : 'roundUp'
    | 'roundDown'
    | 'abs'
    ;

logicalOp
    : 'or'
    | 'and'
    ;

comparisonOp
    : '<'
    | '>'
    | '<='
    | '>='
    | '=='
    | '!='
    ;

METRIC
    : '$' ID // match $speed
    ;

INT
    : DIGIT+
    ;

FLOAT
    : DIGIT+ '.' DIGIT* // match 1. 39. 3.14159 etc...
    | '.' DIGIT+        // match .1 .14159
    ;

STRING
    : '"' (ESC|.)*? '"'
    ;
  • result规则定义了声明输出指标的形式,它是一个小括号表示的元组,指标间用逗号分隔,如果元组为空,则表示输出所有指标。
result
    : '(' STRING (',' STRING)* ')' # ResultWithElements
    | '(' ')'                      # ResultWithoutElements
    ;

好了,到这里针对这门DSL的ANTLR文法也编写完了。

五. 小结

在这一篇中,我们了解了开发一门DSL的基本流程,我们以一门为气象科学家打造的DSL为示例,和大家一起为该DSL设计了语法样例,并用ANTLR4的文法规则定义了这门DSL。

那么这个文法是否能被ANTLR正确解析并生成目标代码?通过这个文法能否正确识别出前面我们给出的语法样例呢?在下一篇“文法验证”中我将给大家揭晓答案。

本文中涉及的代码可以在这里下载 – https://github.com/bigwhite/experiments/tree/master/antlr/tdat 。


“Gopher部落”知识星球旨在打造一个精品Go学习和进阶社群!高品质首发Go技术文章,“三天”首发阅读权,每年两期Go语言发展现状分析,每天提前1小时阅读到新鲜的Gopher日报,网课、技术专栏、图书内容前瞻,六小时内必答保证等满足你关于Go语言生态的所有需求!2022年,Gopher部落全面改版,将持续分享Go语言与Go应用领域的知识、技巧与实践,并增加诸多互动形式。欢迎大家加入!

img{512x368}
img{512x368}

img{512x368}
img{512x368}
img{512x368}

我爱发短信:企业级短信平台定制开发专家 https://tonybai.com/。smspush : 可部署在企业内部的定制化短信平台,三网覆盖,不惧大并发接入,可定制扩展; 短信内容你来定,不再受约束, 接口丰富,支持长短信,签名可选。2020年4月8日,中国三大电信运营商联合发布《5G消息白皮书》,51短信平台也会全新升级到“51商用消息平台”,全面支持5G RCS消息。

著名云主机服务厂商DigitalOcean发布最新的主机计划,入门级Droplet配置升级为:1 core CPU、1G内存、25G高速SSD,价格5$/月。有使用DigitalOcean需求的朋友,可以打开这个链接地址:https://m.do.co/c/bff6eed92687 开启你的DO主机之路。

Gopher Daily(Gopher每日新闻)归档仓库 – https://github.com/bigwhite/gopherdaily

我的联系方式:

  • 微博:https://weibo.com/bigwhite20xx
  • 微信公众号:iamtonybai
  • 博客:tonybai.com
  • github: https://github.com/bigwhite
  • “Gopher部落”知识星球:https://public.zsxq.com/groups/51284458844544

商务合作方式:撰稿、出书、培训、在线课程、合伙创业、咨询、广告合作。

使用ANTLR和Go实现DSL入门

本文永久链接 – https://tonybai.com/2022/05/10/introduction-of-implement-dsl-using-antlr-and-go

一. 引子

设计与实现一门像Go这样的通用编程语言的确很难!那是世界上少数程序员从事的事业,但是实现一门领域特定语言(Domain Specific Language, DSL)似乎是可行的。

就像著名的语言解析器生成工具ANTLR作者Terence Parr在《编程语言实现模式》一书中说的那样:

Yes, building a compiler for a general-purpose programming language requires a strong computer science background. But, most of us don’t build compilers. So, this book focuses on the things that we build all the time: configuration file readers, data readers, model-driven code generators, source-to-source translators, source analyzers, and interpreters. (翻译为中文:是的,为通用编程语言构建一个编译器需要强大的计算机科学背景。但是,我们中的大多数人并不构建编译器。所以,这本书的重点是我们一直在构建的东西:配置文件阅读器、数据阅读器、模型驱动的代码生成器、源码到源码的翻译器、源码分析器和解释器。)

最近因业务需要,我们要在车端实现一个车辆数据处理的规则引擎SDK。这个SDK供车端数据服务使用,用于车辆数据上报前的预处理(如下图)。

这么做,一来是因为隐私数据因隐私法规要求不可上传云端,另外特定业务场景下云端处理海量汽车的窗口数据开销太大,相反在车端处理便容易很多。随着车端算力的不断增强,这种车云结合也是车联网发展的趋势。车端有了数据处理的规则引擎后,通过云端下发规则的方式,车端便可以实现对数据处理逻辑的精准管控与快速安全的热更新(无需OTA)。

针对引擎的规则的描述至少有两种技术方案,一种是使用以标准数据交换格式(比如:Json、yaml、xml等)承载的配置文件,一种则是自定义的领域特定语言(DSL)。我们选择了后者,为的是表达简单精炼、更贴近领域、表达范围安全可控以及抽象层次更高等。

按照Martin Fowler的《领域特定语言》一书的介绍,DSL大体分为外部DSL与内部DSL。其中内部DSL是直接采用现有通用编程语言,比如python、lua、go的语法特性实现的DSL;而外部DSL则需要自己创建一门新语言,并实现语言的编译器或解析器,比如:SQL、ant、make等。

对于在车端的执行的规则而言,使用通用编程语言语法描述的规则具有一定的不安全性,不符合我们的要求。我们只有外部DSL这一条路可走。这就需要我们自行设计DSL语法、DSL语言的解析器以及执行相应语义的执行器,如下图所示:

看到上面示意图中的词法分析、语法分析,你肯定会想起大学时学过的难忘的一门课:编译原理。还记得当时你是如何通过这门课的考核的吗^_^。编译原理是计算机专业学生挂科率较高的一门专业课,它不仅抽象,听起来还十分枯燥。笔者并非计算机专业科班出身,但读本科时一直在旁听计算机系姜守旭老师的形式语言以及编译原理课,虽然当时有些云里雾里,但课程内核我还是有所把握。

好了!现在编译原理课的概念与方法又要派上用场了!我们需要利用编译原理课上学到的知识来手工实现上图中的词法分析器、语法分析器…。

等等!我们非要手工实现么?难道就没有工具能帮助我们吗?编译技术经过这么多年的发展,像词法分析、语法分析这两个阶段已经可以由工具自动帮你完成了。也就是说我们可以通过工具自动生成可以对DSL脚本进行词法分析(lexer)与语法分析(parser)的代码

对于编译器领域的新手,就像我,或者已经将编译原理知识还给老师的童鞋,我个人还是建议先使用辅助工具自动生成lexer和parser。在这一过程中,可以重温编译知识并深刻体会上下文无关文法(context-free grammar)的解析过程。当对这一问题域有深刻认知后,如果觉得自动生成的代码不够漂亮、不够灵活或性能不佳,再考虑手写lexer和parser也不迟。

如果我没记错,Go最初的lexer和parser就是自动生成的,后来才换成Go语言之父之一的Robert Griesemer手写维护的Parser。

那么我们选择哪个语法解析器的生成工具呢?我们继续往下看。

二. 选择ANTLR

市面上可用于自动生成lexer和parser代码的工具有很多种。知名度高,应用较为广泛的包括:Lex和Yacc(GNU对应的版本的叫Flex和Bison)和ANTLR等。这里面lex和yacc(gnu版本:flex和bison)是固定组合。

lex和yacc在20世纪70年代中旬诞生于著名的贝尔实验室,lex的原作者是Mike Lesk和Eric Schmidt(没错,就是Google前CEO),而yacc的原作者为Stephen C. Johnson。同样在贝尔实验室供职的C++之父Bjarne Stroustrup就是用yacc实现了第一个C++编译器cfront的前端的(C代码)。

lex是词法分析器,负责将源码(字符流)解析为一个个词法元素(token);而yacc则将这些token作为输入,构建出一个程序结构,通常是一个抽象语法树(如下图)。

图片来自lex和yacc教程

不过由于lex和yacc诞生较早,支持生成的目标语言较少。经典的贝尔实验室的yacc最初只支持生成C语言的解析器代码。Gnu版本的Bison支持输出C、C++和Java。但和很多后起之秀相比,比如ANTLR,yacc(和bison)在目标语言可选择的广泛性、调试工具多样性以及整个社区的运作方面就显得相形见绌了。

ANTLR是由Terence Parr教授(目前跳槽去Google了)在上世纪90年代初期使用Java语言开发的一个强大的语法分析器生成工具,至今ANTLR依然在积极开发,并且有着一个稳定的社区。ANTLR支持生成C#, Java, Python, JavaScript, C++, Swift, Go, PHP等几乎所有主流编程语言的目标代码,并且ANTLR官方自己维护了Java、C++、Go等目标语言的runtime库(见下图):

ANTLR可以生成各种主流通用编程语言的parser,并且在grammars-v4仓库中提供了这些语言的antlr4语法rule文件(antlr规则文件以g4为文件名后缀),这些rule样例文件可作为我们自己设计文法时的重要参考

这里我们选择使用ANTLR来生成DSL的Parser

三. 如何基于ANTLR定义DSL语法

外部DSL与通用编程语言相比,体量虽小,但也是一门语言,我们在自动生成或手工编写其解析器之前需要定义出该DSL的语法。更准确地说是DSL的形式化语法

那么,如何定义/形式化一门语言呢?和自然语言一样,编程语言也都是有结构的。定义语言就是要把这些结构,包括成分与排列顺序规则,精确地描述出来。我们小学学习语文的时候,大家都学会句型分析,什么主谓宾定状补等。一个汉语完整句子的完整结构如下:

// ()内的语法成分是可选的

(定语)主语 + (状语)谓语(补语) + (定语)宾语(补语)

要使用汉语表达正确的意思,就要满足这样的结构。要定义DSL语言,我们也要精确定义出DSL的结构。

那么我们用什么方式来描述这种DSL的语法结构呢?在学习形式语言或编译原理课程时,想必大家肯定接触过BNF(Backus-Naur Form),即巴科斯范式。巴科斯范式是以美国人巴科斯(Backus)和丹麦人诺尔(Naur)的名字命名的一种形式化的语法表示方法,是用来描述语法的一种形式体系,是一种典型的元语言。自从编程语言Algol 60(Naur,1960)使用BNF符号定义语法以来,这种符号规则体系被证明适合作为形式化编程语言的语法,之后人们也开始习惯于使用此类元语言去定义语言语法。

BNF元语言的典型表达形式如下:

<symbol> ::= expression
<symbol> ::= expression1 | expression2
  • 这个式子左侧放在尖括号中的symbol是一个非终结符号,而expression这个表达式由一个或多个终结符号或非终结符号的序列组成,这个式子也被称为产生式(production)。
  • 产生式中的“::=”这个符号含义是“被定义为”,左边的非终结符号可以被推导为右边的表达式,右边的表达式也可以归约为左边的非终结符号。
  • 如果右侧有多种表达式形式可作为symbol的归约选择,可以使用”|”符号分隔。
  • 从未出现在左边的符号是终结符号。另一方面,出现在左侧的符号为非终结符号,并且总是被包围在一对<>之间。

随着BNF的广泛应用,一些以简化BNF或特定应用为目的的扩展BNF元语言被创建出来,其中典型的包括EBNF、ABNF等。

最早的EBNF是由Niklaus Wirth开发的, 它包含了Wirth语法符号中的一些概念和不同的语法和符号. 1996年,国际标准化组织通过了EBNF标准ISO/IEC 14977:1996

EBNF使用了与BNF不同的符号且对BNF进行了增强,EBNF甚至可以定义自己的语法(如下):

letter = "A" | "B" | "C" | "D" | "E" | "F" | "G"
       | "H" | "I" | "J" | "K" | "L" | "M" | "N"
       | "O" | "P" | "Q" | "R" | "S" | "T" | "U"
       | "V" | "W" | "X" | "Y" | "Z" | "a" | "b"
       | "c" | "d" | "e" | "f" | "g" | "h" | "i"
       | "j" | "k" | "l" | "m" | "n" | "o" | "p"
       | "q" | "r" | "s" | "t" | "u" | "v" | "w"
       | "x" | "y" | "z" ;
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
symbol = "[" | "]" | "{" | "}" | "(" | ")" | "<" | ">"
       | "'" | '"' | "=" | "|" | "." | "," | ";" ;
character = letter | digit | symbol | "_" ;

identifier = letter , { letter | digit | "_" } ;
terminal = "'" , character , { character } , "'"
         | '"' , character , { character } , '"' ;

lhs = identifier ;
rhs = identifier
     | terminal
     | "[" , rhs , "]"
     | "{" , rhs , "}"
     | "(" , rhs , ")"
     | rhs , "|" , rhs
     | rhs , "," , rhs ;

rule = lhs , "=" , rhs , ";" ;
grammar = { rule } ;

我们看到EBNF使用”=”替代BNF中的”::=”,并且终结符号必须放在双引号内,避免了BNF自身使用的符号(<, >, |, ::=)无法在语言中使用。此外,BNF语法只能在一行中定义一条产生式规则,而EBNF使用一个终止字符,即分号字符”;”来标识着一条产生规则的结束,这样EBNF的一条产生式规则可以跨越多行。 此外,EBNF还提供了许多增强的机制,比如:定义重复的数量、支持注释等。

我们看到无论是BNF还是EBNF,它们都有一个共同特点,那就是产生式规则左侧仅有一个非终结符号,这样定义出的语法(文法)称为上下文无关(Context-Free Grammar,CFG)文法。以下面产生式规则为例:

S = aSb

我们看到S始终都可以被推导为aSb,而无需考虑S在什么位置,上下文是什么。如果你还云里雾里,我们可以对比上下文相关文法(Context-Sensitive Grammar,CSG)来理解。下面就是一个上下文相关文法的产生式规则:

aSb = abScd

在这个产生式的左侧,S不再是“孤单”的,而是左右各有一个“保镖”:a和b。a和b就是S的上下文,也就说S只有在“左有a且右有b”的上下文环境下才能被推导为abScd

可以看出上下文相关文法更具通用性,因为一些语言(比如自然语言)可以用上下文相关文法定义,但却无法用上下文无关文法定义。但计算机编程语言更多使用上下文无关文法就可以定义。因此,后续我们定义的文法都是上下文无关文法。

ANTLR使用的是一种类EBNF的语法,通过ANTLR语法定义的DSL的语法规则放置在后缀为”.g4″的规则文件中,下面是一个ANTLR语法描述的简单计算器的DSL语法(该例子来自这里):

// Calc.g4
grammar Calc;

// Rules
start : expression EOF;

expression
   : expression op=('*'|'/') expression # MulDiv
   | expression op=('+'|'-') expression # AddSub
   | NUMBER                             # Number
   ;

// Tokens
MUL: '*';
DIV: '/';
ADD: '+';
SUB: '-';
NUMBER: [0-9]+;
WHITESPACE: [ \r\n\t]+ -> skip;
  • 一个antlr描述的语法规则由grammar关键字开始,后接这份语法的名字,这个名字要与文件名保持一致。比如上面例子中的语法名字为Calc,那么承载这份语法定义的文件名就应该为Calc.g4,否则通过antlr工具生成目标代码时会报错!
  • antlr支持在语法定义文件中使用注释,支持单行注释//和多行注释/* … */。
  • antlr语法定义文件本质上就是一个产生式规则的集合,其主体结构如下:
grammar MyG;
rule1 : «stuff» ;

rule2 : «more stuff» ;
...
  • antlr本身就是一种类EBNF元语言,它使用冒号(:)作为产生式左侧非终结符号与右侧推导表达式的分隔符,使用与EBNF相同的分号(;)作为一条产生式规则的结束符,这样antlr可以支持一个产生式规则跨多行定义,就像上面例子中的非终结符号expression
  • antlr又将非终结符号做了细分,一种是首字母小写的单词代表的语法解析器规则(parser rule),另外一种是首字母大写的单词(通常整个单词都大写)代表的词法分析器规则(lexical/token rule)。前者用于定义语法结构,就像上例中的expression,后者则定义词汇符号,比如上例中的NUMBER。
  • 上面例子中start作为整个Calc语法的起始规则;语法从start开始,自上而下展开。因此一个antlr dsl规则文件都应该有一个起始规则,名字可任意起;
  • 如果产生式右侧有多个可选表达式,可以用竖线(|)分开;
  • expression产生式每个可选表达式后面的井号及后面的单词用于指示这条推导表达式在目标代码中的方法名,主要是服务于生成的目标代码。

比如:上述例子中的expression产生式“等价于”下面语法:

expression
   : muldiv
   | addsub
   | NUMBER
   ;

muldiv
   : expression op=('*'|'/') expression
   ; 

addsub:
   | expression op=('+'|'-') expression
   ;

但是这个所谓的“等价”语法定义是有问题的,当我们用antlr基于该语法文件试图生成目标代码时会提示:

error(119): Calc.g4::: The following sets of rules are mutually left-recursive [expression, muldiv, addsub]

antlr命令行工具提示Calc.g4中存在互斥的左递归问题。Antlr可以自动处理直接左递归,即在一个产生式规则中存在的左递归(对应到代码层面,就是在代表自己的函数Expr中递归调用Expr),比如:

expr: expr op=('*'|'/') expr ;

如果是跨产生式规则的左递归,又称间接左递归(对应到代码层面就是在Expr函数中调用另外一个函数AddSub,而AddSub函数又调用了Expr函数),比如下面规则:

expr: addsub;
addsub: expr op=('+'|'-') expr;

Antlr无法自动解决这种间接左递归,需要你优化DSL语法,消除间接左递归

如果你不习惯antlr定义dsl的语法,你可以通过https://bottlecaps.de/convert/这个在线工具将antlr4语法转换为EBNF语法(如下,可能不是标准EBNF):

start    ::= expression EOF
expression
         ::= expression ( '*' | '/' | '+' | '-' ) expression
           | NUMBER
_        ::= WHITESPACE
          /* ws: definition */

<?TOKENS?>

NUMBER   ::= [0-9]+
WHITESPACE
         ::= [ \r\n\t]+
EOF      ::= $

该工具还支持在线生成语法对应的状态转换图,如下图:

好了,到这里我们铺垫了很多很多了,下面我们来基于antlr进行一次实战!

四. ANTLR安装、代码生成与语法调试

1. 安装和配置ANTLR

ANTLR是一个Java开发的命令行工具包(截至发此文时,最新版本为4.10.1),其安装步骤很简单。在官方醒目的位置有安装步骤,这里摘抄下来^_^:

// 适用于MacOS(已安装JDK)

$ cd /usr/local/lib
$ sudo curl -O https://www.antlr.org/download/antlr-4.10.1-complete.jar

// 通过下面命令将antlr jar包加入classpath并定义antlr4别名
// 或编辑shell的环境文件,比如.zshrc/.bashrc等,将下面内容添加到环境文件中并source生效
// grun别名将启动antlr提供的DSL语法调试工具,非常实用

$ export CLASSPATH=".:/usr/local/lib/antlr-4.10.1-complete.jar:$CLASSPATH"
$ alias antlr4='java -jar /usr/local/lib/antlr-4.10.1-complete.jar'
$ alias grun='java org.antlr.v4.gui.TestRig'

安装后,执行下面命令,如果输出内容与下面相同,则说明安装成功。

$antlr4
ANTLR Parser Generator  Version 4.10.1
... ...

接下来我们就来生成一个示例DSL的目标Parser代码。

2. 生成一个CSV格式解析器的框架代码

本文是一篇入门文章,所以我挑选了一个大家都十分熟悉的数据格式CSV(逗号分隔的数据文件格式),我们为这种数据格式生成一种可以实现解析和转换的DSL的parser。《ANTLR4权威指南》一书的8.1小节有一个CSV的例子,我们就“拿来主义”,为这个CSV语法生成对应的Parser代码框架。

书中给出的CSV语法规则文件如下:

// github.com/bigwhite/experiments/tree/master/antlr/csv2map/CSV.g4
grammar CSV;

csvFile: hdr row+ ;
hdr : row ;

row : field (',' field)* '\r'? '\n' ;

field
    : TEXT
    | STRING
    |
    ;

TEXT   : ~[,\n\r"]+ ;
STRING : '"' ('""'|~'"')* '"' ; // quote-quote is an escaped quote

书中这个例子给出CSV格式是带有header行的,即认为CSV文件的第一行是header。之后的行才是数据。而数据既可以是直接文本也是带有双引号的字符串。

我们基于这个规则文件生成对应的Go代码:

$antlr4 -Dlanguage=Go -o parser CSV.g4

通过-Dlanguage选项告诉antlr要生成的目标代码语言,通过-o指定生成代码存放的目录,这里我们告诉antlr将生成的Go代码放在parser目录下,由于生成的Go包名默认为parser,因此指定parser目录与Go的包导入路径机制是契合的。但是目前antlr不会根据传给-o的目录名去修改生成代码的包名。比如:-o parser1,生成代码在parser1目录下,但代码的包名依旧为parser,这点要注意。

$tree ./parser
.
├── CSV.g4
└── parser
    ├── CSV.interp
    ├── CSV.tokens
    ├── CSVLexer.interp
    ├── CSVLexer.tokens
    ├── csv_base_listener.go
    ├── csv_lexer.go
    ├── csv_listener.go
    └── csv_parser.go

3. 代码探索

下面我们对照CSV.g4中的语法规则,简单探索一下antlr生成的Go代码。

如上面parser目录下的布局,antlr4默认情况下共生成了四个Go源文件:

  • csv_lexer.go:提供词法分析器实现
  • csv_parser.go:提供语法分析器的实现
  • csv_listener.go:定义了CSVListener接口
  • csv_base_listener.go:提供了一个CSVListener接口的默认实现BaseCSVListener,其方法实现默认都为空,即什么也不做。

这里重点看一下CSVListener接口:

// CSVListener is a complete listener for a parse tree produced by CSVParser.
type CSVListener interface {
    antlr.ParseTreeListener

    // EnterCsvFile is called when entering the csvFile production.
    EnterCsvFile(c *CsvFileContext)

    // EnterHdr is called when entering the hdr production.
    EnterHdr(c *HdrContext)

    // EnterRow is called when entering the row production.
    EnterRow(c *RowContext)

    // EnterField is called when entering the field production.
    EnterField(c *FieldContext)

    // ExitCsvFile is called when exiting the csvFile production.
    ExitCsvFile(c *CsvFileContext)

    // ExitHdr is called when exiting the hdr production.
    ExitHdr(c *HdrContext)

    // ExitRow is called when exiting the row production.
    ExitRow(c *RowContext)

    // ExitField is called when exiting the field production.
    ExitField(c *FieldContext)
}

这是antlr根据CSV.g4中的文法生成的Listener,你一定要对照着CSV.g4中的文法来看这个接口的方法集合。我们看到,对于每个CSV.g4中的解析器规则(parser rule),比如:csvFile、hdr、row、field,CSVListener中都有一对与之对应的方法。以hdr为例,EnterHdr对应进入hdr产生式规则时调用的方法,ExitHdr则对应离开hdr产生式规则时调用的方法。后续我们自定义遍历抽象语法树的CSVListener实现,就是要根据需要实现对应的方法即可。这个对照我们稍后的例子中代码,你会有更深刻的体会。

此外,antlr生成的代码不多,但我们看到生成的CSVParser和CSVLexer两个结构中分别内嵌了antlr.BaseParser和antlr.BaseLexer,也就是说核心的实现都在antlr提供的go runtime中。

此外这里还要说一下parser解析完文法后生成的语法树的访问方式。antlr提供两种语法树的遍历方式,一种是listener,一种是visitor,但antlr默认只是生成了listener的代码。如果要生成visitor代码,可以在命令行使用-visitor选项:

$antlr4 -Dlanguage=Go -visitor -o parser CSV.g4

生成的源文件中就会多出csv_visitor.go和csv_base_visitor.go,前者定义了CSVVisitor接口,后者提供了CSVVisitor的基本实现:BaseCSVVisitor:

$tree parser
parser
├── CSV.interp
├── CSV.tokens
├── CSVLexer.interp
├── CSVLexer.tokens
├── csv_base_listener.go
├── csv_base_visitor.go
├── csv_lexer.go
├── csv_listener.go
├── csv_parser.go
└── csv_visitor.go

当然antlr4命令行提供了各种精细的控制开关来控制是否生成listener或visitor:

 -listener           generate parse tree listener (default)
 -no-listener        don't generate parse tree listener
 -visitor            generate parse tree visitor
 -no-visitor         don't generate parse tree visitor (default)

在后面我们将使用listener方式遍历抽象语法树提取我们需要的信息。在深入代码之前,我们再来看看antlr提供的调试工具。

4. 文法调试工具

我们基于antlr4提供的规则手工编写DSL的语法规则,难免会出现各种各样的问题,比如:有二义性、规则顺序导致的错误推导等。antlr提供了十分强大且方便的调试工具grun:

$grun -h
java org.antlr.v4.gui.TestRig GrammarName startRuleName
  [-tokens] [-tree] [-gui] [-ps file.ps] [-encoding encodingname]
  [-trace] [-diagnostics] [-SLL]
  [input-filename(s)]
Use startRuleName='tokens' if GrammarName is a lexer grammar.
Omitting input-filename makes rig read from stdin.

由于grun是java实现的,我们只能在目标代码为Java的情况下对g4文件的解析进行调试。所以使用grun工具的前提是先生成Java目标代码:

$antlr4 CSV.g4

然后调用grun以及其提供的各种选项对解析过程进行调试。

  • 图形化调试

通过下面结合了-gui选项的grun命令:

$grun CSV csvFile demo1.csv -gui

grun可以在新窗口中输出抽象语法树的全貌:

通过这样一个图形,我们可以清晰看出规则匹配是否如我们预期。

  • Tree型调试

通过下面结合了-tree选项的grun命令:

$grun CSV csvFile demo1.csv -tree

grun可以在命令行输出树型匹配结构,这个就等价于图形化调试截图中的左侧窗口。如果你就喜欢命令行方式的输出,可以试试这个。

(csvFile (hdr (row (field Details) , (field Month) , (field Amount) \n)) (row (field Mid Bonus) , (field June) , (field "$2,000") \n) (row field , (field January) , (field """zippo""") \n) (row (field Total Bonuses) , (field "") , (field "$5,000") \n))
  • 词法解析调试

grun还单独提供了针对词法分析阶段的调试命令行选项:-tokens:

使用下面命令:

$grun CSV csvFile demo1.csv -tokens

grun可以输出如下词法分析阶段的详细过程,通过这个输出,我们可以看出输入数据中的字符序列匹配情况,是否如预期的匹配到对应的词法规则上去了,比如CSV.g4中的两个词法规则:TEXT和STRING:

[@0,0:6='Details',<TEXT>,1:0]
[@1,7:7=',',<','>,1:7]
[@2,8:12='Month',<TEXT>,1:8]
[@3,13:13=',',<','>,1:13]
[@4,14:19='Amount',<TEXT>,1:14]
[@5,20:20='\n',<'\n'>,1:20]
[@6,21:29='Mid Bonus',<TEXT>,2:0]
[@7,30:30=',',<','>,2:9]
[@8,31:34='June',<TEXT>,2:10]
[@9,35:35=',',<','>,2:14]
[@10,36:43='"$2,000"',<STRING>,2:15]
[@11,44:44='\n',<'\n'>,2:23]
[@12,45:45=',',<','>,3:0]
[@13,46:52='January',<TEXT>,3:1]
[@14,53:53=',',<','>,3:8]
[@15,54:64='"""zippo"""',<STRING>,3:9]
[@16,65:65='\n',<'\n'>,3:20]
[@17,66:78='Total Bonuses',<TEXT>,4:0]
[@18,79:79=',',<','>,4:13]
[@19,80:81='""',<STRING>,4:14]
[@20,82:82=',',<','>,4:16]
[@21,83:90='"$5,000"',<STRING>,4:17]
[@22,91:91='\n',<'\n'>,4:25]
[@23,92:91='<EOF>',<EOF>,5:0]

此外,grun提供的-trace和-diagnostics均可以从不同角度为文法规则的正确性提供跟踪诊断信息。

为了方便使用,我将grun调试功能嵌入到Makefile中,通过make gui、make tokens、make tree等命令即可实现不同形式的调试。Makefile代码参见本文提供的代码示例csv2map

五. 为示例增加语义

通过grun的调试,只能说明我们定义的文法(CSV.g4)是正确的,是可以解析输入的数据(demo1.csv)的。但解析成功后的数据要怎么处理呢?这就需要我们为示例增加处理语义。

在这个例子中,我们模仿《antlr权威指南》书中的例子将demo1.csv的数据形式转换为另一种map形式输出,举例来说,就是将下面的csv数据:

Details,Month,Amount
Mid Bonus,June,"$2,000"
,January,"""zippo"""
Total Bonuses,"","$5,000"

转换为下面map形式:

[{Details=Mid Bonus, Month=June, Amount="$2,000"},
 {Details=, Month=January, Amount="""zippo"""},
 {Details=Total Bonuses, Month="", Amount="$5,000"}]

虽然前面生成了parser目录下的parser包,但是还远远不够,我们还需手工增加上述语义行为。

首先,我们先来创建一个go module,方便后续依赖版本管理和程序构建:

$go mod init csvparser

然后通过go mod tidy拉取必要的依赖包,主要是github.com/antlr/antlr4/runtime/Go/antlr这个antlr go runtime包。之后我们就可以创建main.go了,下面是该parser的main函数:

// github.com/bigwhite/experiments/tree/master/antlr/csv2map/main.go

func main() {
    csvFile := os.Args[1]
    is, err := antlr.NewFileStream(csvFile)
    if err != nil {
        fmt.Printf("new file stream error: %s\n", err)
        return
    }

    // Create the Lexer
    lexer := parser.NewCSVLexer(is)
    stream := antlr.NewCommonTokenStream(lexer, antlr.TokenDefaultChannel)

    // Create the Parser
    p := parser.NewCSVParser(stream)

    // Finally parse the expression
    l := &CSVMapListener{}
    antlr.ParseTreeWalkerDefault.Walk(l, p.CsvFile())
    fmt.Printf("%s\n", l.String())
}

我们通过命令行传入要解析的csv格式的文件,通过antlr包提供的NewFileStream创建输入数据流,并将该数据流传给新创建的lexer,经过lexer的解析后,我们得到token stream,经过前面的铺垫,我们知道token stream是要传给新创建的Parser。Parser会在内存中建立抽象语法树(见上面抽象语法树那张图)。

之后,也是最重要的就是遍历语法树,提取我们需要的信息了。前面说过,antlr基于CSV.g4仅仅是生成了一个CSVListener的接口以及一个空的BaseCSVListener的实现。但BaseCSVListener不能满足我们的要求,我们需要一个可以提取语法树中重要信息的CSVListener接口的实现,我这里称之为CSVMapListerner:

// github.com/bigwhite/experiments/tree/master/antlr/csv2map/csv_listener.go

type CSVMapListener struct {
    *parser.BaseCSVListener
    headers []string
    cm      []map[string]string
    fields  []string // a slice of fields in current row
}

我们看到,CSVMapListener首先嵌入了BaseCSVListener,“继承”了BaseCSVListener的所有方法实现,这使得CSVMapListener满足CSVListener接口。

CSVMapListener中的cm字段用于存储从抽象语法树中提取到的CSV数据信息,它本身是一个元素类型为map[string]string的切片;headers用于存储从抽象语法树中读取到的CSV文件的头信息;而fields则是代表CSV每一行数据的抽象。

我们不需要override BaseCSVListener的所有方法,我们只需在几个方法中保存提取到的信息即可。

整个CSV文件的关键数据单元是row,每当我们进入产生式规则row时,都需要为后续解析出的row信息准备好存储空间:

func (cl *CSVMapListener) EnterRow(c *parser.RowContext) {
    cl.fields = []string{} // create a new field slice
}

对应到CSVMapListener,就是override EnterRow方法,在该方法中创建一个新的fields slice。

在产生式规则row完成时,将fields信息存储起来,即override ExitRow方法,见下面代码:

func (cl *CSVMapListener) ExitRow(c *parser.RowContext) {
    // get the rule index of parent context
    if i, ok := c.GetParent().(antlr.RuleContext); ok {
        if i.GetRuleIndex() == parser.CSVParserRULE_hdr {
            // ignore this row
            return
        }
    }

    // it is a data row
    m := map[string]string{}

    for i, h := range cl.headers {
        m[h] = cl.fields[i]
    }
    cl.cm = append(cl.cm, m)
}

由于header也是一个row,我们不能将header当成普通row存储在cm中,所以在ExitRow中有一个是否是header row的判断。如果是header row,则啥也不做;否则创建一个map[string]string实例,将row信息存储在该map中,并append到cm的切片中保存起来。

如果row是header,我们只需要override ExitHdr方法,将fields信息保存到headers字段中备用,如下面代码:

func (cl *CSVMapListener) ExitHdr(c *parser.HdrContext) {
    cl.headers = cl.fields
}

下面的ExitField方法是提取row中每个field文本信息的:将每个field的文本信息追加到fields切片中保存起来:

func (cl *CSVMapListener) ExitField(c *parser.FieldContext) {
    cl.fields = append(cl.fields, c.GetText())
}

经过上述这些override方法后,我们就可以从抽象语法树中提取到我们需要的信息了,对应到main函数中的代码,我们将新创建一个CSVMapListener的实例,并将其传给antlr.ParseTreeWalkerDefault.Walk方法,后者会在特定时刻自动回调我们上面的override的方法来提取我们需要的信息:

// github.com/bigwhite/experiments/tree/master/antlr/csv2map/main.go

    l := &CSVMapListener{}
    antlr.ParseTreeWalkerDefault.Walk(l, p.CsvFile())

一旦信息都被提取到CSVMapListener的cm字段和headers字段中后,我们便可以按要求输出这些信息:

// github.com/bigwhite/experiments/tree/master/antlr/csv2map/csv_listener.go
func (cl *CSVMapListener) String() string {
    var s strings.Builder
    s.WriteString("[")

    for i, m := range cl.cm {
        s.WriteString("{")
        for _, h := range cl.headers {
            s.WriteString(fmt.Sprintf("%s=%v", h, m[h]))
            if !cl.lastHeader(h) {
                s.WriteString(", ")
            }
        }
        s.WriteString("}")
        if i != len(cl.cm)-1 {
            s.WriteString(",\n")
            continue
        }
    }
    s.WriteString("]")
    return s.String()
}

这个比较简单,就不赘述了。

以上main.go中的代码都是基于antlr的Parser的经典“套路”,大部分Parser都可以使用这些代码。你的重点在自定义Listener的实现上,就像本例中的CSVMapListener。

六. 小结

到这里我们就实现了一个可以解析CSV文件并将其中数据转换为特定格式输出的DSL解析器了。这个示例仅仅是说明了基于Antlr构建DSL解析器的原理与基本步骤。

简单回顾一下,基于Antlr实现DSL,第一要基于Antlr提供的类EBNF规则设计出DSL的文法,第二要基于antlr生成的代码实现一个DSL的Listener从抽象语法树提取你所需要的信息并构建执行语义。

在这个过程中,我们可以使用antlr提供的强大的调试工具来帮助我们解决问题,尤其是dsl文法中的问题。

本文中涉及的代码可以在这里下载。

七. 参考资料


“Gopher部落”知识星球旨在打造一个精品Go学习和进阶社群!高品质首发Go技术文章,“三天”首发阅读权,每年两期Go语言发展现状分析,每天提前1小时阅读到新鲜的Gopher日报,网课、技术专栏、图书内容前瞻,六小时内必答保证等满足你关于Go语言生态的所有需求!2022年,Gopher部落全面改版,将持续分享Go语言与Go应用领域的知识、技巧与实践,并增加诸多互动形式。欢迎大家加入!

img{512x368}
img{512x368}

img{512x368}
img{512x368}
img{512x368}

我爱发短信:企业级短信平台定制开发专家 https://tonybai.com/。smspush : 可部署在企业内部的定制化短信平台,三网覆盖,不惧大并发接入,可定制扩展; 短信内容你来定,不再受约束, 接口丰富,支持长短信,签名可选。2020年4月8日,中国三大电信运营商联合发布《5G消息白皮书》,51短信平台也会全新升级到“51商用消息平台”,全面支持5G RCS消息。

著名云主机服务厂商DigitalOcean发布最新的主机计划,入门级Droplet配置升级为:1 core CPU、1G内存、25G高速SSD,价格5$/月。有使用DigitalOcean需求的朋友,可以打开这个链接地址:https://m.do.co/c/bff6eed92687 开启你的DO主机之路。

Gopher Daily(Gopher每日新闻)归档仓库 – https://github.com/bigwhite/gopherdaily

我的联系方式:

  • 微博:https://weibo.com/bigwhite20xx
  • 微信公众号:iamtonybai
  • 博客:tonybai.com
  • github: https://github.com/bigwhite
  • “Gopher部落”知识星球:https://public.zsxq.com/groups/51284458844544

微信赞赏:
img{512x368}

商务合作方式:撰稿、出书、培训、在线课程、合伙创业、咨询、广告合作。

如发现本站页面被黑,比如:挂载广告、挖矿等恶意代码,请朋友们及时联系我。十分感谢! Go语言第一课 Go语言精进之路1 Go语言精进之路2 Go语言编程指南
商务合作请联系bigwhite.cn AT aliyun.com

欢迎使用邮件订阅我的博客

输入邮箱订阅本站,只要有新文章发布,就会第一时间发送邮件通知你哦!

这里是 Tony Bai的个人Blog,欢迎访问、订阅和留言! 订阅Feed请点击上面图片

如果您觉得这里的文章对您有帮助,请扫描上方二维码进行捐赠 ,加油后的Tony Bai将会为您呈现更多精彩的文章,谢谢!

如果您希望通过微信捐赠,请用微信客户端扫描下方赞赏码:

如果您希望通过比特币或以太币捐赠,可以扫描下方二维码:

比特币:

以太币:

如果您喜欢通过微信浏览本站内容,可以扫描下方二维码,订阅本站官方微信订阅号“iamtonybai”;点击二维码,可直达本人官方微博主页^_^:
本站Powered by Digital Ocean VPS。
选择Digital Ocean VPS主机,即可获得10美元现金充值,可 免费使用两个月哟! 著名主机提供商Linode 10$优惠码:linode10,在 这里注册即可免费获 得。阿里云推荐码: 1WFZ0V立享9折!


View Tony Bai's profile on LinkedIn
DigitalOcean Referral Badge

文章

评论

  • 正在加载...

分类

标签

归档



View My Stats