Синтаксические предикаты в правилах лексера ANTLR

Question

Вступление

Глядя на документацию, в ANTLR 2 использовалось нечто, называемое предикатным лексингом, с примерами, подобными этому (вдохновлено Паскалем):

RANGE_OR_INT
    :   ( INT ".." ) => INT  { $setType(INT); }
    |   ( INT '.' )  => REAL { $setType(REAL); }
    |   INT                  { $setType(INT); }
    ;    

На мой взгляд, это, по сути, положительное прогнозное утверждение в начале правила: если прогнозное совпадение совпадает INT ".." тогда первое правило будет применяться (и соответствует INT часть этого ввода), и так далее.

Я еще не нашел что-то подобное в ANTLR 4. Руководство по миграции с 2 по 3, похоже, не упоминает об этом, тогда как документ с 3 по 4 изменяет:

Самое большое различие между ANTLR 3 и 4 состоит в том, что ANTLR 4 принимает любую грамматику, которую вы ей даете, если только у грамматики не было косвенной рекурсии слева. Это означает, что нам не нужны синтаксические предикаты или обратный поиск, поэтому ANTLR 4 не поддерживает этот синтаксис; вы получите предупреждение за его использование.

Это соответствует сообщению об ошибке, которое я получаю, если я оставлю это по существу как есть:

(...)=> syntactic predicates are not supported in ANTLR 4

Хотя я могу понять, как более интеллектуальная реализация синтаксического анализатора могла бы разрешить эти неоднозначности, я не вижу, как это будет работать для лексеров.

Воспроизводящий пример

Чтобы быть уверенным, давайте попробуем это:

grammar Demo;
prog:   atom (',' atom)* ;
atom:   INT  { System.out.println("INT:   " + $INT.getText()); }
    |   REAL { System.out.println("REAL:  " + $REAL.getText()); }
    |   a=INT RANGE b=INT { System.out.println("RANGE: " +
                              $a.getText() + " .. " + $b.getText()); }
    ;
WS  :   (' ' | '\t' | '\n' | '\r')+ -> skip ;
INT :   ('0'..'9')+ ;
REAL:   INT '.' INT? | '.' INT ;
RANGE:  '..' ;

Сохранить это в Demo.g, затем скомпилируйте и запустите:

$ wget -nc http://www.antlr.org/download/antlr-4.5.2-complete.jar
$ java -jar antlr-4.5.2-complete.jar Demo.g
$ javac -cp antlr-4.5.2-complete.jar Demo*.java
$ java -cp .:antlr-4.5.2-complete.jar org.antlr.v4.gui.TestRig \
  Demo prog <<< '1,2.,3.4,5 ..6,7..8'
INT:   1
REAL:  2.
REAL:  3.4
RANGE: 5 .. 6
REAL:  7.
line 1:17 extraneous input '.8' expecting {<EOF>, ','}

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

Основной вопрос

Так как же преобразовать этот конкретный пример в ANTLR 4? Есть ли способ выразить прогнозные условия? Или, возможно, способ иметь единственное правило, как INT '..' испустить два разных токена?

Рекомендации и возможные решения

Глядя на грамматику ANTLR 4 Pascal, я замечаю, что она не позволяет действительным числам заканчиваться на . без цифры после этого, поэтому изучение решения оттуда, кажется, не вариант.

Я видел семантические предикаты в ANTLR4? и синтаксические предикаты - Обновление с Antlr 3 до Antlr 4. Оба обсуждают синтаксические предикаты в правилах синтаксического анализа. У последнего также есть пример с правилами лексера, но упреждающий просмотр идентичен последующему правилу, что означает, что правила могут быть удалены без неблагоприятных последствий. Это не так в моем примере выше.

Ответы на проверку предыдущего / левого токена в лексере упоминают emit метод лексера, с комментарием, ссылающимся на Как я могу создать более одного токена на правило лексера? Страница часто задаваемых вопросов в вики ANTLR 3, так что я думаю, что это один из подходов. Я превращу это в ответ, если никто не победит меня, и если я смогу заставить его работать в моем примере.

Ответ на отрицательный прогноз ANTLR4 в лексере использует _input.LA(int) метод, чтобы изучить прогноз. Часто задаваемые вопросы о лексическом анализе ANTLR 4 _input.LA не вдаваясь в детали. Это должно работать и для приведенного выше примера, но будет трудно для сценариев, где нужно рассмотреть более одного символа.

Answer 1

Вот очень короткое решение:

@lexer::members { private int _pos; }
INT_RANGE: INT  { _pos=_input.index(); setType(INT); emit(); }
           '..' { _input.seek(_pos); };

Это соответствует целому INT '..' выражение, но затем перематывает ввод сразу после INT где мы испускаем токен и сохраняем позицию. Эта позиция затем используется в конце правила, чтобы перемотать ввод более постоянным образом.

Однако существует проблема: полученные токены будут содержать неверную информацию о положении, поскольку _input.seek не повлияет на то, что getCharPositionInLine возвращается. В этом случае можно сделать

