Что такое компилятор, интерпретатор, транслятор. Метод рекурсивного спуска ориентирован на те случаи, когда компилятор программируется на одном из языков высокого уровня, когда допускается использование рекурсивных процедур. Вместе с тем, все языки програ

Программам, как и людям, для перевода с одного языка на другой требуется переводчик, или транслятор.

Основные понятия

Программа представляет собой лингвистическое представление вычислений: 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-машин, вероятно, этого не произойдет.

РАЗДЕЛ 7. Трансляция, компиляция и интерпретация

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

Процесс создания программы предполагает несколько этапов. За этапом разработки проекта программы следует этап программирования. На этом этапе пишется программа. Программистами этот текст воспринимается легче двоичного кода, поскольку различные мнемонические сокращения и имена заключают дополнительную информацию.

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

Транслятор - программа или техническое средство, выполняющее трансляцию программы . Машинная программа, которая транслирует с одного языка на другой и, в частности, с одного языка программирования на другой. Обрабатывающая программа, предназначенная для преобразования исходной программы в объектный модуль.

Транслятор обычно выполняет также диагностику ошибок, формирует словари идентификаторов, выдаёт для печати тексты программы и т.д.

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

Язык, на котором представлена входная программа, называется исходным языком , а сама программа - исходным кодом . Выходной язык называется целевым языком или объектным кодом .

Виды трансляторов

Трансляторы подразделяют:

· Адресный . Функциональное устройство, преобразующее виртуальный адрес (англ. Virtual address ) в реальный адрес (англ. Memory address ).

· Диалоговый . Обеспечивает использование языка программирования в режиме разделения времени.

· Многопроходной . Формирует объектный модуль за несколько просмотров исходной программы.

· Обратный . То же, что детранслятор. См. также: декомпилятор, дизассемблер.

· Однопроходной . Формирует объектный модуль за один последовательный просмотр исходной программы.

· Оптимизирующий . Выполняет оптимизацию кода в создаваемом объектном модуле.

· Синтаксически-ориентированный (синтаксически-управляемый) . Получает на вход описание синтаксиса и семантики языка и текст на описанном языке, который и транслируется в соответствии с заданным описанием.

· Тестовый . Набор макрокоманд языка ассемблера, позволяющих задавать различные отладочные процедуры в программах, составленных на языке ассемблера.

Трансляторы реализуются в виде компиляторов или интерпретаторов . С точки зрения выполнения работы компилятор и интерпретатор существенно различаются.

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

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

Компиляция -трансляция программы, составленной на исходном языке, в объектный модуль. Осуществляется компилятором.

Компилировать - проводить трансляцию машинной программы с проблемно-ориентированного языка на машинно-ориентированный язык.

Компилятор читает всю программу целиком , делает ее перевод и создает законченный вариант программы на машинном языке, который затем и выполняется.

Интерпретатор (англ. interpreter - истолкователь, устный переводчик) переводит и выполняет программу строка за строкой . Интерпретатор берёт очередной оператор языка из текста программы, анализирует его структуру и затем сразу исполняет (обычно после анализа оператор транслируется в некоторое промежуточное представление или даже машинный код для более эффективного дальнейшего исполнения). Только после того как текущий оператор успешно выполнен, интерпретатор перейдёт к следующему. При этом если один и тот же оператор будет выполняться в программе многократно, интерпретатор будет выполнять его так как, как будто встретил впервые. Вследствие этого программы, в которых требуется осуществить большой объём вычислений, будут выполняться медленно. Кроме того, для выполнения программы на другом компьютере там тоже должен стоять интерпретатор – ведь без него текст является просто набором символов.

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

Различия между компиляцией и интерпретацией.

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

2. Откомпилированные программы работают быстрее, но интерпретируемые проще исправлять и изменять.

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

С другой стороны, Бейсик создавался как язык для начинающих программистов, для которых построчное выполнение программы имеет неоспоримые преимущества.

Практически все языки программирования низкого уровня и третьего поколения, вроде ассемблера, Си или Модулы-2, являются компилируемыми, а более высокоуровневые языки, вроде Python или SQL, - интерпретируемыми.

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

