乐者为王

Do one thing, and do it well.

共享代码的风险

英文原文:https://www.innoq.com/en/blog/the-perils-of-shared-code/

通往地狱的道路往往是由良好的意愿铺就。在各种软件项目中,我看到人们走在这样的道路上,他们在微服务之间借助库共享代码。在几乎每个组织支持微服务架构的项目中,各个团队和开发者都期望以某些核心库为基础构建他们的微服务。显然,即使可能带来的问题已经被知道很长时间了,很多人仍然不知道它们。在这篇博文中,我想研究为什么使用这样的库可能起初听起来有吸引力,为什么可能会出现问题,以及如何能够减轻这些问题。

共享代码的目的

通过库来共享代码有两个主要目的:共享领域逻辑和共享基础设施层中的抽象。

  1. 共享的领域模型:领域模型的特定部分在两个或多个有界上下文之间是共同的,因此,作为三番五次实现它的替换,你消除了重复的需要和引入该领域逻辑的不一致实现的可能性。通常,人们想要像那样共享的领域模型的部分是核心领域或一个或多个通用子领域。在领域驱动设计的行话中,这也被称为共享内核。通常,你可以在这里找到像会话和身份验证逻辑这样的概念,但不限于此。一套相关的方法是规范数据模型。

  2. 基础设施层抽象:你想避免一次又一次地实现基础设施层的有用抽象,因此你把它们放进一个库里。通常,这些库在数据库访问、消息传递和序列化等方面提供一套统一的方法。

两者的动机是相同的——避免重复,也就是说,遵循DRY原则(Don’t repeat yourself!)。一旦实现这些逻辑有几个好处:

你不需要花费宝贵的时间致力于那些已经被解决的问题。

有一套统一的方式做消息传递、数据库访问等。这意味着,当开发者需要去阅读和修改其他开发者最初创建的微服务中的代码时,他们很容易找到他们的方式。

关于彼此行为略有不同的业务逻辑或基础设施关注点,你不想有不同的实现。取而代之的是,有一套做正确事情的规范实现。

共享代码的问题

在理论上听起来很棒的东西不会没有自己的问题,而且这些问题可能比你试图用你的库解决的问题更令人痛苦。Stefan Tilkov已经详细解释了为什么你应该避免规范的数据模型。除此之外,让我指出一些其它的问题。

分布式单体

通常,似乎存在一个隐含的假设,将东西放入库意味着你永远不必担心使用错误或过时的实现构成的服务,因为他们只需要更新其对库的依赖关系到最新版本。

每当你依靠通过将所有的微服务更新到同样的新版本库,来对所有微服务的某些行为作出一致的改变时,你就会在它们之间引入强耦合。你失去了微服务的一个主要优点,即它们彼此独立地演进和部署的能力。

我见过这样的案例,所有的服务必须同时部署,以便服务仍能正常工作。如果你达到这种状态,不可否认,你实际上构建了一个分布式的单体。

一个流行的示例是使用代码生成,例如,基于服务API的Swagger描述,以便为你的服务提供一个客户端库。比你想象的更多,开发者可能会滥用此种方式进行重大变更,因为依赖服务“只”需要使用新版本的客户端库。这不是你如何演进一个分布式系统

依赖地狱

库,尤其是那些旨在为基础设施关注点提供通用解决方案的库,往往有个额外的问题:它们会附上它们依赖的一整套额外的库。你的库的传递依赖树越大,它导致俗称为依赖地狱的噩梦的可能性就越高。因为你的微服务可能需要自己的额外的依赖,它们同样具有传递依赖性,直到它们中的某些库间接地拉进一些库的冲突版本,这只是个时间问题,只在不同版本之间选择是不可能的,因为它们是二进制不兼容的。

当然,你的解决方案也许只是提供微服务可能需要的所有库作为你的核心库的依赖。那仍然意味着你的微服务不能独立地演进,例如通过升级到它们依赖的唯一的特定库的更高版本——它们都与核心库的发布周期步调一致。除此之外,为什么你要强制每个服务接受一整堆的依赖,当它们实际上可能只需要依赖中的一些时?

自顶而下的库设计

通常情况下,我见过的库被一个或多个架构师强加于开发者,采用自顶而下的方法进行库设计。

通常,在这种情况下发生的是,由库暴露的API太受限制和不灵活,或者使用了错误的抽象级别,因为它们是由不够熟悉广泛的不同的真实世界用例的人设计的。这样的库经常导致不得不使用它的开发者遭受挫折,以及导致人们试图绕过库的限制。

单语言解决一切

强制使用库的最明显的缺陷之一是,这使得它更难以切换到不同的编程语言(或者平台,比如JVM或.NET),再次失去了微服务架构的一个优势,即选择最适合给定问题的技术的能力。如果你后来意识到,你终究需要这种语言或者平台的多样性,你必须创造各种奇怪的支持。例如,Netflix提出的Prana,一个同时运行非JVM服务的附加件,为他们提供到Netflix技术栈的一套HTTP API。

我们能不能做得更好?

由于所有的问题都是通过库共享代码引入的,最极端的解决方案是根本没有这样的库。如果你这样做,你将不得不做一些复制和粘贴或者为新的微服务提供一个模板项目,以便从前面所述的步调一致中释放你的服务。基础设施代码以及领域模型的共享内核中都可以这么做。事实上,Eric Evans在他的关于领域驱动设计的经典蓝皮书中提到,“通常各个团队只是在各自的内核备份上改动,每隔一定时间才会与其他团队集成”[1]。共享内核不一定要是库。

如果你不喜欢复制和粘贴的想法,那也很好。毕竟,如上所述,通过库共享代码有一定的优势。在这种情况下,这里有一些重要的事情需要考虑:

最少依赖的小型库

尝试将大的共享库分成一组非常小的、高度集中的库,每个库解决一个特定的问题。试着让这些库成为零依赖库,只依靠语言的标准库。是的,仅仅针对语言的标准库来编程并不总是令人愉快的,但是对于你公司的所有团队的巨大好处(甚至超出你的公司,如果你的馆是开源的)显然大于这个微小的不便。

当然,零依赖并不总是可能的,特别是对于基础设施关注点。对于这些,通过你的每个小型库最小化所需的依赖。另外,有时可以独立于库的核心,提供与别的库的绑定或集成作为单独的工件。

留下选择余地

不要指望服务将在特定时间点更新到共享库的最新版本的事实。换句话说,不要强制团队进行库更新,而是让他们可以按照自己的节奏自由更新。这可能需要你以向后和向前兼容的方式修改库,但它会解耦你的服务,不仅给你微服务架构的运营成本,而且还有一些优势。

如果可能,不仅要避免强制库更新,还要使库本身的使用可选。

自底而上的库设计

最后,如果你想拥有共享库,我见过的获得成功的项目是使用自底而上的方法。让你的团队实现他们的微服务,而不是让象牙塔架构师设计在现实世界中几乎不可用的库,而当在多个服务的生产中已经证明它们自己的一些常见模式出现时,将它们提取到库中。

[1] Evans, Eric: Domain-Driven Design: Tackling Complexity in the Heart of Software, p. 355

ANTLR 4权威参考读书笔记(32)

前面我们介绍过ANTLR的自动错误恢复机制,现在让我们看看手动机制,有些时候它能够提供更好的错误恢复。

错误选项

某些语法错误非常常见,所以值得特别处理。例如,程序员经常在带有嵌套参数的函数调用结尾处忘记写大括号。特别是处理这些情况,我们所要做的就是添加选项来匹配错误但常见的语法。下面的语法识别单个参数或者可能在参数中使用嵌套括号的函数调用。规则fcall有两个所谓的错误选项。

1
2
3
4
5
6
7
8
9
stat: fcall ';' ;
fcall
    : ID '(' expr ')'
    | ID '(' expr ')' ')' { notifyErrorListeners("Too many parentheses"); }
    | ID '(' expr         { notifyErrorListeners("Missing closing ')'"); }
    ;
expr: '(' expr ')'
    | INT
    ;

虽然这些错误选项可能使ANTLR生成的语法分析器在选项之间选择时更困难,但它们不以任何方式混淆语法分析器。就像任何其它选项,如果它们与当前的输入一致,语法分析器就会匹配它们。现在,让我们从一个有效的函数调用开始,尝试一些匹配错误选项的输入序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
$ antlr Call.g
$ compile Call
$ grun Call stat
f(34);
EOF
$ grun Call stat
f((34);
EOF
line 1:6 Missing closing ')'
$ grun Call stat
f((34)));
EOF
line 1:8 Too many parentheses

ANTLR 4权威参考读书笔记(31)

  • lookahead 前导符

现在我们已经对ANTLR语法分析器生成的消息种类以及如何调整和重定向它们有很好的了解,让我们来探讨错误恢复。

自动错误恢复策略

错误恢复是允许语法分析器找到语法错误后还能继续的东西。ANTLR的错误恢复机制是:如果可能的话,语法分析器在不匹配的记号错误上执行单次记号插入和单次记号删除。如果不能,语法分析器会吞掉记号直到它找到可以合理遵循当前规则的记号然后返回它,继续下去,就好像什么事都没发生。在本节中,我们将探讨ANTLR如何在各种情况下从错误中恢复。让我们从ANTLR使用的基本恢复策略开始。

通过扫描后续记号恢复

当真正面对残缺的输入时,当前规则不能继续,因此语法分析器通过吞掉记号来恢复,直到它认为它已经重新同步然后返回到调用规则。我们可以称之为“同步和返回策略”。有些人称它是“恐慌模式”,但它工作的非常好。语法分析器知道它不能用当前规则匹配当前输入。它只能抛出记号直到前导符与语法分析器退出规则后应该匹配的内容一致。例如,如果在赋值语句中有个语法错误,在语法分析器看到分号或其它语句终结符之前抛出记号是非常有意义的。激烈但有效。正如我们将看到的,ANTLR试图在规则中恢复,然后在撤回到这个基本策略。

每个ANTLR生成的规则方法都被包裹在try-catch中,通过报告错误并在返回之前尝试恢复来响应语法错误。

