Блог

Я использую ANTLR v3, и я хочу правильно анализировать шаблонные выражения, такие как:

 List<List<int>>
  

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

В некоторых случаях входные >> данные представляют собой два токена (две прямоугольные фигурные скобки, закрывающие аргументы универсального типа), а в других случаях это один оператор. Чтобы правильно их обрабатывать, всегда рассматривайте одну прямоугольную фигурную скобку как отдельный токен в лексере и используйте правила синтаксического анализа, чтобы различать случаи. Один из примеров грамматик Java делает именно это. Вы можете использовать код для проверки того, что оператор сдвига не содержит никаких посторонних символов между угловыми фигурными скобками, не влияя на переносимость самой грамматики.

Правила лексера

 GT : '>';
LT : '<';
  

Правила синтаксического анализа

 typeArguments
    :   '<' typeArgument (',' typeArgument)* '>'
    ;

shiftOp
    :   '<' '<'
    |   '>' '>' '>'
    |   '>' '>'
    ;
  

Код (ANTLR 3)

У меня здесь нет конкретного примера, поскольку реализация будет зависеть от промежуточного формата, используемого грамматикой (т. Е. output=AST или какой-либо другой формат). Я настоятельно рекомендую выполнять все новые разработки с использованием ANTLR 4 по слишком многим причинам, чтобы перечислять.

Код (ANTLR 4)

Примечание: в ANTLR 4 это может быть выполнено в прослушивателе или посетителе. Я произвольно использовал здесь метод прослушивания.

 @Override
public void enterShiftOp(ShiftOpContext ctx) {
  Token token = ((TerminalNode)ctx.getChild(0)).getSymbol();
  int firstIndex = token.getStartIndex();
  for (int i = 1; i < ctx.getChildCount(); i  ) {
    Token sibling = ((TerminalNode)ctx.getChild(i)).getSymbol();
    if (sibling.getStartIndex() != firstIndex   i) {
      // report error: spaces/comments cannot appear between chars of a shift operator
    }
  }
}
  

Стандартное решение этой проблемы — '>>' вообще не иметь токена. Вместо этого у вас есть только '>' токен, и в анализаторе вы сопоставляете два последовательных '>' ‘s. Затем, чтобы убедиться, что вы не сопоставили что-то еще, вы выполняете проверку впоследствии, чтобы убедиться, что это действительно было '>>' . Смотрите Ответ @280Z28 для объяснения того, как это сделать таким образом.

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

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

Далее правила лексера. У нас есть два правила лексера. Правило лексера для токена больше, чем вы обычно делаете это:

 OP_GREATER_THAN : '>' ;
  

Сдвиг вправо — это то, где происходит волшебство. Вместо того, чтобы использовать токен сдвига вправо, мы выделяем несколько токенов:

 OP_GREATER_THAN_GREATER_THAN : t='>>' { emitGreaterThanGreaterThan(t); } ;
  

emitGreaterThanGreaterThan() Метод выдает эти:

 private void emitGreaterThanGreaterThan(Token token) {
    // Split the greater than token into two tokens so they can be matched separately.

    CommonToken first = new CommonToken(token);
    first.setType(OP_GREATER_THAN_GREATER_THAN_FIRST);
    emit(first);

    CommonToken second = new CommonToken(token);
    second.setType(OP_GREATER_THAN_GREATER_THAN_SECOND);
    emit(second);
}
  

Этот метод можно добавить в @lexer::members раздел в лексере. Что делает этот метод, так это то, что он берет '>>' токен, копирует его два раза и изменяет типы. Он превращает токен с одним сдвигом вправо в OP_GREATER_THAN_GREATER_THAN_FIRST и OP_GREATER_THAN_GREATER_THAN_SECOND . Эти токены должны быть объявлены, поэтому необходимо добавить следующие правила лексера:

 fragment OP_GREATER_THAN_GREATER_THAN_FIRST : ;
fragment OP_GREATER_THAN_GREATER_THAN_SECOND : ;
  

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

Чтобы немного упростить использование этой конструкции, можно добавить несколько правил синтаксического анализа:

 op_GREATER_THAN_GREATER_THAN
    :
        OP_GREATER_THAN_GREATER_THAN_FIRST
        OP_GREATER_THAN_GREATER_THAN_SECOND
    ;

op_GREATER_THAN_ANY
    : OP_GREATER_THAN
    | OP_GREATER_THAN_GREATER_THAN_FIRST
    | OP_GREATER_THAN_GREATER_THAN_SECOND
    ;
  

Правило синтаксического op_GREATER_THAN_GREATER_THAN анализа соответствует первому токену, за которым следует второй. Это становится маркером сдвига вправо. op_GREATER_THAN_ANY Правило соответствует любому значению, превышающему токен. Это используется для анализа универсального типа.

Правила универсального типа выглядят следующим образом:

 genericTypeArguments
    :
        OP_LESS_THAN
        genericTypeArgument
        (
            OP_COMMA
            genericTypeArgument
        )*
        op_GREATER_THAN_ANY
    ;
  

И именно здесь происходит волшебство. Поскольку мы разделили '>>' токен на несколько токенов, мы можем сопоставить либо токен больше, чем токен, первую часть токена сдвига вправо, либо вторую часть токена сдвига вправо.