Мои первые пятнадцать компиляторов
Компиляторы — сложные программы, переводящие некоторую программу из исходного языка в конечный. Обычно, программу обрабатывают несколькими проходами. Каждый проход может: изменять программу — к примеру, преобразовывать замыкания; оптимизировать — например избавляться от неиспользуемого кода; или же анализировать — и результат анализа будет использован в последующих проходах оптимизаций и изменений.
Нам ясно — чем больше в компиляторе проходов, тем он сложней устроен. К примеру в классической работе "Из system f в типизированный ассемблер" сказано что компилятор "к одной программе может применять вплоть до 20 проходов. Проводя такие сложные изменения и анализ, как преобразование продолжений и замыканий, распаковку значений, и т.д.". 20 проходов должны казаться нам чем-то внушительным — так и есть. А возможно ли упростить разработку компиляторов, приняв, что они должны состоять из большого множества простейших проходов, выполняющих что-то одно?
Подход nanopass
Мой самый первый компилятор переводил scheme в язык ассемблера x86-64, и был написан за один курс института. Но я написала не просто один компилятор, их было пятнадцать, по одному на каждую неделю семестра. Компилятор первой недели на вход получал чуть ли не язык ассемблера — только со скобками, а выдавал asm x86-64. В последующие недели, добавляя проходов к компилятору предшествующей недели, получали компиляторы, выдающие тот же язык ассемблера, но получающие немного более высокоуровневый язык.
По окончанию курса, у меня был компилятор из значительного подмножества scheme в язык ассемблера x86-64, состоящий из сорокатрех маленьких проходов. Каждый следующий проход выдавал чуть более низкоуровневый язык, или же тот же что и предыдущий, просто анализировав или оптимизировав исходный язык.
Сорокатрехпроходный компилятор за пятнадцать недель возможен лишь потому, что для разработки компилятора мы использовали подход nanopass. При таком подходе компилятор строится из простейших проходов, получающих и выдающих определенные языки. Для этого используется фреймворк c доступным исходным кодом, с DSL, эффективно описывающим промежуточные языки и, проходы, переводящие один такой язык в другой.
Nanopass впервые был описан в журнале ICFP в статье "nanopass. фреймворк для обучения построению компиляторов", а позднее и в JFP. Изначально он задумывался не только для обучения, но рецензенты из ICFP настаяли на таком описании, ведь они верили что подобные компиляторы обязательно будут медленными. Позже авторы переписали chez scheme используя nanopass, показав скорость компиляции, и описали это в статье "nanopass для разработки коммерческих компиляторов" (прим. пер. Изначально chez scheme самокомпилировался за три секунды, после переписывания — за шесть. Авторы сказали что время компиляции увеличелось в основном из-за более суровых оптимизаций, и в общем, теперь компилятор выдает более быстрый код).
Для меня nanopass — распростронение подхода комбинаторов парсеров на разработку компилятора в целом. С комбинаторами парсеров, парсер для сложного языка строится из множества маленьких парсеров, например парсеров чисел, знаков и т.п. Постепенно, дописывая парсер можно разбирать все более сложные языки. Но уже с самого начала у нас есть рабочий парсер. Также и с nanopass — с самого начала у нас есть компилятор, со временем способный обрабатывать более сложные языки.
=====
Плохо вычитанный перевод 1\3 статьи.