1
2
3
4
5
6
try {
    ...
} catch (RecognitionException re) {
    _errHandler.reportError(this, re);
    _errHandler.recover(this, re);
}

在这里,recover()会消费记号直到它在重新同步集合中找到记号。重新同步集合是所有调用栈上的规则的规则引用跟随集合的并集。规则引用的跟随集合是可以立即匹配引用而无需离开当前规则的跟随引用的记号集合。例如,选项assign ';',规则引用assign的跟随集合是{';'}。如果选项仅仅是assign,它的跟随集合就为空。

让我们通过示例来看看重新同步集合中包含什么。考虑以下语法,并设想在每个规则调用中,语法分析器跟踪每个规则调用的跟随集合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Filename: F.g

grammar F;

group
    : '[' expr ']'      // Tokens following ref to expr: {']'}
    | '(' expr ')'      // Tokens following ref to expr: {')'}
    ;
expr: atom '^' INT ;    // Tokens following ref to atom: {'^'}
atom: ID
    | INT
    ;

INT : [0-9]+ ;
ID  : [a-zA-Z]+ ;
WS  : [ \t\r\n]+ -> skip ;

对于输入[1^2],考虑下图中左边的语法分析树:

syntax-parse-tree

当在规则atom中匹配记号1时,调用栈是[group, expr, atom](group调用expr,expr调用atom)。通过查看调用栈,我们可以准确地知道记号集合可以跟随语法分析器调用的任何规则,以便把我们带到当前位置。在当前规则中跟随集合只考虑记号,以至在运行时,我们可以只组合与当前调用栈有关系的集合。换句话说,我们不能同时从group的所有选项到达规则expr。

结合从语法F中的注释里提取的跟随集合,我们得到一个重新同步集合{'^', ']'}。为什么这是我们想要的,让我们观察当语法分析器遇到错误的输入[]时会发生什么。我们得到上图中显示在右边的语法分析树。在规则atom中,语法分析器发现当前记号]不符合atom的任何选项。要想重新同步,语法分析器需要消费记号直到它在重新同步集合找到记号。在这种情况下,当前记号]作为重新同步集合的成员开始,所以语法分析器不会消费任何记号以便在atom中重新同步。

在规则atom中完成恢复过程之后,语法分析器回到规则expr但是立刻发现它没有^记号。重复同样的过程,语法分析器消费记号直到它在重新同步集合找到记号。expr的重新同步集合是在group的第一个选项中的expr引用的跟随集合:{ ']' }。再次,语法分析器不消费任何东西并退出expr,回到规则group的第一个选项。现在,跟随着expr的引用,语法分析器明确知道它在寻找什么。它成功地匹配规则group中的']'。语法分析器现在已经正确地同步。

在恢复期间,ANTLR语法分析器避免发出级联错误消息。也就是说,语法分析器为每个语法错误发出单独的错误消息,直到它们从该错误成功地恢复。通过使用一个简单的布尔变量,设置语法错误,语法分析器避免发出更多的错误,直到语法分析器成功匹配记号和重置变量。

在许多情况下,ANTLR可以比单纯消费更智能地恢复,直到重新同步集合并从当前规则返回。尝试“修复”输入并在相同的规则内继续是值得的。在接下来的几个部分,我们将看看语法分析器如何从不匹配的记号以及子规则里的错误中恢复。

从不匹配记号中恢复

在语法分析过程中最常见的操作之一是“匹配记号”。对于语法中的每个记号引用T,语法分析器调用match(T)。如果当前的记号不是T,match()通知错误监听器并尝试重新同步。要重新同步,它有3个选择。它可以删除一个记号,它可以想象出一个,或者可以放弃并抛出异常以便从事基本的同步和返回机制。

如果这样做有意义的话,删除当前记号是最容易去重新同步的方法。让我们再次讨论来自在语法Simple中的简单类定义语言的规则classDef。

1
2
3
4
classDef
    : 'class' ID '{' member+ '}'    // a class has one or more members
      { System.out.println("class " + $ID.text); }
    ;

给定输入class 9 T {int i; },语法分析器将删除9并继续在规则中进行来匹配类体。下图说明了语法分析器消费class后的输入状态:

input-state-1

LA(1)和LA(2)记号前导符号的第一个记号(当前记号)和第二个记号。match(ID)期望LA(1)是一个ID,但它不是。实际上,下一个记号LA(2)才是一个ID。为了恢复分析,我们只需要删除当前记号,消费我们期望的ID并退出match()。

如果语法分析器无法通过删除记号重新同步,则会尝试插入一个记号作为代替。假设我们忘记了ID,以致classDef看到输入class { int i; }。匹配class后,输入状态如下所示:

input-state-2

