2

次のように、それぞれが別々の行にある一連の単純な英語のステートメントのような入力があるとします。

Alice checks
Bob bets 100
Charlie raises 100
Alice folds

この文法で構文解析してみましょう。

actions: action* EOF;
action: player=name (check | call | raise | fold) NEWLINE;
check: 'checks';
call: 'calls' amount;
raise: 'raises' amount;
fold: 'folds';

name: /* The subject of this question */;
amount: '$'? INT;

INT: ('0'..'9')+;
NEWLINE: '\r'? '\n';

異なる動詞の数は固定されていますが、興味深いのは、一致させようとしている名前にスペースが含まれている可能性があることです。動詞もその一部である可能性があります。したがって、次の入力が有効です。

Guy who always bets 100 checks
Guy who always checks bets 100
Guy who always calls folds
Guy who always folds raises 100
Guy who always checks and then raises bets by others calls $100

だから問題は、私たちが通常動詞として扱っているスペースや単語を食べるのに十分貪欲であるが、動詞が規則によって一致することができるように超貪欲ではないように定義するにはどうすればよいですか？nameaction

このタスクを解決するための私の最初の試みは、次のようになりました。

name: WORD (S WORD)*;
WORD: ('a'..'z'|'A'..'Z'|'0'..'9')+; // Yes, 1234 is a WORD, too...
S: ' '; // We have to keep spaces in names

残念ながら、これは「常に賭ける男」とは一致しません。これはbets、ではなく、ルールWORDのリテラルによって定義された別のトークンであるためです。のようなルールを作成し、リテラルの代わりに他のルールを一致させることでそれbetsを回避したかったのですが、それが行き詰まりました。（私はすべての動詞を有効な代替としてリストして、の一部にすることができると思いますが、それは間違っていると感じます。）keyword[String word]keyword["bets"]name

さらに、すべてのnamesが使用される前に宣言されているため、sの解析を開始する前にそれらを読み取ることができますaction。また、MAX_NAME_LENGTH文字より長くすることはできません。ここで何か役に立ちますか？

とにかく、私はそれを間違っているのかもしれません。ANTLRの達人、私はあなたから聞くことができますか？

4

2 に答える 2

2

簡単な方法は、文法全体でグローバル バックトラッキングを有効にすることです。これは通常はお勧めできませんが、文法は比較的小さいままになると思います。その場合、パーサーの実行時間にはあまり影響しません。遅くなったことがわかった場合は、 memoize オプションのコメントを外すと、パーサーが高速になりますが、メモリ消費量がいくらか増えます。

デモ:

in.txt

常に100チェックを賭ける男
常に100ベットをチェックする男
いつもフォールドをコールする男
常にフォールドする奴は 100 レイズする
いつもチェックしてから他の人がベットをレイズする男は、$100 をコールします

Poker.g

grammar Poker;

options {
  backtrack=true;
  // memoize=true;
}

actions
  :  action* EOF
  ;

action
  :  name SPACES (bets | calls | raises | CHECKS | FOLDS) SPACES? (NEWLINE | EOF)
     {
       System.out.println($name.text);
     }
  ;

bets    : BETS SPACES amount;
calls   : CALLS SPACES amount;
raises  : RAISES SPACES amount;
name    : anyWord (SPACES anyWord)*;
amount  : '$'? INT;
anyWord : BETS | FOLDS | CHECKS | CALLS | RAISES | INT | WORD; 

BETS    : 'bets';
FOLDS   : 'folds';
CHECKS  : 'checks';
CALLS   : 'calls';
RAISES  : 'raises';
WORD    : ('a'..'z' | 'A'..'Z')+;
INT     : '0'..'9'+;
SPACES  : ' '+;
NEWLINE : '\r'? '\n';

Main.java

import org.antlr.runtime.*;

public class Main {
  public static void main(String[] args) throws Exception {
    PokerLexer lexer = new PokerLexer(new ANTLRFileStream("in.txt"));
    PokerParser parser = new PokerParser(new CommonTokenStream(lexer));
    parser.actions();
  }
}

Main クラスを実行すると、以下が生成されます。

bart@hades:~/Programming/ANTLR/Demos/Poker$ java -cp antlr-3.3.jar org.antlr.Tool Poker.g
bart@hades:~/Programming/ANTLR/Demos/Poker$ javac -cp antlr-3.3.jar *.java
bart@hades:~/Programming/ANTLR/Demos/Poker$ java -cp .:antlr-3.3.jar メイン
常に100を賭ける男
いつもチェックしてる奴
いつも電話してくる男
いつもフォールドする奴
いつもチェックして他人のベットをレイズするヤツ

編集

逆の方法で行うこともできます: 一致させたくないトークンを無効にしますanyWord:

// other parser rules
anyWord : ~(SPACES | NEWLINE | DOLLAR); 

BETS    : 'bets';
FOLDS   : 'folds';
CHECKS  : 'checks';
CALLS   : 'calls';
RAISES  : 'raises';
WORD    : ('a'..'z' | 'A'..'Z')+;
INT     : '0'..'9'+;
DOLLAR  : '$';
SPACES  : ' '+;
NEWLINE : '\r'? '\n';

anyWord、およびを除くすべてのトークンに一致するようになりました。内部レクサー規則 (文字を否定する) とパーサー規則 (トークンを否定する!)の違いに注意してください。SPACESNEWLINEDOLLAR~

于 2011-06-13T21:03:51.013 に答える
0

簡単な解決策: 空白で分割し、入力を単語ごとに反転し、左からではなく右から解析します。(もちろん、これには文法を書き直す必要があります。)

于 2011-06-13T19:37:35.933 に答える