Процесс компиляции программ на C++
Цель данной статьи:
В данной статье я хочу рассказать о том, как происходит компиляция программ, написанных на языке C++, и описать каждый этап компиляции. Я не преследую цель рассказать обо всем подробно в деталях, а только дать общее видение. Также данная статья — это необходимое введение перед следующей статьей про статические и динамические библиотеки, так как процесс компиляции крайне важен для понимания перед дальнейшим повествованием о библиотеках.
Все действия будут производиться на Ubuntu версии 16.04.
Используя компилятор g++ версии:
Состав компилятора g++
Мы не будем вызывать данные компоненты напрямую, так как для того, чтобы работать с C++ кодом, требуются дополнительные библиотеки, позволив все необходимые подгрузки делать основному компоненту компилятора — g++.
Зачем нужно компилировать исходные файлы?
Исходный C++ файл — это всего лишь код, но его невозможно запустить как программу или использовать как библиотеку. Поэтому каждый исходный файл требуется скомпилировать в исполняемый файл, динамическую или статическую библиотеки (данные библиотеки будут рассмотрены в следующей статье).
Этапы компиляции:
driver.cpp:
1) Препроцессинг
Самая первая стадия компиляции программы.
Препроцессор — это макро процессор, который преобразовывает вашу программу для дальнейшего компилирования. На данной стадии происходит происходит работа с препроцессорными директивами. Например, препроцессор добавляет хэдеры в код (#include), убирает комментирования, заменяет макросы (#define) их значениями, выбирает нужные куски кода в соответствии с условиями #if, #ifdef и #ifndef.
Хэдеры, включенные в программу с помощью директивы #include, рекурсивно проходят стадию препроцессинга и включаются в выпускаемый файл. Однако, каждый хэдер может быть открыт во время препроцессинга несколько раз, поэтому, обычно, используются специальные препроцессорные директивы, предохраняющие от циклической зависимости.
Получим препроцессированный код в выходной файл driver.ii (прошедшие через стадию препроцессинга C++ файлы имеют расширение .ii), используя флаг -E, который сообщает компилятору, что компилировать (об этом далее) файл не нужно, а только провести его препроцессинг:
Взглянув на тело функции main в новом сгенерированном файле, можно заметить, что макрос RETURN был заменен:
В новом сгенерированном файле также можно увидеть огромное количество новых строк, это различные библиотеки и хэдер iostream.
2) Компиляция
На данном шаге g++ выполняет свою главную задачу — компилирует, то есть преобразует полученный на прошлом шаге код без директив в ассемблерный код. Это промежуточный шаг между высокоуровневым языком и машинным (бинарным) кодом.
Ассемблерный код — это доступное для понимания человеком представление машинного кода.
Используя флаг -S, который сообщает компилятору остановиться после стадии компиляции, получим ассемблерный код в выходном файле driver.s:
Мы можем все также посмотреть и прочесть полученный результат. Но для того, чтобы машина поняла наш код, требуется преобразовать его в машинный код, который мы и получим на следующем шаге.
3) Ассемблирование
Так как x86 процессоры исполняют команды на бинарном коде, необходимо перевести ассемблерный код в машинный с помощью ассемблера.
Ассемблер преобразовывает ассемблерный код в машинный код, сохраняя его в объектном файле.
Объектный файл — это созданный ассемблером промежуточный файл, хранящий кусок машинного кода. Этот кусок машинного кода, который еще не был связан вместе с другими кусками машинного кода в конечную выполняемую программу, называется объектным кодом.
Далее возможно сохранение данного объектного кода в статические библиотеки для того, чтобы не компилировать данный код снова.
Получим машинный код с помощью ассемблера (as) в выходной объектный файл driver.o:
Но на данном шаге еще ничего не закончено, ведь объектных файлов может быть много и нужно их всех соединить в единый исполняемый файл с помощью компоновщика (линкера). Поэтому мы переходим к следующей стадии.
4) Компоновка
Компоновщик (линкер) связывает все объектные файлы и статические библиотеки в единый исполняемый файл, который мы и сможем запустить в дальнейшем. Для того, чтобы понять как происходит связка, следует рассказать о таблице символов.
Таблица символов — это структура данных, создаваемая самим компилятором и хранящаяся в самих объектных файлах. Таблица символов хранит имена переменных, функций, классов, объектов и т.д., где каждому идентификатору (символу) соотносится его тип, область видимости. Также таблица символов хранит адреса ссылок на данные и процедуры в других объектных файлах.
Именно с помощью таблицы символов и хранящихся в них ссылок линкер будет способен в дальнейшем построить связи между данными среди множества других объектных файлов и создать единый исполняемый файл из них.
Получим исполняемый файл driver:
5) Загрузка
Последний этап, который предстоит пройти нашей программе — вызвать загрузчик для загрузки нашей программы в память. На данной стадии также возможна подгрузка динамических библиотек.
Запустим нашу программу:
Заключение
В данной статье были рассмотрены основы процесса компиляции, понимание которых будет довольно полезно каждому начинающему программисту. В скором времени будет опубликована вторая статья про статические и динамические библиотеки.
Введение в компиляцию. Структура компилятора. Процесс компиляции.
Язык программирования – это искуственный язык, созданный для взаимодействия с машиной, в частности, с компьютером. ЯП используются для написания программ, которые управляют машиной и/или выражают алгоритмы.
Первые ЯП были созданы задолго до появления компьютеров и управляли поведением, скажем, самоиграющих пианино или автоматических ткацких станков.
Многие ЯП имеют императивную форму, т.е. описывают последовательность операций. Другие могут иметь декларативную форму, т.е. описывают результат, а не то, как его получить.
Некоторые языки определяются стандартом (C,C++,Haskell, и др.). Другие не имеют формального описания, и наиболее широко распространенная реализация используется в качестве эталона.
Описание ЯП обычно делится на две части: синтаксис, т.е. форма, и семантика, т.е. значение.
Синтаксис в свою очередь подразделяется на лексику и грамматику.
Лексика определяет какие “слова” могут быть в языке. Это включает названия переменных, функций, числовые константы, строки, и т.п., а так же управляющие символы языка. Грамматика определяет каким образом эти “слова” комбинируются в более сложные выражения.
Не все синтаксически корректные программы являются семантически корректными. Например:
Семантика же подразделяется на статическую, динамическую, и систему типов.
определяет статические свойства языка, выходящие за рамки синтаксиса. Например, статическая семантика может определять, что все идентификаторы должны быть определены перед использованием, или что вызов функции должен принимать столько же аргументов, сколько указано в её определении (ни то ни другое не является, вообще говоря, обязательным)
определяет стратегию выполнения программы. Она определяет, каким образом исполняются инструкции, порядок их исполнения, значение управляющих структур и т.д.
определяет каким образом ЯП классифицирует значения и выражения, как эти типы взаимодействуют и каким образом ЯП может манипулировать ими. Система типов является практическим приложением теории категорий. Цель системы типов – проверка программы на корректность (до какой-то степени). Любая система типов, отвергая некорректные программы, будет так же отвергать некоторый процент корректных (хотя вероятно необычных) программ. Чтобы обойти это ограничение, ЯП обычно имеют некие механизмы для выхода из ограничений системы типов. В большинстве случаев, указание корректных типов ложится на совесть программиста. Однако некоторые ЯП (обычно функциональные) умеют выводить типы исходя из семантики, и таким образом освобождают программиста от необходимости явно указывать типы.
Динамическая семантика может определяться различными способами. Наиболее распространёнными являются операционная семантика и денотационная семантика.
Операционная семантика способ описания семантики, при котором для описания поведения используется набор аксиоматических определений синтаксических конструкций языка и логических правил вывода (вида “если, то”). Выделяют операционную семантику с малым шагом, когда подробно определяется каждый шаг вычисления для выражений, и операционную семантику с большим шагом, когда определяется конечный результат выражений. Денотационная семантика способ описания семантики, при котором выражениям языка ставятся в соответствие какие-то математические объекты с априори известной семантикой, т.е. смысл языковых конструкций ставится в соответствие конструкциям математическим.
Введение в компиляцию
Компиляция – это трансляция (преобразование) текста программы, написанного на одном языке (исходном), в эквивалентный (сохраняющий семантику) текст на другом языке (целевом).
Компилятор – это программа, читающая текст программы на исходном языке и компилирующая его.
Альтернативным подходом является интерпретация, т.е. непосредственное выполнение операций, указанных в исходном тексте программы.
Интерпретатор – программа, читающая исходный текст, и интерпретирующая его.
Кроме того, компилятор может производить статический анализ исходного кода программы и сообщать об ошибках и выводить предупреждения о потенциальных проблемах.
Целевой язык может быть машинным языком, в таком случае результат работы компилятора может быть выполнен исполнительным устройством непосредственно. Целевой язык может быть также другим языком программирования (транс-компиляция) или машинным языком для некой виртуальной машины (такой язык обычно называется байт-кодом). Байт-код в свою очередь выполняется программой-интерпретатором байт-кода.
Условная схема компиляции
Условная схема интерпретации
Условная схема компиляции в байт-код
Вообще говоря, для создания исполняемой программы на целевом языке могут потребоваться другие программы и компоненты.
Структура компилятора. Процесс компиляции
Процесс компиляции обычно разделяется на две фазы: анализ и синтез.
В фазе анализа происходит чтение исходного текста программы, затем этот текст разбивается на элементарные блоки, на них накладывается грамматическая структура, и создаётся промежуточное представление исходного текста и собирается другая информация об исходном тексте. На этой фазе так же возможен статический анализ исходного текста.
В фазе синтеза, на основе промежуточного представления и прочей информации, строится представление исходной программы в целевом коде. На этой фазе так же возможны преобразования целевого кода, называемые оптимизациями.
Кроме того, между анализом и синтезом может находиться фаза преобразований промежуточного кода, называемая машинно-независимой оптимизацией.
Лексический анализ
Первая фаза компиляции называется лексическим анализом или сканированием.
Лексический анализатор соответственно так же называется лексером или сканером.
Лексический анализатор сканирует входной поток символов (исходного текста программы) и выделяет значащие последовательности символов, называемые лексемами.
Для каждой лексемы анализатор выводит токен, представляющий из себя комбинацию абстрактного символа (названия типа токена) и произвольного набора атрибутов. Часто в качестве “набора атрибутов” выступает ссылка в глобальную таблицу, называемую таблицей символов.
Синтаксический анализ
Вторая фаза – синтаксический анализ или разбор, парсинг (от англ. parsing).
Синтаксический анализатор соответственно называется так же парсером.
Парсер строит из токенов, полученных от лексера, древовидное промежуточное представление (часто неявно), отражающее грамматическую структуру исходного кода. Примером такого представления является синтаксическое дерево, где узлы представляют операцию, дочерние узлы – аргументы этой операции.
Например, синтаксическое дерево арифметического выражения \(1+2*3\) может иметь вид:
Семантический анализ
Семантический анализатор использует синтаксическое дерево для проверки исходной программы на корректность.
На этом же этапе происходит проверка типов, и информация о типах переменных записывается в атрибуты соответствующих узлов синтаксического дерева.
Если спецификация языка разрешает неявное приведение типов, на этом этапе синтаксическое дерево может быть переписано с добавлением явных операций приведения типов.
Генерация промежуточного кода
В процессе компиляции, могут создаваться несколько промежуточных представлений, в частности, синтаксическое дерево.
Как правило, после завершения синтаксического и семантического анализа, значительная часть высокоуровневой информации (типы, названия переменных, многие управляющие конструкции и т.п.) далее не требуется, в связи с чем многие компиляторы по достижении этой фазы генерируют более низкоуровневое представление, называемое обычно промежуточным кодом.
Основными требованиями к промежуточному коду являются, с одной стороны, простота его получения из синтаксического дерева, и с другой стороны, простота генерации на его основе машинного кода.
Как следствие, часто в качестве промежуточного кода используется последовательность инструкций для некой абстрактной вычислительной машины.
На этом этапе обычно принимаются решения о распределении памяти для хранения значений переменных.
Машинно-независимая оптимизация
На фазе машинно-независимой оптимизации, промежуточный код преобразуется с целью “улучшения” без изменений наблюдаемого поведения (в соответствии со спецификацией языка 1 ). Под “улучшением” обычно понимается “ускорение”, но иногда возможны другие критерии, например “код меньшего размера” или “меньшее потребление памяти”.
Часто, алгоритм первичной генерации промежуточного кода достаточно простой, поэтому без фазы оптимизации, код оказывается достаточно неэффективным.
Объём работы, проделываемый различными компиляторами на этом этапе может сильно отличаться. Большинство распространённых на рынке компиляторов являются “оптимизирующими” и значительная часть времени компиляции уходит именно на оптимизацию (обычно есть способ отключить оптимизацию при необходимости).
Генерация целевого кода
Генератор целевого кода, получая на вход промежуточный код, отображает каждую команду промежуточного кода в одну или несколько команд целевого.
Кроме того, генератор целевого кода занимается задачей распределения регистров исполнительного устройства.
Машинно-зависимая оптимизация
Шаг машинно-зависимой оптимизации преобразует, как правило, уже целевой код. Основными способами оптимизации на данном этапе могут быть различные эквивалентные замены последовательностей машинных команд на более быстрые аналоги, не меняющие поведения перестановки команд или блоков команд, приводящие к ускорению и т.п.
Большинство решений машинно-зависимой оптимизации принимаются на основе модели исполнительного устройства, встроенной в компилятор. Например, в компилятор может быть включена информация об относительном времени выполнения различных инструкций определённого процессора (или семейства процессоров).
эта немаловажная оговорка доставляет много боли начинающим, а иногда и опытным, разработчикам C и C++↩︎
Компиляция. 1: лексер
Меня всегда завораживало таинство рождения программой программы. К сожалению, российские вузы уделяют мало внимания сей интереснейшей теме. Рассчитываю написать серию постов, в которых поэтапно создадим маленький работоспособный компилятор.
Первые посты серии уже подготовлены, и бета-тестировались в одном маленьком и наглухо закрытом сообществе. Тем не менее, я буду продолжать их править с учётом пожеланий почтенной хабрапублики.
Далее в посте:
С какой стати писать компиляторы?
Everything that can be invented has been invented.
—Charles H. Duell, Director of U.S. Patent Office, 1899 (attributed)
Что было, то и будет; и что делалось, то и будет делаться, и нет ничего нового под солнцем.
—Екклесиаст 1:9 (ок. 3 в. до н.э.)
Во-первых, языки постоянно создаются и развиваются. Из ныне популярных, Ruby, PHP, Java и C# были созданы на нашей памяти, а бурно применяться начали несколько лет назад. Прямо сейчас Майкрософт проталкивает новый язык F#, и он — учитывая мощь Майкрософт — наверняка также войдёт в число общеупотребимых.
До сих пор остаются ниши для новых языков: например, не прекращаются попытки придумать удобный императивный язык для параллельного программирования.
Во-вторых, используемые в компиляции приёмы (в первую очередь, парсинг по грамматике) имеют массу других приложений. Часто есть потребность в преобразованиях source-to-source (рефакторинг, перевод кода на другой язык, и т.п.), когда нужно разобрать текст на языке программирования, обработать его, и вывести обработанный текст (на том же или на другом языке).
Безусловно, компиляция — довольно экзотичное занятие для программиста, где-нибудь в одном ряду с программированием огромных боевых человекоподобных роботов. Однако у всего этого есть практические применения, в отличие от многих других экстравагантных программистских хобби.
Общий план
Самая challenging часть компилятора — оптимизация кода; на первом этапе выполняется высокоуровневая оптимизация, на уровне узлов дерева (например, разворачиваются циклы, вживляются inline-функции); на втором — низкоуровневая, на уровне потока команд (например, переупорядочиваются так, чтобы полнее нагрузить конвейеры конкретного процессора). До оптимизаций, по традиции, в вузовских курсах дело никогда не доходит; но самые простые (copy elimination, constant propagation) мы в нашем примере постараемся реализовать.
Старые посты на тему синтаксического разбора я на Хабре видел; но к генерации кода, вроде бы, авторы не приближались ни разу.
Анализ текста
Когда начинающий программист пытается написать парсер текста, его естественный подход — рекурсивное углубление: найти начало конструкции (например, <); найти её конец (например, > на том же уровне вложенности); выделить содержимое конструкции, и пропарсить её рекурсивно.
Проблемы с таким подходом — во-первых, избыточная сложность (по одному и тому же фрагменту текста гуляем взад-вперёд); во-вторых, неудобство поддержки (синтаксис языка оказывается рассредоточен по килобайтам и килобайтам ветвистого кода).
Синтаксис языка можно задать декларативно; например, всем знакомы регулярные выражения. Идеально было бы написать стопочку регэкспов для всех конструкций языка, напротив каждого — определение узла, который должен создаться в дереве программы; «универсальный парсер» бы просто подставлял программу в один регэксп за другим, и создавал узлы согласно описанию, один за другим.
Первая из названных проблем решается тем, что поиск всех регэкспов в тексте можно выполнить за один проход, т.е. нет надобности хранить всю программу в памяти целиком — достаточно читать её по одному символу, обрабатывать символ, и тут же забывать.
Вторая — тем, что теперь у нас есть централизованное, формальное описание языка: можем менять регэкспы, вовсе не трогая код; и наоборот, менять код, не рискуя повредить парсер.
Практический пример
По традиции, первым примером станет написание калькулятора:
Имитируется калькулятор торговок с рынка: без скобок, без приоритета операций, без дробей. Выражения разделяются точкой с запятой, и можно вставлять комментарии от // до конца строки.
Скомпилируем наш калькулятор, и попробуем с ним поиграть:
[tyomitch@home
Разбор кода
Как это работает?
У математиков есть понятие ДКА (детерминированный конечный автомат) — штука, которая может находиться в одном из N состояний; которая читает из входного потока символ за символом; и у которой есть таблица: для каждого сочетания текущего состояния и прочитанного символа — в которое состояние перейти. Работа flex заключается в том, что он строит ДКА по заданному набору регэкспов; в некоторых состояниях этот ДКА не только переходит в следующее, но вдобавок вызвает наши правила.
Символы здесь разбиты на 8 классов, идентичных с точки зрения парсера (например, все цифры объединены в один класс). Отдельный массив static yyconst int yy_ec[256] ставит каждому символу в соответствие класс.
Основной цикл работы парсера весьма незамысловат:
Замечательно то, насколько готовый парсер прост: вместо ветвистого распознавания разных конструкций, у нас одна большая таблица, и цикл из десяти строк. Но есть существенная проблема. Вернёмся к примеру из самого начала поста: «найти начало конструкции (например, <); найти её конец (например, > на том же уровне вложенности). » Как регэкспом обозначить условие «на том же уровне вложенности»?
Математики и тут постарались: доказали, что невозможно. Значит, для парсинга языков, поддерживающих вложенные конструкции (а это все языки сложнее BAT-файлов), нам потребуется более мощный инструмент, чем регэкспы. В следующий раз — о нём.
Основные принципы программирования: компилируемые и интерпретируемые языки
Как и в предыдущей статье этого цикла, я хочу обратить ваше внимание на ключевые принципы программирования, которые влияют на всё то, что мы делаем, но с которыми мы редко сталкиваемся напрямую и поэтому не до конца их понимаем. Тема сегодняшней статьи — компилируемые и интерпретируемые языки.
Будучи разработчиками, мы часто сталкиваемся с такими понятиями, как компилятор и интерпретатор, но я считаю, что многие не совсем понимают, что они означают. Между тем, компиляция и интерпретация — это основы работы всех языков программирования. Давайте взглянем на то, как на самом деле устроены эти понятия.
Вступление
Мы полагаемся на такие инструменты, как компиляция и интерпретация, чтобы преобразовать наш код в форму, понятную компьютеру. Код может быть исполнен нативно, в операционной системе после конвертации в машинный (путём компиляции) или же исполняться построчно другой программой, которая делает это вместо ОС (интерпретатор).
Компилируемый язык — это такой язык, что программа, будучи скомпилированной, содержит инструкции целевой машины; этот машинный код непонятен людям. Интерпретируемый же язык — это такой, в котором инструкции не исполняются целевой машиной, а считываются и исполняются другой программой (которая обычно написана на языке целевой машины). Как у компиляции, так и у интерпретации есть свои плюсы и минусы, и именно это мы и обсудим.
Прежде чем мы продолжим, стоит отметить, что многие языки программирования имеют как компилируемую, так и интерпретируемую версии, поэтому классифицировать их затруднительно. Тем не менее, чтобы не усложнять, в дальнейшем я буду разделять компилируемые и интерпретируемые языки.
Компилируемые языки
Главное преимущество компилируемых языков — это скорость исполнения. Поскольку они конвертируются в машинный код, они работают гораздо быстрее и эффективнее, нежели интерпретируемые, особенно если учесть сложность утверждений некоторых современных скриптовых интерпретируемых языков.
Низкоуровневые языки как правило являются компилируемыми, поскольку эффективность обычно ставится выше кроссплатформенности. Кроме того, компилируемые языки дают разработчику гораздо больше возможностей в плане контроля аппаратного обеспечения, например, управления памятью и использованием процессора. Примерами компилируемых языков являются C, C++, Erlang, Haskell и более современные языки, такие как Rust и Go.
Проблемы компилируемых языков, в общем-то, очевидны. Для запуска программы, написаной на компилируемом языке, её сперва нужно скомпилировать. Это не только лишний шаг, но и значительное усложнение отладки, ведь для тестирования любого изменения программу нужно компилировать заново. Кроме того, компилируемые языки являются платформо-зависимыми, поскольку машинный код зависит от машины, на которой компилируется и исполняется программа.
Интерпретируемые языки
В отличие от компилируемых языков, интерпретируемым для исполнения программы не нужен машинный код; вместо этого программу построчно исполнят интерпретаторы. Раньше процесс интерпретации занимал очень много времени, но с приходом таких технологий, как JIT-компиляция, разрыв между компилируемыми и интерпретируемыми языками сокращается. Примерами интерпретируемых языков являются PHP, Perl, Ruby и Python. Вот некоторые из концептов, которые стали проще благодаря интерпретируемым языкам:
Основным недостатком интерпретируемых языком является их невысокая скорость исполнения. Тем не менее, JIT-компиляция позволяет ускорить процесс благодаря переводу часто используемых последовательностей инструкции в машинный код.
Бонус: байткод-языки
В байткод-языке сперва происходит компиляция программы из человекочитаемого языка в байткод. Байткод — это набор инструкций, созданный для эффективного исполнения интерпретатором и состоящий из компактных числовых кодов, констант и ссылок на память. С этого момента байткод передаётся в виртуальную машину, которая затем интерпретирует код также, как и обычный интерпретатор.
При компиляции кода в байткод происходит задержка, но дальнейшая скорость исполнения значительно возрастает в силу оптимизации байткода. Кроме того, байткод-языки являются платформо-независимыми, превосходя при этом по скорости интерпретируемые. Для них также доступна JIT-компиляция.
Заключение
Многие языки в наши дни имеют как компилируемые, так и интерпретируемые реализации, сводя разницу между ними на нет. У каждого вида исполнения кода есть преимущества и недостатки.
Вкратце, компилируемые языки являются самыми эффективными, поскольку они исполняются как машинный код и позволяют использовать аппаратное обеспечение системы. Однако это вводит дополнительные ограничение на написание кода и делает его платформо-зависимым. Интерпретируемые же языки не зависят от платформы и позволяют использовать такие техники динамического программирования, как метапрограммирование. Тем не менее, в скорости исполнения они значительно уступают компилируемым языкам.
Байткод-языки, в свою очередь, пытаются использовать сильные стороны обоих видов языков, и у них это неплохо получается.