4. Трансляция и интерпретация - разные процессы: трансляция занимается переводом программ с одного языка на другой, а интерпретация отвечает за исполнение программ. Однако, поскольку целью трансляции как правило является подготовка программы к интерпретации, то эти процессы обычно рассматриваются вместе.

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

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

Процесс компиляции разделяется на несколько этапов:

1. Препроцессор. Исходная программа обрабатывается путём подстановки имеющихся макросов и заголовочных файлов.

2. Лексический и синтаксический анализ. Программа преобразовывается в цепочку лексем, а затем во внутреннее представление в виде дерева.

3. Глобальная оптимизация. Внутреннее представление программы неоднократно преобразовывается с целью сокращения размера и времени исполнения программы.

4. Генерация кода. Внутреннее представление преобразовывается в блоки команд процессора, которые преобразовываются в ассемблеровский текст или в объектный код.

5. Ассемблирование. Если генерируется ассемблерный текст, производится его ассемблирование с целью получения объектного кода.

6. Сборка. Сборщик соединяет несколько объектных файлов в исполняемый файл или библиотеку.

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

На этапе ЛА обнаруживаются некоторые (простейшие) ошибки (недопустимые символы, неправильная запись чисел, идентификаторов и др.).

Рассмотрим более подробно стадию лексического анализа.

Основная задача лексического анализа - разбить входной текст, состоящий из последовательности одиночных символов, на последовательность слов, или лексем, т.е. выделить эти слова из непрерывной последовательности символов. Все символы входной последовательности с этой точки зрения разделяются на символы, принадлежащие каким-либо лексемам, и символы, разделяющие лексемы (разделители). В некоторых случаях между лексемами может и не быть разделителей. С другой стороны, в некоторых языках лексемы могут содержать незначащие символы (например, символ пробела в Фортране). В Си разделительное значение символов-разделителей может блокироваться («\» в конце строки внутри «...»).

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

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

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

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

Лексический анализатор может быть как самостоятельной фазой трансляции, так и подпрограммой, работающей по принципу «дай лексему». В первом случае (рис. 3.1, а) выходом анализатора является файл лексем, во втором (рис. 3.1, б) лексема выдается при каждом обращении к анализатору (при этом, как правило, признак класса лексемы возвращается как результат функции «лексический анализатор», а значение лексемы передается через глобальную переменную). С точки зрения обработки значений лексем, анализатор может либо просто выдавать значение каждой лексемы, и в этом случае построение таблиц объектов (идентификаторов, строк, чисел и т.д.) переносится на более поздние фазы, либо он может самостоятельно строить таблицы объектов. В этом случае в качестве значения лексемы выдается указатель на вход в соответствующую таблицу.

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

Основная задача синтаксического анализа - разбор структуры программы. Как правило, под структурой понимается дерево, соответствующее разбору в контекстно-свободной грамматике языка. В настоящее время чаще всего используется либо LL(1) - анализ (и его вариант - рекурсивный спуск), либо LR(1)-анализ и его варианты (LR(0), SLR(1), LALR(1) и другие). Рекурсивный спуск чаще используется при ручном программировании синтаксического анализатора, LR(1) - при использовании систем автоматизации построения синтаксических анализаторов.

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

На этапе контекстного анализа выявляются зависимости между частями программы, которые не могут быть описаны контекстно- свободным синтаксисом. Это в основном связи «описание- использование», в частности анализ типов объектов, анализ областей видимости, соответствие параметров, метки и другие. В процессе контекстного анализа строится таблица символов, которую можно рассматривать как таблицу имен, пополненную информацией об описаниях (свойствах) объектов.

Основным формализмом, использующимся при контекстном анализе, являются атрибутные грамматики. Результатом работы фазы контекстного анализа является атрибутированное дерево программы. Информация об объектах может быть как рассредоточена в самом дереве, так и сосредоточена в отдельных таблицах символов. В процессе контекстного анализа также могут быть обнаружены ошибки, связанные с неправильным использованием объектов.

Затем программа может быть переведена во внутреннее представление . Это делается для целей оптимизации и/или удобства генерации кода. Еще одной целью преобразования программы во внутреннее представление является желание иметь переносимый компилятор . Тогда только последняя фаза (генерация кода) является машинно-зависимой. В качестве внутреннего представления может использоваться префиксная или постфиксная запись, ориентированный граф, тройки, четверки и другие.

