parsing - ANTLR词法分析器如何消除其规则的歧义(或者为什么我的解析器会产生 "mismatched input"错误)？

Question

Note: This is a self-answered question that aims to provide a reference about one of the most common mistakes made by ANTLR users.

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

grammar KeyValues;

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

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

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

输入以下内容:

foo = 42;

我最终遇到以下运行时错误:

line 1:6 mismatched input '42' expecting INTEGER
line 1:8 mismatched input ';' expecting '='

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

如果我颠倒了 INTEGER和 IDENTIFIER的定义顺序，那似乎可行，但是为什么顺序首先重要呢？

Answer 1

在ANTLR中，词法分析器与解析器是隔离的，这意味着它将根据词法分析器语法规则将文本拆分为类型化的标记，并且解析器对此过程没有任何影响(例如，不能说“现在给我一个INTEGER”) )。它自己产生 token 流。此外，解析器不在乎 token 文本，它仅在乎 token 类型以匹配其规则。

当多个词法分析器规则可以匹配相同的输入文本时，这很容易成为问题。在这种情况下，将根据以下优先规则选择 token 类型:

首先，选择与最长输入子字符串

匹配的词法分析器规则

如果最长匹配的子字符串等于隐式定义的标记(如'=')，则使用隐式规则作为标记类型

如果多个词法分析器规则匹配相同的输入，则根据定义顺序

选择第一个

为了有效地使用ANTLR，请牢记这些规则非常重要。

在问题的示例中，解析器希望看到以下 token 流与 keyValue解析器规则匹配: IDENTIFIER '=' INTEGER ';'其中 '='和 ';'是隐式 token 类型。

由于 42可以同时匹配 INTEGER和 IDENTIFIER，并且首先定义了 IDENTIFIER，所以解析器将接收以下输入: IDENTIFIER '=' IDENTIFIER ';'，它将无法与 keyValue规则匹配。请记住，解析器无法与词法分析器通信，它只能从词法分析器接收数据，因此它不能说“尝试下一步匹配 INTEGER”。

建议尽量减少词法分析器规则重叠，以限制此效果的影响。在上面的示例中，我们有几个选项:

将IDENTIFIER重新定义为[A-Za-z] [A-Za-z0-9]*(要求以字母开头)。这样可以完全避免问题，但是可以防止定义以数字开头的标识符名称，因此它会改变语法的意图。

重新排序INTEGER和IDENTIFIER。这解决了大多数情况下的问题，但阻止定义全数字标识符，因此，它也以一种微妙的，不太明显的方式改变了语法的意图。

当词法分析器规则重叠时，使解析器接受两种 token 类型:
首先，交换INTEGER和IDENTIFIER，使其优先于INTEGER。然后，定义一个解析器规则id: IDENTIFIER | INTEGER;，然后在其他解析器规则中使用该规则而不是IDENTIFIER，这会将keyValue更改为key=id '=' value=INTEGER ';'。

这是第二个词法分析器行为示例:

以下是组合语法:

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

将从词法分析器生成以下 token 序列:
IDENTIFIER 'foo' BAR IDENTIFIER IDENTIFIER EOF

aaa的类型为IDENTIFIER
只有IDENTIFIER规则可以匹配此 token ，没有歧义。

foo的类型为'foo'
解析器规则randomParserRule引入了隐式'foo' token 类型，该类型比IDENTIFIER规则优先。

bar的类型为BAR
此文本与BAR规则匹配，该规则在IDENTIFIER规则之前定义，因此具有优先权。

baz的类型为IDENTIFIER
该文本与BAZ规则匹配，但也与IDENTIFIER规则匹配。选择后者，因为它是在BAR之前定义的。

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

barz的类型为IDENTIFIERBAR规则可以匹配此字符串的前3个字符(bar)，但是IDENTIFIER规则将匹配4个字符。由于IDENTIFIER与更长的子字符串匹配，因此会选择它作为BAR的替代项。

EOF(文件末尾)是隐式定义的 token 类型，它始终出现在输入的末尾。

根据经验，应在更通用的规则之前定义特定的规则。如果一个规则只能匹配先前定义的规则已经覆盖的输入，则将永远不会使用该规则。

隐式定义的规则(例如 'foo')就像在所有其他词法分析器规则之前定义的一样。由于它们增加了复杂性，因此建议完全避免它们，而改为声明显式词法分析器规则。仅将标记列表放在一个位置，而不是将它们分散在整个语法中，是该方法的显着优势。