|
| |
ГИБКАЯ СТРУКТУРА ТАБЛИЦЫ СИМВОЛОВ
<<< Назад
АННОТАЦИЯ
Хотя язык программирования С++ является развитием
языка С, он имеет со-
вершенно другие правила видимости имен. В данной статье
описана структура
областей видимости С++ и освещены подходы к двум
специфическим для трансля-
ции С++ проблемам представления областей видимости
в таблице символов и оп-
ределение последовательности активации деструкторов
при выходе из области
видимости. Решения, представленные здесь, основаны на
операционном взгляде
на видимость имен в С++ как коллекцию взаимосвязанных
объектов
С++ - существенно новый язык программирования [1]. Предлагая
возможнос-
ти современного языка программирования, включая абстракцию данных,
пере-
грузку знаков операций, упрятывание информации, в то же время оставаясь
в
известной мере совместимым с языком С, С++ является несомненным шагом
впе-
ред. В этой статье освещаются подходы к двум специфическим проблемам
транс-
ляции С++ : представления областей видимости в таблице символов и
определе-
ние последовательности активации деструкторов при выходе из области
видимо-
сти. Техника, описываемая здесь, использовалась при реализации
компилятора
С++ и доказала свою жизненность и эффективность. В статье не
описывается
язык программирования С++ хотя для чтения статьи необходимо
определенное
знакомство с языком. По ходу изложения поясняются только те
возможности
языка, которые необходимы для иллюстрации техники.
ВИДИМОСТЬ
ИМЕН В С И С++.
Хотя С++ является развитием языка С, он имеет совершенно
другие правила
видимости имен.
Видимость имен в С основана на блочной
структуре [2]. Таким образом,
имя считается определенным с точки, где оно
впервые появляется, до конца
блока, где это появление имело место и ни какое
другое имя с тем же иденти-
фикатором в этом блоке не может быть объявлено.
Эта простая структура уси-
ливается множеством пространств имен, существующих
параллельно и следующих
той же самой блочной структуре; данный идентификатор
может быть объявлен в
одном блоке неоднократно, если он не повторяется в
одном и том же простран-
стве имен. Пространства имен в С включают
пространство имен для ярлыков
структур, объединений и перечислимого типа,
пространства имен для каждой
структуры или объединения, и пространство для
всех остальных имен, исключая
метки. Метки формируют свое собственное
пространство имен, но в дальнейшем
изложении игнорируются, так как их правила
видимости отличаются от правил
видимости всех остальных имен.
Имена из
разных пространств имен с одними тем же идентификатором распо-
знаются по
занимаемой ими синтаксической позиции [3]. Например, фрагмент
s r t r u c t C
можно рассматривать как единый идентификатор из простран-
ства имен ярлыков
структур. Выражение p o i n t e r - > m e m b e r обо-
значает имя с
идентификатором m e m b e r из пространства имен базового
типа указателя p o
i n t e r. Вследствие своей простоты структура прост-
ранств имен языка С
может быть эффективно реализована в виде одной блоч-
но-структурированной
таблицы с добавлением средств для распознавания имен
из разных пространств
имен.
С++ сохраняет блочно-структурированную видимость имен языка С, но
поме-
щает все имена (исключая метки) в одно пространство имен. Например,
описа-
ние s t r u c t T { } T; которое объявляет тип s t r u c t T и объект
T за-
конно в С, но не в С++. В добавление к этому, всякое объявление
структуры
или объединения определяют свою область видимости, в которой
существуют
члены структуры (объединения). Это аналогично той точке зрения в
С, что ка-
ждая структура и объединение определяют новое пространство имен.
Семантика,
однако, отличается : в С выражение o b j e c t . m e m b e r
означает, что
m e m b e r существует в текущей области видимости, возможная
неоднознач-
ность снимается по базовому типу переменной o b e j c t ; в С++ m
e m b e r
существует в отдельной области видимости, доступной посредством
базового
типа переменной o b j e c t .
Эта семантическая разница между
пространством имен и областью видимости
необязательно влечет разную
реализацию операции выбора члена сруктуры, так
как в данном случае обе точки
зрения дают одинаковый эффект. Однако, С++
вводит в язык С классы. В данной
статье классы могут рассматриваться как
некий тип записи, вроде структуры или
объединения, но с дополнительными
возможностями. Структуры и объединения
являются просто специальными случая-
ми классов. Две специфические
характеристики классов С++ - составляющие
функции (*1), порождаемые классы -в
сильной степени зависят от существова-
ния области видимости класса
(структуры, объединения).
__________________________
(*1) То есть функции,
которые являются членами класса (member
functions).
прим.переводчика.
Классы С++ могут включать в себя членов
класса, являющихся функциями.
Тело составляющей функции оказывается в области
видимости того класса, чле-
ном которого она является, так как будто блок,
содержащий объявления членов
класса, окружает тело функции (а формальные
параметры функции введены в са-
мый внешний по отношению к телу функции
блок). В примере 1 представлена со-
ставляющая функция. Синтаксическая
конструкция С :: f использует операцию
видимости :: для обозначения того, что
f есть член класса С. Идентификатор
i, упоминаемый в теле функции f,
относится к члену класса C, а не к гло-
бальной переменной i. Функции также
могут быть определены внутри тела клас-
са.
int i;
class C {
int
i;
void f (); (1)
};
void C::f () { ... = i };
В примере (2)
класс С содержит два члена : целую переменную i и функ-
цию f. Описание
дружественной функции (*1) опирается на возможности языка
С++ по упрятыванию
информации, что не относится к теме статьи. Достаточно
заметить, что
дружественная функция не является членом класса С и, таким
образом,
идентификатор i внутри ее тела относится к глобальной переменной
i. Заметим
также, что обе функции могут иметь один и тот же идентификатор,
поскольку они
находятся в разных областях видимости, а составляющая функция
находится в
области видимости класса С, в то время как несоставляющая функ-
ция - в
глобальной области видимости. Семантика составляющей функции f
идентична
семантике составляющей функции примера 1.
int i;
class C {
int i;
(2)
void f () { ... = i; }
friend void f () { ... = i; }
};
Один
класс может быть порожден из другого. Порожденный класс наследует
членов
своего базового класса в добавление к своим собственным членам. Член
базового
класса, однако, не будет виден из порождаемого класса, если тот
же
идентификатор будет использован в порожденном классе. В примере 3 класс
D
порождается из класса B. В теле составляющей функции f значение члена
базо-
вого класса j присваивается члену порождаемого класса i. Порождаемый
класс
находится в области видимости своего базового класса.
class B
{
public:
int i, j;
};
class D : B { (3)
int i;
void f() { i =
j;
}
};
_____________________________________________________________
(*1)
Дружественная функция (friend function) имеет доступ к
членам класса, но сама
не является членом класса.
прим.переводчика.
ВИДИМОСТЬ ИМЕН И
ТАБЛИЦ СИМВОЛОВ.
Подходящая реализация таблицы символов, основанной на
операционном
взгляде видимости имен в компиляторе С++, представляет собой
коллекцию вза-
имосвязанных таблиц, каждая со своей собственной структурой.
Это отличается
от обычного подхода к реализации видимости имен как монолитной
таблицы имен
со сложными правилами доступа и включения.В компиляторе имеются
три вида
таблиц: глобальная, класса и функции.
Каждая таблица
оказывается в области видимости некоторой другой таблицы
и ссылается на эту
таблицу посредством указателя на "родителя". Список таб-
лиц, получаемый при
движении по "родительским" указателям от данной табли-
цы, задает полную
область видимости, в которой существует эта таблица.
1. Глобальная не
имеет родителя. (Равно, имеет "пустого" родителя).
2. Родителем таблицы
непорождаемого класса является глобальная таблица.
Родителем таблицы
порождаемого класса является таблица его базового
класса.
3. Родителем
таблицы несоставляющей функции является глобальная таблица.
Родителем
составляющей функции является таблица класса, членом кото-
рого является
функция.
Пример 4 показывает необходимость гибкой реализации областей
видимос-
ти. Последовательности таблиц, представляющих полные области
видимости в
каждой из точек программы в примере 4 таковы :
1: B,
global
2: f1, global
3: C1, global
4: C2, B, global
5: f2,
global
6: f3, C2, B, global
7: f4, C1, global
Например, в точке 6
область видимости представлена последовательностью
таблиц, состоящей из
таблицы функции f3 таблиц классов С2 и глобальной таб-
лицы.
class B {
/* 1 */ } ;
void f1()
{ /* 2 */
class C1
{ /* 3 */
class C2 :
B
{ /* 4 */ (4)
friend void f2() { /* 5 */ }
void f3() { /* 6 */
}
};
void f4() { /* 7 */ }
};
}
Этот пример показывает, что в
С++ лексическая и семантическая (в виде
восходящей последовательности)
видимость разделены. Например, класс С2, ко-
торый лексически вложен в класс
С1 не находится в области видимости класса
С1, но оказывается на том же
уровне видимости, что и класс С1. Дружествен-
ная функция f2 внутри класса С2
оказывается на глобальном уровне видимости,
но не в области видимости класса
С2. Заметим также, что, хотя функции в С++
могут быть лексически вложенными,
тем не менее в соответствии с правилами
для родительских таблиц невозможно
для одной функции отослаться к записи
активации другой. Поэтому лексическая
вложенность функций не влечет за со-
бой необходимости поддержки видимости во
время исполнения.
При компиляции в каждый момент времени область
семантической видимости
представляется указателем на текущую таблицу.
Достаточно одного указателя,
так как "родитель" в данной таблицы определяется
в момент создания послед-
ней. В примере 4 показана взаимосвязанная структура
таблицы символов в точ-
ке 4 программы примера 4. Сплошные линии представляют
указатели на таблицы,
являющиеся атрибутами имен класса, структуры,
объединения или таблицы для
частично транслированных функций. Пунктирные
линии представляют родительс-
кие связи, формирующие область видимости
программы. "Текущий" указатель ин-
дицирует область видимости в текущий
момент компиляции. В примере С2 - имя
класса, введенное в таблицу, и
являющееся атрибутом функции с именем f1.
Таблица, являющаяся атрибутом имени
С2 в качестве родителя имеет таблицу,
являющуюся атрибутом имени класса
В.
Соответствие между лексической и семантической видимостью
поддержива-
ется стеком лексической видимости. Из соображений эффективности и
модульно-
сти удобно реализовывать стек лексической видимости отдельно от
неявной
стековой поддержки синтаксического анализатора. При входе в новую
область
лексической видимости указатель, представляющий область семантической
види-
мости, засылается в стек. При выходе из области лексической
видимости
предыдущий указатель области семантической видимости выталкивается
из стека.
СТРУКТУРА ТАБЛИЦЫ.
Каждый вид таблицы реализует свою
собственную структуру, включая се-
мантику поиска и включения. Алгоритм
поиска имени внешнего уровня состоит
просто в просмотре таблиц, составляющих
данную область видимости. Каждая
таблица в списке реализует собственную
семантику определения, находится
данное имя в таблице или нет. Например,в
случае простого поиска отдельного
имени список простирается от текущей
таблицы до глобальной. Ссылка вида
p o i n t e r - > m e m b e r влечет те
же действия над списком таблицы,
являющейся атрибутом базового типа p o i n t
e r вплоть до , но не включая,
глобальной таблицы. Использование оператора
видимости, например,
c l a s s n a m e :: m e m b e r , определяет поиск по
списку, начинающему-
ся с таблицы, являющейся атрибутом c l a s s n a m
e.
В самой глобальной таблице реализован простой алгоритм поиска ;
на
глобальнома уровне видимости один и тот же идентификатор не может
использо-
ваться более, чем для одного имени.
В таблицах класса собраны
имена членов класса, структуры или объедине-
ния. Они организованы аналогично
глобальной таблице.
В таблицах функций реализована блочно-структурированный
подход к види-
мости имен. Заметим, что с операционной точки зрения, принятой
компилято-
ром, блок не определяет область видимости ; скорее, блочная
стрктура явля-
ется свойством видимости имен внутри функции.
Реализация
семантики таблицы функции достаточно нетривиальна для объяс-
нения. Блочная
структура реализуется посредством использования заголовков,
связывающих
вместе имена в блоке. Каждый заголовок блока имеет указатель на
заголовок
блока, включающего данный, или пустой указатель (для блока, явля-
ющегося
телом функции). Таблица функции поддерживает указатель на заголовок
активного
на данный момент блока. Последовательность, полученная следовани-
ем по
списку блоков от указателя текущего блока по указателям на включающие
блоки
представляет, таким образом, стек активных в данный момент блоков.
При входев
новый блок резервируется заголовок, указатель на включающий
блок
устанавливается так, чтобы указывать на текущий блок. Новый блок ста-
новится
текущим. При выходе из блока, заголовок текущего блока
становится
неактуальным, а текущим становится блок, включающий данный. Таким
образом,
по мере вхождений в блоки и выходов из них при компиляции функции,
таблица
функции поддерживает n-арное дерево заголовков блоков, представляющих
собой
вложенную структуру рамки стека функции. Восходящая последовательность
в
дереве от указателя текущего блока до корня является стеком активных в
дан-
ный момент блоков. Компилятор впоследствии выполняет просмотр дерева
блоков
в ширину для определения рамки стека функции.
При поиске данного
имени структура блоков обходится за счет обращения
к хэш-таблице. Правила
включения и удаления имен из таблицы гарантируют,
что первое найденное имя с
правильным идентификатором относится к самому
внутреннему
блоку.
ОБСУЖДЕНИЕ.
Вышеописанный подход к проблеме видимости имен в
С++ реализуется опре-
делением таблицы как абстрактного типа данных. В этом
случае динамическая
природа видимости имен во время компиляции может быть
естественным образом
представлена взаимодействием между динамически
создаваемыми объектами обла-
стей видимости.
Представление областей
видимости как объектов позволяет непосредствен-
но отобразить качественно
новые аспекты видимости имен в С++. К примеру,
данный класс может
одновременно быть базовым классом любого количества дру-
гих классов. Если
рассматривать объекты областей видимости как вершины гра-
фа, ребрами
которого являются указатели на таблицыа родителей, описанные
выше, то
иерархия классов B, D1 и D2 в примере 6 явным образом представля-
ется в виде
дерева, узлами которого являются объекты областей видимости.
class B { }
;
class D1 : B { };
void f()
{ (6)
class D2 : B {
};
}
Такое представление позволяет также чисто разделить
лексическую и се-
мантическую видимость. В примере 6 появление области
видимости функции не
ставит объект области видимости функции между D2 и В в
иерархии классов.
Поскольку вся информация о видимости внутри функции
рассматривается как
свойство единого объекта, такое разделение может быть
полностью обеспечено
путем простого помещения объекта области видимости
функции в нужную позицию
на графе. Нет необходимости в сложном алгоритме
поиска, обходящем область
видимости функции при поиске члена класса
D2.
Такая точка зрения на область видимости как объект
проясняет
решение о реализации блочной структуры как свойства
области
видимости функции, нежели представления каждого блока в
виде
отдельной таблицы. Многие свойства функции могут быть
более
естественным путем получен из объекта, реализующего таблицу
функции,
чем из объекта, реализующего таблицу блока. Информация
такого рода, как
структура рамки стека или метки, является
свойством единого объекта,
реализующего таблицу функции, иначе бы
ее необходимо было по частям извлекать
из набора объектов,
реализующих таблицы блоков.
АКТИВАЦИЯ
ДЕСТРУКТОРОВ.
В классах С+ могут быть определены деструкторы. Деструктор
есть вид
составляющей функции, которая неявно активируется для своего
объекта, когда
последний выходит за пределы области видимости.
Последовательность актива-
ции деструкторов для выхода из данной области
видимости обратна по отноше-
нию к последовательности, в которой появлялись
объекты, подлежащие уничто-
жению.
Описание класса в примере 7 содержит
описание деструктора. Именем дес-
труктора является имя класса, которому
предшествует тильда. В функции f ~С
активизируется для объектов c и b перед
оператором c o n t i n u e , для b
и a - перед r e t u r n ; для b - в конце
блока, являющегося оператором при
w h i l e , для a - в конце блока,
являющегося телом функции.
class C
{
~C() { /* код деструктора */
}
};
void f (int i)
{ C a ; (7)
while (i--)
{ C b ;
if
(i)
{ C c
;
...
continue;
}
else
return;
}
}
Задачаа
определения должной последовательности активации деструкторов
для выхода из
данной области видимости создает трудности с точки зрения эф-
фективности
трансляции. Многие С++ программы вообще не используют деструк-
торы, в то
время как в других большинство объектов имеют деструкторы. Под-
ход, принятый
в компиляторе, заключается в том, что эта информация содер-
жится в
структурах данных, отделенных от таблицы символов. Это
соотносит
пространственную и временную сложность определения
последовательностей ак-
тивации деструкторов скорее с числом объектов,
имеющих таковых, чем с общим
количеством имен.
Параллельно каждой таблице
функции компилятор поддерживает древовидную
структуру, описывающую "структуру
деструкторов" этой функции. Таблица сим-
волов содержит указатели на такую
структуру, используемые для извлечения
информации (последовательности
объектов, для которых должны быть активиро-
ваны деструкторы), но само дерево
деструкторов существует независимо от та-
блицы символов.
Вложенные
прямоугольники в левой части примера 8 отображают вложенную
структуру таблицы
функции. Метки d1 - d5 представляют собой появление объ-
екта с деструктором
в данном блоке. Дерево деструкторов, которое будет по-
строено для данной
комбинации вложенных блоков и объектов, приведено в пра-
вой части примера
8.
Каждая таблица функции имеет указатель на соответствующую точку
своего
дерева деструкторов. Текущая точка инициализируется пустым значением.
Когда
появляется объект с имеющим деструктор типом, резервирует элемент
дерева
деструкторов с указателем на объект и указателем на текущую точку в
дереве.
Новый элемент дерева становится затем текущей точкой.
Блочная
структура функции проявляется на дереве деструкторов как побо-
чный эффект от
вхождений и выходов из блока. Каждый заголовок блока имеет
указатель,
устанавливаемый при вхождении в блок на текущую точку дерева де-
структоров.
При выходе из блока текущий указатель переустанавливается на
эту сохраненную
точку. Таким образом, дерево деструкторов создаетсяа так,
чтобы отображать
блочную структуру функции. Заметим также, что дерево дест-
рукторов имеет
размер не более необходимого; оно имеет ровно столькоа уз-
лов, сколько
имеется объектов с деструкторами, независимо от того, из ско-
льких блоков
состоит функция. Корнем дерева деструкторов является пустой
узел.
Подобное
дерево деструкторов создаетсяи для глобальной таблицы для уп-
равления
деструкторами объектов на глобальном уровне видимости, но, поско-
льку
глобальное пространство имен равномерно, дерево всегда будет
простым
списком.
Деструктор для объекта должен быть активирован, когда
поток управления
программы покидает область видимости, в которой объект
определен.
Простой случай происходит, когда поток управления выходит за
пределы
блока (включая блок, являющийся телом функции, и концептуальный блок,
кото-
рым является файл). В этом случае все, что необходимо - это пройти по
спис-
ку узлов от текущей точки дерева до точки, определяемой указателем в
заго-
ловке блока, и сгенерировать код, результатом которого во время
исполнения
будет активация деструкторов. Заметим, что любая корректная
последователь-
ность активации деструкторов является простым списком,
извлеченным из дере-
ва деструкторов. Это следует из того обстоятельства, что
блочная структура
функции отображается на ее дереве деструкторов и что
активные блокив данной
точке функции формируют стек внутри дерева
блоков.
Операторы b r e a k и c o n t i n u e также вызывают выход
из
области видимости, который обрабатывается подобным же образом.
Внутреннее
представление, используемое в компиляторе для b r e a k и c o n t
i-
n u e , содержит указатель на точку в дереве деструкторов, которая
была
текущей в момент, когда был встречен b r e a k или c o n t i n u e.
Де-
структоры, подлежащие активации для объектов до операторов b r e a k
или
c o n t i n u e, находятся в списке от этой точки до точки, записанной
в
заголовке самого внешнего блока, который уходит из области видимости.
(За-
метим, что это всегда граница блока) Активация деструкторов для
оператора
r e t u r n подобна; активируются все деструкторы от точки,
соответствующей
оператору r e t u r n до корня дерева деструкторов. Активация
деструкто-
ров для оператора g o t o является более трудоемкой, так как
переход не
имеет никакого отношения к блочной структуре функции. Рассмотрим
фрагмент
кода в примере 9. Если С есть класс с деструктором, активация
деструктора
должна быть внедрена перед оператором g o t o . (Заметим, что С++
, в отли-
чие от С, рассматривает описание как оператор).
label: C
obj;
... (9)
goto label;
Проблема состоит в определении пути по
дереву деструкторов, которым
следует оператор g o t o к своей цели, и
активации деструкторов для тех
объектов в дереве, которые располагаются на
восходящих участках пути. На-
пример, если g o t o передает управление на
метку на внешнем уровне вложен-
ности, весь путь будет восходящим, если g o t
o передает управление на вну-
тренний уровень, никакая часть пути не будет
восходящей. При передаче упра-
вления между несвязанными областями видимости
проблема состоит в нахождении
ближайшего общего предка в дереве деструкторов
для оператора g o t o и мет-
кой и активации деструкторов на пути от g o t o
к этой точке. Первые два
случая являются вырожденными вариантами
последнего.
Реализация включает установку указателей на текущую точку дерева
дест-
рукторов во внутреннем представлении для g o t o и меток, и нахождении
бли-
жайшего общего предка в дереве
деструкторов.
ЗАКЛЮЧЕНИЕ
Комбинация формализации видимости имени
свойств классов в C+ требует
структуры областей видимости, которая слишком
сложна, чтобы ее легко можно
было выразитьс помощью обычной таблицы символов
языка С. Подход, принятый в
компиляторе, заключается в определении различных
видов областей видимостии
заключении их в объекты. Структуры областей
видимости С++ программы просто
и эффективно представляются взаимодействием
между такими объектами. Добива-
ясь подобного же упрощения, отношение
объектов программы, имеющих деструк-
торы, к блочной структуре функций
изолировано в структуре данных, независи-
мых от остальной таблицы символов.
Такое разделение позволяет уменьшить
временные и пространственные издержки по
определению последовательности ак-
тивации деструкторов, так как только
объекты с деструкторами должны быть
представлены в дереве, и только та
информация о видимости, которая касается
взаимного расположения узлов в
дереве деструкторов, является необходимой.
<<< Назад |
|
|
|
|
