Компиляция и промежуточное представление кода программы презентация

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

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

Лексический анализ

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

Генерация промежуточного кода

Оптимизация промежуточного кода

Генерация внутреннего представления

Компоновка программы

Фазы компиляции

Выполнение и тестирование программы

Выход

их тип. К числу лексем относятся названия операторов, например, read или write; имена (переменных или констант), например, NABOR или CHISLO, различные разделители, такие как круглые скобки, знаки препинания и т.д. Одновременно типами указанных лексем являются названия операторов, имена переменных, разделители и т.д. Если программистом допущена ошибка и оператор ввода указан, например, rread, он будет распознан компилятором как имя. На этом этапе выявляется  также использование недопустимых языком программирования символов, например, символа @. В результате лексического анализа исходная программа кодируется: каждая лексема заменяется кодом ее типа, что сокращает объем текста программы. Кроме того, из текста программы удаляются пробелы.

Определение

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

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

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

Пример 1:
Лексический анализ фрагмента программы на Турбо-Паскале, содержащего только один правильно записанный оператор ввода:
 read (NABOR,CHISLO);                        
 дает цепочку
1 2 3 4 3 2 4
где 1 – код названия оператора;
2 – код скобки;
3 – код имени;
4 – код знака препинания.

Пример 2:
Лексический анализ фрагмента программы на Турбо-Паскале, содержащего только один неправильно записанный оператор ввода:
 
rread (NABOR,CHISLO);
 
дает цепочку
 
3 2 3 4 3 2 4  

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

В то же время структура "правильного" оператора ввода определяется схемой:

Поскольку представленные структуры идентичны, оператор read (NABOR,CHISLO);  при синтаксическом анализе определяется как правильный.

Рис 1

Рис 2

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

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

Именно на этом шаге выявляются ошибки в написании названий операторов: они ведут к некорректной структуре всего оператора. Так, примеру с "неправильным" оператором ввода соответствует структура, показанная на рисунке: (рис. 3)

Рис 3

Рис 4

Поскольку структура этого рисунка не соответствует структуре рисунка 1, оператор rread (NABOR,CHISLO); расценивается как синтаксически некорректный: компилятор не найдет в анализируемом фрагменте требуемого действия, которое задается названием оператора, и сообщит об этом программисту.

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

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

Граф управления [15,16] – аналитическая структура, которую логически можно представить как управляющую надстройку над промежуточным представлением. И в реализации наиболее распространенной схемой является представление управляющего графа как отдельного объекта, имеющего взаимно однозначное соответствие с операционной семантикой промежуточного представления, в которой выражена вся полнота семантики передачи управления. Представляет собой направленный связный граф, каждый узел (вершина) которого соответствует линейному участку, а дугам - управляющие связи между ними, отображающие передачу управления. В графе есть два выделенных узла: узел START, не имеющий входных дуг, и узел STOP, не имеющий выходных дуг.

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

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

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