Фаз оптимизации может быть несколько . Оптимизации обычно делят на машинно-зависимые и машинно-независимые, локальные и глобальные. Часть машинно-зависимой оптимизации выполняется на фазе генерации кода. Глобальная оптимизация пытается принять во внимание структуру всей программы, локальная - только небольших ее фрагментов. Глобальная оптимизация основывается на глобальном потоковом анализе, который выполняется на графе программы и представляет по существу преобразование этого графа. При этом могут учитываться такие свойства программы, как межпроцедурный анализ, межмодульный анализ, анализ областей жизни переменных и т.д.

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

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

Транслятор обычно выполняет также диагностику ошибок, форирует словари идентификаторов, выдаёт для печати тексты программы и т. д.

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

Язык, на котором представлена входная программа, называется исходным языком , а сама программа - исходным кодом . Выходной язык называется целевым языком или объектным кодом .

Понятие трансляции относится не только к языкам программирования, но и к другим компьютерным языкам , вроде языков разметки , аналогичных HTML , и к естественным языкам, вроде английского или русского . Однако данная статья только о языках программирования, о естественных языках см.: Перевод .

Виды трансляторов

• Адресный . Функциональное устройство, преобразующее виртуальный адрес (Virtual address) в реальный адрес памяти (Memory address).
• Диалоговый . Обеспечивает использование языка программирования в режиме разделения времени .
• Многопроходной . Формирует объектный модуль за несколько просмотров исходной программы.
• Обратный . То же, что детранслятор . См. также: декомпилятор , дизассемблер .
• Однопроходной . Формирует объектный модуль за один последовательный просмотр исходной программы.
• Оптимизирующий . Выполняет оптимизацию кода в создаваемом объектном модуле.
• Синтаксически-ориентированный (синтаксически-управляемый) . Получает на вход описание синтаксиса и семантики языка и текст на описанном языке, который и транслируется в соответствии с заданным описанием.
• Тестовый . Набор макрокоманд языка ассемблера , позволяющих задавать различные отладочные процедуры в программах, составленных на языке ассемблера.

Реализации

Цель трансляции - преобразовать текст с одного языка на другой, который понятен адресату текста. В случае программ-трансляторов, адресатом является техническое устройство (процессор) или программа-интерпретатор .

Можно привести ряд других примеров, в которых архитектура разработанных серий вычислительных машин базировалась или сильно зависела от некоторой модели структуры программы. Так, серия GE/Honeywell Multics основывалась на семантической модели выполнения программ, написанных на языке ПЛ/1 . В Шаблон:Не переведено B5500, B6700 … B7800 прототипом послужила модель программы этапа выполнения, написанной на расширенном языке Алгол . …

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

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

В случае, если исходный язык является языком ассемблера (низкоуровневым языком, близким к машинному языку), то компилятор такого языка называется ассемблером .

Противоположный метод реализации - когда программа исполняется с помощью интерпретатора вообще без трансляции. Интерпретатор программно моделирует машину, цикл выборки-исполнения которой работает с командами на языках высокого уровня, а не с машинными командами. Такое программное моделирование создаёт виртуальную машину , реализующую язык. Этот подход называется чистой интерпретацией . Чистая интерпретация применяется как правило для языков с простой структурой (например, АПЛ или Лисп). Интерпретаторы командной строки обрабатывают команды в скриптах в UNIX или в пакетных файлах (.bat) в MS-DOS также как правило в режиме чистой интерпретации.

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

Существуют компромиссные между компиляцией и чистой интерпретацией варианты реализации языков программирования, когда интерпретатор перед исполнением программы транслирует её на промежуточный язык (например, в байт-код или p-код), более удобный для интерпретации (то есть речь идёт об интерпретаторе со встроенным транслятором). Такой метод называется смешанной реализацией . Примером смешанной реализации языка может служить Perl . Этот подход сочетает как достоинства компилятора и интерпретатора (бо́льшая скорость исполнения и удобство использования), так и недостатки (для трансляции и хранения программы на промежуточном языке требуются дополнительные ресурсы; для исполнения программы на целевой машине должен быть представлен интерпретатор). Также, как и в случае компилятора, смешанная реализация требует, чтобы перед исполнением исходный код не содержал ошибок (лексических, синтаксических и семантических).

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

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

