Что позволяет осуществлять транслятор. Что такое транслятор, компилятор, интерпретатор? Общие особенности языков программирования и трансляторов
Каждый процессор имеет свою систему команд. Компьютер способен понять только последовательность команд, понятных процессору, — машинный код. Первоначально программы для компьютеров писались с использованием машинного кода. Программирование в машинном коде – трудоемкий процесс, в ходе которого трудно избежать ошибок. Упростить этот процесс можно, если автоматизировать работу, поручив часть ее самому компьютеру. Поэтому сегодня для записи программ используются языки программирования. Язык программирования — это формальный язык для записи алгоритмов в виде, допускающем их автоматическую подготовку к выполнению на компьютере. Для преобразования программы в машинный код служит специальное программное средство – транслятор .
Трансляторы делятся на две группы по их работе – компиляторы и интерпретаторы .
Интерпретатор преобразует команды исходного текста программы в машинные команды и немедленно их выполняет. Можно сказать, что программа выполняется по стокам исходного текста. При этом происходит проверка правильности написания строк программы с точки зрения правил языка. При обнаружении ошибок специальный отладчик сообщает об ошибке, исполнение программы останавливается. Такой режим очень удобен для программиста, потому что результаты труда сразу же видны в деле. Однако интерпретация программ – довольно медленный процесс. Он заметно усложняется, если программа состоит из нескольких модулей. Кроме того, для запуска созданной программы на конкретном компьютере необходимо, чтобы на нем была установлена программа-интерпретатор.
Компилятор просматривает текст программы (иногда несколько раз – такие компиляторы называют многопроходными) и создает последовательность данных, которая называется объектным кодом. Объектный код еще не является полным аналогом программы. Необходимо дополнительный этап, который называется редактированием связей (или компоновкой). На этом этапе происходит объединение объектного кода программы и объектного кода подпрограмм, взятых из внешних библиотек. Результатом этого этапа является так называемый исполнимый код – он представляет собой набор машинных команд, реализующих алгоритм, записанный в программе. Исполнимый код может запускаться автономно на любом компьютере подходящей платформы. Код, прошедший компиляцию, работает в десятки раз быстрее, чем его эквивалентная программа в режиме интерпретации Операцию компоновки кода выполняет отдельная программа, которая называется редактором связей или компоновщиком. В современных системах программирования компоновщик часто объединяют с компилятором, так что для программиста оба этапа сливаются в один. Двухступенчатый процесс облегчает создание больших и сложных программ.
И компиляторы, и интерпретаторы имеют свои достоинства. Граница между ними постепенно стираются. Некоторые системы разработки программ содержат в своем составе, как компилятор, так и интерпретатор для поддерживаемого языка программирования. В некоторых случаях используются смешанные технологии.
Уровни языков
Язык программирования содержит три основных компонента: алфавит, синтаксис и семантику. Эти компоненты определяют правила записи программ.
Алфавит языка – это набор символов, которые можно применять в инструкциях языка программирования. Другие символы допустимы только в особых случаях, например в строковых константах.
Синтаксис языка определяет правила построения операторов.
Семантика – это смысловое содержание операторов языка программирования. Семантические правила определяют действия, описываемые различными операторами, и, в итоге сущность всего алгоритма.
Языки программирования можно разделить на две группы – языки высокого уровня и языки низкого уровня (машинные).
К языкам низкого уровня относится язык Ассемблер, в котором программа пишется на уровне машинных кодов. Инструкция языка ассемблера описывает ровно одну машинную команду. И наоборот: каждой команде в системе команд процессора соответствует инструкция языка (мнемоника). По сравнению с машинным кодом язык ассемблер имеет ряд преимуществ, облегчающих труд программист:
- Символические мнемоники запоминаются легче, чем шестнадцатеричные коды команд.
- Для регистров и областей памяти также можно использовать символические имена.
- Нет необходимости работать с физическими адресами памяти.
- Числовые константы и строки представляются в программе в привычном виде.
Программировать на языке ассемблера намного проще, чем в машинном коде, но все рано сложно. Поэтому были созданы другие языки программирования, в которых каждая инструкция (оператор) языка преобразуется в группу машинных. Эти языки ориентируются не на систему команд процессора, а на способ мышления, присущий человеку. Языки удобные для людей, называют языками высокого уровня. Достоинства языков высокого уровня:
- Машинная независимость.
- Использование естественных обозначений.
- Эффективное представление этапов обработки данных средствами языка.
- Готовые библиотеки стандартных подпрограмм для выполнения часто встречающихся действий.
Все языки программирования высокого уровня делятся на процедурные, логические и объектно-ориентированные. Несмотря на различия между языками, все они позволяют написать программу любого назначения.
Каждый язык программирования имеет свое название. История этих названий восходит к моменту создания языков. Правила программ в некоторых языках неоднократно менялись, но названия языков остались без изменения.
Поколения языков
1 этап
Операционное программирование. (ЭВМ 1-го поколения с 1945-1959 год). ЭВМ того времени понимали только цифровые команды, и программы состояли из множества строк, состоящих из цифр, интерпретируемых центральным процессором. Например, команда 05 825 631 трактовалась как сложение двух чисел (код 05), записанных в ячейки с номерами 825 и 631. Производительность труда программистов того времени была очень невелика, так как вручную было необходимо распределить все переменные программы в оперативной памяти.
2 этап
Мало отличается от первого. Он связан с ЭВМ 2-го поколения. Появились языки программирования типа Ассемблер и автокод. Теперь команда сложения записывалась с использованием служебных слов – ADD (сложить) PR1, ZET, где ADD – код команды, PR1, ZET – имена ячеек. Перевод программы (трансляция), записанных таким образом в цифровое представление, а только такое понимает ЭВМ, осуществляется с помощью специальных программ, называемых ассемблерами. Технология работы программиста: программа собирается из мелких деталей, отдельных операций и имеет достаточно простую структуру, решаемые задачи в основном расчетные.
3 этап
Развиваются языки программирования высокого уровня. В них реализуются новые идеи: подпрограммы и раздельная компиляция (Фортран 2); блочная структура и типы данных (Алгол 60); описание данных и работа с файлами (Кобол); обработка списков и указателей (Лисп). В следующих версиях языков продолжается развитие: PL/1 (Фортран+Алгол+Кобол), Алгол 68 (приемник Алгол 60), Паскаль (развитие Алгол 60), Simula (классы абстрактные данные).
Возможности языков программирования обеспечивают поддержку нисходящей технологии конструирования программ. Суть нисходящего конструирования программ – разбиение большой задачи на подзадачи, которые могут рассматриваться отдельно.
Основные правила применения данной технологии:
- формализованное и строгое описание программистом входов функций и выходов всех модулей программы и системы;
- согласованная разработка структур данных и алгоритмов;
- ограничение на размер модулей.
Восходящая технология конструирования программ – решение складывается «из отдельных кирпичиков», из известных решений подзадач. Таким образом, данной технологией оговаривается определенный принцип декомпозиции и иерархическая структура программы. Важнейшей составляющей этой технологии является структурное программирование (языки программирования Паскаль, Модула–2). Пионером структурного программирования был Э. Дейкстра, который в 1965 году предположил, что оператор GOTO может быть исключен из языков программирования.
Характерные черты структурного стиля программирования:
- простота и ясность (программа легко читается и анализируется);
- использование только базовых конструкций;
- отсутствие сетевых структур в программе;
- отсутствие многоцелевых функциональных блоков;
- отсутствие неоправданно сложных арифметических и логических конструкций;
- расположение в строке программы не более одного оператора языка программирования;
- содержательность имен переменных.
При этом процесс нисходящей разработки программы может продолжаться до тех пор, пока не будет, достигнут уровень «атомарных» блоков, т.е. базовых конструкций.
К нисходящей технологии следует отнести и то, что называется модульным программированием. Достаточно независимые фрагменты задачи оформляются как модули. Создаются библиотеки модулей, определяется механизм включения модулей в разрабатываемую программу. Модуль должен иметь строго определенный интерфейс и скрытую часть, одну точку входа и одну точку выхода. Структурная технология предоставила в распоряжение разработчиков строгие, формализованные методы описания программ и принимаемых технических решений. При этом использовалась наглядная графическая техника (схемы, диаграммы). Программы имели последовательную структуру, идеи Э. Дейкстры были реализованы в полной мере, что определило новый этап в развитии технологии программирования.
4 этап
Связан с применением объектно-ориентированных языков 4-го поколения. В основе объектно-ориентированного программирования (ООП) лежит идея объединения в одной структуре данных и действий, которые производятся с этими данными. (В терминологии ООП такие действия называются методами). При таком подходе организация данных и программная реализация действий над ними оказываются гораздо сильнее связаны, чем при традиционном структурном программировании.
ООП базируется на трех основных понятиях:
- Инкапсуляция – комбинирование данных с процедурами и функциями, которые манипулируют этими данными. В результате получается новый тип данных – объект.
- Наследование – это возможность использования уже определенных объектов для построения иерархии объектов производных от них. Каждый из «наследников» наследует описание данных «прародителя» и доступ к методам их обработки.
- Полиморфизм – это возможность определения единого по имени действия (процедуры или функции), применимого одновременно ко всем объектам иерархии наследования, причем каждый объект иерархии может «заказывать» особенность реализации этого действия над «самим собой».
ООП может заметно упростить написание сложных программ, придать им гибкость. Одним из его главных преимуществ можно назвать возможность расширять область их применения, не переделывая программу, а лишь добавляя в нее новые уровни иерархии.
Первым языком с элементами ООП был язык Симула-67. В Турбо-Паскале, начиная с версии 5.5, появились средства ООП. Итогом развития Турбо-Паскаля в этом направлении стало создание фирмой Borland системы программирования Delphi (Делфи). Использование этой системы, в частности, даёт возможность легко и быстро программировать сложный графический интерфейс.
5 этап
ЭВМ будущего 5-го поколения называют машинами «искусственного интеллекта». Прототипы языков для этих машин были созданы много раньше их физического появления. Это языки Лисп и Пролог. Эти языки относятся к языкам логического программирования.
Язык Пролог разработан в 70-х годах во Франции. Его появление связано с первыми работами в области создания искусственного интеллекта (экспертных систем, программ-переводчиков, интеллектуальных игр и пр.). Базируется на логической модели знаний.
РАЗДЕЛ 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) - при использовании систем автоматизации построения синтаксических анализаторов.
Результатом синтаксического анализа является синтаксическое дерево со ссылками на таблицу имен. В процессе синтаксического анализа также обнаруживаются ошибки, связанные со структурой программы.
На этапе контекстного анализа выявляются зависимости между частями программы, которые не могут быть описаны контекстно- свободным синтаксисом. Это в основном связи «описание- использование», в частности анализ типов объектов, анализ областей видимости, соответствие параметров, метки и другие. В процессе контекстного анализа строится таблица символов, которую можно рассматривать как таблицу имен, пополненную информацией об описаниях (свойствах) объектов.
Основным формализмом, использующимся при контекстном анализе, являются атрибутные грамматики. Результатом работы фазы контекстного анализа является атрибутированное дерево программы. Информация об объектах может быть как рассредоточена в самом дереве, так и сосредоточена в отдельных таблицах символов. В процессе контекстного анализа также могут быть обнаружены ошибки, связанные с неправильным использованием объектов.
Затем программа может быть переведена во внутреннее представление . Это делается для целей оптимизации и/или удобства генерации кода. Еще одной целью преобразования программы во внутреннее представление является желание иметь переносимый компилятор . Тогда только последняя фаза (генерация кода) является машинно-зависимой. В качестве внутреннего представления может использоваться префиксная или постфиксная запись, ориентированный граф, тройки, четверки и другие.
Фаз оптимизации может быть несколько . Оптимизации обычно делят на машинно-зависимые и машинно-независимые, локальные и глобальные. Часть машинно-зависимой оптимизации выполняется на фазе генерации кода. Глобальная оптимизация пытается принять во внимание структуру всей программы, локальная - только небольших ее фрагментов. Глобальная оптимизация основывается на глобальном потоковом анализе, который выполняется на графе программы и представляет по существу преобразование этого графа. При этом могут учитываться такие свойства программы, как межпроцедурный анализ, межмодульный анализ, анализ областей жизни переменных и т.д.
Наконец, генерация кода - последняя фаза трансляции. Результатом ее является либо ассемблерный модуль, либо объектный (или загрузочный) модуль. В процессе генерации кода могут выполняться некоторые локальные оптимизации, такие как распределение регистров, выбор длинных или коротких переходов, учет стоимости команд при выборе конкретной последовательности команд. Для генерации кода разработаны различные методы, такие как таблицы решений, сопоставление образцов, включающее динамическое программирование, различные синтаксические методы.
Конечно, те или иные фазы транслятора могут либо отсутствовать совсем, либо объединяться. В простейшем случае однопроходного транслятора нет явной фазы генерации промежуточного представления и оптимизации, остальные фазы объединены в одну, причем нет и явно построенного синтаксического дерева.
Программам, как и людям, для перевода с одного языка на другой требуется переводчик, или транслятор.
Основные понятия
Программа представляет собой лингвистическое представление вычислений: 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-машин, вероятно, этого не произойдет.
4. Основные принципы построения трансляторов. Трансляторы, компиляторы и интерпретаторы – общая схема работы. Современные компиляторы и интерпретаторы.
Основные принципы построения трансляторов.
Трансляторы, компиляторы, интерпретаторы – общая схема работы.
Определение транслятора, компилятора, интерпретатора
Для начала дадим несколько определений - что же все-таки такое есть уже многократно упоминавшиеся трансляторы и компиляторы.
Формальное определение транслятора
Транслятор - это программа, которая переводит входную программу на исходном (входном) языке в эквивалентную ей выходную программу на результирующем (выходном) языке. В этом определении слово «программа» встречается три раза, и это не ошибка и не тавтология. В работе транслятора, действительно, участвуют всегда три программы.
Во-первых, сам транслятор является программой 1 - обычно он входит в состав системного программного обеспечения вычислительной системы. То есть транслятор - это часть программного обеспечения (ПО), он представляет собой набор машинных команд и данных и выполняется компьютером, как и все прочие программы в рамках операционной системы (ОС). Все составные части транслятора представляют собой фрагменты или модули программы со своими входными и выходными данными.
Во-вторых, исходными данными для работы транслятора служит текст входной программы - некоторая последовательность предложений входного языка программирования. Обычно это символьный файл, но этот файл должен содержать текст программы, удовлетворяющий синтаксическим и семантическим требованиям входного языка. Кроме того, этот файл несет в себе некоторый смысл, определяемый семантикой входного языка.
В-третьих, выходными данными транслятора является текст результирующей программы. Результирующая программа строится по синтаксическим правилам, заданным в выходном языке транслятора, а ее смысл определяется семантикой выходного языка. Важным требованием в определении транслятора является эквивалентность входной и выходной программ. Эквивалентность двух программ означает совпадение их смысла с точки зрения семантики входного языка (для исходной программы) и семантики выходного языка (для результирующей программы). Без выполнения этого требования сам транслятор теряет всякий практический смысл.
Итак, чтобы создать транслятор, необходимо прежде всего выбрать входной и выходной языки. С точки зрения преобразования предложений входного языка в эквивалентные им предложения выходного языка транслятор выступает как переводчик. Например, трансляция программы с языка С в язык ассемблера по сути ничем не отличается от перевода, скажем, с русского языка на английский, с той только разницей, что сложность языков несколько иная (почему не существует трансляторов с естественных языков - см. раздел «Классификация языков и грамматик», глава 9). Поэтому и само слово «транслятор» (английское: translator) означает «переводчик».
Результатом работы транслятора будет результирующая программа, но только в том случае, если текст исходной программы является правильным - не содержит ошибок с точки зрения синтаксиса и семантики входного языка. Если исходная программа неправильная (содержит хотя бы одну ошибку), то результатом работы транслятора будет сообщение об ошибке (как правило, с дополнительными пояснениями и указанием места ошибки в исходной программе). В этом смысле транслятор сродни переводчику, например, с английского, которому подсунули неверный текст.
Теоретически возможна реализация транслятора с помощью аппаратных средств. Автору встречались такого рода разработки, однако широкое практическое применение их не известно. В таком случае и все составные части транслятора могут быть реализованы в виде аппаратных средств и их фрагментов - вот тогда схема распознавателя может получить вполне практическое воплощение!
Определение компилятора.
Отличие компилятора от транслятора
Кроме понятия «транслятор» широко употребляется также близкое ему по смыслу понятие «компилятор».
Компилятор - это транслятор, который осуществляет перевод исходной программы в эквивалентную ей объектную программу на языке машинных команд или на языке ассемблера.
Таким образом, компилятор отличается от транслятора лишь тем, что его результирующая программа всегда должна быть написана на языке машинных кодов.или на языке ассемблера. Результирующая программа транслятора, в общем случае, может быть написана на любом языке - возможен, например, транслятор программ с языка Pascal на язык С. Соответственно, всякий компилятор является транслятором, но не наоборот - не всякий транслятор будет компилятором. Например, упомянутый выше транслятор с языка Pascal на С компилятором являться не будет 1 .
Само слово «компилятор» происходит от английского термина «compiler» («составитель», «компоновщик»). Видимо, термин обязан своему происхождению способности компиляторов составлять объектные программы на основе исходных программ.
Результирующая программа компилятора называется «объектной программой» или «объектным кодом». Файл, в который она записана, обычно называется «объектным файлом». Даже в том случае, когда результирующая программа порождается на языке машинных команд, между объектной программой (объектным файлом) и исполняемой программой (исполняемым файлом) есть существенная разница. Порожденная компилятором программа не может непосредственно выполняться на компьютере, так как она не привязана к конкретной области памяти, где должны располагаться ее код и данные (более подробно - см. раздел «Принципы функционирования систем программирования», глава 15) 2 .
Компиляторы, безусловно, самый распространенный вид трансляторов (многие считают их вообще единственным видом трансляторов, хотя это не так). Они имеют самое широкое практическое применение, которым обязаны широкому распространению всевозможных языков программирования. Далее всегда будем говорить о компиляторах, подразумевая, что выходная программа написана на
Естественно, трансляторы и компиляторы, как и все прочие программы, разрабатывает человек (люди) - обычно это группа разработчиков. В принципе они могли бы создавать его непосредственно на языке машинных команд, однако объем кода и данных современных компиляторов таков, что их создание на языке машинных команд практически невозможно в разумные сроки при разумных трудозатратах. Поэтому практически все современные компиляторы также создаются с помощью компиляторов (обычно в этой роли выступают предыдущие версии компиляторов той же фирмы-производителя). И в этом качестве компилятор является уже выходной программой для другого компилятора, которая ничем не лучше и не хуже всех прочих порождаемых выходных программ 2 .
Определение интерпретатора. Разница между интерпретаторами и трансляторами
Кроме схожих между собой понятий «транслятор» и «компилятор» существует принципиально отличное от них понятие интерпретатора.
Интерпретатор - это программа, которая воспринимает входную программу на исходном языке и выполняет ее.
В отличие от трансляторов интерпретаторы не порождают результирующую программу (и вообще какого-либо результирующего кода) - и в этом принципиальная разница между ними. Интерпретатор, так же как и транслятор, анализирует текст исходной программы. Однако он не порождает результирующей программы, а сразу же выполняет исходную в соответствии с ее смыслом, заданным семантикой входного языка. Таким образом, результатом работы интерпретатора будет результат, заданный смыслом исходной программы, в том случае, если эта программа правильная, или сообщение об ошибке, если исходная программа неверна.
Конечно, чтобы исполнить исходную программу, интерпретатор так или иначе должен преобразовать ее в язык машинных кодов, поскольку иначе выполнение программ на компьютере невозможно. Он и делает это, однако полученные машинные коды не являются доступными - их не видит пользователь интерпретатора. Эти машинные коды порождаются интерпретатором, исполняются и унич-
1 Следует особо упомянуть, что сейчас в современных системах программирования стали появляться компиляторы, в которых результирующая программа создается не на языке машинных команд и не на языке ассемблера, а на некотором промежуточном языке. Сам по себе этот промежуточный язык не может непосредственно исполняться на компьютере, а требует специального промежуточного интерпретатора для выполнения написанных на нем программ. Хотя в данном случае термин «транслятор» был бы, наверное, более правильным, в литературе употребляется понятие «компилятор», поскольку промежуточный язык является языком очень низкого уровня, будучи родственным машинным командам и языкам ассемблера.
Здесь возникает извечный вопрос «о курице и яйце». Конечно, в первом поколении самые первые компиляторы писались непосредственно на машинных командах, но потом, с появлением компиляторов, от этой практики отошли. Даже самые ответственные части компиляторов создаются, как минимум, с применением языка ассемблера - а он тоже обрабатывается компилятором. тожаются по мере надобности - так, как того требует конкретная реализа) интерпретатора. Пользователь же видит результат выполнения этих кодов -есть результат выполнения исходной программы (требование об эквивалент сти исходной программы и порожденных машинных кодов и в этом случае, (условно, должно выполняться).
Более подробно вопросы, связанные с реализацией интерпретаторов и их от чием от компиляторов, рассмотрены далее в соответствующем разделе.
Назначение трансляторов, компиляторов и интерпретаторов. Примеры реализации
Первые программы, которые создавались еще для ЭВМ первого поколения, сались непосредственно на языке машинных кодов. Это была поистине аде работа. Сразу стало ясно, что человек не должен и не может говорить на яз машинных команд, даже если он специалист по вычислительной технике. О; ко и все попытки научить компьютер говорить на языках людей успехов увенчались и вряд ли когда-либо увенчаются (на что есть определенные o6i тивные причины, рассмотренные в первой главе этого пособия).
С тех пор все развитие программного обеспечения компьютеров неразрывно i зано с возникновением и развитием компиляторов.
Первыми компиляторами были компиляторы с языков ассемблера или, как назывались, мнемокодов. Мнемокоды превратили «филькину грамоту» яз машинных команд в более-менее доступный пониманию специалиста язык ^ монических (преимущественно англоязычных) обозначений этих команд. (давать программы уже стало значительно проще, но исполнять сам мнемс (язык ассемблера) ни один компьютер неспособен, соответственно, возникла обходимость в создании компиляторов. Эти компиляторы элементарно про но они продолжают играть существенную роль в системах программировани сей день. Более подробно о языке ассемблера и компиляторах с него расска: далее в соответствующем разделе.
Следующим этапом стало создание языков высокого уровня. Языки высо] уровня (к ним относится большинство языков программирования) предста ют собой некоторое промежуточное звено между чисто формальными язык и языками естественного общения людей. От первых им досталась строгая с мализация синтаксических структуру предложений языка, от вторых - зн тельная часть словарного запаса, семантика основных конструкций и выражс (с элементами математических операций, пришедшими из алгебры).
Появление языков высокого уровня существенно упростило процесс програи рования, хотя и не свело его до «уровня домохозяйки», как самонадеянно п гали некоторые авторы на заре рождения языков программирования 1 . Снатаких языков были единицы, затем десятки, сейчас, наверное, их насчитывается более сотни. Процессу этому не видно конца. Тем не менее по-прежнему преобладают компьютеры традиционной, «неймановской», архитектуры, которые умеют понимать только машинные команды, поэтому вопрос о создании компиляторов продолжает быть актуальным.
Как только возникла массовая потребность в создании компиляторов, стала развиваться и специализированная теория. Со временем она нашла практическое приложение во множестве созданных компиляторов. Компиляторы создавались и продолжают создаваться не только для новых, но и для давно известных языков. Многие производители от известных, солидных фирм (таких, как Microsoft или Inprise) до мало кому знакомых коллективов авторов выпускают на рынок все новые и новые образцы компиляторов. Это обусловлено рядом причин, которые будут рассмотрены далее.
Наконец, с тех пор как большинство теоретических аспектов в области компиляторов получили свою практическую реализацию (а это, надо сказать, произошло довольно быстро, в конце 60-х годов), развитие компиляторов пошло по пути их дружественности человеку - пользователю, разработчику программ на языках высокого уровня. Логичным завершением этого процесса стало создание систем программирования - программных комплексов, объединяющих в себе кроме непосредственно компиляторов множество связанных с ними компонентов программного обеспечения. Появившись, системы программирования быстро завоевали рынок и ныне в массе своей преобладают на нем (фактически, обособленные компиляторы - это редкость среди современных программных средств). О том, что представляют собой и как организованы современные системы программирования, см. в главе «Современные системы программирования». Ныне компиляторы являются неотъемлемой частью любой вычислительной системы. Без их существования программирование любой прикладной задачи было бы затруднено, а то и просто невозможно. Да и программирование специализированных системных задач, как правило, ведется если не на языке высокого уровня (в этой роли в настоящее время чаще всего применяется язык С), то на языке ассемблера, следовательно, применяется соответствующий компилятор. Программирование непосредственно на языках машинных кодов происходит исключительно редко и только для решения очень узких вопросов. Несколько слов о примерах реализации компиляторов и интерпретаторов, а также о том, как они соотносятся с другими существующими программными средствами. Компиляторы, как будет показано далее, обычно несколько проще в реализации, чем интерпретаторы. По эффективности они также превосходят их - очевидно, что откомпилированный код будет исполняться всегда быстрее, чем происходит интерпретация аналогичной исходной программы. Кроме того, не каждый язык программирования допускает построение простого интерпретатора. Однако интерпретаторы имеют одно существенное преимущество - откомпилированный код всегда привязан к архитектуре вычислительной системы, на которую он ориентирован, а исходная программа - только к семантике языка программирования, которая гораздо легче поддается стандартизации. Этот аспект первоначально не принимали во внимание. Первыми компиляторами были компиляторы с мнемокодов. Их потомки - современные компиляторы с языков ассемблера - существую практически для всех известных вычислительных систем. Они предельно жестко ориентированы на архитектуру. Затем появились компиляторы с таких языков, как FORTRAN, ALGOL-68, PL/1. Они были ориентированы на большие ЭВМ с пакетной обработкой задач. Из вышеперечисленных только FORTRAN, пожалуй, продолжает использоваться по сей день, поскольку имеет огромное количество библиотек различного назначения . Многие языки, родившись, так и не получили широкого распространения - ADA, Modula, Simula известны лишь узкому кругу специалистов. В то же время на рынке программных систем доминируют компиляторы языков, которым не прочили светлого будущего. В первую очередь, сейчас это С и C++. Первый из них родился вместе с операционными системами типа UNIX, вместе с нею завоевал свое «место под солнцем», а затем перешел под ОС других типов. Второй удачно воплотил в себе пример реализации идей объектно-ориентированного программирования на хорошо зарекомендовавшей себя практической базе 1 . Еще можно упомянуть довольно распространенный Pascal, который неожиданно для многих вышел за рамки чисто учебного языка для университетской среды.
История интерпретаторов не столь богата (пока!). Как уже было сказано, изначально им не предавали существенного значения, поскольку почти по всем параметрам они уступают компиляторам. Из известных языков, предполагавших интерпретацию, можно упомянуть разве что Basic, хотя большинству сейчас известна его компилируемая реализация Visual Basic, сделанная фирмой Microsoft . Тем не менее сейчас ситуация несколько изменилась, поскольку вопрос о переносимости программ и их аппаратно-платформенной независимости приобретает все большую актуальность с развитием сети Интернет. Самый известный сейчас пример - это язык Java (сам по себе он сочетает компиляцию и интерпретацию), а также связанный с ним JavaScript. В конце концов, язык HTML, на котором зиждется протокол HTTP, давший толчок столь бурному развитию Всемирной сети, - это тоже интерпретируемый язык. По мнению автора, в области появления новых интерпретаторов всех еще ждут сюрпризы, и появились уже первые из них - например, язык С# («си-диез», но название везде идет как «Си шарп»), анонсируемый фирмой Microsoft.
Об истории языков программирования и современном состоянии рынка компиляторов можно говорить долго и много. Автор считает возможным ограничиться уже сказанным, поскольку это не является целью данного пособия. Желающие могут обратиться к литературе .
Этапы трансляции. Общая схема работы транслятора
На рис. 13.1 представлена общая схема работы компилятора. Из нее видно, что ъ целом процесс компиляции состоит из двух основных этапов - синтеза и анализа.
На этапе анализа выполняется распознавание текста исходной программы, создание и заполнение таблиц идентификаторов. Результатом его работы служит некое внутреннее представление программы, понятное компилятору.
На этапе синтеза на основании внутреннего представления программы и информации, содержащейся в таблице (таблицах) идентификаторов, порождается текст результирующей программы. Результатом этого этапа является объектный код.
Кроме того, в составе компилятора присутствует часть, ответственная за анализ и исправление ошибок, которая при наличии ошибки в тексте исходной программы должна максимально полно информировать пользователя о типе ошибки и месте ее возникновения. В лучшем случае компилятор может предложить пользователю вариант исправления ошибки.
Эти этапы, в свою Очередь, состоят из более мелких этапов, называемых фазами компиляции. Состав фаз компиляции приведен в самом общем виде, их конкретная реализация и процесс взаимодействия
Во-первых, он является распознавателем для языка исходной программы. То ее он должен получить на вход цепочку символов входного языка, проверить принадлежность языку и, более того, выявить правила, по которым эта цепоч была построена (поскольку сам ответ на вопрос о принадлежности «да» и. «нет» представляет мало интереса). Интересно, что генератором цепочек входи го языка выступает пользователь - автор входной программы.
Во-вторых, компилятор является генератором для языка результирующей пр граммы. Он должен построить на выходе цепочку выходного языка по опре; ленным правилам, предполагаемым языком машинных команд или языком i семблера. Распознавателем этой цепочки будет выступать уже вычислительн система, под которую создается результирующая программа.
Лексический анализ (сканер) - это часть компилятора, которая читает лите] программы на исходном языке и строит из них слова (лексемы) исходного яз ка. На вход лексического анализатора поступает текст исходной программ а выходная информация передаётся для дальнейшей обработки компилятор на этапе синтаксического разбора. С теоретической точки зрения лексическ анализатор не является обязательной, необходимой частью компилятора. Од1 ко существует причины, которые определяют его присутствие практически всех компиляторах. Более подробно см. раздел «Лексические анализаторы (а неры). Принципы построения сканеров».
Синтаксический разбор - это основная часть компилятора на этапе анализа. О выполняет выделение синтаксических конструкций в тексте исходной прогре мы, обработанном лексическим анализатором. На этой же фазе компиляц проверяется синтаксическая правильность программы. Синтаксический раз£ играет главную роль - роль распознавателя текста входного языка програмл рования (см. раздел «Синтаксические анализаторы. Синтаксически управл; мый перевод» этой главы).
Семантический анализ - это часть компилятора, проверяющая правильно* текста исходной программы с точки зрения семантики входного языка. Крс непосредственно проверки, семантический анализ должен выполнять преоб; зования текста, требуемые семантикой входного языка (такие, как добавлен функций неявного преобразования типов). В различных реализациях компи. торов семантический анализ может частично входить в фазу синтаксическ* разбора, частично - в фазу подготовки к генерации кода.
Подготовка к генерации кода - это фаза, на которой компилятором выполнят ся предварительные действия, непосредственно связанные с синтезом текста зультирующей программы, но еще не ведущие к порождению текста на вых ном языке. Обычно в эту фазу входят действия, связанные с идентификащ элементов языка, распределением памяти и т. п. (см. раздел «Семантическ анализ и подготовка к генерации кода», глава 14).
Генерация кода - это фаза, непосредственно связанная с порождением кома составляющих предложения выходного языка и в целом текст результируюи
Могут, конечно, различаться в зависимости от версии компилятора. Однако в том или ином виде все представленные фазы практически всегда присутствуют в каждом конкретном компиляторе .
Компилятор в целом с точки зрения теории формальных языков выступает в «двух ипостасях», выполняет две основные функции. программы. Это основная фаза на этапе синтеза результирующей программы. Кроме непосредственного порождения текста результирующей программы, генерация обычно включает в себя также оптимизацию - процесс, связанный с обработкой уже порожденного текста. Иногда оптимизацию выделяют в отдельную фазу компиляции, так как она оказывает существенное влияние на качество и эффективность результирующей программы (см. разделы «Генерация кода. Методы генерации кода» и « Оптимизация кода. Основные методы оптимизации», глава 14).
Таблицы идентификаторов (иногда - «таблицы символов») - это специальным образом организованные наборы данных, служащие для хранения информации об элементах исходной программы, которые затем используются для порождения текста результирующей программы. Таблица идентификаторов в конкретной реализации компилятора может быть одна, или же таких таблиц может быть несколько. Элементами исходной программы, информацию о которых нужно хранить в процессе компиляции, являются переменные, константы, функции и т. п. - конкретный состав набора элементов зависит от используемого входного языка программирования. Понятие «таблицы» вовсе не предполагает, что это хранилище данных должно быть организовано именно в виде таблиц или других массивов информации - возможные методы их организации подробно рассмотрены далее, в разделе «Таблицы идентификаторов. Организация таблиц идентификаторов».
Представленное на рис. 13.1 деление процесса компиляции на фазы служит скорее методическим целям и на практике может не соблюдаться столь строго. Далее в подразделах этого пособия рассматриваются различные варианты технической организации представленных фаз компиляции. При этом указано, как они могут быть связаны между собой. Здесь рассмотрим только общие аспекты такого рода взаимосвязи.
Во-первых, на фазе лексического анализа лексемы выделяются из текста входной программы постольку, поскольку они необходимы для следующей фазы синтаксического разбора. Во-вторых, как будет показано ниже, синтаксический разбор и генерация кода могут выполняться одновременно. Таким образом, эти три фазы компиляции могут работать комбинированно, а вместе с ними может выполняться и подготовка к генерации кода. Далее рассмотрены технические вопросы реализации основных фаз компиляции, которые тесно связаны с понятием прохода.
Понятие прохода. Многопроходные и однопроходные компиляторы
Как уже было сказано, процесс компиляции программ состоит из нескольких фаз. В реальных компиляторах состав этих фаз может несколько отличаться от рассмотренного выше - некоторые из них могут быть разбиты на составляющие, другие, напротив, объединены в одну фазу. Порядок выполнения фаз компиляции также может меняться в разных вариантах компиляторов. В одном случае компилятор просматривает текст исходной программы, сразу выполняет все фазы компиляции и получает результат - объектный код. В другом варианте он выполняет над исходным текстом только некоторые из фаз компиляции и получает не конечный результат, а набор некоторых промежуточных данных. Эти данные затем снова подвергаются обработке, причем этот процесс может повторяться несколько раз.
Реальные компиляторы, как правило, выполняют трансляцию текста исходной программы за несколько проходов.
Проход - это процесс последовательного чтения компилятором данных из внешней памяти, их обработки и помещения результата работы во внешнюю память. Чаще всего один проход включает в себя выполнение одной или нескольких фаз компиляции. Результатом промежуточных проходов является внутреннее представление исходной программы, результатом последнего прохода - результирующая объектная программа.
В качестве внешней памяти могут выступать любые носители информации - оперативная память компьютера, накопители на магнитных дисках, магнитных лентах и т. п. Современные компиляторы, как правило, стремятся максимально использовать для хранения данных оперативную память компьютера, и только при недостатке объема доступной памяти используются накопители на жестких магнитных дисках. Другие носители информации в современных компиляторах не используются из-за невысокой скорости обмена данными.
При выполнении каждого прохода компилятору доступна информация, полученная в результате всех предыдущих проходов. Как правило, он стремится использовать в первую очередь только информацию, полученную на проходе, непосредственно предшествовавшем текущему, но в принципе может обращаться и к данным от более ранних проходов вплоть до исходного текста программы. Информация, получаемая компилятором при выполнении проходов, недоступна пользователю. Она либо хранится в оперативной памяти, которая освобождается компилятором после завершения процесса трансляции, либо оформляется в виде временных файлов на диске, которые также уничтожаются после завершения работы компилятора. Поэтому человек, работающий с компилятором, может даже не знать, сколько проходов выполняет компилятор - он всегда видит только текст исходной программы и результирующую объектную программу. Но количество выполняемых проходов - это важная техническая характеристика компилятора, солидные фирмы - разработчики компиляторов обычно указывают ее в описании своего продукта.
Понятно, что разработчики стремятся максимально сократить количество проходов, выполняемых компиляторами. При этом увеличивается скорость работы компилятора, сокращается объем необходимой ему памяти. Однопроходный компилятор, получающий на вход исходную программу и сразу же порождающий результирующую объектную программу, - это идеальный вариант.
Однако сократить число проходов не всегда удается. Количество необходимых проходов определяется прежде всего грамматикой и семантическими правилами исходного языка. Чем сложнее грамматика языка и чем больше вариантов предполагают семантические правила - тем больше проходов будет выполнять компилятор (конечно, играет свою роль и квалификация разработчиков компилятора). Например, именно поэтому обычно компиляторы с языка Pascal работают быстрее, чем компиляторы с языка С - грамматика языка Pascal более проста, а семантические правила более жесткие. Однопроходные компиляторы - редкость, они возможны только для очень простых языков. Реальные компиляторы выполняют, как правило, от двух до пяти проходов. Таким образом, реальные компиляторы являются многопроходными. Наиболее распространены двух- и трехпроходные компиляторы, например: первый проход - лексический анализ, второй - синтаксический разбор и семантический анализ, третий - генерация и оптимизация кода (варианты исполнения, конечно, зависят от разработчика). В современных системах программирования нередко первый проход компилятора (лексический анализ кода) выполняется параллельно с редактированием кода исходной программы (такой вариант построения компиляторов рассмотрен далее в этой главе).
Интерпретаторы. Особенности построения интерпретаторов
Интерпретатор - это программа, которая воспринимает входную программу на исходном языке и выполняет ее. Как уже было сказано выше, основное отличие интерпретаторов от трансляторов и компиляторов заключается в том, что интерпретатор не порождает результирующую программу, а просто выполняет исходную программу.
Термин «интерпретатор» (interpreter), как и «транслятор», означает «переводчик». С точки зрения терминологии эти понятия схожи, но с точки зрения теории формальных языков и компиляции между ними большая принципиальная разница. Если понятия «транслятор» и «компилятор» почти неразличимы, то с понятием «интерпретатор» их путать никак нельзя.
Простейшим способом реализации интерпретатора можно было бы считать вариант, когда исходная программа сначала полностью транслируется в машинные команды, а затем сразу же выполняется. В такой реализации интерпретатор, по сути, мало бы чем отличался от компилятора с той лишь разницей, что результирующая программа в нем была бы недоступна пользователю. Недостатком такого интерпретатора было бы то, что пользователь должен был бы ждать компиляции всей исходной программы прежде, чем начнется ее выполнение. По сути, в таком интерпретаторе не было бы никакого особого смысла - он не давал бы никаких преимуществ по сравнению с аналогичным компилятором 1 . Поэтому подавляющее большинство интерпретаторов действует так, что исполняет исходную программу последовательно, по мере ее поступления на вход интерпретатора. Тогда пользователю не надо ждать завершения компиляции всей исходной программы. Более того, он может последовательно вводить исходную программу и тут же наблюдать результат ее выполнения по мере ввода команд .
При таком порядке работы интерпретатора проявляется существенная особенность, которая отличает его от компилятора, - если интерпретатор исполняет команды по мере их поступления, то он не может выполнять оптимизацию исходной программы. Следовательно, фаза оптимизации в общей структуре интер- претатора будет отсутствовать. В остальном же она будет мало отличаться от структуры аналогичного компилятора. Следует только учесть, что на последнем этапе - генерации кода - машинные команды не записываются в объектный файл, а выполняются по мере их порождения.
Отсутствие шага оптимизации определяет еще одну особенность, характерную для многих интерпретаторов: в качестве внутреннего представления программы в них очень часто используется обратная польская запись (см. раздел «Генерация кода. Методы генерации кода», глава 14). Эта удобная форма представления операций обладает только одним существенным недостатком - она плохо поддается оптимизации. Но в интерпретаторах именно это как раз и не требуется.
Далеко не все языки программирования допускают построение интерпретаторов которые могли бы выполнять исходную программу по мере поступления команд Для этого язык должен допускать возможность существования компилятора выполняющего разбор исходной программы за один проход. Кроме того, язык не может интерпретироваться по мере поступления команд, если он допускает по явление обращений к функциям и структурам данных раньше их непосредствен ного описания. Поэтому данным методом не могут интерпретироваться такш языки, как С и Pascal.
Отсутствие шага оптимизации ведет к тому, что выполнение программы с помо щью интерпретатора является менее эффективным, чем с помощью аналогично го компилятора. Кроме того, при интерпретации исходная программа должна за ново разбираться всякий раз при ее выполнении, в то время как при компиляци] она разбирается только один раз, а после этого всегда используется объектны] файл. Таким образом, интерпретаторы всегда проигрывают компиляторам в про изводительности.
Преимуществом интерпретатора является независимость выполнения програм мы от архитектуры целевой вычислительной системы. В результате компиляци: получается объектный код, который всегда ориентирован на определенную архн тектуру. Для перехода на другую архитектуру целевой вычислительной систем] программу требуется откомпилировать заново. А для интерпретации программ] необходимо иметь только ее исходный текст и интерпретатор с соответствующе го языка.
Интерпретаторы долгое время значительно уступали в распространенности коь пиляторам. Как правило, интерпретаторы существовали для ограниченного крз га относительно простых языков программирования (таких, например, как Basic Высокопроизводительные профессиональные средства разработки программш го обеспечения строились на основе компиляторов.
Новый импульс развитию интерпретаторов придало распространение глобал] ных вычислительных сетей. Такие сети могут включать в свой состав ЭВМ ра: личной архитектуры, и тогда требование единообразного выполнения на каждс из них текста исходной программы становится определяющим. Поэтому с разв] тием глобальных сетей и распространением всемирной сети Интернет появило
В современных системах программирования существуют реализации программного обеспечения, сочетающие в себе и функции компилятора, и функции интерпретатора - в зависимости от требований пользователя исходная программа либо компилируется, либо исполняется (интерпретируется). Кроме того, некоторые современные языки программирования предполагают две стадии разработки: сначала исходная программа компилируется в промежуточный код (некоторый язык низкого уровня), а затем этот результат компиляции выполняется с помощью интерпретатора данного промежуточного языка. Более подробно варианты таких систем рассмотрены в главе «Современные системы программирования».
Широко распространенным примером интерпретируемого языка может служить HTML (Hypertext Markup Language) - язык описания гипертекста. На его основе в настоящее время функционирует практически вся структура сети Интернет. Другой пример - языки Java и JavaScript - сочетают в себе функции компиляции и интерпретации. Текст исходной программы компилируется в некоторый промежуточный двоичный код, не зависящий от архитектуры целевой вычислительной системы, этот код распространяется по сети и выполняется на принимающей стороне - интерпретируется.
Трансляторы с языка ассемблера («ассемблеры»)
Язык ассемблера - это язык низкого уровня. Структура и взаимосвязь цепочек этого языка близки к машинным командам целевой вычислительной системы, где должна выполняться результирующая программа. Применение языка ассемблера позволяет разработчику управлять ресурсами (процессором, оперативной памятью, внешними устройствами и т. п.) целевой вычислительной системы на уровне машинных команд. Каждая команда исходной программы на языке ассемблера в результате компиляции преобразуется в одну машинную команду.
Транслятор с языка ассемблера всегда, безусловно, будет и компилятором, поскольку языком результирующей программы являются машинные коды. Транслятор с языка ассемблера зачастую просто называют «ассемблер» или «программа ассемблера».
Реализация компиляторов с языка ассемблера
Язык ассемблера, как правило, содержит мнемонические коды машинных команд. Чаще всего используется англоязычная мнемоника команд, но существуют и другие варианты языков ассемблера (в том числе существуют и русскоязычные варианты). Именно поэтому язык ассемблера раньше носил названия «язык мнемокодов» (сейчас это название уже практически не употребляется). Все возможные команды в каждом языке ассемблера можно разбить на две группы: в первую группу входят обычные команды языка, которые в процессе трансляции преобразуются в машинные команды; вторую группу составляют специальные команды языка, которые в машинные команды не преобразуются, но используются компилятором для выполнения задач компиляции (таких, например, как задача распределения памяти). Синтаксис языка чрезвычайно прост. Команды исходной программы записыв ются обычно таким образом, чтобы на одной строке программы располагала одна команда. Каждая команда языка ассемблера, как правило, может быть рг делена на три составляющих, следующих последовательно одна за другой: по метки, код операции и поле операндов. Компилятор с языка ассемблера обыч] предусматривает и возможность наличия во входной программе комментарш которые отделяются от команд заданным разделителем .
Поле метки содержит идентификатор, представляющий собой метку, либо явл ется пустым. Каждый идентификатор метки может встречаться в программе языке ассемблера только один раз. Метка считается описанной там, где она у посредственно встретилась в программе (предварительное описание меток требуется). Метка может быть использована для передачи управления на поь ченную ею команду. Нередко метка отделяется от остальной части команды сг циальным разделителем (чаще всего - двоеточием «:»).
Код операции всегда представляет собой строго определенную мнемонику одн из возможных команд процессора или также строго определенную команду (мого компилятора. Код операции записывается алфавитными символами вхс ного языка. Чаще всего его длина составляет 3-4, реже - 5 или 6 символов.
Поле операндов либо является пустым, либо представляет собой список из одг го, двух, реже - трех операндов. Количество операндов строго определено и: висит от кода операции - каждая операция языка ассемблера предусматривг жестко заданное число своих операндов. Соответственно, каждому из этих вар антов соответствуют безадресные, одноадресные, двухадресные или трехадресн команды (большее число операндов практически не используется, в совреме ных ЭВМ даже трехадресные команды встречаются редко). В качестве опер; дов могут выступать идентификаторы или константы.
Особенностью языка ассемблера является то, что ряд идентификаторов в н выделяется специально для обозначения регистров процессора. Такие идет фикаторы, с одной стороны, не требуют предварительного описания, но, с Д1 гой, они не могут быть использованы пользователем для иных целей. Набор эт идентификаторов предопределен для каждого языка ассемблера.
Иногда язык ассемблера допускает использование в качестве операндов оп] деленных ограниченных сочетаний обозначений регистров, идентификатор и констант, которые объединены некоторыми знаками операций. Такие соче ния чаще всего используются для обозначения типов адресации, допустим в машинных командах целевой вычислительной системы.
Например, следующая последовательность команд
Представляет собой пример последовательности команд языка ассемблера п; цессоров семейства Intel 80x86. Здесь присутствуют команда описания наб(данных (db), метка (loops), коды операций (mov, dec и jnz). Операндами яв. ются идентификатор набора данных (datas), обозначения регистров процессе
(Ьх и сх), метка (loops) и константа (4). Составной операнд datas отображает косвенную адресацию набора данных datas по базовому регистру Ьх со смещением 4.
Подобный синтаксис языка без труда может быть описан с помощью регулярной грамматики. Поэтому построение распознавателя для языка ассемблера не представляет труда. По этой же причине в компиляторах с языка ассемблера лексический и синтаксический разбор, как правило, совмещены в один распознаватель.
Семантика языка ассемблера целиком и полностью определяется целевой вычислительной системой, на которую ориентирован данный язык. Семантика языка ассемблера определяет, какая машинная команда соответствует каждой команде языка ассемблера, а также то, какие операнды и в каком количестве допустимы для того или иного кода операции.
Поэтому семантический анализ в компиляторе с языка ассемблера также прост, как и синтаксический. Основной его задачей является проверить допустимость операндов для каждого кода операции, а также проверить, что все идентификаторы и метки, встречающиеся во входной программе, описаны и обозначающие их идентификаторы не совпадают с предопределенными идентификаторами, используемыми для обозначения кодов операции и регистров процессора.
Схемы синтаксического и семантического анализа в компиляторе с языка ассемблера могут быть, таким образом, реализованы на основе обычного конечного автомата. Именно эта особенность определила тот факт, что компиляторы с языка ассемблера исторически явились первыми компиляторами, созданными для ЭВМ. Существует также ряд других особенностей, которые присущи именно языкам ассемблера и упрощают построение компиляторов для них.
Во-первых, в компиляторах с языка ассемблера не выполняется дополнительная идентификация переменных - все переменные языка сохраняют имена, присвоенные им пользователем. За уникальность имен в исходной программе отвечает ее разработчик, семантика языка никаких дополнительных требований на этот процесс не накладывает. Во-вторых, в компиляторах с языка ассемблера предельно упрощено распределение памяти. Компилятор с языка ассемблера работает только со статической памятью. Если используется динамическая память, то для работы с нею нужно использовать соответствующую библиотеку или функции ОС, а за ее распределение отвечает разработчик исходной программы. За передачу параметров и организацию дисплея памяти процедур и функций также отвечает разработчик исходной программы. Он же должен позаботиться и об отделении данных от кода программы - компилятор с языка ассемблера, в отличие от компиляторов с языков высокого уровня, автоматически такого разделения не выполняет. И в-третьих, на этапе генерации кода в компиляторе с языка ассемблера не производится оптимизация, поскольку разработчик исходной программы сам отвечает за организацию вычислений, последовательность машинных команд и распределение регистров процессора.
За исключением этих особенностей компилятор с языка ассемблера является обычным компилятором, но значительно упрощенным по сравнению с любым компилятором с языка высокого уровня. Компиляторы с языка ассемблера реализуются чаще всего по двухпроходной схеме. На первом проходе компилятор выполняет разбор исходной программы, ее преобразование в машинные коды и одновременно заполняет таблицу идентификаторов. Но на первом проходе в машинных командах остаются незаполненными адреса тех операндов, которые размещаются в оперативной памяти. На втором проходе компилятор заполняет эти адреса и одновременно обнаруживает неописанные идентификаторы. Это связано с тем, что операнд может быть описан в программе после того, как он первый раз был использован. Тогда его адрес еще не известен на момент построения машинной команды, а поэтому требуется второй проход. Типичным примером такого операнда является метка, предусматривающая переход вперед по ходу последовательности команд.
Макроопределения и макрокоманды
Разработка программ на языке ассемблера - достаточно трудоемкий процесс, требующий зачастую простого повторения одних и тех же многократно встречающихся операций. Примером может служить последовательность команд, выполняемых каждый раз для организации стекового дисплея памяти при входе в процедуру или функцию.
Для облегчения труда разработчика были созданы так называемые макрокоманды.
Макрокоманда представляет собой текстовую подстановку, в ходе выполнения которой каждый идентификатор определенного вида заменяется на цепочку символов из некоторого хранилища данных. Процесс выполнения макрокоманды называется макрогенерацией, а цепочка символов, получаемая в результате выполнения макрокоманды, - макрорасширением.
Процесс выполнения макрокоманд заключается в последовательном просмотре текста исходной программы, обнаружении в нем определенных идентификаторов и их замене на соответствующие строки символов. Причем выполняется именно текстовая замена одной цепочки символов (идентификатора) на другую цепочку символов (строку). Такая замена называется макроподстановкой .
Для того чтобы указать, какие идентификаторы на какие строки необходимо заменять, служат макроопределения. Макроопределения присутствуют непосредственно в тексте исходной программы. Они выделяются специальными ключевыми словами либо разделителями, которые не могут встречаться нигде больше в тексте программы. В процессе обработки все макроопределения полностью исключаются из текста входной программы, а содержащаяся в них информация запоминается для обработки при выполнении макрокоманд.
Макроопределение может содержать параметры. Тогда каждая соответствующая ему макрокоманда должна при вызове содержать строку символов вместо каждого параметра. Эта строка подставляется при выполнении макрокоманды в каждое место, где в макроопределении встречается соответствующий параметр. В качестве параметра макрокоманды может оказаться другая макрокоманда, тогда она будет рекурсивно вызвана всякий раз, когда необходимо выполнить подстановку параметра. В принципе макрокоманды могут образовывать последовательность
Рекурсивных вызовов, аналогичную последовательности рекурсивных вызовов процедур и функций, но только вместо вычислений и передачи параметров они выполняют лишь текстовые подстановки 1 .
Макрокоманды и макроопределения обрабатываются специальным модулем, называемым макропроцессором или макрогенератором. Макрогенератор получает на вход текст исходной программы, содержащий макроопределения и макрокоманды, а на выходе его появляется текст макрорасширения исходной программы, не содержащий макроопределений и макрокоманд. Оба текста являются только текстами программы, никакая другая обработка не выполняется. Именно макрорасширение исходного текста поступает на вход компилятора.
Синтаксис макрокоманд и макроопределений не является строго заданным. Он может различаться в зависимости от реализации компилятора с языка ассемблера. Но сам принцип выполнения макроподстановок в тексте программы неизменен и не зависит от их синтаксиса.
Макрогенератор чаще всего не существует в виде отдельного программного модуля, а входит в состав компилятора с языка ассемблера. Макрорасширение исходной программы обычно недоступно ее разработчику. Более того, макроподстановки могут выполняться последовательно при разборе исходного текста на первом проходе компилятора вместе с разбором всего текста программы, и тогда макрорасширение исходной программы в целом может и вовсе не существовать как таковое.
Например, следующий текст определяет макрокоманду push_0 в языке ассемблера процессора типа Intel 8086:
Хог ах,ах ■ push ax endm
Семантика этой макрокоманды заключается в записи числа «0» в стек через регистр процессора ах. Тогда везде в тексте программы, где встретится макрокоманда
Она будет заменена в результате макроподстановки на последовательность команд:
Хог ах,ах ■ push ax
Это самый простой вариант макроопределения. Существует возможность создавать более сложные макроопределения с параметрами. Одно из таких макроопределений описано ниже:
Глубина такой рекурсии, как правило, сильно ограничена. На последовательность рекурсивных вызовов макрокоманд налагаются обычно существенно более жесткие ограничения, чем на последовательность рекурсивных вызовов процедур и функций, которая при стековой организации дисплея памяти ограничена только размером стека передачи параметров. add_abx macro xl,x2
Push ax
endm
Тогда в тексте программы макрокоманда также должна быть указана с соответствующим числом параметров. В данном примере макрокоманда
Add_abx4,8 будет в результате макроподстановки заменена на последовательность команд:
Add ах,4 add bx.4 add ex,8 push ax
Во многих компиляторах с языка ассемблера возможны еще более сложные конструкции, которые могут содержать локальные переменные и метки. Примером такой конструкции может служить макроопределение:
Loop_ax macro xl,x2,yl
Хог bx.bx loopax: add bx.yl
Здесь метка 1 oopax является локальной, определенной только внутри данного макроопределения. В этом случае уже не может быть выполнена простая текстовая подстановка макрокоманды в текст программы, поскольку если данную макрокоманду выполнить дважды, то это приведет к появлению в тексте программы двух одинаковых меток 1 оорах. В таком варианте макрогенератор должен использовать более сложные методы текстовых подстановок, аналогичные тем, что используются в компиляторах при идентификации лексических элементов входной программы, чтобы дать всем возможным локальным переменным и меткам макрокоманд уникальные имена в пределах всей программы. Макроопределения и макрокоманды нашли применение не только в языках ассемблера, но и во многих языках высокого уровня. Там их обрабатывает специальный модуль, называемый препроцессором языка (например, широко известен препроцессор языка С). Принцип обработки остается тем же самым, что и для программ на языке ассемблера - препроцессор выполняет текстовые подстановки непосредственно над строками самой исходной программы. В языках высокого уровня макроопределения должны быть отделены от текста самой исходной программы, чтобы препроцессор не мог спутать их с синтаксическими конструкциями входного языка. Для этого используются либо специальные символы и команды (команды препроцессора), которые никогда не могут встречаться в тексте исходной программы, либо макроопределения встречаются
Внутри незначащей части исходной программы - входят в состав комментариев (такая реализация существует, например, в компиляторе с языка Pascal, созданном фирмой Borland). Макрокоманды, напротив, могут встречаться в произвольном месте исходного текста программы, и синтаксически их вызов может не отличаться от вызова функций во входном языке.
Следует помнить, что, несмотря на схожесть синтаксиса вызова, макрокоманды принципиально отличаются от процедур и функций, поскольку не порождают результирующего кода, а представляют собой текстовую подстановку, выполняемую прямо в тексте исходной программы. Результат вызова функции и макрокоманды может из-за этого серьезно отличаться.
Рассмотрим пример на языке С. Если описана функция
Int fKint a) { return a + а: } и аналогичная ей макрокоманда
#define f2(a) ((a) + (а)) то результат их вызова не всегда будет одинаков.
Действительно, вызовы j=fl(i) и j=f2(i) (где i и j - некоторые целочисленные переменные) приведут к одному и тому же результату. Но вызовы j=fl(++i) и j=f2(++i) дадут разные значения переменной j. Дело в том, что поскольку f2 - это макроопределение, то во втором случае будет выполнена текстовая подстановка, которая приведет к последовательности операторов j=((++i) + (++i)). Видно, что в этой последовательности операция ++i будет выполнена дважды, в отличие от вызова функции fl(++i), где она выполняется только один раз.
Транслятор (англ. translator - переводчик) - это программа-переводчик. Она преобразует программу, написанную на одном из языков высокого уровня, в программу, состоящую из машинных команд. Транслятор обычно выполняет также диагностику ошибок, формирует словари идентификаторов, выдаёт для печати тексты программы и т. д. Язык, на котором представлена входная программа, называется исходным языком, а сама программа - исходным кодом. Выходной язык называется целевым языком или объектным кодом.
В общем случае понятие трансляции относится не только к языкам программирования, но и к другим языкам - как формальным компьютерным (вроде языков разметки типа HTML), так и естественным (русскому, английскому и т. п.).
Виды трансляторов
Диалоговый. Обеспечивает использование языка программирования в режиме разделения времени (англ.).
Синтаксически-ориентированный (синтаксически-управляемый). Получает на вход описание синтаксиса и семантики языка и текст на описанном языке, который и транслируется в соответствии с заданным описанием.
Однопроходной. Формирует объектный модуль за один последовательный просмотр исходной программы.
Многопроходной. Формирует объектный модуль за несколько просмотров исходной программы.
Оптимизирующий. Выполняет оптимизацию кода в создаваемом объектном модуле.
Тестовый. Набор макрокоманд языка ассемблера, позволяющих задавать различные отладочные процедуры в программах, составленных на языке ассемблера.
Обратный. Для программы в машинном коде выдаёт эквивалентную программу на каком-либо языке программирования (см.: дизассемблер, декомпилятор).
Трансляторы реализуются в виде компиляторов или интерпретаторов. С точки зрения выполнения работы компилятор и интерпретатор существенно различаются.
Компилятор (англ. compiler - составитель, собиратель) читает всю программу целиком, делает ее перевод и создает законченный вариант программы на машинном языке, который затем и выполняется. Входной информацией для компилятора (исходный код) является описание алгоритма или программа на проблемно-ориентированном языке, а на выходе компилятора - эквивалентное описание алгоритма на машинно-ориентированном языке (объектный код).
Виды компиляторов
Векторизующий. Транслирует исходный код в машинный код компьютеров, оснащённых векторным процессором.
Гибкий. Сконструирован по модульному принципу, управляется таблицами и запрограммирован на языке высокого уровня или реализован с помощью компилятора компиляторов.
Диалоговый. См.: диалоговый транслятор.
Инкрементальный. Повторно транслирует фрагменты программы и дополнения к ней без перекомпиляции всей программы.
Интерпретирующий (пошаговый). Последовательно выполняет независимую компиляцию каждого отдельного оператора (команды) исходной программы.
Компилятор компиляторов. Транслятор, воспринимающий формальное описание языка программирования и генерирующий компилятор для этого языка.
Отладочный. Устраняет отдельные виды синтаксических ошибок.
Резидентный. Постоянно находится в оперативной памяти и доступен для повторного использования многими задачами.
Самокомпилируемый. Написан на том же языке, с которого осуществляется трансляция.
Универсальный. Основан на формальном описании синтаксиса и семантики входного языка. Составными частями такого компилятора являются: ядро, синтаксический и семантический загрузчики.