ANTLR词法分析器如何消除其规则的歧义(或者为什么我的解析器会产生"不匹配的输入"错误)？

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;

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

第1行:第6行不匹配输入'42'期望INTEGER
第1行:8输入不匹配';' 期待'='

为什么不承认ANTLR 42作为INTEGER在这种情况下？
它应该匹配模式[0-9]+就好了.

如果我颠倒了定义的顺序INTEGER并且IDENTIFIER定义它似乎有效,但为什么顺序首先重要？

Answer 1

在ANTLR中,词法分析器与解析器隔离,这意味着它将根据词法分析器语法规则将文本拆分为类型化的标记,并且解析器对此过程没有影响(例如,它不能说" INTEGER现在给我一个") .它自己生成令牌流.此外,解析器不关心令牌文本,它只关心与其规则匹配的令牌类型.

当几个词法分析器规则可以匹配相同的输入文本时,这可能很容易成为问题.在这种情况下,将根据这些优先级规则选择令牌类型:

• 首先,选择与最长输入子字符串匹配的词法分析器规则
• 如果最长匹配的子字符串等于隐式定义的标记(如'='),则使用隐式规则作为标记类型
• 如果多个词法分析器规则匹配相同的输入,请根据定义顺序选择第一个

为了有效地使用ANTLR,这些规则非常重要.

在该问题的示例中,解析器期望看到以下标记流与keyValue解析器规则匹配:IDENTIFIER '=' INTEGER ';'where '='和';'是隐式标记类型.

由于42可以搭配既 INTEGER和IDENTIFIER,并IDENTIFIER首先定义,解析器会收到以下输入:IDENTIFIER '=' IDENTIFIER ';'它不能够匹配的keyValue规则.记住,解析器不能传达到词法分析器,它只能从它接收数据,因此不能说"尝试匹配INTEGER下一个".

建议最小化词法分析器规则重叠以限制此效果的影响.在上面的例子中,我们有几个选择:

• 重新定义IDENTIFIER为[A-Za-z] [A-Za-z0-9]*(要求以字母开头).这完全避免了问题,但是防止了定义以数字开头的标识符名称,因此它改变了语法的意图.
• 重新排序INTEGER和IDENTIFIER.这解决了大多数情况下的问题,但是阻止了完全数字标识符的定义,因此它也以一种微妙的,不那么明显的方式改变了语法的意图.
• 当词法分析器规则重叠时,使解析器接受两种令牌类型:
  首先,交换INTEGER并IDENTIFIER优先使用INTEGER.然后,定义解析器规则,id: IDENTIFIER | INTEGER;然后使用该规则而不是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

将从词法分析器生成以下标记序列:

IDENTIFIER 'foo' BAR IDENTIFIER IDENTIFIER EOF

• aaa 是类型的 IDENTIFIER

  只有IDENTIFIER规则可以匹配此令牌,没有歧义.

• foo 是类型的 'foo'

  解析器规则randomParserRule引入隐式'foo'令牌类型,该类型优先于IDENTIFIER规则.

• bar 是类型的 BAR

  此文本与BAR规则之前定义的IDENTIFIER规则匹配,因此具有优先权.

• baz 是类型的 IDENTIFIER

  此文本与BAZ规则匹配,但也与IDENTIFIER规则匹配.后者是按照之前的 定义选择的BAR.

  鉴于语法,BAZ永远无法匹配,因为IDENTIFIER规则已经涵盖了所有BAZ可以匹配的内容.

• barz 是类型的 IDENTIFIER

  该BAR规则可以匹配该字符串(的前3个字符bar),但IDENTIFIER规则将匹配4个字符.作为IDENTIFIER一个较长的字符串相匹配,则选择了BAR.

• EOF(文件结尾)是一个隐式定义的标记类型,它始终出现在输入的末尾.

根据经验,应在更通用的规则之前定义特定规则.如果规则只能匹配先前定义的规则已涵盖的输入,则永远不会使用该规则.

隐式定义的规则,例如'foo'它们就像在所有其他词法分析规则之前定义一样.由于它们增加了复杂性,因此建议完全避免它们并且声明明确的词法规则.只需在一个地方拥有一个令牌列表而不是将它们分散在语法中就是这种方法的一个引人注目的优势.