Рис. Н.З

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

Часто (в зависимости от компилируемого языка) проблема построения и поиска в таблицах символов в компиляторе оказывается гораздо сложнее, чем мы ее себе представляем. Как отмечалось в гл. 6, большинство современных языков имеет блочную структуру, причем различные блоки могут содержать реализации одного и того же идентификатора, но (: разными значениями. Например, мы можем написать следующую программу на Алголе 68:

Ье(>1п иат : = 4; Ьедн! сНаг т = ~а";

рпп! (т) еоА:

Ьет т! т : = 1,

рпп1 (т) еай:

ргйа (т)

и выходом будет

А i 4

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

Осложнение возникает и в связи с тем, что во многих языках, таких, как Алгол 68 (но не Паскаль), идентификаторы могут появляться в тексте, прежде чем они описываются. В результате компилятор строит таблицу символов за один проход, н только при последующем" проходе или проходах в ней осуществляется поиск. Допустим, что /4 помещает

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

1еияа. ге!

где - это

1а§ - целочисленное представление идентификатора (в предположении, что лексический анализ уже прошел), а 1уре - его тип (или вид}.-Каждый блок соответствует элементу массива ЫаЪ, описанному как

[/ : п]ЫаЫе ЫаЬ

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

Во время компиляции при входе в блок при проходе А выполняется инициализация элемента ЫаЬ следующим образом:

ЫаЬ \Ьп р)и5эЬ /] : (1 п р!и«аЬ /, пН)

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

1п тшичаЬ /

Когда встречается описание идентификатора Штипа 1урек1, выполняется действие

и1Кх1 о\ ЫаЬ \Ьп\: = \клу \к\: = (1<1, 1уреи1, йШз! о[ ЫаЬ [Ьп\\

где Ьеар - «генератор», выделяющий место для другого элемента

П&1. Порядок идентификаторов в Н$1 обратеп тому порядку, в котором соответствующие описания появлялись в программе. Как указывалось в разд. 6.2, можно проверить, не описывался ли уже идентификатор в блоке.

Для приводимой ниже программы:

Ьоат т! а. ь, <•:

г!, I1,./;

Ьецш ш! а, (>; геа! с, <1\ еш)

соответствующая таблица будет выглядеть так, как показано на рис. 8,4. В Алголе 68 можно также описывать объекты, их виды и знаки операций, специфицируемые пользователем, и в каждой записи ЫаЬ должны также содержаться списки этих объектов и их видов.

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

Рис. 84

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

Блок О

Рис. 8.5

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

тойе 5(-51гис1 (т* 1еипо, ге! [ ]51еп1гу 51е, гс[ 51 пех!)

где я1еп1гу описывается как

тоА; 5(сп(гу-51гие1 (т! !а§, 1уре) Идентификатор 57" описывается (и инициализируется) так;

М( 51 5 Т :=- ш!

При входе в блок выполняется следующее действие;

57" := (1а р!ияаЬ /, геаЛМз. 57") где 1п -номер уровня блока, а геайШ - процедура чтения иденти-

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

5Г := п?*1 Ы 6Г. /п гшлизаЬ /

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

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

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

Рис. 8.7

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

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

8.2. ТАБЛИЦА ВИДОВ

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

1. Основные виды, например т1, геа1, сКаг, Ьоо1.

2. Длинные и короткие виды, которые содержат символ !опЁ или зпог1, появляющийся несколько раз перед некоторыми основными ви дами, например

геа!, ш!

3. Именные виды, состоящие из символа геЕ и следующего за

вида, например

ге[ 1опс 1м!

Значение именного вида можно представить как имя (в терминах Алгола 68) или как адрес значения вида, следующего за ге1.

4. Структурные виды, представленные символом з4п1С( и последо вательностью полей; каждое поле имеет вид и селектор, заключенные в скобки, например

Структурные виды соответствуют записям или структурам в других языках.

5. Виды массивов, представленные с помощью [ 1, [,1 или [,,1 и т. д. и следующего за этим вида, например

! >еа!

Они используются для выражения значений вида гот из \п1 (одномерного массива) или готя-гот из 1опд геа! (двумерного массива).

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

ишоп (геа1, т!)

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

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

ргос {геа1, гса!) !п1

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

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

I [ОПЁ геа! ге! г*! 1п1 ге( ге( Ьоо!

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

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

ргос (геа1, Го()Ьоо1

выражающий значение вида «процедура-с-вещественным;парамет-ром-и - целочисленным-параметром-дающая-логический-результат», может быть представлен структурой с отдельными указателями на список параметров и результат (рис. 8.8). Аналогичным образом вид

$1гис( (1п1 I, 5(гис( (т( /. Ьоо! у), геа! П

может быть представлен так, как показано на рис. 8.9, а вид

оп (геа1, $(гис! (ш1 (, Ьоо! й)

Рис. 8.8