语法分析器调用match(ID)后发现是{。在这种情况下,语法分析器知道{是下一步需要的记号,因为它在classDef中跟随ID引用。要重新同步,match()可以假装看到标识符并返回,从而允许下一个match('{')调用成功。

如果我们忽略嵌入动作(如引用类名标识符的print语句),那么这很有用。print语句通过$ID.text引用缺失的记号,如果记号为空,将导致异常。而不是简单地假装记号存在,由错误处理程序想象出一个。这个想象出的记号有语法分析器期望的记号类型以及从当前输入记号LA(1)中获得的行和字符的位置信息。这个想象出的记号也用于阻止在监听器和访问者中引用缺失记号的异常。

看看发生了什么的最简单的方法是查看语法分析树,它显示语法分析器如何识别所有记号。在出现错误的情况下, 语法分析树用红色突出显示在重新同步期间语法分析器删除或想象出的记号。对于输入class { int i; }和语法Simple,我们得到以下的语法分析树:

error-parse-tree

语法分析器也会执行嵌入print动作而不抛出异常,因为错误恢复会为$ID想象出一个有效的Token对象。

1
2
3
4
5
6
$ grun Simple prog -gui
class { int i; }
EOF
line 1:6 missing ID at '{'
var i
class <missing ID>

当然,带有文本<missing ID>的标识符对于任何我们试图完成的目标都不是很有用,但至少错误恢复不会导致一堆空指针异常。现在我们知道ANTLR如何对简单的记号引用进行规则内恢复,下面让我们来探讨如何从以前和子规则识别期间的错误中恢复。

从子规则的错误中恢复

为避免刚碰到错误就从子规则循环中抽身,对周围规则强制同步和返回恢复,ANTLR v4会在开始和循环继续测试处自动插入同步检查。机制看起来是这样:

子规则开始 在任何子规则的开头,语法分析器尝试单个记号删除。但是,与记号匹配不同,语法分析器不会尝试单个记号插入。ANTLR很难想象出一个记号,因为它将不得不猜测几个选项中的哪个最终会成功。

循环子规则继续测试 如果子规则是循环结构,(...)*或者(...)+,语法分析器在错误出现时积极尝试恢复以停留在循环中。在成功匹配循环的某个选项后,语法分析器消费直到它找到符合以下这些集合之一的记号:

  1. 循环的另个迭代
  2. 循环后面的
  3. 当前的重新同步集合

让我们先来看下子规则前的单个符号删除。考虑规则classDef中的member+循环结构。如果我们不小心输入一个额外的{member+子规则在跳进member前将会删除这个额外的记号,就像下面语法分析树显示的那样:

member-parse-tree

以下的会话可以证实恢复是妥当的,因为它能正确地识别变量i:

1
2
3
4
5
6
$ grun Simple prog
class T { { int i; }
EOF
line 1:9 extraneous input '{' expecting 'int'
var i
class T

现在让我们尝试一些真正混乱的输入,看看member+循环能否恢复并继续寻找member。

1
2
3
4
5
6
7
8
9
10
11
12
$ grun Simple prog
class T { {
  int x;
  y;;;
  int z;
}
EOF
line 1:9 extraneous input '{' expecting 'int'
var x
line 3:2 extraneous input 'y' expecting {'int', '}'}
var z
class T

语法分析器重新同步并停留在循环中是因为它确定了变量z。语法分析器消费y;;;直到看到另一个成员的开始(就如前面所说的集合3),然后循环回到member。如果输入不包含int z,语法分析器会一直消费下去直到看到}(前面的集合2)并退出循环。语法分析树突出显示已被删除的记号并说明语法分析器仍然把int z;解释为有效的成员。

parse-tree-10

如果提供的规则member有语法错误并且没有},在语法分析器找到}之前我们不希望它进行扫描。语法分析器重新同步可以为查找}抛出整个下面的类定义。相反,语法分析器如果看到集合3中的记号会停止消费,就如同下面的会话那样:

1
2
3
4
5
6
7
8
9
10
11
$ grun Simple prog
class T {
  int x;
  ;
class U { int y; }
EOF
var x
line 3:2 extraneous input ';' expecting {'int', '}'}
class T
var y
class U

如我们所见,语法分析器在看到关键字class时会停止从语法分析树重新同步。

parse-tree-11

除了记号和子规则的识别之外,语法分析器也可能无法匹配语义谓词。

捕捉失败的语义谓词

语义谓词就像断言,它指定在运行时必须为真的条件以便让语法分析器通过它们。如果谓词评估为假,则语法分析器将抛出FailedPredicateException异常,被当前规则的catch所捕获。语法分析器报告错误,并进行通用的同步和返回恢复。

让我们来看一个使用语义谓词限制矢量中的整数数量的例子,规则ints匹配max整数。

1
2
3
4
5
vec4: '[' ints[4] ']' ;
ints[int max]
locals [int i=1]
    : INT ( ',' { $i++; } { $i<=$max }? INT )*
    ;

如果像下面的会话那样,给定一个太多整数的矢量,我们会看到错误消息并得到抛出额外逗号和整数的错误恢复:

1
2
3
4
5
6
$ antlr Vec.g
$ compile Vec
$ grun Vec vec4
[1,2,3,4,5,6]
EOF
line 1:9 rule ints failed predicate: { $i<=$max }?

语法分析树显示语法分析器在第5个整数处检测到错误。

parse-tree-12

错误消息{ $i <= $max }可能对作为文法设计者的我们有帮助,但对我们的用户肯定没有帮助。我们可以通过使用语义谓词上的失败选项把消息变得更加可读。例如,下面是带有计算可读字符串动作的ints规则:

1
2
3
4
ints[int max]
locals [int i=1]
    : INT ( ',' { $i++; } { $i<=$max }?<fail={"exceeded max "+$max}> INT )*
    ;

对于相同的输入,现在我们得到一个更好的消息。

1
2
3
4
5
6
$ antlr VecMsg.g
$ compile VecMsg
$ grun VecMsg vec4
[1,2,3,4,5,6]
EOF
line 1:9 rule ints exceeded max 4

fail选项使用在双引号中的字符串字面量或者计算结果是字符串的动作。如果你想在谓词失败时执行一个函数,这个动作是很方便的。只需使用一个调用{...}?<fail={failedMaxTest()}>那样的函数的动作。

谨慎使用语义谓词来测试输入有效性。在向量示例中,谓词强制执行语法规则,所以它可以抛出异常并尝试恢复。另一方面,如果我们有一个语法上有效但语义无效的结构,那么使用语义谓词并不是一个好主意。

想象一下,在某种语言中,我们可以给变量赋除0外的任何值。这意味着赋值语句x = 0;在语法上是有效的,但在语义上是无效的。当然,我们必须向用户发出一个错误,但是我们不应该触发错误恢复。x = 0;在语法上是完全合法的。从某种意义上说,语法分析器会从错误中自动执行“恢复”。这是个简单的语法问题:

1
2
3
4
assign
    : ID '=' v=INT {$v.int>0}? ';'
      { System.out.println("assign "+$ID.text+" to "); }
    ;

如果规则assign中的谓词抛出异常,则同步和返回行为会在谓词之后抛出;。这可能会进行的很顺利,但我们冒着不完美重新同步的风险。更好的解决办法是手动发出一个出错,并让语法分析器继续匹配正确的语法。所以,我们应该用一个有条件的简单动作而不是谓词。

1
{if ($v.int==0) notifyListeners("values must be > 0");}

现在我们已经看过所有可能引发错误恢复的情况。现在需要指出这个机制存在潜在的缺陷。鉴于语法分析器有时在单次恢复尝试期间不消费任何记号,整体恢复可能会陷入无限循环。如果我们能够不消费记号而恢复并回到语法分析器中的相同位置,我们可以再次恢复而不消费记号。在下一节中,我们将会显示ANTLR如何避免这个陷阱。

错误恢复的失效保护

ANTLR语法分析器具有内置的失效保护,以保证错误恢复终止。如果我们到达相同的语法分析器位置并具有相同的输入位置,语法分析器在尝试恢复之前会强制消费一个记号。现在让我们来看一个失效保护的例子。如果我们在字段定义中添加一个额外的int记号,语法分析器检测到错误并尝试恢复。就像我们将在下个测试中看到的那样,语法分析器将调用recover()并在正确重新同步前尝试重新分析多次。

parser-resynchronization

右边的语法分析树显示从classDef到member有3次调用。

1
2
3
4
5
6
7
8
$ grun Simple prog
class T {
  int int x;
}
EOF
line 2:6 no viable alternative at input 'intint'
var x
class T

第一个引用不匹配任何东西,但第二个引用匹配没有直接联系的int记号。匹配member的第三次尝试匹配正确的int x;序列。

我们来看一下事件的确切顺序。当语法分析器检测到第一个错误时它在规则member中。

1
2
3
4
5
6
member
    : 'int' ID ';'                          // field definition
      { System.out.println("var "+$ID.text); }
    | 'int' f=ID '(' ID ')' '{' stat '}'    // method definition
      { System.out.println("method: "+$f.text); }
    ;

输入int int不适合member的任何选项,所以语法分析器参与同步并返回错误恢复策略。它发出第一个错误信息然后消费记号,直到它在调用栈[prog, classDef, member]的重新同步集合中看到记号为止。

由于语法中的classDef+member+循环,计算重新同步集合有点复杂。在调用member之后,语法分析器可以循环回去并找到另一个成员,或退出循环并找到关闭类定义的'}'。在调用classDef之后,语法分析器可以循环回去查看另一个类的开始或简单地退出prog。因此对于调用栈[prog, classDef, member],重新同步集合是{'int', '}', 'class'}

在这点上,语法分析器恢复不消费记号,因为当前输入记号int在重新同步集合中。它只是返回到调用者:classDef中的member+循环。然后循环尝试匹配另一个成员。不幸的是,因为它没有消费任何记号,当语法分析器返回到member时它检测到另一个错误(虽然它凭借errorRecovery标志消除了虚假错误消息)。

在第2次错误的恢复过程中,语法分析器触发失效保护,因为它已经到达相同的语法分析器位置和输入位置。失效保护在尝试重新同步之前强制记号消费。由于int是在重新同步集合中,它不会消费第2个记号。幸运的是,这正是我们想要的,因为语法分析器现在是正确地同步的。接下来的3个记号表示一个有效的成员定义:int x;。语法分析器再次从member返回到classDef中的循环。第3次,我们回到member,但现在语法分析将会成功。

ANTLR 4权威参考读书笔记(30)

有时我们在调试语法时需要ANTLR提供更好的消息提示,为达到这个目的,我们可以改变ANTLR的标准错误报告。

改变和重定向ANTLR错误消息

默认情况下,ANTLR把所有的错误发送给标准错误,但我们可以通过提供ANTLRErrorListener接口的实现来修改目标和内容。该接口有syntaxError()方法可以应用于词法分析器和语法分析器。方法syntaxError()接收各种有关错误的位置以及错误消息的信息。它也接收语法分析器的一个引用,因此我们可以查询关于识别的状态。

例如,这里是一个错误监听器,它打印规则调用栈以及随后的用有问题的记号信息来加强的通常错误消息:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static class VerboseListener extends BaseErrorListener {
    @Override
    public void syntaxError(Recognizer<?, ?> recognizer,
                            Object offendingSymbol,
                            int line, int charPositionInLine,
                            String msg,
                            RecognitionException e)
    {
        List<String> stack = ((Parser)recognizer).getRuleInvocationStack();
        Collections.reverse(stack);
        System.err.println("rule stack: "+stack);
        System.err.println("line "+line+":"+charPositionInLine+" at "+
        offendingSymbol+": "+msg);
    }
}

使用这个定义,我们的应用可以很容易地在调用开始规则前给语法分析器添加一个错误监听器。

1
2
3
4
SimpleParser parser = new SimpleParser(tokens);
parser.removeErrorListeners();    // remove ConsoleErrorListener
parser.addErrorListener(new VerboseListener());    // add ours
parser.prog();    // parse as usual

在添加我们自己的错误监听器之前,必须先移除标准的终端错误监听器,否则的话就会得到重复的错误消息。

现在让我们看下包含一个额外类名以及缺少字段名的类定义的错误消息看起来是什么样子:

1
2
compile *.java
run TestE_Listener

以下是包含额外类名以及缺少字段名的类定义:

1
2
3
class T T {
  int ;
}

然后我们就会看到如下错误消息:

1
2
3
4
5
rule stack: [prog, classDef]
line 1:8 at [@2,8:8='T',<9>,1:8]: extraneous input 'T' expecting '{'
rule stack: [prog, classDef, member]
line 2:6 at [@5,18:18=';',<8>,2:6]: no viable alternative at input 'int;'
class T

栈[prog, classDef]指出语法分析器在规则classDef中,且被prog调用。注意,记号信息包含在输入流中的字符位置,这在高亮输入中的错误时是非常有用的。例如,记号[@2,8:8='T',<9>,1:8]指出它是记号流中的第3个记号(索引从0开始),字符范围从8到8,记号类型为9,位于第1行,并且在字符位置8(计数从0开始,且TAB被当作一个字符)。

作为另一个示例,让我们构建一个错误监听器TestE_Listener2.java,它打印带有被下划线强调的有错误的记号的行。

1
2
compile *.java
run TestE_Listener2

输入以下数据:

1
2
3
class T XYZ {
  int ;
}

然后就会看如如下错误信息:

1
2
3
4
5
6
7
line 1:8 extraneous input 'XYZ' expecting '{'
class T XYZ {
        ^^^
line 2:6 no viable alternative at input 'int;'
  int ;
      ^
class T

为了让事情变得更容易,我们将忽略TAB——charPositionInLine不是列号,因为TAB的大小不是统一定义的。这里是一个错误监听器实现,强调输入中的错误位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public static class UnderlineListener extends BaseErrorListener {
    public void syntaxError(Recognizer<?, ?> recognizer,
                            Object offendingSymbol,
                            int line, int charPositionInLine,
                            String msg,
                            RecognitionException e) {
        System.err.println("line "+line+":"+charPositionInLine+" "+msg);
        underlineError(recognizer,(Token)offendingSymbol,
        line, charPositionInLine);
    }

    protected void underlineError(Recognizer recognizer,
                                  Token offendingToken, int line,
                                  int charPositionInLine) {
        CommonTokenStream tokens =
            (CommonTokenStream)recognizer.getInputStream();
        String input = tokens.getTokenSource().getInputStream().toString();
        String[] lines = input.split("\n");
        String errorLine = lines[line - 1];
        System.err.println(errorLine);
        for (int i=0; i<charPositionInLine; i++) System.err.print(" ");
        int start = offendingToken.getStartIndex();
        int stop = offendingToken.getStopIndex();
        if ( start>=0 && stop>=0 ) {
            for (int i=start; i<=stop; i++) System.err.print("^");
        }
        System.err.println();
    }
}

关于错误监听器还有一件事需要知道。当语法分析器侦测到一个模棱两可的输入序列时,它会通知错误监听器。默认的错误监听器ConsoleErrorListener实际上不会在终端打印任何东西,也就是说,语法分析器不会通知用户。让我们回顾下能用两种方式匹配输入f();的那段歧义语法。

1
2
3
4
5
6
7
8
9
10
11
12
13
grammar Ambig;

stat: expr ';'    // expression statement
    | ID '(' ')' ';'    // function call statement
    ;

expr: ID '(' ')'
    | INT
    ;

INT : [0-9]+ ;
ID  : [a-zA-Z]+ ;
WS  : [ \t\r\n]+ -> skip ;

如果我们测试这段语法,我们不会看到有关模棱两可的输入的警告。

1
2
3
antlr Ambig.g
compile *.java
grun Ambig stat

然后输入:

1
f();

等到语法分析器侦测到二义性时,告诉语法分析器通过addErrorListener()使用DiagnosticErrorListener的实例。

1
2
parser.removeErrorListeners(); // remove ConsoleErrorListener
parser.addErrorListener(new DiagnosticErrorListener());

你还应该通知语法分析器你对所有的二义性警告感兴趣,而不仅仅是那些可以被侦测到的。为了效率,ANTLR的决策机制并不总是追逐完整的二义性信息。以下代码告诉你如何让语法分析器报告所有的二义性:

1
2
parser.getInterpreter()
.setPredictionMode(PredictionMode.LL_EXACT_AMBIG_DETECTION);

如果你通过grun使用TestRig,用选项-diagnostics去让它使用DiagnosticErrorListener代替默认的终端错误监听器(并且开启LL_EXACT_AMBIG_DETECTION)。

1
grun Ambig stat -diagnostics

输入:

1
f();

你会看到:

1
2
line 1:3 reportAttemptingFullContext d=0, input='f();'
line 1:3 reportAmbiguity d=0: ambigAlts={1, 2}, input='f();'

输出显示语法分析器也会调用reportAttemptingFullContext()。当SLL(*)分析失败并且语法分析器进行更强大的全ALL(*)机制时,ANTLR调用这个方法。

在开发中使用诊断错误监听器是个好主意,因为ANTLR工具不能给你有关歧义语法结构的警告(当生成语法分析器时)。只有在运行时语法分析器才可以侦测到二义性。

ANTLR 4权威参考读书笔记(29)

当我们开发一套语法时,会有很多错误要去修复。在完成语法前,生成的语法分析器不会识别所有有效的句子。在这期间,提供有用信息的错误消息帮助我们追踪到语法问题。一旦我们有了一套正确的语法,然后我们就必须处理用户输入的不合语法的句子,或者甚至由其它程序发生故障生成的不合语法的句子。在这两种情况下,语法分析器对不合语法的输入的响应方式是一个需要重点考虑的问题。

在这里,我们将学习被ANTLR生成的语法分析器使用的自动错误报告和恢复策略。

错误展示

描述ANTLR的错误恢复策略的最好方式是观察由它生成的语法分析器对错误输入的响应。让我们看一个类Java语言的语法,它包含带有字段和方法成员的类定义。该方法有简单的语句和表达式。嵌入动作在语法分析器找到元素时就打印它们。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
grammar Simple;

prog: classDef+ ; // match one or more class definitions

classDef
    : 'class' ID '{' member+ '}' // a class has one or more members
      {System.out.println("class "+$ID.text);}
    ;

member
    : 'int' ID ';'    // field definition
      {System.out.println("var "+$ID.text);}
    | 'int' f=ID '(' ID ')' '{' stat '}'    // method definition
      {System.out.println("method: "+$f.text);}
    ;

stat: expr ';'
      {System.out.println("found expr: "+$stat.text);}
    | ID '=' expr ';'
      {System.out.println("found assign: "+$stat.text);}
    ;

expr: INT
    | ID '(' INT ')'
    ;

INT : [0-9]+ ;
ID  : [a-zA-Z]+ ;
WS  : [ \t\r\n]+ -> skip ;

现在,先让我们使用一些有效的输入运行语法分析器,借以观测正常的输出。

1
2
3
antlr Simple.g
compile *.java
grun Simple prog

输入以下数据:

1
class T { int i; }

你就会看到:

1
2
var i
class T

语法分析器没有显示任何错误,它执行打印语句,报告关于变量i和类定义T的正确识别。

接下来,让我们尝试一个带有方法定义的类,该方法含有一个虚假赋值表达式。

1
grun Simple prog -gui

输入测试数据:

1
2
3
class T {
  int f(x) { a = 3 4 5; }
}

然后你就会看到:

1
2
3
line 2:19 mismatched input '4' expecting ';'
method: f
class T

在4记号处,语法分析器没有找到它期待的“;”,所以它报告一个错误。line 2:19指出有问题的标记是在第2行第19列的字符位置(字符位置从0开始)。因为使用了-gui参数,我们可以看到带有高亮错误节点的语法分析树。

simple-parse-tree

在这里,有两个额外的记号,并且语法分析器给出一个不匹配的通用错误消息。如果只有单个的额外记号,语法分析器可能会智能一点,指出它是一个额外的记号。在接下来的运行测试中,有个额外的“;”在类名和类体之间:

1
grun Simple prog

输入如下:

1
class T ; { int i; }

输出结果:

1
2
3
line 1:8 extraneous input ';' expecting '{'
var i
class T

在“;”处语法分析器报告一个错误,但给出了一个稍微翔实的答案,因为它知道下一个记号就是它实际上在寻找的那个。这个特性被称为单个记号删除(single-token deletion),因为语法分析器可以简单地装作额外的记号不存在并继续执行。

同样的,语法分析器可以在侦测到缺少一个记号时做单个记号插入(single-token insertion)。让我们删掉结束的“}”看看会发生什么。

1
grun Simple prog

然后输入:

1
2
class T {
  int f(x) { a = 3; }

结果是:

1
2
3
4
found assign: a=3;
method: f
line 3:0 missing '}' at '<EOF>'
class T

语法分析器报告它不能找到必须的结束记号“}”。

当语法分析器处于决策点时,会出现另一个常见的语法错误,并且剩余的输入与规则或子规则的任何选项都不一致。例如,如果我们忘记字段声明中的变量名,规则member中的选项都不匹配。语法分析器报告没有可行的选项。

1
grun Simple prog

输入以下代码:

1
class T { int ; }

然后结果是:

1
2
line 1:14 no viable alternative at input 'int;'
class T

在“int”和“;”之间没有空格,因为我们在WS()规则中告诉词法分析器skip()。

如果有词法错误,ANTLR也会放出错误消息,指出哪些字符不能匹配为记号。例如,如果我们提交一个完全未知的字符,我们将得到一个记号识别错误。

1
grun Simple prog

输入:

1
class # { int i; }

输出:

1
2
3
4
line 1:6 token recognition error at: '#'
line 1:8 missing ID at '{'
var i
class <missing ID>

因为没有给出有效的类名,单个记号插入机制召唤了“missing ID”名字,以致类名记号是非空值。如果想控制语法分析器如何召唤记号,可以覆盖DefaultErrorStrategy中的getMissingSymbol()。

ANTLR 4权威参考读书笔记(28)

  • scope 作用域

为了阐明Cymbol语法是可复用的,本节中我们将在不做修改的基础上再次使用它,用于构建一个完全不同的应用。不仅如此,我们还会在同样的树上使用两个不同的监听器做两次遍历。

验证程序符号的使用情况

为Cymbol这样的编程语言构建解释器、编译器或者转换器,我们需要验证Cymbol程序是否正确地使用符号(标志符)。接下来,我们将构建一个Cymbol验证器用于检查以下的条件:

  • 可见的变量引用有相应的定义(在作用域内)。
  • 函数引用有相应的定义(函数可以以任何顺序出现)。
  • 变量不作为函数使用。
  • 函数不作为变量使用。

让我们看一下有许多不同引用的Cymbol示例代码,其中有些是无效的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int f(int x, float y) {
    g();      // forward reference is ok
    i = 3;    // no declaration for i (error)
    g = 4;    // g is not variable (error)
    return x + y;    // x, y are defined, so no problem
}
void g() {
    int x = 0;
    float y;
    y = 9;    // y is defined
    f();      // backward reference is ok
    z();      // no such function (error)
    y();      // y is not function (error)
    x = f;    // f is not a variable (error)
}

为验证程序中的一切都没问题,根据前面的条件,我们应该打印出函数列表和本地变量以及全局符号列表(函数和全局变量)。更进一步,当我们发现问题时应该给出一个错误。例如,使用上述输入,让我们构建一个称为CheckSymbols的应用。

1
java CheckSymbols vars.cymbol

在执行以上命令后会生成如下输出:

1
2
3
4
5
6
7
8
9
10
locals:[]
function<f:tINT>:[<x:tINT>, <y:tFLOAT>]
locals:[x, y]
function<g:tVOID>:[]
globals:[f, g]
line 3:4 no such variable: i
line 4:4 g is not a variable
line 13:4 no such function: z
line 14:4 y is not a function
line 15:8 f is not a variable

实现这类问题的关键是一个被称为符号表的相应的数据结构。我们的应用会把符号存在符号表中,然后通过在符号表中查找符号引用检查它们的正确性。在接下来的部分,我们将大概看一看数据结构看起来像什么,并且使用它去解决手头的验证问题。

符号表中的速成课

语言实现者通常称持有符号的数据结构为符号表。语言的实现决定符号表的结构和复杂性,如果一门语言允许相同的标志符在不同的上下文中指向不同的东西,符号表会将那些符号分组到不同的作用域中。作用域只是一组符号,例如函数的参数列表或变量列表以及在全局作用域内的函数。

符号表自身只是一个符号定义的存储库——它不作任何检查。为了验证代码,我们需要检查表达式中违反我们之前设置的规则的变量和函数引用。符号验证有两个基本操作:定义符号和解决符号。定义一个符号意味着把它添加到一个作用域中。解决一个符号意味着计算出符号指向哪个定义。在某种程度上,解决一个符号意味着找到最近的匹配定义。最近的作用域是最近的封闭作用域。例如,让我们看看另一个Cymbol例子,它在不同的作用域有符号定义。

1
2
3
4
5
6
7
8
9
10
11
12
13
int x;
int y;
void a()
{
    int x;
    x = 1;
    // x resolves to current scope, not x in global scope
    y = 2;
    // y is not found in current scope, but resolves in global
    { int y = x; }
}
void b(int z)
{ }

全局作用域包含变量x和y以及函数a()和b()。函数处于全局作用域,但它们也构成新的作用域用于持有函数的参数,如果有的话。同样嵌套在函数作用域内的是函数本地代码块,它们构成另一个新的作用域。本地变量被约束在嵌套在函数作用域内的本地作用域内。

因为符号x被定义了两次,所以做不到仅把所有标识符都填充进单个集合而没有冲突。这也是作用域出现的原因。我们保留一组作用域,并且一个作用域中的每个标志符只允许有单个定义。我们还保留一个指向父作用域的指针,以便在外层作用域中找到符号定义。这些作用域形成了一棵树。

cymbol-scope-tree

沿着从任何作用域到根(全局作用域)的路径的所有节点形成一堆作用域。为了找到一个符号的定义,我们从围绕着引用的作用域开始,并沿着作用域树向上遍历,直到找到它的定义。

验证器架构

开始构建验证器前,先让我们思考下大方向和总体策略。我们可以根据关键操作——定义和解决——把问题分解。对于定义,我们需要侦听变量和函数定义事件,然后把符号对象插入围绕着定义的作用域。在函数定义的开始处,我们需要压栈一个新的作用域,然后在函数定义的结尾处把它出栈。

为解决和检查符号引用,我们需要侦听在表达式中的变量和函数名字引用。针对每个引用,我们将验证是否有匹配的定义,以及引用是否正确使用符号。

这似乎很直截了当,但有个并发症:在源码文件中,Cymbol程序可以调用在它之后定义的一个函数。我们称它为前向引用。为支持这个特性,我们需要在语法分析树上执行两次遍历。第一遍,或者阶段,定义包含函数的符号,然后第二遍进行解决。用这种方法,第二遍可以看到文件中的所有函数。以下是用于触发在语法分析树上两次遍历的代码:

1
2
3
4
5
6
ParseTreeWalker walker = new ParseTreeWalker();
DefPhase def = new DefPhase();
walker.walk(def, tree);
// create next phase and feed symbol table info from def to ref phase
RefPhase ref = new RefPhase(def.globals, def.scopes);
walker.walk(ref, tree);

在定义阶段,我们将创建许多作用域。除非我们保持对它们的引用,否则垃圾收集器会回收它们。为了符号表能够度过从定义到解决阶段的转变,我们需要追踪这些作用域。储存它们最合乎逻辑的地方是在语法分析树本身(或者,从技术上讲,使用关联值与树节点的注解映射)。然后引用阶段就可以在它下行语法分析树时很简单地获得当前作用域的指针。与函数和本地块关联的树节点将可以获得它们的作用域的指针。

定义和解决符号

考虑到我们的基本策略,让我们从DefPhase开始构建我们的验证器。这个阶段类需要3个字段:一个全局作用域的引用、一个用于追踪我们创建的作用域的语法分析树注解器,以及一个当前作用域的指针。enterFile()的监听器代码在活动开始时创建全局变量。当活动结束时,exitFile()负责打印结果。

1
2
3
4
5
6
7
8
9
10
11
public class DefPhase extends CymbolBaseListener {
    ParseTreeProperty<Scope> scopes = new ParseTreeProperty<Scope>();
    GlobalScope globals;
    Scope currentScope;    // define symbols in this scope
    public void enterFile(CymbolParser.FileContext ctx) {
        globals = new GlobalScope(null);
        currentScope = globals;
    }
    public void exitFile(CymbolParser.FileContext ctx) {
        System.out.println(globals);
    }

当语法分析器找到函数声明时,应用需要创建一个FunctionSymbol对象。作为一个符号和作为一个包含参数的作用域,FunctionSymbol对象负有双重责任。为把函数作用域嵌套在全局作用域内,我们需要把函数作用域压栈。我们通过设置函数的封闭作用域为当前作用域并重置当前作用域来做到这点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void enterFunctionDecl(CymbolParser.FunctionDeclContext ctx) {
    String name = ctx.ID().getText();
    int typeTokenType = ctx.type().start.getType();
    Symbol.Type type = CheckSymbols.getType(typeTokenType);

    // push new scope by making new one that points to enclosing scope
    FunctionSymbol function = new FunctionSymbol(name, type, currentScope);
    currentScope.define(function);    // Define function in current scope
    saveScope(ctx, function);         // Push: set function's parent to current
    currentScope = function;          // Current scope is now function scope
}

void saveScope(ParserRuleContext ctx, Scope s) {
    scopes.put(ctx, s);
}

方法saveScope()使用函数作用域注解functionDecl规则节点,以便在随后的引用阶段可以获得它。当我们离开函数时就出栈函数作用域,因此当前作用域仍然是全局作用域。

1
2
3
4
public void exitFunctionDecl(CymbolParser.FunctionDeclContext ctx) {
    System.out.println(currentScope);
    currentScope = currentScope.getEnclosingScope();    // pop scope
}

本地作用域以类似的方式工作。我们在监听器方法enterBlock()中压栈一个作用域,然后在exitBlock()中出栈它。

在处理好作用域和函数定义后,我们就可以开始定义参数和变量。

1
2
3
4
5
6
7
8
9
10
11
12
public void exitFormalParameter(CymbolParser.FormalParameterContext ctx) {
    defineVar(ctx.type(), ctx.ID().getSymbol());
}
public void exitVarDecl(CymbolParser.VarDeclContext ctx) {
    defineVar(ctx.type(), ctx.ID().getSymbol());
}
void defineVar(CymbolParser.TypeContext typeCtx, Token nameToken) {
    int typeTokenType = typeCtx.start.getType();
    Symbol.Type type = CheckSymbols.getType(typeTokenType);
    VariableSymbol var = new VariableSymbol(nameToken.getText(), type);
    currentScope.define(var); // Define symbol in current scope
}

到此,定义阶段已经完成。

为构建引用阶段,让我们将当前作用域设置为从定义阶段传递过来的全局作用域。

1
2
3
4
5
6
7
public RefPhase(GlobalScope globals, ParseTreeProperty<Scope> scopes) {
    this.scopes = scopes;
    this.globals = globals;
}
public void enterFile(CymbolParser.FileContext ctx) {
    currentScope = globals;
}

然后,就像树遍历器触发Cymbol函数和块的进入与退出事件那样,监听器方法通过访问在定义阶段期间存储在树中的值来及时更新currentScope。

1
2
3
4
5
6
7
8
9
10
11
12
public void enterFunctionDecl(CymbolParser.FunctionDeclContext ctx) {
    currentScope = scopes.get(ctx);
}
public void exitFunctionDecl(CymbolParser.FunctionDeclContext ctx) {
    currentScope = currentScope.getEnclosingScope();
}
public void enterBlock(CymbolParser.BlockContext ctx) {
    currentScope = scopes.get(ctx);
}
public void exitBlock(CymbolParser.BlockContext ctx) {
    currentScope = currentScope.getEnclosingScope();
}

随着遍历器的行进恰当地设置作用域,我们可以通过实现变量引用和函数调用的监听器方法解决符号。当遍历器遇到一个变量引用时,它调用exitVar(),该方法使用resolve()试图在当前作用域的符号表中查找变量名。如果resolve()在当前作用域中没有找到符号,它会查找封闭作用域链。如果必要,resolve()将寻找所有方式直到全局作用域。如果找不到一个合适的定义,它会返回null值。如果resolve()找到的符号是一个函数而不是变量,就需要生成一个错误消息。

1
2
3
4
5
6
7
8
9
10
public void exitVar(CymbolParser.VarContext ctx) {
    String name = ctx.ID().getSymbol().getText();
    Symbol var = currentScope.resolve(name);
    if ( var==null ) {
        CheckSymbols.error(ctx.ID().getSymbol(), "no such variable: "+name);
    }
    if ( var instanceof FunctionSymbol ) {
        CheckSymbols.error(ctx.ID().getSymbol(), name+" is not a variable");
    }
}

处理函数调用基本上是相同的,如果不能找到一个定义或找到了一个变量,都需要发出一个错误。

最后,是用来显示早先需要的输出的构建和测试序列:

1
2
3
antlr Cymbol.g
compile *.java
run CheckSymbols vars.cymbol

输出结果如下所示:

1
2
3
locals:[]
function<f:tINT>:[<x:tINT>, <y:tFLOAT>]
...

ANTLR 4权威参考读书笔记(27)

前面我们主要处理的是数据,今天我们就来做些编程语言方面的事情。

生成调用关系图

软件很难编写和维护,这就是为什么我们试图构建工具去提高我们的生产力和工作效率。例如,在过去的十年里,我们已经看到测试框架、代码覆盖工具和代码分析器的激增,也很高心看到类层次结构的可视化树,以及大部分开发环境支持这个功能。其中有种可视化被称为调用图,它由函数作为节点,并且函数调用作为节点间的有向边。

这本节中,我们将使用Cymbol语法构建一个调用图生成器。考虑以下函数和函数调用集:

1
2
3
4
5
6
7
8
9
10
11
int main() { fact(); a(); }
float fact(int n) {
    print(n);
    if (n == 0) then return 1;
    return n * fact(n - 1);
}
void a() { int x = b(); if false then {c(); d();} }
void b() { c(); }
void c() { b(); }
void d() { }
void e() { }

我们将会把它可视化成如下的调用图:

cymbol-call-graph

可视化的好处是人眼可以很容易地挑出偏差。例如,e()节点是个孤立节点,它意味着没有函数调用它,因此它是一段死代码。一目了然,我们找到一个可以被丢弃的函数。我们还可以通过在图中寻找像fact() -> fact()和b() -> c() -> d()这样的循环非常容易地检测递归。

为了可视化调用图,我们需要读入一段Cymol程序和创建一个DOT文件。例如,以下是我们需要为t.cymbol生成的DOT文件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
digraph G {
    ranksep=.25;
    edge [arrowsize=.5]
    node [shape=circle, fontname="ArialNarrow",
    fontsize=12, fixedsize=true, height=.45];
    main; fact; a; b; c; d; e;
    main -> fact;
    main -> a;
    fact -> print;
    fact -> fact;
    a -> b;
    a -> c;
    a -> d;
    b -> c;
    c -> b;
}

上面的输出包括样本设置描述,例如ranksep=.25;和一列节点和边。为抓住孤立节点,我们需要确保为每个函数名生成节点定义,即使它没有出边和入边。否则它将不会出现在图中。注意在节点定义行末尾的e节点。

1
main; fact; a; b; c; d; e;

我们的策略很简单,当语法分析器找到一个函数声明时,应用会把当前函数名添加到一个列表,并且设置一个字段称为currentFunctionName。当语法分析器看到一个函数调用,应用会记录从currentFunctionName到被调用函数名的一条边。

开始之前,让我们给Cymbol.g中的一些规则选项打上标签,以便获得更精确的监听器方法。

1
2
3
4
5
6
7
8
9
10
11
expr: ID '(' exprList? ')'    # Call
    | expr '[' expr ']'       # Index
    | '-' expr                # Negate
    | '!' expr                # Not
    | expr '*' expr           # Mult
    | expr ('+'|'-') expr     # AddSub
    | expr '==' expr          # Equal
    | ID                      # Var
    | INT                     # Int
    | '(' expr ')'            # Parens
    ;

然后,作为语言应用的基础,把所有图相关的东西封装进一个类。

1
2
3
4
5
6
7
static class Graph {
    // I'm using org.antlr.v4.runtime.misc: OrderedHashSet, MultiMap
    Set<String> nodes = new OrderedHashSet<String>();    // list of functions
    MultiMap<String, String> edges = new MultiMap<String, String>();    // caller->callee
    public void edge(String source, String target) {
        edges.map(source, target);
    }

从节点和边的集合中,我们可以在类Graph的toDOT()中使用一些Java代码转储出适当的DOT代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public String toDOT() {
    StringBuilder buf = new StringBuilder();
    buf.append("digraph G {\n");
    buf.append("    ranksep=.25;\n");
    buf.append("    edge [arrowsize=.5]\n");
    buf.append("    node [shape=circle, fontname=\"ArialNarrow\",\n");
    buf.append("    fontsize=12, fixedsize=true, height=.45];\n");
    buf.append("    ");
    for (String node : nodes) {    // print all nodes first
        buf.append(node);
        buf.append("; ");
    }
    buf.append("\n");
    for (String src : edges.keySet()) {
        for (String trg : edges.get(src)) {
            buf.append("    ");
            buf.append(src);
            buf.append(" -> ");
            buf.append(trg);
            buf.append(";\n");
        }
    }
    buf.append("}\n");
    return buf.toString();
}

现在我们要做的是使用监听器填满这些数据结构,监听器需要两个字段用于记录。

1
2
3
static class FunctionListener extends CymbolBaseListener {
    Graph graph = new Graph();
    String currentFunctionName = null;

然后应用只需要监听两个事件。首先,在语法分析器发现函数声明时记录当前的函数名。

1
2
3
4
public void enterFunctionDecl(CymbolParser.FunctionDeclContext ctx) {
    currentFunctionName = ctx.ID().getText();
    graph.nodes.add(currentFunctionName);
}

其次,当语法分析器侦测到函数调用时,应用需要记录从当前函数到被调用函数的一条边。

1
2
3
4
5
public void exitCall(CymbolParser.CallContext ctx) {
    String funcName = ctx.ID().getText();
    // map current function to the callee
    graph.edge(currentFunctionName, funcName);
}

注意,函数调用不能隐藏在嵌套代码块或诸如a()这样的声明中。

1
void a() { int x = b(); if false then {c(); d();} }

无论什么时候,只要树遍历器发现函数调用就触发监听器方法exitCall()。

通过语法分析树和类FunctionListener,我们可以启动带有监听器的一个遍历器去产生输出。

1
2
3
4
ParseTreeWalker walker = new ParseTreeWalker();
FunctionListener collector = new FunctionListener();
walker.walk(collector, tree);
System.out.println(collector.graph.toString())

在转储DOT字符串前,该代码会打印出函数和边的列表。

1
2
3
antlr Cymbol.g
compile *.java
run CallGraph t.cymbol

以下是部分输出结果:

1
2
3
4
5
6
edges: {main=[fact, a], fact=[print, fact], a=[b, c, d], b=[c], c=[b]},
functions: [main, fact, a, b, c, d, e]
digraph G {
ranksep=.25;
edge [arrowsize=.5]
...

协议分析器的威力

英文原文:http://arstechnica.com/information-technology/2016/09/the-power-of-protocol-analyzers/

问题发生在错综复杂的网络世界里。但要在一时激动之下确定一种新型问题的确切原因变得有些冒险。在这种情况下,当Google-fu耗尽的时候甚至其他能干的工程师也可能会被迫去依赖试错法。

幸运的是,有个秘密武器等待乐意的工程师去部署——协议分析器。该工具允许你明确地确定几乎任何错误的根源,给你提供在底层协议上自我学习的能力。现在唯一的问题是,许多工程师因为(毫无根据的)恐惧而完全回避它。

什么是协议分析器?

协议分析器,或者数据包嗅探器,是一个用于拦截通信量,存储它们,并以一个已解码的、人类可读的状态呈现它们的工具。现代协议分析器比如Wireshark甚至可以靠自己发现基本的问题,然后使用捕获的数据执行统计分析。

不理会特性,数据包嗅探器都以基本相同的方式工作。它们把自己插入到网络堆栈中,把所有通信量复制到一个缓冲区或文件。大部分还会将网络驱动置于“混杂模式”,该模式从根本上说允许这些工具取回所有进入网络堆栈的通信量,而不是只采集前往系统本身的通信量。

协议分析仪如何帮助

在很多情况下,解决一个困难的网络问题的最难部分是找到和理解问题的根源。这种困难的部分源于这样的事实,你对大多数问题使用的工具不是正确的对底层问题的工具。

如果你是一个系统管理员,很有可能你经常用于数据采集的工具是某种日志和错误消息。通常,这些都是解释工具。这些实体试图把原始数据总结为对非开发者或非工程师有意义的东西。因为解释工具是从应用层的视角提供问题的汇总数据,它们往往不能帮助你解决底层的问题。

例如,一条事件日志消息可以告诉你应用程序无法连接到服务器。它甚至可以告诉你根本原因是超时。但这条消息不大可能告诉你超时是由一个黑洞路由器丢弃一个大帧引起。它不能,因为事件日志消息服务不知道错误为何发生。为了使工具知道那个,它需要预测(不解释)这个非常问题,在MTU稳步减少的情况下发送数据包,直到一个通过。如果一个事件日志消息服务早就被编写好要做那件事,从一开始你就不会有这个问题。

当使用错误的工具时,你可能会在某处花上几个小时甚至几周的时间,直到你侥幸得到解决方案。然而,通过使用协议分析器和历久弥新的ping命令,你可以非常容易地在大约5分钟内诊断这个问题。就像早在高中时我的汽车技术辅导员就告诉我的,它全都是关于对任务使用恰当的工具。

除了确定错误,协议分析器提供为数不多的方法之一去证实问题的根源。以前我在微软的时候,棘手问题在团队间来回穿梭是很常见的,因为每个组误解由解释工具提供的数据。首先,问题可能被发送到Exchange团队,接着它可能被穿梭到Active Directory团队,然后最后到Networking团队。

通常,这是因为在其它团队的能力范围之内一个问题好像是合理的。然而,烫手山芋的游戏往往停止在Networking团队。为什么?因为Networking团队的头号工具是证实问题根源的救世主。

网络,像所有的计算,其核心是完全合乎逻辑的。一旦你了解它在幕后是如何工作的,你就有能力在底层确定问题,不论问题是多么独特。作为协议分析的一个伟大副作用,你也将学到很多关于网络的知识,它们将帮助你解决各种各样的网络问题(即使那些不需要协议分析)。

Wireshark基础

现在,有各种各样的协议分析器可供选择,从免费的和相当功能的微软消息分析器到特性极其丰富但十分昂贵的Savvius Omnipeek。多年来我已经使用过大量的分析器,但我最喜欢的用于常规故障排除的协议分析器是Wireshark。它是免费的,开源的,多平台的具有很多特性的分析器。有个充满活力的社区站在它背后,而且Wireshark也相当容易习惯。这让它成为一个很好的开始的地方。

你可以从 https://www.wireshark.org/ 下载用于你操作系统的Wireshark。安装它没有什么特别的,但如果你是安装在Windows上,确保也安装了捆绑的WinPCAP驱动程序。这允许Wireshark实际上捕获数据包(没有它,你只能观看存档的数据包)。

Wireshark通常将你的NIC置于混杂模式。正常情况下,你的NIC只会保留前往你的MAC或者广播MAC(FF-FF-FF-FF-FF-FF)的帧。启用混杂模式后,不管怎样,你的NIC保留所有它听到的帧。

从理论上讲,这意味着你应该接收所有的在你Ethernet段上的数据包。不过,实际上如今几乎所有的Ethernet网络都是交换网络。如果你想接收所有的通信量,必须多做些工作。

一旦你已经安装了Wireshark,使用它是相当简单的。把它打开,你将看到如下显示的屏幕:

wireshark-network-analyzer

这个屏幕给你展示选择一个在它上面捕获数据包的NIC的选项和输入一个用于只捕获一部分入站数据包的过滤器的选项。如果你选择一个NIC然后点击在文件菜单下面的小鱼翅图标,Wireshark将立即开始捕获数据包。

随着数据包被捕获,Wireshark在主界面中实时地显示它们。当你准备停止时,你只需点击在鱼翅图标旁边的小红方块。

wireshark-main-interface

数据包列表部分显示在这个点捕获的每件事物,按它们被捕获的顺序排序(默认)。(你可以通过点击要作为排序依据的标题任意地排序这些数据包。)

数据包细节部分显示Wireshark解码的在数据包中的每个报头。基本上,Wireshark有几乎今天在用的每个协议的解码器,并且为了显示分成字段的数据,解码器工具自动应用到每个数据包。

举例来说,如下,我已经为一个典型的HTTP数据包增加了Ethernet II报头。

wireshark-http-header

你可以清楚地看到Wireshark已经析出了Destination和Source的MAC地址,以及Type字段,它是0x0800。Type字段指出下个报头应该是一个IPv4报头,Wireshark很方便告诉你这个。

这个解码特性使你不必自己计算字节和解码它(不过,如果你愿意,你仍然还可以在原始字节部分做)。如果对原始字节部分有兴趣:Wireshark同时为所有数据提供ASCII转换,它有时提供令人惊讶的数据。在下图,你可以在ASCII视图里的这个数据包中清楚地看到HTTP请求发送的细节。

wireshark-ascii-view

Wireshark同时也提供一些非常实用的分析和统计特性,包括测量响应时间和往返时间的能力。但到目前为止,最有用的特性是过滤功能。

在数据包列表直接的上方是一个文本框,那里你可以输入显示过滤器。默认不使用过滤器,意味着显示被捕获的所有数据包。然而,你经常最后得到信息过载,而过滤掉噪音是数据包分析的一个非常重要的部分。

Wireshark中的过滤器按照一门简单的语言结合协议字段、比较运算符和逻辑运算符以便过滤掉不匹配条件的数据包。例如,过滤器http将只显示HTTP通信量,而过滤器ip.addr == 192.168.1.10将只显示源或目标的IP地址是192.168.1.10的数据包。

当你是第一次开始的时候,过滤可能会有点令人生畏,但通常在Wireshark中学习过滤器的最简单的方法是使用内建的表达式工具。可以通过点击过滤器文本框右边的Expression按钮访问它。

这个工具允许你寻遍Wireshark本身支持的所有协议,挑选你想过滤的字段而不需要知道过滤器动词或语法。只需选择协议,填写呈现的字段,然后过滤器将会为你而建。这里,我使用表达式工具构建一个仅查找Ethernet广播的过滤器。

wireshark-filter-expression

注意工具如何在底部的绿框中显示最终的过滤器语法。通过注意这个字段,你将最终变得熟悉你的最常用的过滤器。

然而,你不能用表达式工具做的一件事是把过滤器串起来。因为那个原因,你需要学习一些逻辑运算符。Wireshark的基本逻辑运算符是and(&&)、or(||)和not(!)。

and被用于结合过滤器,只有满足所有条件的数据包会被显示。例如,过滤器http && ip.addr == 192.168.1.10将只显示在第7层报头中的HTTP协议和在IP报头中的IP地址192.168.1.10两者都包括的数据包。

or被用于查找两者中的任何一个过滤器,因此满足你输入的任何条件的数据包都会被显示。举例来说,过滤器http || ip.addr == 192.168.1.10将显示在第7层报头中的HTTP协议或在IP报头中的IP地址192.168.1.10的数据包。

not被用于从结果中过滤掉一些东西。例如,过滤器ip.addr == 192.168.1.10 ! http将显示有在IP报头中的IP地址192.168.1.10但没有在第7层报头中的HTTP协议的数据包。

关于基本的Wireshark功能最后要注意的事是,除保存你的原始捕获外,你也有多种多样的选项导出捕获。

首先,你导出当前选择的数据包、所有数据包、你标记的数据包或者一段范围的数据包。在这些选项的每一个中,你可以选择导出所有被捕获的数据包或只是被显示的数据包(考虑当前应用的过滤器)。这些选项让你非常具体地知道你想导出哪些数据包。

wireshark-export-packets

此外,你可以把数据包导出成几乎任何常用的格式。在Wireshark中用于文档和电子邮件转出的最好的特性之一是以纯文本或CSV格式导出解剖数据包(完整的数据包解码)的能力。要做到这个,只需从文件菜单里选择“Export Packet Dissections”。

理解你所看到的

尽管所有这些功能都很好,底线是如果你不明白在每个报头中字段的目的它们都是无用的。幸运的是,除了少量专有协议,你遇到的几乎每个协议的规格说明都是免费在线的。

例如:Ethernet,你可以直接到IEEE下载标准;802.3标准可以在 http://standards.ieee.org/about/get/802/802.3.html 获得。它是免费的直接来自权威人士。如果你在查找802.3 Ethernet帧格式,你将发现真的只有3个感兴趣的字段:目标MAC地址、源MAC地址和类型/长度字段。下图中在Wireshark解剖体左边的是来自IEEE 802.3规格说明Section 1中Part 3.1.1的Figure 3-1:

wireshark-packet-format

如果你想知道preamble和SFD发生了什么,它们在帧从NIC到Wireshark向上传递给栈之前被移除。同样地,你通常不会在末尾看到FCS,因为它在向上传递帧之前被剥去。

在第2层上面,所有TPCTCP/IP协议由IETF管理和由RFCs(请求评论)定义。所有这些RFCs可以在站点 https://www.rfc-editor.org/ 上即刻地免费地获得。虽然它们有点简洁(并且因为这个原因有时难以理解),它们总是正确的,具体问题的澄清可以使用Google快速搜索获得。

举例来说,通常混淆新手的事情之一是大量TCP重置,或者在TCP报头中数据包有打开的RST标记。浏览RFC 793(TCP),你可能会得到RST总是用信号告知一些坏事情的印象。几乎所有的35个左右提到的RST与某种错误条件有关联。

然而,使用关键词“tcp rst from client”的Google快速搜索将让你得到大量的关于这个现象的很好的讨论。也许最好的是来自Wireshark论坛,在那里他们解释说这很平常,因为客户端应用仅仅被编码去重置链接而不是优雅地关闭它。在这种情况下,服务端已经发送一个FIN。作为回复一个FIN/ACK并等待最终的ACK的替换,客户端只需通过发送一个RST并中止会话来优化过程。在下面的示例中这可以清楚地被看到。

wireshark-pcap-example

除了规格说明和Google,另一个学习协议通常如何运转的良好来源是示例跟踪的资料库。这些示例跟踪允许你去查看相当典型的既常见又晦涩的协议操作,以及一些十分罕见的平常可能不会碰到的错误。

一个很好的起点是Wireshark Wiki上的样板捕获:https://wiki.wireshark.org/SampleCaptures 。在这里有大量非常有用的捕获让你去下载以及用过滤和其它Wireshark特性做实验,包括像广播风暴、病毒和攻击套装这样有意思的错误。如果这些还不够,在这个页面上还有一些其它资源的链接去协助你。但是毫无疑问地,变得擅长协议分析的最快方式是仔细观看大量的捕获并试图理解被使用的协议。

如何得到好的捕获

如果不能捕获正确的数据,世界上所有的领悟都无济于事。在最基本的层面,目标是只捕获涉及你试图解决的问题的数据包,有效减少你跟踪里的噪音。

为了做到这点,你可以使用一个捕获过滤器去从捕获中排除那些匹配过滤器外的所有数据。如果你确切地知道你在寻找什么这会工作的很好,但往往这种方法会导致你不能觉察一些重要的事情。大多数时候你只有一个问题是什么的粗略想法,或者你忘了一些潜在的找到错误的关键的过程。如果这种情况发生,使用捕获过滤器就没那么幸运,而且你不能返回和没重设置它就不过滤捕获。

例如,在诊断一个网站的性能问题时,你可能决定使用一个捕获过滤器集从Web服务器自身取得捕获,以便只捕获在其与客户端系统和后台SQL服务器之间往返的数据。然而,这个问题实际上可能仅仅是Web服务器使用的身份验证服务器过载,等待身份验证才是引起整个性能问题的原因。使用你选择的捕获过滤器你将永远不会发现这个问题。

这是我倾向于捕获所有数据并且使用显示过滤器去减少跟踪里的噪音的原因。这不是说捕获过滤器完全不必要。捕获过滤器的一个常见用途是当你有一个非常繁忙的你正在捕获的千兆或万兆连接的时候,捕获过滤器变得有用仅仅是因为大量的数据。不过,你始终需要牢记过滤器的限制。

得到一个好的捕获的第二部分是正确识别你需要捕获的系统。举例来说,在前面关于Web服务器性能问题的例子中,我可能首先会从Web服务器和Web客户端两者取得同时发生的捕获。这样你可以看到两边的正常预期行为的任何偏差,这有助于你将问题隔离到服务器或客户端。

一旦查明延迟是一个与身份验证有关的服务端问题,然后我会从Web服务器和身份验证服务器两者取得其它的跟踪。这样,我可以看到是本地到身份验证服务器的问题还是等待像DNS这样其它服务的问题或者Global Catalog是实际上的罪魁祸首。

得到一个好的捕获的第三步是在成功和失败条件中都使用捕获。举例来说,如果你有一个间歇性的Web服务器性能问题,设法在站点正常和不正常工作时都得到跟踪。这能给你一个好的和坏的比较跟踪,可以使用它去隔离问题。

最后,当处理一个间歇性的问题时,你会发现很难得到一个失败捕获。在这种情况下,Wireshark有一个很重要的特性被称为环形缓冲区,它允许你持续地捕获。

通常,特别在一个繁忙的网络上,持续的捕获将冒填满磁盘的风险。但有了环形缓冲区,Wireshark会写入文件直到它达到指定大小或者经过一段时间,然后它会切换到一个新文件。一旦指定数量的文件已经被写入,程序删除最旧的文件。例如,看看下面我已经定义的设置:

wireshark-capture-interfaces

这个配置告诉Wireshark不管文件大小每10分钟创建一个新文件,并且确保程序保留总计3个文件,根据需要删除最旧的。这确保从错误被通知的时间起我有30分钟去停止捕获。这是一个非常有用的技术用于捕获极其间歇性的问题。

这些是你需要的以便用Wireshark开始故障排除的所有基本技术。使用这些技术和资源,你会发现你经常能用比几乎任何其它技术更短的时间找到和验证网络问题的原因。快乐的故障排除。

ANTLR 4权威参考读书笔记(26)

今天准备做的是把JSON文本文件转换成XML文本文件。

把JSON转换成XML

许多Web服务返回的是JSON数据,但是我们可能会遇到一种情况,需要把JSON数据送给那些只接受XML数据的代码。这就需要我们构建一个JSON到XML的转换器。我们的目标是读入像下面这样的JSON数据:

1
2
3
4
5
6
7
{
"description" : "An imaginary server config file",
"logs" : {"level":"verbose", "dir":"/var/log"},
"host" : "antlr.org",
"admin": ["parrt", "tombu"],
"aliases": []
}

放出等价的XML数据,就像下面这样的:

1
2
3
4
5
6
7
8
9
10
11
<description>An imaginary server config file</description>
<logs>
  <level>verbose</level>
  <dir>/var/log</dir>
</logs>
<host>antlr.org</host>
<admin>
  <element>parrt</element>
  <element>tombu</element>
</admin>
<aliases></aliases>

正如我们对CSV做的那样,让我们给JSON语法中的一些选项打上标签,以便让ANTLR生成更精确的监听器方法。

1
2
3
4
5
6
7
8
object
    : '{' pair (',' pair)* '}'    # AnObject
    | '{' '}'                     # EmptyObject
    ;
array
    : '[' value (',' value)* ']'  # ArrayOfValues
    | '[' ']'                     # EmptyArray
    ;

我们将对规则value做同样的事,但是稍有不同。除3个选项外的其它所有选项只需要返回被匹配的值的文本,所以我们可以为其它所有选项使用相同的标签,使语法分析树遍历器为那些选项触发相同的监听器方法。

1
2
3
4
5
6
7
8
9
value
    : STRING    # String
    | NUMBER    # Atom
    | object    # ObjectValue
    | array     # ArrayValue
    | 'true'    # Atom
    | 'false'   # Atom
    | 'null'    # Atom
    ;

为构建这样的转换器,明智的做法是让每个规则返回被它匹配的输入短语的XML等价物。为追踪部分结构,我们使用字段xml和两个帮助方法来注解语法分析树。

1
2
3
4
public static class XMLEmitter extends JSONBaseListener {
    ParseTreeProperty<String> xml = new ParseTreeProperty<String>();
    String getXML(ParseTree ctx) { return xml.get(ctx); }
    void setXML(ParseTree ctx, String s) { xml.put(ctx, s); }

我们把每棵子树转换后的字符串挂载到该子树的根节点。在语法分析树更高节点上工作的方法可以捕获这些值以便计算更大的字符串。然后挂载在根节点上的字符串完成计算。

让我们从最简单的转换开始。value的Atom选项返回匹配记号的文本。

1
2
3
public void exitAtom(JSONParser.AtomContext ctx) {
    setXML(ctx, ctx.getText());
}

字符串基本上是相同的,只是我们必须去除双引号。

1
2
3
public void exitString(JSONParser.StringContext ctx) {
    setXML(ctx, stripQuotes(ctx.getText()));
}

如果value()规则方法找到一个对象或数组,它可以把组合元素的部分转换拷贝到它自己的语法分析树节点。以下代码是找到对象时的处理:

1
2
3
4
public void exitObjectValue(JSONParser.ObjectValueContext ctx) {
    // analogous to String value() {return object();}
    setXML(ctx, getXML(ctx.object()));
}

一旦我们可以转换所有的值,我们需要担心名-值对以及把它们转换成标签和文本。生成的XML的标签名字来源于STRING ':' value选项中的STRING。在左右尖括号之间的文本来源于挂载在value子节点上的文本。

1
2
3
4
5
6
public void exitPair(JSONParser.PairContext ctx) {
    String tag = stripQuotes(ctx.STRING().getText());
    JSONParser.ValueContext vctx = ctx.value();
    String x = String.format("<%s>%s</%s>\n", tag, getXML(vctx), tag);
    setXML(ctx, x);
}

JSON对象由名-值对组成。因此,对于被选项中标记为AnObject的object找到的每个对,我们把计算后的结果追加在语法分析树。

1
2
3
4
5
6
7
8
9
10
11
public void exitAnObject(JSONParser.AnObjectContext ctx) {
    StringBuilder buf = new StringBuilder();
    buf.append("\n");
    for (JSONParser.PairContext pctx : ctx.pair()) {
        buf.append(getXML(pctx));
    }
    setXML(ctx, buf.toString());
}
public void exitEmptyObject(JSONParser.EmptyObjectContext ctx) {
    setXML(ctx, "");
}

处理数组遵循相似的模式,只是简单地连接来自子节点的结果列表,然后把它们包裹在<element>标签中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void exitArrayOfValues(JSONParser.ArrayOfValuesContext ctx) {
    StringBuilder buf = new StringBuilder();
    buf.append("\n");
    for (JSONParser.ValueContext vctx : ctx.value()) {
        buf.append("<element>"); // conjure up element for valid XML
        buf.append(getXML(vctx));
        buf.append("</element>");
        buf.append("\n");
    }
    setXML(ctx, buf.toString());
}
public void exitEmptyArray(JSONParser.EmptyArrayContext ctx) {
    setXML(ctx, "");
}

最后,我们需要使用从一个对象或数组收集来的全部转换注解语法分析树的根节点。

1
2
3
json: object
    | array
    ;

我们可以在监听器里用一个集合运算做到这点。

1
2
3
public void exitJson(JSONParser.JsonContext ctx) {
    setXML(ctx, getXML(ctx.getChild(0)));
}

以下是构建和测试序列:

1
2
3
antlr JSON.g
compile *.java
run JSON2XML t.json

下面的是部分的输出结果:

1
2
3
4
<description>An imaginary server config file</description>
<logs>
<level>verbose</level>
...

有些转换不总是像JSON到XML那样直白的。但是,这个例子向我们表明如何通过拼凑部分翻译短语处理句子转换问题。

ANTLR 4权威参考读书笔记(25)

这次我们要做的是通过监听器实现CSV文件的加载器,用于建立一个二维列表数据结构。

加载CSV数据

我们的目标是构建一个监听器去加载CSV数据到一个映射列表数据结构中,这是任何数据格式阅读器或配置文件阅读器都会做的事。我们会收集每行的字段并放到一个映射中,构成头名-值组合。以下是示例文件t.csv的内容:

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

我们想要看到如下的映射列表被打印出:

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

为了在监听器中得到精确的方法,我们给CSV语法中field规则的每个选项打上标签:

1
2
3
4
5
6
7
8
9
10
11
12
13
grammar CSV;

file : hdr row+ ;
hdr : row ;
row : field (',' field)* '\r'? '\n' ;
field
    : TEXT    # text
    | STRING  # string
    |         # empty
    ;

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

我们可以从定义我们需要的数据结构开始监听器的实现。首先,我们需要的数据结构是称为rows的映射列表。我们也需要在头行中找到的列名列表header。为处理数据行,我们需要把字段值读到一个临时列表currentRowFieldValues中,然后把列名映射到那些值上。以下是监听器LoadCSV.java的实现代码:

1
2
3
4
5
6
7
8
public static class Loader extends CSVBaseListener {
    public static final String EMPTY = "";
    /** Load a list of row maps that map field name to value */
    List<Map<String,String>> rows = new ArrayList<Map<String, String>>();
    /** List of column names */
    List<String> header;
    /** Build up a list of fields in current row */
    List<String> currentRowFieldValues;

下面的3个规则方法通过计算适当的字符串处理字段值,并把它添加到currentRowFieldValues中。

1
2
3
4
5
6
7
8
9
public void exitString(CSVParser.StringContext ctx) {
    currentRowFieldValues.add(ctx.STRING().getText());
}
public void exitText(CSVParser.TextContext ctx) {
    currentRowFieldValues.add(ctx.TEXT().getText());
}
public void exitEmpty(CSVParser.EmptyContext ctx) {
    currentRowFieldValues.add(EMPTY);
}

在我们能处理数据行之前,我们需要从第一行取得列名列表。头行在语法上仅仅是另外的行,但我们在对待它时要不同于常规的数据行,那意味着我们需要检查上下文。暂时让我们假设在exitRow()执行后,currentRowFieldValues包含列名列表。要填充header,我们只需要捕获第一行的字段值。

1
2
3
4
public void exitHdr(CSVParser.HdrContext ctx) {
    header = new ArrayList<String>();
    header.addAll(currentRowFieldValues);
}

谈到行时,我们需要两个操作:一个是当我们开始一行时,另一个是当我们结束一行时。当我们开始一行时,我们需要分配或清除currentRowFieldValues,准备获取一组新的数据。

1
2
3
public void enterRow(CSVParser.RowContext ctx) {
    currentRowFieldValues = new ArrayList<String>();
}

在行结束的时候,我们必须考虑上下文。如果我们仅仅加载头行,那我们不能改变rows字段,因为列名不是数据。在exitRow()中,我们可以通过查看在语法分析树中的父节点的getRuleIndex()值(或者询问父节点是否是HdrContext类型)测试上下文。如果当前行是数据行,我们将通过同时遍历header中的列名和currentRowFieldValues中的值获取的内容创建映射。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void exitRow(CSVParser.RowContext ctx) {
    // If this is the header row, do nothing
    // if ( ctx.parent instanceof CSVParser.HdrContext ) return; OR:
    if ( ctx.getParent().getRuleIndex() == CSVParser.RULE_hdr ) {
        return;
    }
    // It's a data row
    Map<String, String> m = new LinkedHashMap<String, String>();
    int i = 0;
    for (String v : currentRowFieldValues) {
        m.put(header.get(i), v);
        i++;
    }
    rows.add(m);
}

到这里,加载CSV数据到数据结构中的任务就算已经完成。在使用ParseTreeWalker遍历树后,我们就可以紧接着打印出rows字段:

1
2
3
4
ParseTreeWalker walker = new ParseTreeWalker();
Loader loader = new Loader();
walker.walk(loader, tree);
System.out.println(loader.rows);

以下是构建和测试序列:

1
2
3
antlr CSV.g
compile *.java
run LoadCSV t.csv

下面显示的是输出结果:

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