Компилятороведение.

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

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

Моделирование при проектировании и реализации компилятора

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

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

Изучение оптимизации кода

Термин "оптимизация" в проектировании компиляторов означает попытки компилятора получить код, более эффективный, чем обычно. "Оптимизация", та­ким образом, является некорректным названием, поскольку нет способа гаранти­рованно получить код столь же быстрый (или более быстрый), как любой другой код, выполняющий те же задачи.

В настоящее время оптимизация кода, выполняемая компилятором, становит­ся все более важной и более сложной. Она становится более сложной, поскольку архитектуры процессоров также становятся все более сложными, предоставляя все больше возможностей для улучшения способа выполнения кода. Оптими­зация становится более важной, поскольку массовое наступление компьютеров с возможностью параллельных вычислений требует существенной оптимизации, иначе их производительность падает на порядки. Вероятное преобладание много­ядерных машин (компьютеров с большим количеством процессоров) требует от компиляторов использования преимуществ многопроцессорности.

Очень трудно, если вообще возможно, построить мощный компилятор без "хакерства". Соответственно, вокруг задачи оптимизации кода построена богатая и полезная теория. Используя точные математические основы, можно убедиться в корректности оптимизации и получить желаемый эффект для всех возможных входных данных. 

С другой стороны, одной голой теории недостаточно. Как и у многих других задач реального мира, здесь нет окончательного идеального ответа. В действитель­ности большинство вопросов, задаваемых при оптимизации кода компилятором, оказываются неразрешимыми. Одно из важных проявлений профессионализма в проектировании компиляторов состоит в умении корректно сформулировать решаемую задачу. Для начала требуются хорошее понимание поведения программ и всестороннее экспериментирование и вычисления для подтверждения интуи­тивных предположений.

Оптимизации, выполняемые компилятором, должны отвечать четырем требовани­ям проектирования:

1. оптимизация должна быть корректной, т.е. сохранять смысл компилируе­мой программы;

2. оптимизация должна повышать производительность многих программ;

3. время компиляции должно оставаться в разумных пределах;

4. требуемая для реализации оптимизации инженерная работа должна быть осуществима.

Невозможно переоценить важность корректности. Написать компилятор, ге­нерирующий быстрый код, — тривиальная задача, если генерируемый код может быть неверным! Оптимизирующие компиляторы настолько сложны, что мы гото­вы даже заявить, что нет ни одного полностью безошибочного оптимизирующего компилятора! Итак, наиболее важная цель при написании компилятора — это его корректность.

Вторая цель состоит в том, чтобы компилятор мог повышать производитель­ность многих программ. Обычно производительность означает скорость выпол­нения программы. Если говорить о встраиваемых приложениях, то тут может оказаться желательным также малый размер сгенерированного кода. В случае мо­бильных устройств желательно, чтобы код минимизировал потребление энергии. Обычно та же оптимизация, которая повышает скорость выполнения, приводит и к экономии энергии. Помимо производительности, важны и такие потребитель­ские аспекты, как сообщения об ошибках и отладка.

Время компиляции должно оставаться достаточно небольшим, чтобы поддер­живать быстрый цикл разработки и отладки. Выполнить это требование стано­вится все проще с ростом быстродействия машин. Зачастую сначала программа разрабатывается и отлаживается без оптимизации. Это делается не только для снижения времени компиляции, но и, что более важно, потому что неоптими- зированную программу легче отлаживать (оптимизация компилятором зачастую ухудшает связь между исходным и объектным кодами). Включение оптимиза­ции компилятора иногда выявляет новые проблемы в исходной программе; таким образом, тестирование должно выполняться для оптимизированного кода зано­во. Требование дополнительного тестирования иногда удерживает от использова­ния оптимизации в приложениях, в особенности если их производительность не критична.

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

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