Эквивалентность типов данных. Ассоциации наименований объектов (пространства имен)

Эквивалентность типов данных

1.  Кодированное представление и сравнение типов:

00 – означает отсутствие конструктора;

01 – означает указатель (pointer) на тип t, закодированный правее;

10 – массив (array) неопределенной длины элементов типа t;

11 – функцию, возвращающую объект типа t (freturns).

Например, массив указателей на функции, возвращающие целые значения:

int	int	000000 0001
int function(…)	freturns(int)	000011 0001
*(int function(…))	pointer(freturns(int))	000111 0001
(*(int function(…)))[…]	array(pointer(freturns(int))	100111 0001

2.  Именное представление и сравнение типов: типы хранятся и обрабатываются в текстовом виде, извлеченном из программы (с удалением всех лишних литер форматирования)

Трудности:

intне то же самое, что signedint

char* и char[] – разные типы

int[10] и int[11] – это разные типы

…

3.  Структурное представление и сравнение типов:          struct{int; char* }*()

Каждое применение конструктора производных типов – это очередной уровень (дуга + узел) в структурном представлении.

Алгоритм сравнения:

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

Если оба – листья, то вернуть истину, если они имеют один и тот же базовый тип, и вернуть ложь в противном случае.

Иначе, если один тип – базовый, а второй – производный, то вернуть ложь.

Иначе обойти все пары исходящих дуг.

Если есть непарная дуга – вернуть ложь.

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

Здесь нужно решать проблему эквивалентности дуг.

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

 

При рекурсивном определении производных типов, например таком:

Struct node {

int num;

struct node* inner;

struct node * next;

char* val

};

прямое применение этого алгоритма приведет к зацикливанию.

Способы предотвращения зацикливания:

1. Отметки уже пройденных вершин

2. Преобразование циклического графа в ациклический (дерево)

Ассоциации наименований объектов (пространства имен)

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

С каждой ассоциацией происходят следующие события:

1.  Создание (при входе в процедуру/программу) – однократное.

2.  Использование (доступ к объекту на основе ассоциации его имени со значением) – множественное.

3.  Деактивирование (обычно при вызове процедуры; объект существует, но доступа к нему нет) –множественное.

4.  Реактивирование (обычно при возврате из процедуры) –множественное.

5.  Уничтожение (исчезает объект, как правило вместе с именем) – однократное.

Для одного и того же имени могут существовать одновременно много ассоциаций. Каждая из них проходит свой жизненный цикл от 1 к 5. В одном пространстве ассоциаций на стадии 2 в любой момент может находиться не более одной ассоциации для любого наименования. Поэтому во многих языках реализуется существование многих пространств ассоциаций:

X : X . X=Y :: X ( ) ;

Первое  - это метка, второе – имя структуры или класса, третье – имя элемента структуры или публичного члена класса, четвертое – имя метода другого класса.

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

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

1.  Допускаются ли рекурсивные вызовы процедур?

2.  В какой момент создаются локальные объекты процедур?

3.  Что происходит с локальными переменными при возвращении управления из процедуры?

4.  Может ли процедура обращаться к нелокальным не статическим (не глобальным) объектам, не являющимся ее фактическими аргументами?

5.  Каким образом в вызываемую процедуру передаются параметры?

6.  Может ли процедура быть передана в качестве параметра?

7.  Может ли процедура быть возвращена в качестве результата?

8.  Может ли память выделяться динамически, по явному запросу программы?

9.  Должна ли динамически выделенная память освобождаться также по явному запросу?