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中，词法分析器与解析器是隔离的，这意味着它会根据词法分析器的文法规则将文本拆分成typed个token，解析器对它没有影响这个过程（它不能说 "give me an INTEGER now" 例如）。它自己产生一个令牌流。此外，解析器不关心令牌文本，它只关心匹配其规则的令牌类型。

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

选择代币类型

首先，select词法分析器规则匹配最长输入子串
如果最长的匹配子串等于隐式定义的标记（如'='），使用隐式规则作为标记类型
如果多个词法分析器规则匹配相同的输入，选择第一个，基于定义顺序

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

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

由于42可以匹配INTEGER和IDENTIFIER，并且IDENTIFIER先定义，解析器将接收以下输入：IDENTIFIER '=' IDENTIFIER ';' 它无法与 keyValue 规则匹配。请记住，解析器不能与词法分析器通信，它只能从它接收数据，因此它不能说 "try to match INTEGER next".

建议尽量减少词法分析器规则的重叠，以限制这种影响的影响。在上面的例子中，我们有几个选项：

重新定义IDENTIFIER为[A-Za-z] [A-Za-z0-9]*（要求以字母开头）。这完全避免了这个问题，但阻止了定义以数字开头的标识符名称，因此它改变了语法的意图。
重新排序 INTEGER 和 IDENTIFIER。这解决了大多数情况下的问题，但阻止了定义全数字标识符，因此它也以一种微妙的、不那么明显的方式改变了语法的意图。
当词法分析器规则重叠时让解析器接受两种标记类型：
首先，交换 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

将从词法分析器中产生以下标记序列：

IDENTIFIER 'foo' BAR IDENTIFIER IDENTIFIER EOF

aaa 是类型 IDENTIFIER

只有IDENTIFIER规则才能匹配这个token，没有歧义。
foo 的类型是 'foo'

解析器规则 randomParserRule 引入了隐式 'foo' 标记类型，它优先于 IDENTIFIER 规则。
bar 的类型是 BAR

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

此文本匹配 BAZ 规则，但它也匹配 IDENTIFIER 规则。选择后者，因为它被定义为 before BAR.

鉴于语法，BAZ 永远无法匹配，因为 IDENTIFIER 规则已经涵盖了 BAZ 可以匹配的所有内容。
barz 是类型 IDENTIFIER

BAR规则可以匹配这个字符串的前3个字符（bar），但是IDENTIFIER规则会匹配4个字符。由于 IDENTIFIER 匹配更长的子字符串，因此它被选中而不是 BAR.
EOF（文件结尾）是一种隐式定义的标记类型，它总是出现在输入的末尾。

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

隐式定义的规则，例如 'foo' 就像它们是在所有其他词法分析器规则之前定义的一样。由于它们增加了复杂性，因此建议完全避免使用它们并改为声明显式词法分析器规则。只在一个地方有一个标记列表而不是将它们分散在语法中是这种方法的一个引人注目的优势。

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

How does the ANTLR lexer disambiguate its rules (or why does my parser produce "mismatched input" errors)?

parsing

antlr

lexer

antlr4