Этот метод хорошо подходит для

Языки программирования могут быть разделены на компилируемые и интерпретируемые.

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

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

Кратко говоря, компилятор переводит исходный текст программы на машинный язык сразу и целиком, создавая при этом отдельную исполняемую программу, а интерпретатор выполняет исходный текст прямо во время исполнения программы.

Разделение на компилируемые и интерпретируемые языки является несколько условным. Так, для любого традиционно компилируемого языка, как, например, Паскаль, можно написать интерпретатор. Кроме того, большинство современных "чистых" интерпретаторов не исполняют конструкции языка непосредственно, а компилируют их в некоторое высокоуровневое промежуточное представление (например, с разыменованием переменных и раскрытием макросов).

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

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

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

Однако интерпретируемые программы выполняются заметно медленнее, чем компилируемые, кроме того, они не могут выполняться без дополнительной программы-интерпретатора.

Некоторые языки, например, Java и C#, находятся между компилируемыми и интерпретируемыми. А именно, программа компилируется не в машинный язык, а в машинно-независимый код низкого уровня, байт-код. Далее байт-код выполняется виртуальной машиной. Для выполнения байт-кода обычно используется интерпретация, хотя отдельные его части для ускорения работы программы могут быть транслированы в машинный код непосредственно во время выполнения программы по технологии компиляции "на лету" (Just-in-time compilation, JIT). Для Java байт-код исполняется виртуальной машиной Java (Java Virtual Machine, JVM), для C# - Common Language Runtime.

Подобный подход в некотором смысле позволяет использовать плюсы как интерпретаторов, так и компиляторов. Следует упомянуть также оригинальный язык Форт (Forth) имеющий и интерпретатор и компилятор.

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

Транслятор - обслуживающая программа, преобразующая исходную программу, предоставленную на входном языке программирования, в рабочую программу, представленную на объектном языке.

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

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

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

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

Интерпретатор - программа или устройство, осуществляющее пооператорную трансляцию и выполнение исходной программы. В отличие от компилятора, интерпретатор не порождает на выходе программу на машинном языке. Распознав команду исходного языка, он тут же выполняет ее. Как в компиляторах, так и в интерпретаторах используются одинаковые методы анализа исходного текста программы. Но интерпретатор позволяет начать обработку данных после написания даже одной команды. Это делает процесс разработки и отладки программ более гибким. Кроме того, отсутствие выходного машинного кода позволяет не "захламлять" внешние устройства дополнительными файлами, а сам интерпретатор можно достаточно легко адаптировать к любым машинным архитектурам, разработав его только один раз на широко распространенном языке программирования. Поэтому, интерпретируемые языки, типа Java Script, VB Script, получили широкое распространение. Недостатком интерпретаторов является низкая скорость выполнения программ. Обычно интерпретируемые программы выполняются в 50-100 раз медленнее программ, написанных в машинных кодах.

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

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

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

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

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

Макропроцессоры используются и с языками высокого уровня. Они увеличивают функциональные возможности таких языков как PL/1, C, C++. Особенно широко макропроцессоры применяются в C и C++, позволяя упростить написание программ. Макропроцессоры повышают эффективность программирования без изменения синтаксиса и семантики языка.

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

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

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

Любой транслятор выполняет следующие основные задачи:

• - анализирует транслируемую программу, в частности определяет, содержит ли она синтаксические ошибки;
• - генерирует выходную программу (ее часто называют объектной) на языке машинных команд;
• - распределяет память для объектной программы.1.1 Интерпретаторы

Одно, часто упоминаемое преимущество интерпретаторной реализации состоит в том, что она допускает "непосредственный режим". Непосредственный режим позволяет вам задавать компьютеру задачу вроде PRINT 3.14159*3/2.1 и возвращает вам ответ, как только вы нажмете клавишу ENTER (это позволяет использовать компьютер стоимостью 3000 долларов в качестве калькулятора стоимостью 10 долларов). Кроме того, интерпретаторы имеют специальные атрибуты, которые упрощают отладку. Можно, например, прервать обработку интерпретаторной программы, отобразить содержимое определенных переменных, бегло просмотреть программу, а затем продолжить исполнение.

