Программам, как и людям, для перевода с одного языка на другой требуется переводчик, или транслятор.
Основные понятия
Программа представляет собой лингвистическое представление вычислений: i → P → P(i). Интерпретатор представляет собой программу, на вход которой подается программа Р и некоторые входные данные x. Он выполняет P на х: I(P, x) = P(x). Тот факт, что существует единственный транслятор, способный выполнять все возможные программы (которые можно представить в формальной системе), является очень глубоким и значительным открытием Тьюринга.
Процессор является интерпретатором программ на машинном языке. Как правило, слишком дорого писать интерпретаторы для языков высокого уровня, поэтому их транслируют в форму, которую интерпретировать легче.
Некоторые виды трансляторов имеют очень странные имена:
- Ассемблер транслирует программы на ассемблере в машинный язык.
- Компилятор транслирует с языка высокого уровня на язык более низкого.
Транслятор – это программа, которая принимает в качестве входных данных программу на некотором языке S и выдает программу на языке T таким образом, что обе они имеют ту же семантику: P → X → Q. То есть, ∀x. P(х) = Q(х).
Если транслировать всю программу в нечто интерпретируемое, то это называется компиляцией перед исполнением, или АОТ-компиляцией. АОТ-компиляторы могут использоваться последовательно, последний из которых часто является ассемблером, например:
Исходный код → Компилятор (транслятор) → Ассемблерный код → Ассемблер (транслятор) → Машинный код → ЦПУ (интерпретатор).
Оперативная или динамическая компиляция происходит, если часть программы транслируется, когда исполняются другие ранее скомпилированные части. JIT-трансляторы запоминают то, что они уже выполнили, чтобы не повторять исходный код снова и снова. Они способны даже производить адаптивную компиляцию и перекомпиляцию, основанную на поведении среды выполнения программы.
Многие языки позволяют выполнять код во время трансляции и компилировать новый код во время выполнения программы.
Этапы трансляции
Трансляция состоит из этапов анализа и синтеза:
Исходный код → Анализатор → Концептуальное представление → Генератор (синтезатор) → Целевой код.
Это обусловлено такими причинами:
- Любой другой способ не подходит. Пословный перевод просто не работает.
- Хорошее инженерное решение: если нужно написать трансляторы для M исходных языков и N целевых, потребуется написать только M + N простых программ (полукомпиляторов), а не M × N комплексных (полных трансляторов).
Тем не менее на практике концептуальное представление очень редко бывает достаточно выразительным и мощным, чтобы охватить все мыслимые исходные и целевые языки. Хотя некоторые и смогли к этому приблизиться.
Реальные компиляторы проходят через множество этапов. При создании собственного компилятора не нужно повторять всю тяжелую работу, которую люди уже проделали при создании представлений и генераторов. Можно транслировать свой язык прямо в JavaScript или C и воспользоваться существующими JavaScript-движками и компиляторами языка C, чтобы сделать все остальное. Также можно использовать существующие промежуточные представления и виртуальные машины.
Запись транслятора
Транслятор – это программа или техническое средство, в котором задействованы три языка: исходный, целевой и базисный. Их можно записать в Т-форме, расположив исходный слева, целевой справа и базисный ниже.
Существует три вида компиляторов:
- Транслятор – это самокомпилятор, если у него исходный язык соответствует базисному.
- Компилятор, у которого целевой язык равен базисному, называется саморезидентным.
- Транслятор – это кросс-компилятор, если у него целевой и базисный языки различные.
Почему это важно?
Даже если вы никогда не сделаете настоящий компилятор, хорошо знать о технологии его создания, потому что используемые для этого концепции применяются повсеместно, например в:
- форматировании текстов;
- языках запросов к базам данных;
- расширенных компьютерных архитектурах;
- обобщенных задачах оптимизации;
- графических интерфейсах;
- языках сценариев;
- контроллерах;
- виртуальных машинах;
- машинных переводах.
Кроме того, если нужно написать препроцессоры, сборщики, загрузчики, отладчики или профилировщики, необходимо пройти через те же этапы, что и при написании компилятора.
Также можно узнать, как лучше писать программы, так как создание транслятора для языка означает лучшее понимание его тонкостей и неясностей. Изучение общих принципов трансляции также позволяет стать хорошим дизайнером языка. Так ли это важно, насколько крут язык, если он не может быть реализован эффективно?
Всеобъемлющая технология
Технология компилятора охватывает множество различных областей информатики:
- формальную теорию языка: грамматику, парсинг, вычислимость;
- компьютерную архитектуру: наборы инструкций, RISC или CISC, конвейерную обработку, ядра, тактовые циклы и т.д.;
- концепции языков программирования: например, управление последовательностью выполнения, условное выполнение, итерации, рекурсии, функциональное разложение, модульность, синхронизацию, метапрограммирование, область видимости, константы, подтипы, шаблоны, тип вывода, прототипы, аннотации, потоки, монады, почтовые ящики, продолжения, групповые символы, регулярные выражения, транзакционную память, наследование, полиморфизм, режимы параметров и т. д.;
- абстрактные языки и виртуальные машины;
- алгоритмы и структуры данных: регулярные выражения, алгоритмы парсинга, графические алгоритмы, динамическое программирование, обучение;
- языки программирования: синтаксис, семантику (статическую и динамическую), поддержку парадигм (структурной, ООП, функциональной, логической, стековой, параллелизма, метапрограммирования);
- создание ПО (компиляторы, как правило, крупные и сложные): локализацию, кэширование, компонентизацию, API-интерфейсы, повторное использование, синхронизацию.
Проектирование компилятора
Некоторые проблемы, возникающие при разработке реального транслятора:
- Проблемы с исходным языком. Легко ли его скомпилировать? Есть ли препроцессор? Как обрабатываются типы? Имеются ли библиотеки?
- Группировка проходов компилятора: одно- или многоходовая?
- Степень желательной оптимизации. Быстрая и нечистая трансляция программы практически без оптимизации может быть нормальной. Чрезмерная оптимизация будет тормозить компилятор, но лучший код во время выполнения может того стоить.
- Требуемая степень обнаружения ошибок. Может ли транслятор просто остановиться на первой ошибке? Когда он должен остановиться? Доверить ли компилятору исправление ошибок?
- Наличие инструментов. Если исходный язык не является очень маленьким, сканер и генератор анализаторов являются обязательными. Также существуют генераторы генераторов кода, но они не так распространены.
- Вид целевого кода для генерации. Следует выбирать из чистого, дополненного или виртуального машинного кода. Или просто написать входную часть, создающую популярные промежуточные представления, такие как LLVM, RTL или JVM. Или сделать трансляцию от исходного в исходный код на C или JavaScript.
- Формат целевого кода. Можно выбрать язык ассемблера, переносимый машинный код, машинный код образа памяти.
- Перенацеливание. При множестве генераторов хорошо иметь общую входную часть. По этой же причине лучше иметь один генератор для многих входных частей.
Архитектура компилятора: компоненты
Это главные функциональные компоненты транслятора, генерирующего машинный код (если выходной программой является программа на С или виртуальная машина, то потребуется не так много этапов):
- Входная программа (поток знаков) поступает в сканер (лексический анализатор), который преобразует ее в поток токенов.
- Парсер (синтаксический анализатор) строит из них абстрактное синтаксическое дерево.
- Семантический анализатор раскладывает семантическую информацию и проверяет узлы дерева на ошибки. В результате строится семантический граф – абстрактное синтаксическое дерево с дополнительными свойствами и установленными ссылками.
- Генератор промежуточного кода строит граф потока (кортежи группируются в основные блоки).
- Машинонезависимый оптимизатор кода проводит как локальную (внутри базового блока), так и глобальную (по всем блокам) оптимизацию, в основном оставаясь в рамках подпрограмм. Сокращает избыточный код и упрощает вычисления. В результате получается модифицированный граф потока.
- Генератор целевого кода связывает базовые блоки в прямолинейный код с передачей управления, создавая объектный файл на ассемблере с виртуальными регистрами (возможно, неэффективными).
- Машинозависимый оптимизатор-компоновщик распределяет память между регистрами и производит планирование команд. Осуществляет преобразование программы на ассемблере в настоящий ассемблер с хорошим использованием конвейерной обработки.
Кроме того, используются подсистемы обнаружения ошибок и менеджер таблиц символов.
Лексический анализ (сканирование)
Сканер конвертирует поток знаков исходного кода в поток токенов, убирая пробелы, комментарии и расширяя макросы.
Сканеры часто встречаются с такими проблемами, как принимать или не принимать во внимание регистр, отступы, перевод строки и вложенные комментарии.
Ошибки, которые могут встретиться при сканировании, называются лексическими и включают:
- символы, отсутствующие в алфавите;
- превышение числа знаков в слове или строке;
- не закрытый знак или строковый литерал;
- конец файла в комментарии.
Синтаксический анализ (парсинг)
Парсер преобразует последовательность токенов в абстрактное синтаксическое дерево. Каждый узел дерева сохраняется как объект с именованными полями, многие из которых сами являются узлами дерева. На этом этапе циклы отсутствуют. При создании парсера необходимо обратить внимание на уровень сложности грамматики (LL или LR) и выяснить, есть ли какие-либо правила снятия неоднозначности. Некоторые языки действительно требуют проведения семантического анализа.
Ошибки, встречающиеся на этом этапе, называются синтаксическими. Например:
- k = 5 * (7 – y;
- j = /5;
- 56 = x * 4.
Семантический анализ
Во время проведения семантического анализа необходимо проверить правила допустимости и связать части синтаксического дерева (разрешая ссылки имен, вставляя операции для неявного приведения типов и т. д.) для формирования семантического графа.
Очевидно, что набор правил допустимости у разных языков различный. Если компилируются Java-подобные языки, трансляторы могут найти:
- множественные объявления переменной в пределах области ее действия;
- ссылки на переменную до ее объявления;
- ссылки на необъявленное имя;
- нарушение правил доступности;
- слишком большое или недостаточное количество аргументов при вызове метода;
- несоответствие типов.
Генерация
Генерация промежуточного кода производит граф потока, составленный из кортежей, сгруппированных в базовые блоки.
Генерация кода производит реальный машинный код. В традиционных компиляторах для RISC-машин на первом этапе создается ассемблер с бесконечным числом виртуальных регистров. Для CISC-машин, вероятно, этого не произойдет.
