ANTLR4 列表中标记的非贪婪匹配

Question

在中，我学会了处理可以包含关键字列表中的关键字的 ID。我的实际语法有点复杂：在不同类型的句子中有几个关键字列表。这是我尝试用一个简单的语法来讲述这个故事：

grammar Hello;

file     : ( fixedSentence )* EOF ;
sentence : KEYWORD1 ID+ KEYWORD2 ID+ PERIOD
         | KEYWORD3 ID+ KEYWORD4 ID+ PERIOD;

KEYWORD1 : 'hello' | 'howdy' | 'hi' ;
KEYWORD2 : 'bye' | 'goodbye' | 'adios' ;
KEYWORD3 : 'dear' | 'dearest' ;
KEYWORD4 : 'love' | 'yours' ;
PERIOD  : '.' ;
ID      : [a-z]+ ;
WS      : [ \t\r\n]+ -> skip ;

所以我要匹配的句子是，例如：

hello snickers bar goodbye mars bar.
dear peter this is fun yours james.

效果很好。但我也想匹配包含预计不会终止 ID+ 块的关键字的句子。例如

hello hello kitty goodbye my dearest raggedy ann and andy.

hello 拳头显示为 KEYWORD1，然后作为第一个 ID+ 的一部分紧随其后。按照上述链接问题的示例，我可以这样修复它：

// ugly solution:
fixedSentence : KEYWORD1 a=(ID|KEYWORD1|KEYWORD3|KEYWORD4)+ KEYWORD2 b=(ID|KEYWORD1|KEYWORD2|KEYWORD3|KEYWORD4)+ PERIOD
              | KEYWORD3 a=(ID|KEYWORD1|KEYWORD2|KEYWORD3)+ KEYWORD4 b=(ID|KEYWORD1|KEYWORD2|KEYWORD3|KEYWORD4)+ PERIOD;

哪个有效并且完全符合我的要求。在我的真实语言中，我有数百个关键字列表，用于不同类型的句子，所以如果我尝试这种方法，我这样做肯定会犯错误，当我用我的语言创建新结构时，我必须回去编辑所有其他的。

按照 ANTLR4 书中的注释示例，从列表中进行非贪婪匹配会更好。所以我尝试了这个

// non-greedy matching concept:
KEYWORD : KEYWORD1 | KEYWORD2 | KEYWORD3 | KEYWORD4 ;
niceID : ( ID | KEYWORD ) ;
niceSentence : KEYWORD1 niceID+? KEYWORD2 niceID+? PERIOD
             | KEYWORD2 niceID+? KEYWORD3 niceID+? PERIOD;

我认为它遵循了评论模型（例如在本书的第 81 页给出）：

COMMENT : '/*' .*? '*/' -> skip ;

通过使用 ? 来暗示非贪婪。（虽然这个例子是一个词法分析器规则，但这会改变这里的意思吗？）fixedSentence 有效但 niceSentence 是失败的。我从这里去哪里？

具体来说，上面解析hello kitty测试语句报的错误是，

测试规则sentence:

line 1:6 extraneous input 'hello' expecting ID
line 1:29 extraneous input 'dearest' expecting {'.', ID}

测试规则fixedSentence：没有错误。

测试规则niceSentence:

line 1:6 extraneous input 'hello' expecting {ID, KEYWORD}
line 1:29 extraneous input 'dearest' expecting {KEYWORD2, ID, KEYWORD}
line 1:57 extraneous input '.' expecting {KEYWORD2, ID, KEYWORD}

如果有助于查看解析树，here they are。

Answer 1

认识到解析器非常适合处理语法，即，结构，而不是语义区别。一个关键字在一个上下文中是否是 ID 终止符，而在另一个上下文中不是，两者在语法上是等价的，本质上是语义的。

处理语义歧义的典型 ANTLR 方法是创建一个尽可能多地识别结构差异的解析树，然后遍历树分析每个节点与周围节点（在本例中）的关系以解决歧义.

如果这解析为您的解析器

sentences : ( ID+ PERIOD )* EOF ;

那么你的句子基本上是自由形式的。更合适的工具可能是 NLP 库——斯坦福大学有一个不错的工具。

额外

如果您将词法分析器规则定义为

KEYWORD1 : 'hello' | 'howdy' | 'hi' ;
KEYWORD2 : 'bye' | 'goodbye' | 'adios' ;
KEYWORD3 : 'dear' | 'dearest' ;
KEYWORD4 : 'love' | 'yours' ;
. . . .
KEYWORD : KEYWORD1 | KEYWORD2 | KEYWORD3 | KEYWORD4 ;

词法分析器永远不会发出 KEYWORD 标记 - 'hello' 被消耗并作为 KEYWORD1 发出并且永远不会评估 KEYWORD 规则。由于解析树无法识别标记的类型（显然），因此它不是很有启发性。转储令牌流以查看词法分析器实际在做什么

hello    hello    kitty goodbye  my dearest  ...
KEYWORD1 KEYWORD1 ID    KEYWORD2 ID KEYWORD3 ...

如果您将 KEYWORD 规则放在其他规则之前，那么词法分析器将只发出 KEYWORD 个标记。

更改为解析器规则

niceID : ( ID | keyword ) ;
keyword : KEYWORD1 | KEYWORD2 | KEYWORD3 | KEYWORD4 ;

将允许这个非常有限的示例工作。

ANTLR4 列表中标记的非贪婪匹配

Non-greedy matching of tokens from lists in ANTLR4

antlr4