Лексеры, синтаксические анализаторы, PSI, AST v. CST и другие фундаментальные концепции, помогающие понять, как писать плагины для IDE/компилятора.
Как программисты, мы любим говорить о технических вещах как о черном ящике. Хорошо это или плохо, но компилятор Kotlin немного похож на него. Существует документация по использованию Kotlin PSI для плагинов IDE, но помимо комментариев, оставленных в исходном коде, там не так уж много всего. Я надеюсь, что смогу помочь другим узнать достаточно информации, чтобы запачкать свои локти (и даже побудить других поделиться тем, что они найдут).
Этот мини-сериал выйдет в двух частях:
- 1. Внешний интерфейс: этап парсинга
- 2. Внешний интерфейс: этап разрешения (скоро)
Компилятор Kotlin уникален тем, что его внешний интерфейс построен поверх него, что упрощает совместное использование внешнего интерфейса как с подключаемыми модулями компилятора, так и с подключаемыми модулями IDE. Для Kotlin цель внешнего интерфейса состоит в том, чтобы анализировать написанный код и анализировать его интерпретируемую структуру, чтобы он мог генерировать промежуточное представление (IR). Этот IR вместе с дополнительной сгенерированной информацией затем передается на серверную часть компилятора¹, который дополнительно анализирует, дополняет и оптимизирует IR, прежде чем он в конечном итоге станет машинным кодом.
В этой серии статей рассказывается о том, что происходит, когда вы загружаете код через компилятор Kotlin: это самый простой способ понять, что компилятор делает на каждом этапе. В этом посте рассматривается первая часть внешнего интерфейса, этап анализа.
Фаза синтаксического анализа
Когда исходный код компилируется, первое, что должен сделать компилятор, — выяснить, что именно написал разработчик. Предположим, мы отправляем следующий файл через компилятор:
fun main() { 1 + 2 1.plus(2) }
Компиляторы могут «понимать» то, что пишут разработчики, анализируя и позже переводя удобочитаемый код в формат, понятный самому компилятору. На изображении ниже файл Kotlin сначала загружается на фазу синтаксического анализа. Лексер создается для первоначального анализа исходного файла и создания токенов. Затем эти токены обрабатываются синтаксическим анализом, который, в свою очередь, создает структуру PSI (подробнее об этом рассказывается на этапе Анализ синтаксиса).
На этом этапе компилятор не заботится о том, работает код или нет — его интересует только выяснение того, что было написано в файле. Этап Синтаксический анализ отвечает за создание синтаксических деревьев, чтобы компилятор мог проанализировать и проверить код позже, на этапе Разрешение.
Основу синтаксического анализа можно увидеть в следующем двухэтапном процессе:
- Лексический анализ. Текстовый файл разбирается на токены.
- Анализ синтаксиса. Токены анализируются и упорядочиваются /в виде синтаксического дерева.
Лексический анализ
Во время лексического анализа парсер 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, оптимизирует его, снова оптимизирует и генерирует все это в байт-код. Об этом будет рассказано в следующем посте.