Компиляторы. Оптимизация кода


Компиляторы. Генерация кода. Общая схема распределения памяти.

Генерация машинного кода

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

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

Исторически различают три формы объектного кода:

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

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

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

 


 

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

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

1. модель информационных или запоминающих ресурсов.

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

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

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

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

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

Для каждого элемента в таблице символов выполняется следующее:

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

2. текущая таблица увеличивается на длину элементов, отведенных под формальные параметры.

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

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

Процесс генерации кодов отдельных команд отражается на каноническое множество адресов и модификаций команд. Во множество адресов включается как минимум:

1. прямая адресация глобальных и динамических данных.

2. относительная адресация аргументов и локальных данных, процедур и функций в стеке.

3. индексная адресация глобальных и локальных данных.

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

При изучении форматов объектных модулей решить следующие вопросы:

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

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

Словарь внешних символов (ESD) определяет и дает единственное имя и номер таким объектам как кодовые сегменты и внешние ссылки на программные сегменты и другие точки входа, к которым обращаются в этом модуле, но которые не включены в него.


Интерпритатор – программа которая не выдает результат программы

Целью компилятора является трансляция программы, написанной на ЯВУ в машинные коды некоторого компьютера. Большинство ЯВУ построено так чтобы независимыми от тех машин на которых они будут исполняться. Это означает что процесс анализа синтаксиса программ написанных на этих языках должен быть так же машинно-независимым. Но процесс генерации кода является машинно-зависимым поскольку необходимо знать систему команд компьютера для которого этот код генерируется.

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

Синтаксический анализ – Во время синтаксического анализа предложения исходной программы распознаются как язык. Конструкции описываемые используемые грамматикой. Можно рассматривать этот процесс как построение дерева грамматического разбора для транслируемых предложений.

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