Как написать простейший компилятор

[Renelio]

Лучший способ понять работу компиляторов — написать свой собственный. В этом поможет этот краткий, но исчерпывающий гайд.

Введение
Стандартный компилятор осуществляет следующие шаги:

• Парсинг: исходный текст конвертируется в абстрактное синтаксическое дерево (Abstract Syntax Tree, AST).
• Разрешение зависимостей с другими модулями (С откладывает этот этап на шаг линковки).
• Семантическая валидация: исключение синтаксически корректных, но бессмысленных выражений, например, повторного объявления переменных.
• Эквивалентные преобразования и высокоуровневая оптимизация: AST преобразуется для осуществления более эффективных вычислений при той же семантике.
• Генерация кода: AST трансформируется в линейный код низкого уровня с переходами, распределением регистров и тому подобным.
• Локальная оптимизация: низкоуровневый код проверяется на простые локальные недостатки.

В большинстве современных компиляторов (вроде gcc и clang) последние два пункта повторяются еще раз. Для начальной генерации кода они используют не совсем низкоуровневый, но платформонезависимый язык. Потом этот промежуточный код переводится в зависящий от архитектуры (x86, ARM и так далее).

После этого объектный код готов к линковке. Большая часть нативных компиляторов автоматически вызывает линковщик, создающий исполняемый код, но это еще не компиляция. В языках вроде Java или C# линковка может быть полностью динамической и выполняться в виртуальной машине в момент загрузки.

Запомните основные моменты
Компилятор должен быть:

• работающим
• красивым
• эффективным

Эта классическая последовательность применима ко всей сфере разработки ПО. Сконцентрируйтесь на первом пункте. Сделайте простейшую вещь и заставьте ее работать.

Читайте книги!

Прочтите книгу «Компиляторы: принципы, технологии и инструменты». Эта бессмертная классика до сегодняшнего дня не потеряла актуальности. «Дизайн современных компиляторов» — также стоящая вещь.

Если на данном этапе это кажется вам слишком сложным, почитайте для начала какие-нибудь введения в парсинг.

Убедитесь, что вам комфортно работать с графами, особенно с деревьями. Это основа построения программ на логическом уровне.

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

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

Также нормально писать разные стадии развития компилятора на разных языках, если это требуется.

Приготовьтесь к написанию множества тестов
Весь ваш язык должен быть стопроцентно покрыт тестами, эффективнее всего, если он будет определен ими. Будьте на ты с выбранным тестовым фреймворком. Пишите тесты с первого дня. Рационально отдавать предпочтение «позитивным» тестам, которые предполагают корректную работу кода.

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

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

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

На выходе ваш парсер должен генерировать абстрактное синтаксическое дерево. Если ваш язык использует модули, то результатом работы парсера может быть простейшее представление генерируемого «объектного кода».

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

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

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

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

Забудьте об эффективности и сосредоточьтесь только на правильности.

Настройте платформо-независимую низкоуровневую виртуальную машину
Вероятнее всего, вас не очень интересуют низкоуровневые аспекты, если только вы не страстный поклонник всего, что связано с архитектурой.

Варианты для вас:

• LLVM: позволяет эффективно генерировать машинный код, чаще всего для х86 и ARM.
• CLR: ориентирована на .NET.
• JVM: нацелена на мир Java, мультиплатформенна.

Забудьте об оптимизации
Оптимизация — это сложно. И почти всегда она бывает преждевременной. Генерируйте неэффективный, но рабочий код. Реализуйте весь язык прежде чем приступите к оптимизации.

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