乐者为王

Do one thing, and do it well.

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 "); }
    ;

Comments