Больше всего программистам нравится в интерпретаторах возможность получения быстрого ответа. Здесь нет необходимости в компилировании, так как интерпретатор всегда готов для вмешательства в вашу программу. Введите RUN и результат вашего самого последнего изменения оказывается на экране.

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

Слабо различимым недостатком интерпретаторов является то, что они имеют тенденцию отбивать охоту к хорошему стилю программирования. Поскольку комментарии и другие формализуемые детали занимают значительное место программной памяти, люди стремятся ими не пользоваться. Дьявол менее яростен, чем программист, работающий на интерпретаторном Бейсике, пытающийся получить программу в 120К в памяти емкостью 60К. но хуже всего то, что интерпретаторы тихоходны.

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

Рассмотрим программу: на интерпретаторном Бэйсике 10 FOR N=1 TO 1000 20 PRINT N,SQR(N) 30 NEXT N при первом переходе по этой программе Бейсик-Интерпретатор должен разгадать что означает строка 20:

• 1. преобразовать числовую переменную N в строку
• 2. послать строку на экран
• 3. переместить в следующую зону печати
• 4. вычислить квадратный корень из N
• 5. преобразовать результат в строку
• 6. послать строку на экран

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

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

Транслятор: основные понятия

Такая программа как транслятор представляет собой лингвистическое представление вычислений I ->P ->P (i). Интерпретатор представляет собой программу, на вход которой подается программа P с некоторыми входными данными X.Выполняет он P на X: I(P, x)=P(x).Существует единственный транслятор, который способен выполнять все возможные программы (которые можно представить в формальной системе). Это является очень значительным и глубоким открытием Тьюринга. Процессор представляет собой интерпретатор программ на машинном языке. Писать интерпретаторы для языков высокого уровня, как правило, слишком дорого, поэтому их транслируют в ту форму, которую легче интерпретировать. Некоторые виды трансляторов обладают очень странными именами. Программа транслирует программы на ассемблере в машинный язык. Компилятор позволяет транслировать с языка высокого уровня на язык более низкого уровня. Транслятор представляет собой программу, которая в качестве входных данных принимает программу на некотором языке S и после обработки выдает программу на языке T.Таким образом, они обе имеют ту же семантику: P->X->Q. Таким образом, для любого xP(x)=Q(x). Если транслировать всю программу в нечто интерпретируемое, то это называется компиляцией перед исполнением или компиляцией AOT. Компиляторы AOT могут использоваться последовательно. Последний из них очень часто является ассемблером. Так, рассмотрим пример: Исходный код ->Компилятор (транслятор) -> Ассемблерный код -> Ассемблер (транслятор) -> Машинный код -> ЦПУ (интерпретатор). Динамическая или оперативная компиляция осуществляется в том случае, если часть программы транслируется, когда исполняются другие скомпилированные ранее части. Трансляторы JIT запоминают то, что они уже выполнили ранее, чтобы снова и снова не повторять исходный код. Они даже способны выполнять адаптивную компиляцию и перекомпиляцию, которая основана на поведении среды выполнения программы. Многие языки дают возможность выполнять код во время трансляции, а также компилировать новый код во время выполнения программы.

Трансляция: этапы

Процесс трансляции состоит из этапов синтеза и анализа. Схематично этот процесс выглядит примерно следующим образом: Исходный код -> Анализатор -> Концептуальное представление -> Синтезатор (генератор) -> Целевой код. Обусловлено это следующими причинами:

— любой другой способ просто не подходит;

— перевод по словам просто не работает.

Можно использовать следующее инженерное решение: если необходимо написать трансляторы для M исходных языков и N целевых, потребуется написать только M+N простых программ (полукомпиляторов), а не MxN полных (комплексных) трансляторов. На практике, тем не менее, концептуальное представление довольно редко бывает выразительным и мощным, чтобы охватить все существующие целевые и исходные языки. Хотя некоторые пользователи смогли приблизиться к этому. Реальные компиляторы проходят через множество различных этапов. При создании собственного компилятора не нужно будет заново проводить всю тяжелую работу, которую программисты уже проделали при создании генераторов и представлений. Свой язык можно транслировать непосредственно в JavaScript или C и использовать для этой цели существующие компиляторы языка C и JavaScript движки для того, чтобы сделать все остальное. Можно также использовать существующие промежуточные представления и виртуальные машины.

