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

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

1 голос
/ 13 июня 2011

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

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, могу ли я услышать от вас?

Ответы [ 2 ]

2 голосов
/ 14 июня 2011

Самый простой выход - включить глобальный возврат всей грамматики. Обычно это не рекомендуется, но я думаю, что ваша грамматика останется относительно небольшой, и в этом случае она не будет иметь большого значения для времени выполнения вашего анализатора. Если вы обнаружите, что он работает медленно, вы можете отменить комментирование опции 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

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 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

EDIT

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

0 голосов
/ 13 июня 2011

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

...