Автоматно-лингвистические и алгоритмические основы разработки и программной реализации трансляторов, компиляторов и интерпретаторов

2004 г.

Глава 7. Организация таблиц символов компилятора

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

7.1. Таблицы идентификаторов и таблицы символов

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

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

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

7.2. Таблицы идентификаторов

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

Рис. 6.1

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

Пусть число элементов массива равно N. Определим некоторую функцию h (первичную функцию рас-становки), определенную на множестве идентификаторов и принимающую значения id - идентификатор. Если элемент таблицы h(id) свободен, то это означает, что идентификатора в таблице нет. Если же занят, то это еще не означает, что идентификатор id в таблицу занесен, поскольку (вообще говоря) много идентификаторов могут иметь одно и то же значение функции расстановки. Для того чтобы определить, нашли ли мы нужный идентификатор, сравниваем id с элементом таблицы h(id). Если они равны - идентификатор нашли, если нет - надо продолжать поиск дальше. Для этого вычисляют вторичную функцию расстановки h₂(h). Вновь возможны четыре варианта: либо элемент таблицы свободен, либо нашли идентификатор, либо таблица вся просмотрена и идентификатора нет, либо надо продолжать поиск. Для продолжения поиска приме-няют вновь функцию h₃(h₂), и т.д. Как правило, h_i=h₂ для i2. Аргументом функции h₂ является целое в диапазоне [0,N-1] и она может быть устроена по-разному. Приведем три варианта.

h₂(i) = (i+1) modN. Берется следующий (циклически) элемент массива. Этот вариант плох тем, что занятые элементы "группируются", образуют последовательные занятые участки и в пределах этого уча-стка поиск становится по-существу линейным.
h₂(i) = (i+k) modN, где k и N взаимно просты. По-существу это предыдущий вариант, но элемен-ты накапливаются не в последовательных элементах, а "разносятся".
h₂(i) = (a*i+c) modN - "псевдослучайная последовательность". Здесь c и N должны быть взаимно просты, b=a-1 кратно p для любого простого p, являщегося делителем N, b кратно 4, если N кратно 4. Поиск в таблице можно описать следующим алгоритмом:

type Pair = record 
              Yes   : boolean;
              Point : integer
            end;
function Search( id ) : Pair;
  var H, H0 : integer;
begin 
  H  := h( id ); H0 := h;
  loop 
    if T[ H ] = id 
    then return( TRUE, H )
    elsif T[ H ] = Empty 
    then return( FALSE, H )
    else H := h2( H );
    if H = H0 
    then return( FALSE, NIL )
    end
    end 
  end 
end;

Алгоритм вырабатывает:

(TRUE,P), если нашли требуемый идентификатор, P - указатель на него;
(FALSE,NIL), если искомого идентификатора нет и в таблице нет свободного места;
(FALSE,P), если искомого идентификатора нет, но в таблице есть свободный вход P.

Занесение идентификатора в таблицу осуществляется следующим алгоритмом:

function Insert( id ) : integer;
  var P : Pair;
begin 
  P := search( id );
  with P do
    if not Yes and Point <> NIL
    then T[ Point ] := id
    end;
    return( Point )
  end 
end;

Второй способ организации таблицы идентификаторов- хранение идентификаторов в сплошном массиве символов. В этом случае идентификатору соответствует номер его первого символа в этом массиве, как это изображено на рис.6.2. Идентификатор в массиве заканчивается каким-либо специальным символом (EOS). Второй возможный вариант - в качестве первого символа идентификатора в массив заносится его длина. Для организации поиска в таком массиве создается таблица расстановки (рис.6.3).

7.3. Таблицы символов и таблицы расстановки

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

Вначале таблица расстановки пуста (все элементы имеют значение NIL). При поиске идентификатора id вычисляется функция расстановки H(id) и просматривается линейный список T[H]. Поиск в таблице может быть описан следующей процедурой:

type Element = record 
                 IdenP : integer;
                 Next  : pointer to Element;
               end;
     Pointer = pointer to Element
function Search( id ) : Pointer;
  var P : Pointer;
begin 
  P := T[ H( id ) ];
  loop 
    if P = NIL 
    then return( NIL )
    elsif IdenTab[ P^.IdenP ] = id 
    then return( P )
    else P := P^.Next
    end  
  end 
end;

IdenTab - таблица идентификаторов. Занесение объекта в таблицу может осуществляться следующей процеду-рой:

function Insert( id ) : Pointer;
  var P, H : Pointer;
begin 
  P := Search( id );
  if P <> NIL 
  then return( P )
  else H := H( id ); 
  new( P );
  P^.Next := T[ H ];
  T[ H ] := P;
  P^.Idenp := Include( id )
  end;
  return( P )
 end;

Процедура Include заносит идентификатор в таблицу идентификаторов. Алгоритм иллюстрируется рис.6.4.

7.4. Функции расстановки

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

По символам строки s определяем положительное целое H. Преобразование одиночных символов в целые обычно можно сделать средствами языка реализации. В Паскале для этого служит функция ord, в Си при выполнении арифметических операций символьные значения трактуются как целые.
Преобразуем H, вычисленное выше, в номер списка, т.е. целое между 0 и m-1, где m - размер таблицы расстановки, например, взятием остатка при делении H на m. Функции расстановки, учитывающие все символы строки, распределяют лучше, чем функции, учитывающие только несколько символов, например в конце или середине строки. Но такие функции требуют больше вычислений.

Простейший способ вычисления H - сложение кодов символов строки. Перед сложением с очередным символом можно умножить старое значение H на константу q. Т.е. полагаем H₀=0, H_i=q*H_i-1+c_i для , k - длина строки. При q=1 получаем простое сложение символов. Вместо сложения можно выполнять (сложение по модулю 2). Переполнение при выполнении арифметических операций можно игнорировать.

Функция Hashpjw, приведенная ниже, вычисляется, начиная с H=0. Для каждого символа c сдвигаем биты H на 4 позиции влево и добавляем c. Если какой-нибудь из четырех старших бит H равен 1, сдвигаем эти 4 бита на 24 разряда вправо, затем складываем по модулю 2 с H и устанавливаем в 0 каждый из четырех старших бит, равных 1.

#define PRIME 211
#define EOS '\0'
int Hashpjw(s)
char *s;
{ char *p;
unsigned H=0, g;
for (p=s; *p != EOS; p=p+1)
 {H=(H< < 4)+(*p);
   if (g = H & 0xf0000000)
      {H=H^(g>>24);
      H=H^g;
 }    }
return H%PRIME;
}

Рис. 6.5

7.5. Таблицы на деревьях

Рассмотрим еще один способ организации таблиц с использованием двоичных деревьев. Будем считать, что на множестве идентификаторов задан некоторый линейный порядок (например, лексикографический), т.е. задано некоторое отношение '<', транзитивное, антисимметричное и антирефлексивное. Каждой вершине двоичного дерева, представляющего таблицу символов, сопоставлен идентификатор. Вершина может иметь нуль, одного (правого или левого) или двух (правого и левого) потомков. Если вершина имеет левого потомка, то идентификатор, сопоставленный левому потомку, меньше идентификатора, сопоставленного самой вершине; если имеет правого потомка, то ее идентификатор больше. Элемент таблицы изображен на рис.6.6.

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

7.7. Сравнение различных методов реализации таблиц

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

Назад Вперед