Компилятор

К началу 1950-х годов программы писали непосредственно в машинных кодах, а типовые вычисления переписывали из тетрадей вручную. Грейс Хоппер предложила поручить эту работу самой машине: её система А-0 выбирала нужные подпрограммы из библиотеки по символьным меткам и собирала из них готовую программу^[5]. Хоппер назвала такую обработку «автоматическим программированием» и подчёркивала, что перевод освобождает программиста от знания команд конкретной машины^[5]. Вслед за А-0 появились развитые версии её системы для машин UNIVAC, а сама Хоппер настаивала, что вычислительная машина должна понимать запись, близкую к обычной математике^[9].

Следующий шаг сделал коллектив под руководством Джона Бэкуса, создавший к 1957 году компилятор Фортрана для машины IBM 704. Заказчики сомневались, что автоматический перевод окупится: ручное кодирование считалось неизбежным злом. Проект доказал обратное: скомпилированные программы работали достаточно эффективно, а затраты на разработку компилятора быстро окупились^[10]. После этого языки высокого уровня стали основным способом записи программ, а компилятор — обязательной частью вычислительной платформы^[9].

Стихийные приёмы перевода быстро упёрлись в сложность языков. Отчёт об АЛГОЛЕ 60, подготовленный группой Питера Наура, закрепил описание синтаксиса языка в форме Бэкуса — Наура — формальной грамматике, порождающей правильные программы^[11]. Ещё в 1956 году Ноам Хомский описал иерархию формальных грамматик, задавшую теоретический каркас разбора языков^[12]. С этого момента построение компилятора превратилось из ремесла в инженерную дисциплину с проверяемой теорией: грамматика служит и определением языка, и схемой работы синтаксического анализатора^[1].

Инструменты подхватили теорию почти сразу: генераторы синтаксических анализаторов строят программу-анализатор по формальному описанию грамматики, поэтому новая версия языка подхватывается перекомпиляцией описания, а не переписыванием анализатора вручную^[1]. Та же участь постигла и лексику: описания токенов в терминах регулярных выражений превращаются генератором в таблицы конечных автоматов^[2]. Благодаря этому значительная часть компилятора собирается из готовых компонентов, а усилия разработчиков сосредоточены на семантике языка и качестве генерируемого кода^[13].

В 1960—1970-е годы центр тяжести сместился к качеству порождаемого кода. Коллектив Фрэнсис Аллен в компании IBM развил теорию анализа потоков данных, на которой держатся современные оптимизирующие компиляторы; сама Аллен стала первой женщиной — лауреатом Премии Тьюринга в 2006 году^[14]. В СССР под руководством Андрея Ершова создавался Альфа-транслятор для М-20, ориентированный на получение эффективного объектного кода. При переходе к БЭСМ-6 был разработан кросс-транслятор Алгибр^[15].

Идея единого компилятора для разных процессоров породила многоязычные и переносимые системы. В 1984 году Дойч и Шиффман показали, что даже динамический язык вроде Smalltalk-80 можно ускорить переводом «горячих» методов в машинный код прямо во время работы программы, — так оформилась динамическая компиляция^[16]. Первый бета-выпуск свободного компилятора GCC (0.9) вышел 22 марта 1987 года, а версия 1.0 — 23 мая 1987 года, закрепив за GNU роль центра открытых средств разработки^[17]. Инфраструктура LLVM, представленная Латтнером и Адве в 2004 году, довела переносимость до логического конца: единый промежуточный код отделил языки от процессоров, и под него стали строиться новые языки и среды^[18].

Лексический анализатор читает текст программы слева направо и разрезает его на минимальные значимые единицы — токены: имена, ключевые слова, числовые литералы, знаки операций. Обработка пробелов и переводов строк зависит от языка. Например, в Python отступы и окончания логических строк участвуют в формировании токенов INDENT, DEDENT и NEWLINE^[19]. Сведения об идентификаторах используются при дальнейшем анализе имён и областей видимости.^[1] Работа лексера опирается на регулярные выражения и конечные автоматы: правила выделения токенов описываются регулярными выражениями, и по ним строится конечный автомат^[2]. Если очередной символ не образует допустимого токена, анализатор немедленно сообщает о лексической ошибке с указанием позиции^[13].

