Как указать «жадные идентификаторы с пробелом» в ANTLR?

Предположим, у нас есть ввод, который выглядит как последовательность простых английских утверждений, каждое в отдельной строке, например:

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

Итак, возникает вопрос: как нам определить name, чтобы оно было достаточно жадным, чтобы потреблять пробелы и слова, которые мы обычно рассматриваем как глаголы, но не было сверхжадным, чтобы глаголы все еще могли сопоставляться по правилу action?

Моя первая попытка решить эту задачу выглядела так:

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, но это кажется неправильным.)

Вот что еще: все name объявлены до того, как они будут использованы, поэтому я могу прочитать их до того, как начну парсить action. И они не могут быть длиннее MAX_NAME_LENGTH символов. Может тут чем поможет?

Может быть, я делаю это неправильно, в любом случае. Гуру ANTLR, могу я услышать от вас?


person Stepan Stolyarov    schedule 13.06.2011    source источник


Ответы (2)


Простым выходом было бы включить глобальный возврат для всей вашей грамматики. Обычно это не рекомендуется, но я предполагаю, что ваша грамматика останется относительно небольшой, и в этом случае она не будет иметь большого значения во время выполнения вашего синтаксического анализатора. Если вы обнаружите, что он становится медленным, вы можете раскомментировать параметр memoize, который сделает ваш синтаксический анализатор быстрее за счет некоторого потребления памяти.

Демо:

in.txt

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

Покер.г

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 Main
Guy who always bets 100
Guy who always checks
Guy who always calls
Guy who always folds
Guy who always checks and then raises bets by others

РЕДАКТИРОВАТЬ

Вы можете сделать это наоборот: отрицать токены, которым вы не хотите соответствовать 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 теперь соответствует любому токену, кроме SPACES, NEWLINE и DOLLAR. Обратите внимание на разницу между ~ внутри правил лексера (отменяет символы) и правил парсера (отменяет токены!).

person Bart Kiers    schedule 13.06.2011
comment
Это определенно выглядит так, как будто это требует возврата из-за присущей двусмысленности (ну, большое спасибо, естественные языки!). Но то, что я искал, - это какой-то рецепт, чтобы все «ключевые слова» попали в одну категорию токенов, потому что фактическая грамматика намного больше и многословнее, чем то, что я опубликовал. Я действительно не хочу добавлять новую альтернативу ANY_WORD каждый раз, когда вводится новый литерал — их уже около 40+, и это далеко не все. - person Stepan Stolyarov; 14.06.2011
comment
@Степан Столяров, от этого никуда не деться: слова токенизируются либо как ключевые слова, либо как WORD. Вам придется учитывать это в правиле парсера. Вы можете сделать это немного по-другому (см. мой РЕДАКТИРОВАТЬ). - person Bart Kiers; 14.06.2011
comment
Хм, кажется, мне нравится эта идея. Придумать новую пунктуацию сложнее, чем новое ключевое слово. Спасибо, Барт, обязательно попробую! - person Stepan Stolyarov; 14.06.2011

Простое решение: разделить на пробелы, инвертировать ввод слово за словом, затем анализировать справа, а не слева. (Конечно, это требует переписывания вашей грамматики.)

person Fred Foo    schedule 13.06.2011
comment
Ммм... Нет, извините. Я все еще забочусь о здравомыслии моих коллег. И я боюсь, что они заботятся и о моей тоже. - person Stepan Stolyarov; 14.06.2011
comment
@Stepan: Я могу понять :) Я хочу сказать, что язык, который вы определяете, на самом деле не двусмысленный; Я думаю, что это даже правильное решение, и решения с конечным состоянием/RE будет достаточно. - person Fred Foo; 14.06.2011
comment
Это не двусмысленно, по крайней мере, не для людей, и не в той части, которую я продемонстрировал. Я просто искал совета о том, как скормить его синтаксическому анализатору LL (*). Другие решения — я пытался установить на него пакет RE — сложны в обслуживании, медленны или что-то в этом роде. - person Stepan Stolyarov; 14.06.2011
comment
Скомпилированный RE не должен быть очень медленным для этой задачи, но я понимаю, хотите ли вы использовать ANTLR. Очень немногие инструменты готовы к подобным вещам. - person Fred Foo; 14.06.2011