Как устроен компилятор?

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

Конечно, во многих ВУЗах есть специальные курсы, посвящённые устройству различных компонентов современных компиляторов и интерпретаторов. И современные компиляторы слишком сложны для того, чтобы рассказать о них в одной статье достаточно подробно. Тем не менее, базовые механизмы работы компиляторов остались неизменными со времён выпуска первого компилятора языка Фортран.


С высоты птичьего полёта...

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

Итак, что же это за части? Это лексический анализатор, или сканер; синтаксический анализатор, или парсер; семантический анализатор; а также один или несколько генераторов кода и один или несколько оптимизаторов. Также к компилятору часто относят дополнительные инструменты, нужные для создания исполняемого файла - сборщик и компоновщик.

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


От "А" до "Я"

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

Следом за лексическим анализом может быть препроцессор. Тем, кто знаком с языками программирования C или С++, нет нужды объяснять, в чём состоит его функция. Для остальных же скажу, что основная задача препроцессора - это замена одних лексем другими, которые были заранее определены в тексте программы. Используется препроцессор также для условной компиляции (т.е. когда кусок кода должен быть откомпилирован только при выполнении определённых условий - для определённой платформы, только при отладочном билде и т.д. и т.п.), для выполнения определённых макросов (как в том же C/C++) и некоторых других подобных вещей. Препроцессор не является обязательной частью компилятора, поскольку многие языки программирования не нуждаются в нём.

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

Следом за синтаксическим анализом следует этап анализа семантического. Если синтаксический анализатор строил скелет нашей программы, то семантический помогает этому скелету обрасти плотью. Программа наполняется смыслом: переменные становятся переменными, объекты - объектами, а баги - багами. На самом деле, никакого волшебства не происходит - просто дерево разбора, терпеливо построенное парсером, дополняется семантической информацией о значении идентификаторов. Кстати, на этом этапе возникают и многие ошибки компиляции - например, такие, как несоответствие типов. Хотя, конечно, на парсинг тоже приходится изрядное количество ошибок, без которых, к сожалению, текст свеженаписанной программы обходится крайне редко даже у очень опытных программистов.

Дальше пути различных компиляторов расходятся. В большинстве компиляторов следом за этапом семантического анализа идёт перевод программы в некоторый промежуточный код, который может использоваться для генерации кода под разные аппаратные платформы. Если компилятор выполняет компиляцию только для какой-то одной аппаратной платформы, то программа может транслироваться в коды на языке Ассемблера соответствующей процессорной архитектуры, или, если компилятор трудится для какой-то виртуальной машины (как, например, в случае Java или Microsoft .NET), то переводиться программа может затем в специальный байт-код, понятный соответствующей виртуальной машине. Тем не менее, в большинстве современных компиляторов нет непосредственной трансляции в ассемблерный код - даже если в итоге компилятор не должен стараться для создания кросс-платформенных программ, всё равно, сначала идёт трансляция программы в какой-то промежуточный код, а только потом уже в исполняемый. Причина этого в оптимизации кода.

Современные компиляторы, даже самые слабенькие и плохонькие, поддерживают хотя бы базовую оптимизацию кода. Более мощные коммерческие компиляторы содержат в себе очень мощные алгоритмы оптимизации кода, которые позволяют при некоторых условиях сделать её в разы быстрее. Особенно мощными в плане оптимизации давным-давно тому назад считались компиляторы производства Watcom, сейчас, вроде бы, постепенно восстанавливающие свою былую славу в виде open-source продукта. Потом пальма первенства перешла к компиляторам Intel, и сейчас именно они считаются самыми лучшими компиляторами в плане оптимизации. Что ж, это довольно логично - кому, как ни создателям процессоров, знать, как лучше всего оптимизировать программы для работы на них. Впрочем, не важно, плоха оптимизация в компиляторе или нет - главное, что в любом оптимизирующем компиляторе есть модуль, называемый оптимизатором, который начинает свою работу после генератора промежуточного кода. Справедливости ради стоит сказать, что оптимизатор может работать и после генерации уже исполняемого кода, но в наши дни такая схема встречается уже редко, поскольку производители компиляторов, как правило, выпускают целую линейку подобных продуктов для разных языков программирования и стараются делать оптимизаторы, которые можно встроить в любой из этих компиляторов. Какими именно методами оптимизатор может повышать скорость работы программы - это тема отдельной статьи, которую, возможно, вы когда-нибудь и сможете увидеть на страницах "Компьютерных вестей".

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

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


Дополнительные компоненты

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

Ассемблер и компоновщик в ряде случаев встроены прямо в компилятор, в других же случаях они выделяются в отдельные программы, которые запускаются после завершения работы самого компилятора. Их может и вовсе не быть, как, например, для компиляторов, преобразующих программы с одного языка высокого уровня на другой высокоуровневый язык (так называемых фронт-эндов), или они могут присутствовать только в виде, например, специфического сборщика, создающего код для виртуальной машины и помещающего его в какую-то специальную оболочку компоновщика (классический пример - Java с её JAR-файлами). Стоит, тем не менее, сказать пару слов о назначении этих двух инструментов.

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

Компоновщик создаёт из того кода, который сгенерировал ассемблер, исполняемые файлы. Даже для одной и той же процессорной архитектуры исполняемые файлы будут отличаться в зависимости от операционной системы. Например, для Windows формат исполняемых файлов - это Portable Executable (PE), а для Linux - Executable Linked File (EXE).


Резюме

Как видите, если смотреть на компиляторы со стороны, то всё в них просто и не вызывает никаких особенно заковыристых вопросов. На практике всё, мягко говоря, немного сложнее. И если вы вдруг решите написать собственный компилятор, то не стоит заранее пугаться, хотя к определённым сложностям нужно, как и в любой новой работе, быть готовым. Я бы лично рекомендовал начинать знакомство с предметом с написания какого-нибудь простого эзотерического языка вроде Brainfuck или Whitespace. Поскольку сам я в своё время интересовался благодаря своему знакомому Марату Духану первым из них, то и вам рекомендую его.

Вообще, если же вы вдруг решили проникнуть глубже в тайны создания компиляторов, то в Интернете для вас найдётся масса литературы - и простой, и академически точной и подробной. Начать можно, например, отсюда: kit.kulichki.net. Хотя сайт уже не обновлялся целую вечность, информация, размещённая на нём, подойдёт для новичка и не устареет ещё не один десяток лет. Вообще, если погуглить, информации найдёте очень много, даже придётся её фильтровать. Так что успехов вам с компиляторами!

Вадим СТАНКЕВИЧ

Версия для печатиВерсия для печати

Номер: 

37 за 2008 год

Рубрика: 

Software
Заметили ошибку? Выделите ее мышкой и нажмите Ctrl+Enter!