来自ANTLR4中列表的令牌的非贪婪匹配

Question

在a previous question with a simple grammar中，我学会了处理可包含关键字列表中关键字的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

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

处理语义歧义的典型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令牌 - “你好”被消耗，发出的KEYWORD1和KEYWORD规则就是，永远评估。由于解析树无法识别令牌的类型（显然），它不是很明亮。转储标流，看看有什么词法分析器实际上是做

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

如果将KEYWORD规则在别人面前，然后词法分析器是要只发出KEYWORD令牌。

更改为语法规则

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

将使这个非常有限的例子来工作。