Папа Карло и инкрементальные компиляторы

Коллеги,

а помните была такая статья-перевод на Хабре Чек-лист разработчика языка программирования Колина Макмиллена о проблемах новых языков программирования? Статья просто изумительная! Если не читали — обязательно посмотрите.

Одна из ключевых проблем, о которых говорит Колин: языки без хорошей поддержки IDE никому не нужны. Конечно это не единственная проблема, которая стоит перед разработчиком языка программирования. Но, я думаю, все согласятся с тем, что при прочих равных язык, поддерживаемый многими редакторами, уже будет иметь неплохое конкурентное преимущество.

По стечению обстоятельств я как раз занимаюсь компиляторами и языковыми плагинами для IDE уже не первый год. И буду рад поделиться с вами опытом, рассказав о том, как сделать компилятор, который будет намного легче интегрироваться со множеством современных редакторов кода. А заодно немного расскажу о своих собственных наработках в этой области.

Проблема

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

• Парсер, который разбирает исходный код, и превращает его в дерево синтаксиса.
• Семантический анализатор, связывающий сущности языка друг с другом: ссылки между именами, переменными, классами.
• Бэкэнд, отвечающий за генерацию и оптимизацию машинного кода.

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

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

Подход с полной перекомпиляцией проекта не будет применим для IDE, даже если мы отключим бэкэнд компилятора. По мере увеличения объема исходных кодов в проекте, время компиляции все равно будет расти.

На помощь приходит так называемый инкрементальный подход. Идея заключается в том, что компилятор кеширует почти все промежуточные результаты своей работы: результаты компиляции отдельных файлов, их синтаксические деревья и даже отдельные лексемы языка. И если пользователь-программист вносит небольшие изменения в исходный код, компилятор переразбирает только какой-то локальный фрагмент кода вокруг этих изменений. Таким образом, производительность компилятора становится пропорциональна вносимым изменениям в код, а не объему всего кода целиком.

К сожалению, разработка парсера для инкрементального компилятора является достаточно нетривиальной задачей. Особенно с учетом того, что парсер должен уметь еще и разбирать код, содержащий синтаксические ошибки. К примеру, если в начале объявления класса программист делает синтаксическую ошибку:

import javax.swing.JApplet; import java.awt.Graphics;   public class Hello extends JApplet {     int x = // Я начал объявлять переменную, но еще не закончил.      public void paintComponent(final Graphics g) {         g.drawString("Hello, world!", 65, 95);         // Но это не помешает мне продолжить писать код тут.     } } 

То в методе ниже программист по прежнему может писать код, который будет понятен редактору: пользователю будут доступны и code-completion, и jump-to-definition, и многие другие функции IDE.

Готовых генераторов и комбинаторов инкрементальных парсеров довольно мало, и они весьма специфичны. Скажем, в таком монструозном продукте как ANTLR в последней версии появилась поддержка инкрементального разбора в некотором виде. Надо сказать, что ANTLR довольно тяжелый продукт, работать с ним намного сложнее, чем с каким-нибудь PEG комбинатором обычных (не инкрементальных) парсеров вроде PEG.js на JavaScript.

Приходится констатировать печальный факт, что на сегодняшний день, за редким исключением, разработка языковых плагинов для каждого отдельного текстового редактора или IDE ведется более-менее «на коленке». И является достаточно сложной задачей, из которой не редко вырастают самостоятельные продукты.

Решение

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

Разработчик задает грамматику языка прямо в коде на Скале, используя API этой библиотеки. И полученный парсер может разбирать в том числе и код, содержащий синтаксические ошибки, и создавать синтаксическое дерево прямо «из коробки». Никакого дополнительного шага генерации кода нет. Парсер создается в рантайме, как и многие современные комбинаторы обычных парсеров вроде того же JParsec для Java.

Затем разработчик связывает выходы созданного компилятора с API тех редакторов кода, которые он хочет поддерживать. Например, с API Sublime Text.

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

Проект еще не завершен, но я уже выложил рабочий вариант на GitHub под лицензией Apache, и провел несколько экспериментов. К примеру, есть готовый инкрементальный парсер JSON файлов. Парсер определяется ровно одним файлом грамматики на Scala. Код парсера можно посмотреть тут.

В одном из тестов на вход подается вот такой вот json, содержащий явные синтаксические ошибки:

{   "key 1": "hello world",   "key 1.1":   "key 2": ["array value 1", "array value 2", "array value 3"], } 

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

object 1 {   entry:     entry 27 {       key: "key 1"       value:         string 26 {           value: "hello world"         }     }   entry:     entry 25 {       key: "key 1.1"       value:         string 24 {           value: "key 2"         }     } } 

Указывая при этом и на синтаксические ошибки, разумеется:

 > code mismatched: {   "key 1": "hello world",   "key 1.1":   "key 2"<<<: ["array value 1", "array value 2", "array value 3"],>>> } 

Однако намного интереснее другой пример, в котором вводится сравнительно объемный файл размером в 600 строк. После первого запуска парсер благополучно создает синтаксическое дерево, и работает 0.27 секунды. Что в общем-то не мало. Затем в файл два раза вносятся небольшие изменения, и на втором и третьем запусках парсер уже работает 0.007 и 0.008 секунды соответственно. Точно так же создавая синтаксическое дерево для всех 600 строк этих новых файлов. Такой эффект достигается именно благодаря использованию кеша, полученного при предыдущих запусках парсера.

Заключение и ссылки

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

Я уверен, что среди нас найдутся еще разработчики, имеющие опыт создания расширений для IDE. Было бы очень интересно услышать ваши дополнения и комментарии.

Вот напоследок несколько полезных ссылок:

• Grammar Kit. Конструктор парсеров от JetBrains, используемый в разработке плагинов для IntelliJ Idea.
• Java Development Tools. Инкрементальный парсер Java, используемый внутри Eclipse.
• Parboiled. Конструктор неинкрементальных парсеров для Scala и Java. Несмотря на то, что он строит обычные, неинкрементальные парсеры, это один из наиболее развитых и известных конструкторов парсеров в Scala комьюнити. На мой взгляд, проект заслуживает внимания.
• Papa Carlo. Мой собственный конструктор инкрементальных парсеров для Scala, упомянутый выше.