Факультет вычислительной математики и кибернетики (стр. 14 из 15)

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

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

с несанкционированным появлением в тексте программы необъявленных переменных , с неявным преобразованием типов и т.п. . Можно было

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

ошибок в период компиляции ,а также невозможность использования для

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

1) таблица символов ;

2) таблица типов ;

3) таблица функций ;

4) таблица меток .

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

пару вида <имя переменной , тип переменной > . При организации

таблицы необходимо учитывать возможность появления одинаковых

имен переменных , являющихся на самом деле различными из за

объявления их в разных блоках программы . Например переменная

с именем x может быть объявлена как глобальная переменная и

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

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

в которую в процессе анализа текста программы заносятся все

объявляемые в анализируемом блоке переменные , а после конца

анализа этого блока из стека удаляются переменные , принадлежащие

только данному блоку.

Таблица типов . Компилятор должен обеспечивать уникальность

представления каждого типа в конкретной программе. При наличии

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

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

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

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

операций над типами , выполняемых в период компиляции .

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

integer , real , char и т.п. , можно кодировать целыми числами ,

а составные типы представлять в виде соответствующих структур .

Пример .

type datet=record

day:integer ;

month:integer ;

year: integer

end;

Определенный выше тип можно представить в виде следующей

древовидной структуры .

datet

<day,integer> <year,integer>

<month,integer>

Рис. 3.5-1. Пример древовидного представления структурного типа .

Аналогично можно представить и друтие составные типы .

Также как имена переменных , имена типов могут иметь области

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

Таблица функций(операций) связывает типы параметров (аргументов)

с типом значения (результата) для каждой функции (операции).

Например, строка таблицы может представляться в виде:

integer+integer -> integer .

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

вхождений меток .

Кроме указанных здесь действий по семантическому анализу , могут

быть предусмотрены дополнительные действия , определяемые

спецификой той или иной системы программирования .

3.6.Этап синтеза .

3.6.1.Распределение памяти.

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

может принадлежать к одному из перечисленных ниже видов .

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

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

(например процедуры или функции ) . Может быть освобождена после

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

такой вид памяти выделяется для локальных переменных .

3. Глобальная память выделяется для объектов , время жизни которых неизвестно в период компиляции и определяется только в процессе выполнения программы. Таким образом глобальная память может выделяться или освобождаться только в процессе выполнения программы . Например , в языке PASCAL- это динамические типы , для которых выделение (new) и освобождение памяти (dispose) происходит

только при выполнении программы .

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

какое - либо "совместное использование" этой памяти не допускается .

Средства реализации ранних языков программирования (например для языка FORTRAN ) основывались на статической памяти .

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

Управление глобальной памятью реализуется следующим образом.

Резервируется общее пространство памяти , из которого

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

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

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

|||||| |||||| … |||||| ||||||

a) Обычное состояние

||||||||||||||||||||||||

b) Идеальное состояние

Рис.3.6.1-1. Иллюстрация представления памяти в процессе

выполнения программы.

Занятые участки памяти определяются заштрихованными частями ,

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

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

непрерывной памяти отсутствует и в то же время общий объем всей

свободной памяти имеет достаточно большие размеры . В этом

случае выполняется операция сжатия памяти , приводящая

состояние памяти к "идеальному" (см. рис. 3.6-1b) .

2. Освобождение памяти может инициироваться применением

соответствующего оператора программы (в языке PASCAL

освобождение памяти может инициироваться выполнением

оператора dispose ) . Однако далеко не всегда следует процесс

освобождения возлагать на программиста , поскольку в этом случае

предполагается высокий профессионализм и ответственность

программиста . Например в языке JAVA освобождение памяти

обеспечивается средствами реализации языка . Этот механизм

освобождения памяти реализуется в большинстве случаев так

называемыми программами сборки мусора . Сборка мусора

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

есть ссылки из действующих в программе объектов . Затем все

немаркированные участки занятой памяти считаются

неиспользуемыми в работе программы и освобождаются (то есть

переходят в свободный участок памяти ) .

3.6.2.Генерация кода.

Перед генерацией кода в большинстве современных компиляторов

происходит формирование так называемого промежуточного кода ,

с помощью которого осуществляется непосредственно генерация .

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

следующие .

1. Необходимость четкого разделения между машинно-зависимой и

машинно-независимой частями компиляции .

2. Обеспечение удобства переноса компилятора в другую новую среду.

3. Упрощение реализации средств оптимизации кода.