Лексеры, синтаксические анализаторы, PSI, AST v. CST и другие фундаментальные концепции, помогающие понять, как писать плагины для IDE/компилятора.

Как программисты, мы любим говорить о технических вещах как о черном ящике. Хорошо это или плохо, но компилятор Kotlin немного похож на него. Существует документация по использованию Kotlin PSI для плагинов IDE, но помимо комментариев, оставленных в исходном коде, там не так уж много всего. Я надеюсь, что смогу помочь другим узнать достаточно информации, чтобы запачкать свои локти (и даже побудить других поделиться тем, что они найдут).

Этот мини-сериал выйдет в двух частях:

Компилятор Kotlin уникален тем, что его внешний интерфейс построен поверх него, что упрощает совместное использование внешнего интерфейса как с подключаемыми модулями компилятора, так и с подключаемыми модулями IDE. Для Kotlin цель внешнего интерфейса состоит в том, чтобы анализировать написанный код и анализировать его интерпретируемую структуру, чтобы он мог генерировать промежуточное представление (IR). Этот IR вместе с дополнительной сгенерированной информацией затем передается на серверную часть компилятора¹, который дополнительно анализирует, дополняет и оптимизирует IR, прежде чем он в конечном итоге станет машинным кодом.

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

Фаза синтаксического анализа

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

fun main() {
    1 + 2
    1.plus(2)
}

Компиляторы могут «понимать» то, что пишут разработчики, анализируя и позже переводя удобочитаемый код в формат, понятный самому компилятору. На изображении ниже файл Kotlin сначала загружается на фазу синтаксического анализа. Лексер создается для первоначального анализа исходного файла и создания токенов. Затем эти токены обрабатываются синтаксическим анализом, который, в свою очередь, создает структуру PSI (подробнее об этом рассказывается на этапе Анализ синтаксиса).

На этом этапе компилятор не заботится о том, работает код или нет — его интересует только выяснение того, что было написано в файле. Этап Синтаксический анализ отвечает за создание синтаксических деревьев, чтобы компилятор мог проанализировать и проверить код позже, на этапе Разрешение.

Основу синтаксического анализа можно увидеть в следующем двухэтапном процессе:

  1. Лексический анализ. Текстовый файл разбирается на токены.
  2. Анализ синтаксиса. Токены анализируются и упорядочиваются /в виде синтаксического дерева.

Лексический анализ

Во время лексического анализа парсер Kotlin сначала создает KotlinLexer. Этот лексер сканирует файл Kotlin и разбивает текст на набор токенов, называемых KtTokens. Например, KtTokens обозначает символы ( и ) как:

KtSingleValueToken LPAR = new KtSingleValueToken("LPAR", "(");
KtSingleValueToken RPAR = new KtSingleValueToken("RPAR", ")");

KotlinExpressionParsing настроит посетителя для организации этих токенов в наборы узлов выражения. Эти узлы выражения затем добавляются для построения дерева PSI через ASTNode.

Интерфейс структуры программирования (PSI) — это абстракция, созданная JetBrains. Это что-то вроде массивного универсального синтаксического дерева, обрабатывающего текст/код/язык в их IDE. Эти деревья представляют собой представления в памяти, созданные во время синтаксического анализа, и необходимы компилятору для создания дополнительных данных и рекурсивного анализа самого себя для проверки кода на более поздних этапах. PSI полезен как для подключаемых модулей компилятора, так и для подключаемых модулей IDEA, поскольку вы можете фильтровать PSI для перехвата определенных фрагментов кода.

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

/*
 * : "throw" element
 */
private void parseThrow() {
    assert _at(THROW_KEYWORD)
    PsiBuilder.Marker marker = mark();
    advance(); // THROW_KEYWORD
    parseExpression(); 
    marker.done(THROW);
}

В следующем разделе анализ синтаксиса создаст синтаксический анализатор PSI, который упаковывает токены как PsiElements. Каждый узел содержит описание, которое рекурсивно описывает грамматическую структуру исходного кода.

Синтаксический анализ

Сгенерированный файл PSI описывает иерархию PsiElements (так называемых деревьев PSI), которая создает модели синтаксического и семантического кода. Дерево PSI больше похоже на Абстрактное синтаксическое дерево (AST)или Конкретное синтаксическое дерево (CST)? Похоже, сгенерированное PSI-дерево обладает характеристиками для обоих.

Блог Эли Бендерски на тему Абстрактные и конкретные синтаксические деревья отлично объясняет разницу между ними более подробно. Подобно дереву CST, структура PSI содержит более формальное представление того, что было написано, включая символы. Однако, как и AST, дерево PSI содержит дополнительную полезную информацию в каждом узле.

В IntelliJ IDEA вы можете загрузить плагин PSIViewer для проверки PSI кода, который вы пишете. Вы также можете выделить части своего кода, чтобы увидеть, что PSIViewer выбирает в отображаемом дереве.

На изображении ниже показано, как PSIViewer интерпретирует 5.minus(2) как DOT_QUALIFIED_EXPRESSION, чей первый дочерний элемент — anINTEGER_CONSTANT как 5, второй дочерний элемент DOT вместо . и третий дочерний элемент CALL_EXPRESSION как minus(2).

Эти элементы PSI содержат токены и могут содержать информацию о дочерних и родительских элементах, к которым они могут относиться. Эти структуры PSI становятся еще более сложными по мере того, как компилятор создает и генерирует из них дополнительную информацию. Структуры PSI имеют общие характеристики как для CST, так и для AST, хотя со временем их структуры становятся более похожими на AST. Для обсуждения и удобства мы будем называть эти деревья терминами AST.

Рассмотрим выражение 5 — 2. Сгенерированный AST выглядит следующим образом, где более темные узлы дерева представлены как элементы, а более светлые узлы представлены как токены.

Выражение 5 – 2 можно разбить на двоичное выражение, состоящее из двух целочисленных констант в качестве операндов и OPERATION_REFERENCE в качестве оператора. Но выражение 5.minus(2), даже если оно даст тот же результат, что и 5 — 2, будет иметь совершенно другую структуру AST.

Дерево PSI сообщает нам, как код был написан конечным пользователем, но не более того на данном этапе. Это означает, что в этот момент компилятор может только сообщить нам, как был написан код, но он не знает, компилируется ли код или нет.

PSI-дерево можно построить независимо от того, верен код или нет. Рассмотрим скриншот IntelliJ IDEA ниже. В левой части панели показан код в файле Utils.kt. Внутри функции main есть два оператора, причем вторая строка функции имеет значение 5.((2) вместо 5.minus(2). Мы знаем (и IDE знает), что такой оператор, как 5.((2), не будет компилироваться. Но помните, PSI-дереву это знать не обязательно. Он все равно сгенерирует элементы, хотя может быть не в состоянии точно интерпретировать отношения иерархии внутри.

Как IDE может показать нам красную волнистую линию на левой панели скриншота? Именно за это отвечает этап разрешения, который дает нам идеальный переход к теме следующего сообщения. В следующей статье будет рассмотрен этап Разрешение, который создает необходимый анализ, необходимый для определения того, может ли код компилироваться или нет. Следите за обновлениями!

Большое спасибо Леланду Ричардсону за его отзыв о деталях компилятора и Луису CAD за его обзор и отзыв о статье/диаграммах.

¹ Затем серверная часть берет этот IR, оптимизирует его, снова оптимизирует и генерирует все это в байт-код. Об этом будет рассказано в следующем посте.