Обзор предметной области

Компилятор – программа, способная получать на вход код программы, написанной на одном (исходном) языке и транслировать его в код эквивалентной программы на другом (целевом) языке. Важной ролью компилятора является обнаружение ошибок во время трансляции кода исходной программы и сообщение о них пользователю. Если целевая программа является машиночитаемой (исполняемой компьютером), она может быть вызвана пользователем для обработки входных и получения выходных данных. Этот подход используется в таких языках программирования, как Си, C++, Go и т. д.

Интерпретатор – это другой распространённый вид программ для обработки языков. Вместо создания целевой программы в процессе трансляции интерпретатор непосредственно выполняет операции, указанные в коде исходной программы, с использованием предоставленных пользователем входных данных. Интерпретируемыми языками являются, например, Python, PHP, JavaScript и т. д.

Стоит отметить, что целевая программа, предварительно транслированная с помощью компилятора, выполняется, как правило, быстрее в сравнении с исполнением при помощи интерпретатора. Интерпретатор, тем не менее, обычно может предоставить более подробную диагностику в случае возникновения ошибок, чем это способен сделать компилятор, поскольку интерпретация подразумевает выполнение программы «построчно» \cite{dragon_book}.

Компилятор, как правило, можно разделить на несколько подмодулей:

  • Сканер (scanner) обрабатывает исходный текст программы и группирует отдельные символы в конечные слова (токены). Это аналогично группировке символов в слова в естественном языке.

  • Парсер (parser) обрабатывает токены и объединяет их в выражения и инструкции, подобно тому как слова объединяются в предложения в естественном языке. Парсер руководствуется грамматикой, которая определяет формальные правила композиции для данного языка. Результатом работы парсера является абстрактное синтаксическое дерево (abstract syntax tree, AST), отражающее грамматическую структуру программы. AST также сохраняет информацию о местоположении каждой конструкции в исходном файле, что позволяет генерировать точные сообщения об ошибках при необходимости.

  • Процедуры семантического анализа (semantic routines) обходят AST и определяют дополнительную смысловую информацию (семантику) программы на основе правил языка и взаимосвязей между элементами программы. Например, можно установить, что выражение x + 1.0 имеет тип float, если из предыдущего объявления следует, что x имеет тип int, а затем применить правило языка, согласно которому сложение int и float дает результат типа float. После семантического анализа AST часто преобразуется в промежуточное представление (intermediate representation, IR), которое является упрощенной формой ассемблерного кода, пригодной для детального анализа.

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

  • Наконец, генератор кода (code generator) преобразует оптимизированное IR в конкретную программу на языке ассемблера. Обычно генератор кода выполняет распределение регистров (register allocation) для эффективного управления ограниченным количеством аппаратных регистров, а также выбирает и упорядочивает инструкции (instruction selection and sequencing) для формирования наиболее эффективного ассемблерного кода.

Вдобавок к описанному способу компиляции, называемому AOT-компиляцией (от англ. ahead-of-time – заранее), существует подход, называемый JIT-компиляцией (от англ. just-in-time – во время). В этом случае компиляция происходит непосредственно перед началом исполнения программы. Технология JIT основывается на компиляции байт-кода и динамической компиляции.

Для разработки компиляторов существуют различные инструменты, облегчающие создание компонентов компилятора, например:

  • генераторы синтаксических анализаторов – для создания синтаксических анализаторов на основе имеющегося описания грамматики языка в некоторой форме (например, GNU Bison, yacc);

  • генераторы лексических анализаторов – для создания лексических анализаторов на основе имеющегося описания лексем (слов) языка в виде набор регулярных выражений (например, flex);

  • генераторы генераторов кода – для создания генераторов кода на основе имеющегося набора правил трансляции каждой операции на некотором промежуточном языке в машинный код, распознаваемый целевой платформой (исполнителем) (например, LLVM);

  • инструменты для анализа графов потоков управления – для упрощения сбора информации о продвижении данных в множестве путей выполнения программы, может использоваться для оптимизации программы во время компиляции (например, aiSee);

  • наборы инструментов для создания компиляторов, предоставляющие вспомогательные средства для реализации различных компонентов (например, LLVM, Coco/R).

Назад