read (NABOR,CHISLO
 
она будет определена как семантически некорректная, поскольку в ней отсутствуют описания вводимых переменных.

                 
 
расценивается семантическим анализатором как семантически корректная.

Пример 4:
Программа
 
var CHISLO: integer;
CHISLO:=CHISLO + 1;                
 
расценивается семантическим анализатором как семантически корректная.

генерации кода при компиляции.

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

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

ассемблере:
 
$1 DD ? ; операторы DD описывают переменные: каждый из них
$2 DD ?; отводит под переменную 2 байта памяти;
$3 DD ?; переменные $1 - $3 вводятся генератором кода как
CHISLO DD ?; вспомогательные переменные;
MOVE 1, $1; в операторах MOVE константы или содержимое        
MOVE CHISLO, $2; переменных слева от запятой помещаются в переменные и
MOVE $1, AX;  регистры процессора (АХ и СХ), указанные справа;
MOVE $2, CX;                
ADD AX, CX;  выполняется сложение содержимого регистров АХ и СХ;
езультат остается в регистре АХ
MOVE AX, $3; выполняются перемещения значений,
находящихся в 
MOVE $3, CHISLO; регистре и переменной, в соответствующие переменные

Создание промежуточного кода

Генерация промежуточного кода программы при компиляции

Полученный код избыточен: в самом деле, выполняется бессмысленная пересылка константы 1 и значения переменной CHISLO  сначала в дополнительные переменные $1 и $2, а затем уже в регистры АХ и СХ, которые и используются при сложении. Аналогичные бессмысленные действия выполняются и с результатом сложения. Однако уменьшение размеров кода осуществляется на следующем этапе.

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

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

Промежуточный код может выглядеть по-разному. Он может связываться с реализуемым языком, например Р-код для языка Pascal, Diana для языка Ada, байт-код для языка Java. В качестве альтернативы он может также связываться с машинами, на которых осуществляется реализация. Пример: язык CTL (Compiler Target Language), который применялся в 70-х годах в Манчестерском университете в качестве промежуточного языка для машины MU5.

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

Примеры промежуточного кода

Трехадресный код

Р - код

Байт-код

с
Здесь ор — арифметический (или другой) оператор, b и с — его операн­ды (или их адреса), а а – адрес результата применения оператора к опе­рандам. Арифметическое выражение
(а + b)*(c+d)
можно представить в виде последовательности таких инструкций трехадресного кода:
t1 = a + b
t2 = c + d
t3 = t1*t2

Здесь t — создаваемые компилятором временные имена. Можно также применять унарные операторы (monadic operator).
Например, оператор
-m
создаст инструкцию
t1 = -m
(хотя, безусловно, в этом случае трехадресный код будет содержать всего лишь два адреса!).

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

многоцелевой стек мог хранить операторы и операнды (в том числе временные имена). Действиями являются:
А1 — занести оператор в стек;
А2 — следующим образом напечатать инструкции трехадресного кода:
напечатать имя следующей распределяемой временной величины;
напечатать "=";
напечатать три верхних элемента стека снизу вверх;
занести в стек только что распределенное имя временной величины;
A3 — занести в стек операнд;
А4 — следующим образом напечатать инструкции трехадресного кода:
напечатать имя следующей распределяемой временной величины;
напечатать "=";
напечатать два верхних элемента стека снизу вверх;
занести в стек только что распределенное имя временной величины.

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

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

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

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

Здесь действиями являются: (см. далее)

while можно реализовать путем добав­ления к грамматике следующих действий.

Здесь действиями являются: (см. далее)

требует использования сте­ка времени компиляции. Он включает в себя переходы вперед и назад по коду, а применимое и определяющее вхождения меток обычно вклады­ваются "обычным образом". В то же время следует быть осторожными в тех случаях (например, внутри действия W3), когда порядок появления меток в стеке не совсем соответствует порядку, в котором они требуются. Стек меток может быть отдельным стеком времени компиляции или может объединяться с другими стеками времени компиляции.

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

Каждая инструкция Р-кода имеет следующий формат.
F P Q
Здесь F — код функции, а Р или (иногда — и) Q могут отсутствовать в зависимости от конкретного кода. При наличии этих параметров Р может применяться для определения уровня статического блока, а Q — для определения офсета внутри фрейма или промежуточного операнда (например, константы). Инструкции без параметров применяются к верхним элементам стека и включают следующие инструкции:
and применяет булев оператор AND к верхним двум элементам сте­ка, удаляет их и оставляет результат действия оператора (истина или ложь) на вершине стека.
dif применяет оператор разности множеств к верхним двум эле­ментам стека, удаляет их и оставляет результат действия оператора (множество) на вершине стека,
ngi изменяет знак целого значения на вершине стека.
flt преобразует значение на вершине стека из целого в действительное.
flo преобразует значение второго сверху элемента стека из целого в действительное.
inn проверяет на предмет принадлежности к множеству, используя верхние два элемента стека как параметры и оставляя вместо них значения "истина" или "ложь'.

на вершину стека используются одно- или двухадресные инструкции. Например:

Здесь адреса времени компиляции представлены в виде пары целых чисел (статический уровень, офсет) Р-код также включает в себя инструкции переходов, например:

Метки могут устанавливаться в коде, например:

Единичные инструкции определяются таким образом, чтобы к значению на вершине стека можно было применить стандартные функции, например:
CSP ATAN
Здесь функция arctg применяется к значению на вершине стека, оставляя результат действия функции на месте этого значения. Другой пример:
CSP WLN
Здесь к файлу, который определяется верхним элементом стека, применяется инструкция writeln.

ранее. Предполагается, что при вычислении выражения подсчитанное значение выражения оставляется на вершине стека.

UJP L1
L2
При каждом применимом вхождении переменной образуется код для помещения в стек адреса или значения переменной (в зависимости от обстоятельств). Например,
LDA 1 7 будет загружать адрес (1, 7) на вершину стека, а
LODI 1 7 будет загружать значение целой переменной с адресом (1,7) на вершину стека.
Реализация присваивания, в простейшем случае, включает в себя копирование значения верхнего элемента стека в адрес второго сверху элемента стека. После этого два верхние элемента стека удаляются. Это можно сделать с помощью простой адресной инструкции.

необходимо скопировать множество последовательно расположенных значений, при­сваивание осуществляется с помощью инструкции
MOV m
Она переносит т значений, начиная с исходного адреса, в соответствующее число адресов, начиная с целевого адреса (целевой и исходный адреса распо­лагаются на вершине стека). В это же время два адреса удаляются из стека.
Несмотря на то, что Р-код в дальнейшем может быть откомпилирован в машинный код для конкретной машины, чаше он выполняется посредством использования интерпретатора. Широко распространенный в кон­це 70-х перенос Pascal из одной среды в другую во многом был связан с тем, что при наличии компилятора Pascal, написанного на языке Pascal, который требовалось использовать в новой среде, нужно было всего лишь написать интерпретатор Р-кода для этой среды, что занимало около месяца работы. В действительности, многие компиляторы "немного не доходят" до создания действительного машинного кода. В некоторых случаях, например, генерируется ассемблерный код» который позже (посредством системного ассемблера) преобразуется в машинный код.

(JVM). Он, подобно Р-коду для языка Pascal, основан на использо­вании стека. Отметим, что Java Virtual Machine разрабатывалась, чтобы Реализации Java были:
эффективными;
защищенными;
переносимыми;
что отражено в системе времени выполнения Java, основные компоненты которой перечислены ниже.
Механизм выполнения (execution engine), который выполняет инструкции байт-кода.
Модуль управления памятью (memory manager), который управляет кучей, где хранятся все объекты и массивы.
Модуль управления обработкой ошибок и исключительных ситуации (error and exception manager), который используется для планомерного и систематического нахождения ошибок периода выполнения
Интерфейс потоков (threads interface), который управляет параллельной работой.
Загрузчик класса (class loader), который загружает, связывает и устанавливает классы в исходное состояние (инициализирует классы).
Модуль управления защитой (security manager), который препятствуюет запуску "враждебных" программ.

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

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

Важной особенностью реализаций Java является то, что верификация происходит до выполнения программы, что позволяет избавиться от по­тенциально трудоемкой проверки в процессе выполнения. В то же время верификация обходится недешево: она основывается на разновидности средства доказательства теорем, имеющего некоторые теоретические ог­раничения.
Существует более 160 различных инструкций байт-кода, многие из них отличаются только типами операндов. Для верификации важным является хранение информации о типах в байт-коде, множество имеющихся инструкций по-разному поддерживают различные типы данных! Основные типы инструкций байт-кода можно выделить в такие группы:
работа со стеками;
выполнение арифметических операций;
оперирование объектами и массивами;
поток управления;
вызов методов;
обработка исключительных ситуаций и параллельная работа.

и локальных переменных в стек, собственно работы со стеком и запоминания значений из стека в локальных переменных.

Инструкция Значение
incost_4 загружает в стек целую константу 4 inload_4 загружает в стек значение локальной переменной номер 4 pop отбрасывает верхнее значение стека
dup копирует верхний элемент стека
swap меняет местами два верхних элемента стека
istore_4 заносит значение верхнего элемента стека в локальную переменную номер 4

Примеры инструкций для выполнения арифметических операций.

Инструкция Значение
iadd суммирует две целых величины на вершине стека
fadd суммирует две величины типа float на вершине стека
fmul умножает две величины типа float на вершине стека

Доступ к массивам осуществляется с помощью инструкций, подобных приведенной ниже.

Инструкция Значение
iaload помещает значение элемента массива на вершину стека (предполагается, что ссылка массива и индекс индекса уже находятся в стеке)

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

Инструкция Значение
ifeq L1 переход к L1, если целое значение на вершине стека равно нулю
if_icmpne L1 переход к L1, если два целых значения на вершине стека различны goto L1, переход к L1

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

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

1. if (выражение) оператор1 else оператор2
Данный оператор в байт-коде представляется в следующем виде.
байт-код для помещения значения выражения на вершину стека
ifeq L1
байт-код для выполнения оператора1
goto L2
L1
байт-код для выполнения оператора2
L2

представлен в следующем виде.
L1,
байт-код для помещения значения выражения на вершину стека
ifeq L2
байт-код для выполнения оператора
goto L1
L2

Следует отметить, что в байт-коде значению "ложь" соответствует 0, а значению "истина" — 1. Отсюда — использование ifeq, а не обратной инструкции ifne. В языке Java булевский тип отсутствует.

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

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

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

Из программы, полученной на предыдущем шаге, устраняются «лишние» операторы, переменные  и константы, использование которых  не влияет на корректность выполняемых действий

Пример 6:
Оптимизация промежуточного кода для программы из примера 5 приводит  ее к виду:
CHISLO DD ?                
MOVE 1, AX                
MOVE CHISLO, CX                                                                        
ADD AX, CX                
MOVE AX, CHISLO        
Такой результат связан с тем, что ряд операторов выполняли лишние перемещения данных из одного места хранения в другое. Удаление этих операторов повлекло удаление вспомогательных переменных.

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

Алгоритм устроен следующим образом:
 
Цикл по всем дугам графа управления
Если вероятность дуги равна нулю
Добавить все узлы (кроме STOP),достижимые вниз из дуги, в множество С копируемых узлов
Пометить дугу маркером
Конец если
Конец цикла
Цикл по всем узлам из множества С
Создать копию узла
Пометить копию специальной меткой
Цикл по всем дугам, входящим в узел
Если дуга помечена маркером
Перенаправить дугу на копию
Конец цикла
Конец цикла
Цикл по всем узлам графа управления
Если узел недостижим из узла START
Удалить узел
Конец цикла

на примере. Допустим, узел N является последователем узла M. Рассмотрим следующие ситуации:
Узлы N и M входят в множество С;
Узел N входит в множество С, узел M не входит.
Результаты копирования в случаях a и b представлены на Рис. 3, где штрихами обозначены копии соответствующих узлов

Таким образом обеспечивается корректная структура последователей. Перенаправление дуг необходимо для обеспечения наличия пути из узла START в начальный узел копируемого подграфа. Последний цикл алгоритма необходим для удаления излишних, недостижимых из узла START узлов, появившихся после перенаправления дуг. Тем самым обеспечивается связность и корректная структура графа управления в целом.
В результате работы алгоритма получаем модифицированный граф, представленный на Рис. 4.
Копии узлов, получаемые в результате работы алгоритма, помечаются специальным признаком, который обозначает нулевую вероятность передачи управления в этот узел. Будем называть эти узлы, помеченные этим признаком, узлами «черной дыры».

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

Использование результатов оптимизации при компиляции
Рассмотрим исходную ситуацию, представленную на Рис. 2. Как видно из рисунка, управление по дуге со значением вероятности 1.0 и управление по дуге со значением вероятности 0.0 сходятся в узле Node 7. Различные оптимизации, такие как if-conversion, глобальное планирование, основываясь на профильной информации, которая содержится в узлах и дугах, охватывающих представленный подграф, могут преобразовать весь подграф в единый узел, называемый расширенным скалярным участком , перемешав, таким образом, вычисления, находящиеся на ветках управления с разными вероятностями исполнения.
В результате применения алгоритма получается новый подграф, в котором эти ветки управления не пересекаются. Узлы, помеченные признаком «черной дыры», обрабатываются оптимизациями специальными способами. В частности, if-conversion и глобальное планирование не преобразует такие узлы в расширенные скалярные участки. Отказываясь, таким образом, от применения оптимизаций в области «черной дыры», мы тем самым сохраняем чистоту высоковероятных вычислений.
Подобным образом могут обрабатывать такие узлы и остальные оптимизации. Таким образом, получается, что область «черной дыры» существует отдельно от основной части программы, и вычисления, находящиеся в ней, не попадают в код с большим количеством исполнений.
Иногда полезно модифицировать алгоритм и требовать равенства значения вероятности дуги не нулю, а некоторому малому числу в окрестности нуля. Подобрав этот параметр, можно улучшить производительность полученного кода. Такой эксперимент был поставлен на задаче 147.vortex из пакета Spec95.

Эту задачу решает фаза генерации кода (code generator) .

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

(так называемый объектный модуль), в котором использованы относительные, а не абсолютные адреса основной памяти. Как правило, для получения объектного модуля применяется условная память с начальным адресом 1. Каждый оператор программы преобразуется в машинную команду и размещается, начиная с начального адреса, в той последовательности, в которой он следует в программе. При этом учитывается размер каждого оператора. Пусть командам программы из примера 6 соответствуют машинные команды:
код объем     действие
операции
124                  1 б          сложить содержимое регистров АХ и СХ, результат – в регистре АХ,
125                  3 б          поместить содержимое регистра АХ по адресу,
126                  2 б          поместить константу в регистр АХ,
127                  3 б          поместить содержимое адреса в регистр СХ.                 

 Оператор DD выделяет объем памяти в 2 байта для описываемой переменной. Тогда схема размещения объектного кода имеет вид, представленный в таблице:                 

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

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

Трансляция в ассемблер

Виртуальная машина

Способы получения объектного кода

Кросс-транслятор

программой или загрузочным модулем. При этом решаются две основные задачи:
если в программе используются функции, например, sin, exp и т.д., соответствующие им программные модули выбираются из библиотеки подпрограмм соответствующей системы программирования и вставляются в объектный модуль;
объектный модуль преобразуется в соответствии с реальными адресами основной памяти, куда будет размещаться программа для выполнения.

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

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

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

Тестирование программы имеет целью определение работоспособности программы на всем требуемом диапазоне исходных данных. Программистом составляется представительная выборка исходной информации, которая позволит определить корректность программы при любых входных параметрах.
Для программы из примера 1 задаются набором переменной CHISLO. Так, если среди этих значений будет такое, которое превышает допустимый диапазон типа integer, при выполнении программы в процессе тестирования возникает переполнение разрядной сетки (overflow), что обсуждалось ранее. Это потребует от программиста переделки исходной программы в части описания переменной  CHISLO.
      

Пример 7:
Для программы  
var CHISLO: integer;
CHISLO:=CHISLO + 1;        
 и (ее кода) будут выявлены две логические ошибки:
неизвестность результата ввиду отсутствия в программе оператора вывода, например, write (CHISLO);
после добавления оператора вывода в программу и выполнения последней, полученное потребителем значение переменной CHISLO имеет произвольный характер, так как не определено начальное значение этой переменной.
 
Тогда правильная программа вместо той, которая приведена в примере 1, могла бы иметь вид:
 var CHISLO: integer;
input (CHISLO);
CHISLO:=CHISLO+1;                                                                        
write (CHISLO);        

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

A и компьютер М1 с языком ассемблера А1 . Кроме того, предположим, что имеется компилятор КА1: Р А1, а сам компьютер M по каким-то причинам не доступен либо пока еще не существует компилятор КА: Р А . Нас интересует компилятор КА: L А . В такой ситуации мы можем использовать М1 в качестве инструментальной машины и написать компилятор КР: L А . , который принято называть кросс-транслятором (cross-compiler) . Как только машина M станет доступной, мы сможем перенести КР на M и "раскрутить" его с помощью КА . Понятно, что это решение достаточно трудоемко, поскольку могут возникнуть проблемы при переносе, например, из-за различий операционных систем.
Под переносимой (portable) программой понимается программа, которая может без перетрансляции выполняться на нескольких (по меньшей мере, на двух) платформах. В связи с этим возникает вопрос о переносимости объектных программ, создаваемых компилятором. Компиляторы, созданные по методикам, рассмотренным выше, порождают непереносимые (non-portable) объектные программы. Поскольку компилятор, в конечном итоге, является программой, то мы можем говорить и о переносимых компиляторах. Одним из способов получения переносимых объектных программ является генерация объектной программы на языке более высокого уровня, чем язык ассемблера. Такие компиляторы иногда называют конвертерами (converter) .
      

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

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

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

Компиляция на лету

Виртуальная JAVA машина

Внешний и внутренний интерфейсы

Просмотры

Техника «заплат»

том, что обычно время выполнения интерпретируемой программы значительно больше, чем время работы программы, оттранслированной в "родной" машинный код. Для того, чтобы увеличить скорость работы приложений, была разработана технология компиляции "на лету" (Just-In-Time compiling; иногда такой подход называют также динамической компиляцией). Идея заключается в том, что JIT-компилятор генерирует машинный код прямо в оперативной памяти, не сохраняя его. Это приводит к значительному увеличению скорости выполнения приложения.       

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

Использование связки "компилятор+интерпретатор+JIT-компилятор" позволяет заметно повысить скорость выполнения исходной программы, причем переносимость кода, создаваемого компилятором, естественно, сохраняется.

которое затем интерпретируется так называемой «виртуальной машиной Java». Виртуальная машина Java представляет собой стековую машину: она не имеет памяти прямого доступа, все операции выполняются над операндами, расположенными на вершине стека. Чтобы, например, выполнить операцию с участием константы или переменной, их предварительно необходимо загрузить на верхушку стека. Код операции – всегда один байт. Если операция имеет операнды, они располагаются в следующих байтах.
К элементарным типам данных, с которыми работает машина, относятся short, integer, long, float, double (все знаковые).

указатель на стек-фрейм исполняемого метода;
Vars указатель на 0-ю переменную исполняемого метода.

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

локальных переменных на стек;
запоминание значений из стека в локальных переменных;
обработка массивов;
управление стеком;
арифметические команды;
логические команды;
преобразование типов;
передача управления;
возврат из функции;
табличный переход;
обработка полей объектов;
вызов методов;
обработка исключительных ситуаций;
прочие операции над объектами;
мониторы;
отладка.
Рассмотрим некоторые команды подробнее.

Помещение локальных переменных в стек

Вызов метода

Обработка исключительных ситуаций

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

Команда isore – сохранить целое в локальной переменной. Операндом операции является смещение переменной в области локальных переменных. Значение с верхушки стека операций копируется в указываемую область локальных переменных. Имеются аналогичные команды для помещения плавающих, двойных целых, двойных плавающих и т.д.

методов, вообще говоря, нельзя статически протранслировать вызов метода объекта. Это связано с тем, что если метод перекрыт в производном классе, и вызывается метод объекта-переменной, то статически неизвестно, объект какого класса (базового или производного) хранится в переменной. Поэтому с каждым объектом связывается таблица всех его виртуальных методов: для каждого метода там помещается указатель на его реализацию в соответствии с принадлежностью самого объекта классу в иерархии классов.
В языке Java различные классы могут реализовывать один и тот интерфейс. Если объявлена переменная или параметр типа интерфейс, то динамически нельзя определить, объект какого класса присвоен переменной:
interface I;
class C1 implements I;
class C2 implements I;
I O;
C1 O1;
C2 O2;
…
O=O1;
…
O=O2;
…

значение хранится в переменной O. Кроме того, при работе программы на языке Java имеется возможность использования методов из других пакетов. Для реализации этого механизма в Java-машине используется динамическое связывание.
Предполагается, что стек операндов содержит handle объекта или массива и некоторое количество аргументов. Операнд операции используется для конструирования индекса в области констант текущего класса. Элемент по этому индексу в области констант содержит полную сигнатуру метода. Сигнатура метода описывает типы параметров и возвращаемого значения. Из handle объекта извлекается указатель на таблицу методов объекта. Просматривается сигнатура метода в таблице методов. Результатом этого просмотра является индекс в таблицу методов именованного класса, для которого найден указатель на блок метода. Блок метода указывает тип метода (native, synchronized и т.д.) и число аргументов, ожидаемых на стеке операндов.
Если метод помечен как synchronized, запускается монитор, связанный с handle. Базис массива локальных переменных для нового стек-фрейма устанавливается так, что он указывает на handle на стеке. Определяется общее число локальных переменных, используемых методом, и после того, как отведено необходимое место для локальных переменных, окружение исполнения нового фрейма помещается на стек. База стека операндов для этого вызова метода устанавливается на первое слово после окружения исполнения. Затем исполнение продолжается с первой инструкции вызванного метода.

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

степени зависят от входного языка и в меньшей степени от целевого. Другие фазы, наоборот, в меньшей степени зависят от входного языка и в большей степени от целевого. Например, лексический, синтаксический, видозависимый анализ и некоторые оптимизации не слишком значительно зависят от целевого языка. Эти фазы иногда объединяют вместе под названием внешний интерфейс или front-end. Front-end подразумевает также обработку ошибок, которые могут встретиться на перечисленных фазах Остальные фазы, несущие на себе отпечаток целевого языка, называются внутренним интерфейсом (back-end) .
Таким образом, если мы хотим иметь компиляторы некоторого языка на разных платформах, то наша задача сводится к написанию нескольких back-end'ов без изменения front-end'а. С другой стороны, для создания многоязыкового компилятора достаточно написать несколько front-end'ов.

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

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

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

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

можем использовать его не только для перехода назад, но и для перехода вперед. Таким образом, мы не всегда можем определить операнд команды перехода, по крайней мере до тех пор, пока не доберемся до конца программы. Однако в простых случаях мы можем использовать технику "заплат" (backpatching) . Рассмотрим фрагмент программы на языке ассемблера:
...
goto target;
...
goto target;
…
target: mov foobar, r1

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