來自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 ; 

將使這個非常有限的例子來工作。