setCharPositionInLine(getCharPositionInLine() - 2)

в конце правила, но этот подход не будет работать, если вместо .. один имел дело с вводом переменной длины. Я надеялся, что смогу сохранить результат getCharPositionInLine() в первом действии, но, к сожалению, это уже отражает конец всего выражения.

Смотря на LexerATNSimulator.evaluatePredicate Я вижу, что этот метод пытается восстановить заданное положение. Таким образом, мы можем получить правильное состояние, используя семантический предикат для его побочных эффектов:

@lexer::members {
    private int _savedIndex, _savedLine, _savedColumn;
    private boolean remember() {
        _savedIndex = _input.index();
        _savedLine = getLine();
        _savedColumn = getCharPositionInLine();
        return true;
    }
    private void recall(int type) {
        _input.seek(_savedIndex);
        setLine(_savedLine);
        setCharPositionInLine(_savedColumn);
        setType(type);
    }
}
INT_RANGE: INT { remember() }? '..' { recall(INT); } ;

Имейте в виду, что семантический предикат будет выполняться в тот момент времени, когда еще не гарантируется, что все выражение будет фактически совпадать. Так что если вы используете этот трюк в нескольких местах, вы должны быть осторожны, чтобы не получить remember() звонки по разным правилам переписывают состояние. Если вы сомневаетесь, вы можете использовать несколько таких функций или индекс в массиве, чтобы сделать каждое совпадение однозначным.

Answer 2

Источники тока (на момент написания статьи) Lexer Реализация содержит несколько записей документации, касающихся выдачи нескольких токенов. Они, конечно, представлены в Lexer API JavaDoc также. В соответствии с этим необходимо сделать следующее:

1. Override emit(Token):

   По умолчанию не поддерживает несколько выбросов nextToken вызов по соображениям эффективности. Подкласс и переопределить этот метод, nextToken, а также getToken (вставлять токены в список и извлекать из этого списка, а не одну переменную, как это делает эта реализация).

2. Override nextToken(),

3. Override getToken():

   Переопределить, если испускается несколько токенов.

4. Обязательно установите _token не- null:

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

Тем не менее, я не понимаю, почему переопределение getToken было бы важно, так как я не вижу вызовов этого метода нигде в библиотеке времени выполнения. И если вы установите _token тогда это будет вывод getToken также.

Итак, что я сделал, чтобы испустить два токена из одного правила:

@lexer::members {

    private Token _queued;

    @Override public Token nextToken() {
        if (_queued != null) {
            emit(_queued);
            _queued = null;
            return getToken();
        }
        return super.nextToken();
    }

    @Override public Token emit() {
        if (_type != INT_RANGE)
            return super.emit();
        Token t = _factory.create(
            _tokenFactorySourcePair, INT, null, _channel,
            _tokenStartCharIndex, getCharIndex()-3,
            _tokenStartLine, _tokenStartCharPositionInLine);
        _queued = _factory.create(
            _tokenFactorySourcePair, RANGE, null, _channel,
            getCharIndex()-2, getCharIndex()-1, _tokenStartLine,
            _tokenStartCharPositionInLine + getCharIndex()-2 -
            _tokenStartCharIndex);
        emit(t);
        return t;
    }
}

INT_RANGE: INT '..' ;

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

Answer 3

Это еще одна попытка реализации опережающего просмотра.
В основном для потомков и проверки.

У меня есть язык, похожий на XML, но с менее строгими правилами.
Следующий пример:

      <myTag>a bit of <text </myTag>

Должен быть токенизирован как:

      <               TagOpen
myTag           TagName
>               TagClose
a bit of <text  Text
</              TagOpenClose
myTag           TagName
>               TagClose

Обратите внимание, как текст не мешает.
Для этого мне нужно заглянуть вперед и убедиться, что это<является частью допустимого тега , а затем и допустимого элемента .

В следующем фрагменте обратите внимание, какisValidTagиспользуется функция. Я создаю новый экземпляр своего лексера, передавая тот же_inputпоток, но восстанавливая свою позицию в конце метода.

      @lexer::members {
  private boolean isValidTag() {
    final int mark = _input.mark();
    final int index = _input.index();
    final Lexer lexer = new MyCustomLexer(_input);
    lexer.mode(TAG);

    Token token = lexer.nextToken();
    boolean isMatch = false;

    if (token.getType() == TagName) {
      token = lexer.nextToken();

      if (token.getType() == TagClose ||
          token.getType() == AttrName) {
        isMatch = true;
      }
    }

    _input.seek(index);
    _input.release(mark);
    return isMatch;
  }
}

TagOpenClose      : '</'                    -> mode(TAG);
TagOpen           : '<' { isValidTag() }?   -> mode(TAG);
Text              : ~[<\n]+;
TextTagOpen       : '<'                     -> more;
NewLine           : ('\r\n' | '\r' | '\n');
...

Кажется, это работает прилично, хотя я не уверен в производительности и крайних случаях.