Синтаксический анализатор, или парсер, получает поток токенов и проверяет, образуют ли они правильную программу с точки зрения грамматики языка; результатом становится дерево разбора, отражающее вложенность конструкций^[1]. Выражение в правой части присваивания получает корень в знаке операции, а операнды становятся его потомками, поэтому порядок вычислений выводится из структуры дерева, хотя фактический порядок вычисления операндов и побочных эффектов зависит от семантики конкретного языка^[13]. Практические анализаторы строятся по методам рекурсивного спуска либо табличных алгоритмов LR-семейства; выбор метода определяет класс допустимых грамматик и удобство сообщений об ошибках^[13]. Обнаружив недопустимую конструкцию, парсер локализует её и продолжает разбор, чтобы собрать программисту несколько замечаний за один прогон^[2].

Правильная по грамматике программа может быть бессмысленной: переменная не объявлена, типы несовместимы, функция вызвана с неверным числом аргументов. Эти проверки выполняет семантический анализатор, который обходит дерево разбора, сверяется с таблицей символов и дополняет узлы сведениями о типах^[1]. Проверенная программа переводится в промежуточное представление — внутренний язык компилятора, достаточно низкий, чтобы выражать команды процессоров, и достаточно высокий, чтобы сохранять структуру программы^[4]. Классической формой служит трёхадресный код, в котором каждая операция имеет не более одного результата; распространены и представление в виде ациклического графа, и форма единственного присваивания, облегчающая оптимизацию^[20]. Именно единое промежуточное представление позволило связать в одном конвейере десятки языков и десятки целевых архитектур — так устроены GCC и LLVM^[18].

Практический компилятор обязан работать с ошибочным текстом так, чтобы за один прогон сообщить о как можно большем числе проблем. Для этого используется восстановление после ошибки: анализатор локализует повреждённую конструкцию, отбрасывает её часть и продолжает разбор со следующего пункта, не позволяя одной ошибке обрушить всю трансляцию^[1]. Простейшая стратегия — панический режим, при котором входные символы пропускаются до синхронизирующего ключевого слова или знака; языки со структурными разделителями позволяют восстанавливаться точнее^[13].

Качество диагностик определяет удобство языка не меньше, чем скорость готового кода: сообщение должно указывать позицию ошибки, предполагаемую причину и место связанного объявления^[2]. Особую сложность составляют каскадные ошибки, когда одна неточность порождает целую серию вторичных сообщений, исчезающих после первого исправления^[2]. Поэтому типовые ситуации — пропущенная точка с запятой, несовпадение числа аргументов, несовместимость типов при присваивании — стараются описывать в терминах исходной программы, а не внутреннего представления компилятора^[1].

Оптимизацией называют безопасные преобразования программы, сохраняющие её видимый результат, но сокращающие время работы или размер кода^[20]. Локальные преобразования действуют внутри линейных участков: свёртка констант подставляет значения известных выражений, понижение силы операций заменяет умножение сдвигами, избыточные пересылки удаляются^[4]. Внутрипроцедурные преобразования анализируют граф потока управления всей функции: они удаляют вычисления, результат которых не используется, разворачивают короткие циклы и переносят инвариантные вычисления за их границы^[20]. Межпроцедурный анализ охватывает программу целиком и позволяет встраивать тела функций вместо вызовов, открывая дальнейшие оптимизации на стыке процедур^[4].

Задняя часть компилятора превращает оптимизированное представление в команды конкретного процессора. Выбор инструкций подбирает для каждой операции эквивалентные машинные команды, сопоставляя их стоимость; планирование переупорядочивает команды, заполняя задержки конвейера^[4]. Распределение регистров назначает переменные ограниченному набору регистров процессора; классическое решение — раскраска графа несовместимости, где цвета соответствуют регистрам^[20]. Не уместившиеся значения вытесняются в память, и качество этого шага заметно влияет на скорость готового кода^[4]. Компиляторы применяются и за пределами обычной трансляции: например, система SWIFT вставляет в код избыточные вычисления и проверки для обнаружения и маскировки аппаратных сбоев в суперкомпьютерных программах^[21].

Программист управляет глубиной преобразований через уровни оптимизации: сборка без оптимизации обычно проходит быстрее и может упрощать отладку, а высшие уровни включают более сложные проходы анализа и могут заметно удлинять трансляцию^[22]. Уровень подбирают по назначению сборки: библиотеки могут собирать с контролем размера кода, вычислительно ёмкие программы — с более агрессивной оптимизацией^[22]. Отдельные ключи отключают преобразования, способные изменить наблюдаемое поведение программы: например, в GCC флаг -fwrapv задаёт циклическое переполнение знаковых операций, что требует явного указания, если код полагается на такое поведение^[20].