Запись транслятора

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

1. Транслятор – это самокомпилятор, если исходный язык у него соответствует базисному.
2. Саморезидентным называется компилятор, у которого целевой язык равняется базисному.
3. Если целевой и базисный языки различные, то транслятор – это кросс-компилятор.

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

Масштабная технология

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

Проектирование компилятора. Возможные проблемы, возникающие при создании реального транслятора

Какие проблемы могут возникать с исходным языком? Легко ли его скомпилировать? Имеется ли для этого препроцессор? Каким образом обрабатываются типы? Какая группировка проходов компилятора используется – одно- или многоходовая? Также особого внимания заслуживает желаемая степень оптимизации. Быстрая и нечистая трансляция программы практически без оптимизации может быть нормальной. Чрезмерная оптимизация может тормозить компилятор, однако, во время выполнения лучший код может того стоить.

Степень обнаружения ошибок. Нужно ли, чтобы транслятор остановился уже на первой ошибке? Когда он должен остановиться? Стоит ли доверять компилятору процедуру исправления ошибок?

Необходимый набор инструментов

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

Что касается вида целевого кода для генерации, тут необходимо выбирать из чистого, дополненного или виртуального машинного кода. Можно также написать входную часть, которая создает популярные промежуточные представления, такие как LLVM, JVM, RTL. Можно также сделать трансляцию из исходного в исходный код на Java Script или C. Если говорить о формате целевого кода, тут здесь можно выбрать переносимый машинный код, машинный код образа памяти, язык ассемблера.

Перенацеливание

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

Компоненты компилятора

Перечислим главные функциональные компоненты транслятора, который генерирует машинный код, если выходной программой является программа, написанная на языке C или виртуальная машина:

— входная программа поступает в лексический анализатор, или по-другому сканер, который преобразует ее в поток токенов;

— синтаксический анализатор (парсер) строит из них абстрактное синтаксическое дерево;

— семантический анализатор раскладывает семантическую информацию и проверяет на предмет наличия ошибок узлы дерева;

— в результате строится семантический граф. Под этим термином понимают абстрактное синтаксическое дерево с установленными ссылками и дополнительными свойствами;

— генератор промежуточного кода строит граф потока (кортежи группируются в основные блоки);

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

— для связи базовых блоков в прямолинейный код с передачей управления используется генератор целевого кода. Он создает на ассемблере объектный файл с визуальными регистрами, возможно не слишком эффективными;

— для распределения памяти между виртуальными регистрами и выполнения планирования команд используется машинозависимый оптимизатор-компоновщик. Он также осуществляет преобразование программы, написанной на ассемблере, в настоящий ассемблер с применением конвейерной обработки.

— используются подсистемы обнаружения ошибок и менеджер таблиц символов;

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

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

— отсутствующие в алфавите символы;

— превышение количества знаков в строке или слове;

— не закрытый строковый литерал или знак;

— конец файла в комментарии.

Синтаксический анализ или парсинг применяется для преобразования последовательности токенов в абстрактное синтаксическое дерево. При этом каждый узел дерева сохраняется как объект с именованными полями. Многие из них сами являются узлами дерева. Циклы на этом этапе отсутствуют. При создании парсера нужно в первую очередь обращать внимание на уровень сложности грамматики (LRили LL) и выяснить, имеются ли какие-то правила снятия неоднозначности. Действительно некоторые языки требуют проведения семантического анализа. Ошибки, которые встречаются на данном этапе, называются синтаксическими.

Семантический анализ

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

— множественные объявления переменной в пределах области ее действия;

— нарушение правил доступности;

— наличие ссылок на необъявленное имя;

— чересчур большое или, наоборот, недостаточное число аргументов при вызове метода;

— несоответствие типов.

Генерация

Путем генерации промежуточного кода производится граф потока, который составлен из кортежей, сгруппированных в базовые блоки. После генерации кода получается реальный машинный код. На первом этапе в традиционных компиляторах для машин RISC на первом этапе создается ассемблер с бесконечным количеством виртуальных регистров. Вероятно, этого не произойдет для машин CISC.