ANTLR lexer如何消除其规则的歧义（或者为什么我的解析器会产生“不匹配的输入”错误）？

Question

注意：这是一个自我回答的问题，旨在提供一个关于ANTLR用户最常见的错误之一的参考。

当我测试这个非常简单的语法时：

grammar KeyValues;

keyValueList: keyValue*;
keyValue: key=IDENTIFIER '=' value=INTEGER ';';

IDENTIFIER: [A-Za-z0-9]+;
INTEGER: [0-9]+;

WS: [ \t\r\n]+ -> skip;

foo = 42;

在这种情况下，ANTLR为什么不将42识别为整数？
它应该很好地匹配模式[0-9]+。

如果我颠倒定义integer和identifier的顺序，这似乎是可行的，但为什么顺序首先重要呢？

Answer 1

在ANTLR中，lexer与解析器是隔离的，这意味着它会根据lexer语法规则将文本拆分为类型化的令牌，解析器对这个过程没有影响（它不能说“现在给我一个integer”）。它自己产生一个令牌流。而且，解析器并不关心令牌文本，它只关心与它的规则匹配的令牌类型。

当几个lexer规则可以匹配相同的输入文本时，这可能很容易成为一个问题。在这种情况下,将根据以下优先规则选择令牌类型：

• 首先，选择与最长输入子字符串匹配的lexer规则
• 如果匹配的最长子字符串等于隐式定义的令牌（如'=')，请使用隐式规则作为令牌类型
• 如果多个lexer规则匹配相同的输入，则根据定义顺序选择第一个规则

为了有效地使用ANTLR，记住这些规则是非常重要的。

在问题的示例中，解析器希望看到以下令牌流以匹配keyvalue解析器规则:identifier'='integer'；“其中'='和；”是隐式令牌类型。

由于42可以同时匹配integer和identifier并且identifier是首先定义的，解析器将接收以下输入:identifier'='identifier；它将无法与keyvalue规则匹配的'。请记住，解析器不能与lexer通信，它只能从lexer接收数据，因此它不能说“Try to matchintegernext”。

最好将lexer规则的重叠最小化，以限制这种效果的影响。在上面的例子中，我们有几个选项：

• 将标识符重新定义为[A-Za-z][A-Za-z0-9]*（要求它以字母开头）。这完全避免了这个问题，但防止定义以数字开头的标识符名称，因此它改变了语法的意图。
• 重新排序整数和标识符。这解决了大多数情况下的问题，但防止定义完全数值化的标识符，因此它还以一种微妙的、不那么明显的方式改变了语法的意图。
• 当lexer规则重叠时，使解析器接受两种令牌类型:
  首先，交换integer和identifier以便优先使用integer。然后，定义分析器规则id:IDENTIFIER；然后使用该规则而不是其他分析器规则中的IDENTIFIER，这会将keyvalue更改为key=id'='value=integer'；'。

下面是第二个lexer行为示例总结：

以下组合语法：

grammar LexerPriorityRulesExample;

// Parser rules

randomParserRule: 'foo'; // Implicitly declared token type

// Lexer rules

BAR: 'bar';
IDENTIFIER: [A-Za-z]+;
BAZ: 'baz';

WS: [ \t\r\n]+ -> skip;

考虑到以下输入：

aaa foo bar baz barz

将从lexer生成以下令牌序列：

identifier'foo'baridentifieridentifierEof

>

AAA是标识符类型

只有identifier规则可以与此令牌匹配，没有二义性。

foo的类型为'foo'

bar的类型为bar

此文本与bar规则匹配，该规则在identifier规则之前定义，因此具有优先级。

BAZ类型为identifier

该文本与BAZ规则匹配，但也与identifier规则匹配。选择后者，因为它是在bar之前定义的。

给定语法，BAZ将永远无法匹配，因为Identifier规则已经覆盖了BAZ可以匹配的所有内容。

barz类型为标识符

bar规则可以匹配此字符串(bar)的前3个字符，但identifier规则将匹配4个字符。由于identifier匹配较长的子字符串，因此它被选在bar之上。

EOF（文件末尾）是隐式定义的标记类型，它总是出现在输入的末尾。

作为经验法则，特定的规则应该在更通用的规则之前被定义。如果规则只能匹配先前定义的规则已经覆盖的输入，则永远不会使用该规则。

隐式定义的规则（如'foo'）的作用就好像它们是在所有其他lexer规则之前定义的。由于它们增加了复杂性，因此最好完全避免它们，而声明显式的lexer规则。这种方法的一个显著优点是只在一个地方有一个令牌列表，而不是将它们分散在语法中。