Разработка компиляторов полна красивых примеров решения сложных задач, возникающих при реальной работе над компиляторами, путем математического абстрагирования. Они служат прекрасной иллюстрацией того, как для решения задач могут быть применены абстракции: для этого надо для конкретной задачи сформулировать математическую абстракцию, которая содержит ключевые характеристики задачи, и решить ее с применением математических методов. Формулировка задачи должна основываться на четком понимании характеристик компьютерных программ, а решение должно быть проверено и уточнено эмпирически.
Компилятор должен принимать все исходные программы, которые соответствуют спецификации языка; множество исходных программ бесконечно, а сама программа может быть очень большой, состоящей, возможно, из миллионов строк. Любые преобразования, выполняемые компилятором при трансляции исходной программы, должны сохранить неизменным смысл компилируемой программы. Таким образом, разработчики компиляторов оказывают влияние не только на создаваемые ими компиляторы, но и на все программы, которые будут скомпилированы их компилятором. Это делает написание компиляторов особенно достойным занятием, но и налагает на программистов особую ответственность.
Моделирование при проектировании и реализации компилятора Изучение компиляторов, в основном, заключается в изучении способов разработки математических моделей и выбора правильных алгоритмов, балансируя между обобщенностью и мощью, с одной стороны, и простотой и эффективностью — с другой.
Некоторые из наиболее фундаментальных моделей — конечные автоматы и регулярные выражения. Эти модели полезны для описания лексических единиц программы (ключевых слов, идентификаторов и т.п.) и алгоритмов, используемых компилятором для распознавания этих единиц. К фундаментальным моделям относятся и контекстно-свободные грамматики, используемые для описания синтаксических структур языков программирования, таких как вложенные скобки и управляющие конструкции.
Изучение оптимизации кода Термин "оптимизация" в проектировании компиляторов означает попытки компилятора получить код, более эффективный, чем обычно. "Оптимизация", таким образом, является некорректным названием, поскольку нет способа гарантированно получить код столь же быстрый (или более быстрый), как любой другой код, выполняющий те же задачи.
В настоящее время оптимизация кода, выполняемая компилятором, становится все более важной и более сложной. Она становится более сложной, поскольку архитектуры процессоров также становятся все более сложными, предоставляя все больше возможностей для улучшения способа выполнения кода. Оптимизация становится более важной, поскольку массовое наступление компьютеров с возможностью параллельных вычислений требует существенной оптимизации, иначе их производительность падает на порядки. Вероятное преобладание многоядерных машин (компьютеров с большим количеством процессоров) требует от компиляторов использования преимуществ многопроцессорности.
Очень трудно, если вообще возможно, построить мощный компилятор без "хакерства". Соответственно, вокруг задачи оптимизации кода построена богатая и полезная теория. Используя точные математические основы, можно убедиться в корректности оптимизации и получить желаемый эффект для всех возможных входных данных.
С другой стороны, одной голой теории недостаточно. Как и у многих других задач реального мира, здесь нет окончательного идеального ответа. В действительности большинство вопросов, задаваемых при оптимизации кода компилятором, оказываются неразрешимыми. Одно из важных проявлений профессионализма в проектировании компиляторов состоит в умении корректно сформулировать решаемую задачу. Для начала требуются хорошее понимание поведения программ и всестороннее экспериментирование и вычисления для подтверждения интуитивных предположений.
Оптимизации, выполняемые компилятором, должны отвечать четырем требованиям проектирования:
1. оптимизация должна быть корректной, т.е. сохранять смысл компилируемой программы;
2. оптимизация должна повышать производительность многих программ;
3. время компиляции должно оставаться в разумных пределах;
4. требуемая для реализации оптимизации инженерная работа должна быть осуществима.
Невозможно переоценить важность корректности. Написать компилятор, генерирующий быстрый код, — тривиальная задача, если генерируемый код может быть неверным! Оптимизирующие компиляторы настолько сложны, что мы готовы даже заявить, что нет ни одного полностью безошибочного оптимизирующего компилятора! Итак, наиболее важная цель при написании компилятора — это его корректность.
Вторая цель состоит в том, чтобы компилятор мог повышать производительность многих программ. Обычно производительность означает скорость выполнения программы. Если говорить о встраиваемых приложениях, то тут может оказаться желательным также малый размер сгенерированного кода. В случае мобильных устройств желательно, чтобы код минимизировал потребление энергии. Обычно та же оптимизация, которая повышает скорость выполнения, приводит и к экономии энергии. Помимо производительности, важны и такие потребительские аспекты, как сообщения об ошибках и отладка.
Время компиляции должно оставаться достаточно небольшим, чтобы поддерживать быстрый цикл разработки и отладки. Выполнить это требование становится все проще с ростом быстродействия машин. Зачастую сначала программа разрабатывается и отлаживается без оптимизации. Это делается не только для снижения времени компиляции, но и, что более важно, потому что неоптими- зированную программу легче отлаживать (оптимизация компилятором зачастую ухудшает связь между исходным и объектным кодами). Включение оптимизации компилятора иногда выявляет новые проблемы в исходной программе; таким образом, тестирование должно выполняться для оптимизированного кода заново. Требование дополнительного тестирования иногда удерживает от использования оптимизации в приложениях, в особенности если их производительность не критична.
И наконец, компилятор представляет собой сложную систему, которая при этом должна быть достаточно простой, чтобы стоимость ее разработки и поддержки оставалась в разумных пределах. Имеется бесконечное число оптимизаций, которые могут быть реализованы, но для получения корректной и эффективной оптимизации часто требуются выходящие из ряда вон усилия. Приоритет в реализации отдается тем оптимизациям, которые приводят к большему выигрышу для встречающихся на практике исходных программ.
Таким образом, при изучении компиляторов следует не только научиться строить компилятор, но и освоить общую методологию решения сложных и не ограниченных определенными рамками задач. Подход, используемый при разработке компиляторов, включает как теорию, так и эксперимент. Обычно работа начинается с постановки задачи, основанной на интуитивном представлении о важности тех или иных вопросов.
