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の本のコメントの例に従って、リストから貪欲でないマッチングを行うのがいいです。非貪欲を提案する?を使用して

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

：だから私は、私はコメントのためのモデルを（例えば本のP.81に与えられた）次のだと思う。この

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

を試してみました。 （例はレクサールールですが、ここでその意味が変わりますか？）fixedSentenceが動作しますが、niceSentenceは失敗です。ここからどこに行くのですか？

---

。具体的には、上記のハローキティのテスト文を解析中で報告されたエラーがあり、

テストは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ライブラリである可能性があります。スタンフォードは素晴らしいツールです。

追加

あなたはレクサーはKEYWORDトークンを放出することはありません

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

としてあなたレクサーのルールを定義する場合 - 「ハロー」の消費と放出さKEYWORD1ようとKEYWORDルールは決してありません評価される。解析ツリーはトークンの種類を識別することができないので（明らかに）、それはあまり明るくはありません。レクサーは、実際にあなたが他の人の前にKEYWORDルールを配置する場合は、レクサーのみKEYWORDトークンを放出するために起こっている

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

をやっているかを見るためにトークンストリームをダンプします。

パーサーに変更すると、

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

は、この非常に限られた例が動作するようになりますルール。