Стоимость проходов вынуждает выстраивать их порядок: дешёвые локальные преобразования выполняются на каждом уровне, а дорогие формы анализа включаются только по явному запросу^[4]. Прирост от высших уровней насыщается: часть преобразований дублирует друг друга, а последние проценты скорости достигаются машинно-зависимой настройкой под конкретный процессор^[20].

Конкретная стратегия зависит от среды исполнения. Например, CPython использует собственный байткод, формат которого не гарантированно совместим между версиями и реализациями.^[23] В движке JavaScript V8 применяется интерпретатор Ignition, работающий с байткодом; интерпретация может сочетаться с компиляцией в машинный код^[24]. Такая динамическая компиляция опирается на предположения, накопленные при наблюдении за программой: если типы значения изменились, скомпилированный код отбрасывается и исполнение возвращается к интерпретатору^[7]. Приём восходит к системе Smalltalk-80, где перевод методов в машинный код на ходу ускорил исполнение в десятки раз^[16]. Современные виртуальные машины JavaScript компилируют один и тот же код несколькими уровнями оптимизации, постепенно повышая качество там, где это окупается^[25].

Предварительная компиляция переносит перевод кода на этап до выполнения; динамическая компиляция выполняет его во время работы программы.^[3] Интерпретатор может исполнять заранее полученное промежуточное представление, например байткод CPython, поэтому повторный разбор исходного текста при каждом выполнении не обязателен^[23].

Никлаус Вирт отмечал, что сам язык можно проектировать так, чтобы компиляция выполнялась за один проход и была быстрой даже на скромной машине^[26].

Среды исполнения используют разные комбинации механизмов. В типичном JIT-сценарии .NET код CIL компилируется в машинный при вызове метода; обязательный предварительный этап интерпретации для этого не требуется^[27]. Учебные системы идут по пути упрощения: транслятор проекта РуСи переводит программу на Си в коды учебной виртуальной машины, что позволяет студентам работать с единым и понятным исполнением на разных платформах^[28]. Способ поставки программы сам по себе не определяет стратегию её исполнения: среда может сочетать интерпретацию и компиляцию.^[3][23]

Кен Томпсон показал, что компилятор можно научить внедрять закладку: заражённый транслятор добавляет скрытый вход в компилируемые программы и заодно копирует сам себя в свои новые сборки, так что закладка переживает замену исходного текста^[8]. Обнаружить такую модификацию чтением исходников невозможно — нужен контроль над всем конвейером сборки. Пример практической атаки показал вирус XcodeGhost в сентябре 2015 года: разработчики приложений для iOS собрали свои программы заражённой копией среды разработки, и вредоносный код попал в ряд приложений официального магазина^[29].

Воспроизводимой называют сборку, при которой одинаковые исходный код, окружение и инструкции позволяют независимо получить побитово совпадающие артефакты^[30]. Такая воспроизводимость сама по себе не доказывает отсутствие вредоносного кода в исходниках или используемом компиляторе.

Дэвид А. Уилер описал метод двойного разнообразного компилирования (DDC). Сначала доверенным компилятором компилируют исходный код компилятора-родителя, затем полученным компилятором — исходный код проверяемого компилятора. При выполнении предпосылок метода побитовое совпадение результата с проверяемым исполняемым файлом подтверждает соответствие этого файла исходному коду^[31]. Движение воспроизводимых сборок переносит ту же идею на промышленные дистрибутивы: пакет собирается в описанной среде, и любой может повторить процесс побитово, что делает скрытые вставки уязвимыми к проверке^[32]. Воспроизводимость уже стала частью практик крупных проектов и дистрибутивов, а её отсутствие фиксируется как дефект сборки^[33].

Те же механизмы трансформации, что ускоряют программу, пригодны и для её защиты. Колберг и Торборсон формализовали обфускацию, водяные знаки и защиту от изменения как преобразования программы: первое затрудняет понимание кода, вторая помогает в установлении авторства, третья мешает несанкционированным модификациям^[34]. Силу защиты ограничивает сама природа компиляции: из работающей программы извлекается наблюдаемое поведение, поэтому обфускация лишь повышает стоимость анализа, не делая его невозможным^[34]. Обратная задача — восстановление исходного представления по машинному коду — решается декомпиляторами и применяется при анализе вредоносного кода и проверке унаследованного кода^[13].