Пользователь
0,0
рейтинг
13 ноября 2013 в 13:17

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



Коллеги,

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

Одна из ключевых проблем, о которых говорит Колин: языки без хорошей поддержки 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 строк этих новых файлов. Такой эффект достигается именно благодаря использованию кеша, полученного при предыдущих запусках парсера.

Входной файл Размер(строки) Разница с предыдущим(строки) Время разбора и построения AST(миллисекунд)
step0.json 634 - 270
step1.json 634 1 7
step2.json 634 2 8


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


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

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

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

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (22)

  • –4
    Забавно, что большинство выбирают тот же Sublime, а не какой-нибудь Eclipse, именно за то, что это текстовый редактор, а не IDE, и не подвисает в непредсказуемые моменты времени из-за попыток разбора.
    • +10
      Смотря на каком языке писать. Если язык со слабой динамической типизацией, то да, на нем реально проще писать в текстовом редакторе, потому что IDE все равно едва может подсказать что-то вменяемое. Если же брать языки вроде C# или Java, уверен что практически все разработчики пользуются инструментами типа Visual Studio + R# или Idea.
      • +4
        потому что IDE все равно едва может подсказать что-то вменяемое

        Посмотрите IDE от JetBrains для PHP, Python и Ruby.
        • +2
          Как раз сейчас по воле судьбы пришлось написать кое-что на PHP. Воспользовался PhpStorm 7.

          AutoComplete работает только там, где данные можно считать из PhpDoc-комментариев. Кроме того, даже если комментарий есть, но указан тип mixed — тоже ничего не определишь, и очень много стандартных функций используют такой тип полиморфизма.

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

          Проблема не в том, что ребята из JetBrains не постарались — даже наоборот, они проделали титаническую работу. Visual Studio 2012 примерно так же с трудом переваривает код на JS. Проблема в самой динамической типизации — за свободу действий приходится платить сложностью статического анализа.
          • –1
            Ещё семёрку не ставил, но шестёрка вполне корректно выводит типы сама.

            Сомневаюсь, что в семёрке это сломали :) Вкупе с phpdoc решает процентов 90 если не больше проблем с автодополнением, если динамической типизацией не злоупотреблять, переменные повторно не использовать и т. п. В общем использовать PHP примерно как, емнип, Scala.

          • 0
            Сравнивать code completion для PHP и для JS не совсем корректно.
            Сделать приличный code completion для JS намного труднее, чем для PHP.
            Хотя бы потому, что в PHP способы декларации полей и методов класса жёстко заданы, а в JS этих способов +∞ и какой-нибудь

            jQuery.each(
              someMember.split(" "), 
              function(index, value) {
                jQuery.fn[value] = function(x) {};
              }
            );
            


            внезапно может понадобавлять кучу методов непонятно куда.
            • +2
              Совсем не обязательно. Объекты в JS — то же самое, что массивы в PHP. Ни одна среда разработки не подскажет вам, какие ключи следует ожидать массиве. И в PHP тоже можно намусорить в глобальную область видимости, например так:
              <?php
              if(mt_rand(1, 1000) < 500)
              {
                  function A($a) { echo 'A = ' . $a; }
              }
              else
              {
                  function B($a) { echo 'B = ' . $a; }
              }
              

              А еще можно вообще сделать eval, как и в JS. Повторюсь — если понимать под фразой «приличный code completion» качество подсказок, которое дают R# или Idea, то как для PHP, так и для JS это априори невозможно. Поэтому все среды разработки на динамических языках работают примерно одинаково: дают контекстные подсказки только локально, а для остального выдают полный список найденных в проекте идентификаторов.
              • –1
                Та же Idea с PHP плагином показывает довольно адекватно подсказки, когда может автоматически вывести тип (грубо — во всем проекте только одно присваивание данной переменной, тип которого не вызывает сомнения) или есть актуальные phpdoc комментарии (плюс выявление заметной части противоречий между кодами и phpdoc).
    • +1
      Учитывая, что у eclipse есть только один аналог сходный по возможностям — IDEA — и тот платный и закрытый, вернее было бы говорить «не eclipse, а какой-нибудь sublime». А вообще говоря, не знаю, как у вас, а у меня в eclipse на сегодняшний день проблемы только с кособокой и недоделанной ADT. С CDT и тем более с JDT никаких проблем нет.
      • +8
        Я не знаю, про какой язык вы говорите, но в Scala я долго с муками цеплялся за любимый много лет Eclipse, а потом в какой то момент сел на IDEA и весьма ей доволен. Только шорткаты переделал на эклипсовские. И ничего она не платная, Community Edition ничем меня не ограничивает.
      • НЛО прилетело и опубликовало эту надпись здесь
        • НЛО прилетело и опубликовало эту надпись здесь
          • 0
            А как на ваш взгляд с поддержкой Scala в NetBeans по сравнению с Idea? С NetBeans я работал совсем мало, слышал, что там тоже есть плагин для Scala, но пощупать не приходилось.

            Если что, я вас не минусовал. И мне действительно интересен вопрос.
            • НЛО прилетело и опубликовало эту надпись здесь
      • НЛО прилетело и опубликовало эту надпись здесь
  • +1
    Кастую монографию Мартина Фаулера «Domain Specific Languages».
  • +1
    Так а что в этом проекте помогает инкрементальной компиляции? Парсер — это тривиальная задача по сравнению с собственно компилятором.
    • 0
      Папа Карло не только инкрементально разбирает исходный код, но и сохраняет незатронутые куски AST инввариантными(каждый узел имеет свой идентификатор — уникальный на все время работы компилятора). Таким образом, любые сущности, которые вы нацепите на AST в следующих фазах компиляции, включая семантические связи и байт-код, будут также сохранены и могут быть переиспользованы.

      Согласен, что при ряде ограничений разработка бэкэнда инкрементального компилятора может тоже оказаться весьма нетривиальной проблемой, но я не стал бы вот так легко списывать со счетов фронтэнд.
  • 0
    Jetbrains Nitra примерно про то же?
    • 0
      Достаточно разные вещи. Nitra по большому счету — это еще один инструмент для разработки плагинов для IntelliJ Idea, путем расширения синтаксиса существующих языков в некоторых заданных рамках.

      Если все же сравнивать:

      * Nitra больше про расширение существующих языков. Papa Carlo — вполне традиционный парсер-комбинатор.
      * Подход Nitra — все из коробки. Papa Carlo — отдельная библиотека для бесшовного связывания с другими компонентами компилятора.
      * У Nitra свой синтаксис, свой отдельный язык. Papa Carlo — API для Scala или Java.
      * Nitra скорее всего будет завязан на разработку языковых плагинов/расширений именно под продукты JetBrains. Papa Carlo не привязан ни к каким конкретным продуктам. Его можно использовать и для Eclipse, и для Sublime Text или даже для Vim и Emacs.

      Надо сказать, Nitra не первая попытка JetBrains сделать систему для построения DSL поверх существующих языков. До этого еще был MPS. А еще у Eclipse есть похожий проект — Xtet
      • 0
        Не такие уж и разные. Nitra — развитие вот этой библиотеки за деньги JetBrains. И с первого взгляда, разницы между PapaCarlo и Nemerle.PEG особой и нет, кроме того что там не java, а .net. Хотя это, конечно не отменяет того факта, что разработчики упорно Нитру называет «фреймворком для создания языков».
        • 0
          Интересно, спасибо за ссылку. Надо будет изучить поподробнее.

          А как там, в PegGrammar-Macro, с инкрементальным разбором? Это в общем-то ключевой момент. PEG парсеров довольно много, и не только на Nemerle со Scala, конечно. Но почти все они не поддерживают инкрементальный парсинг.

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