Автор: В.А.Серебряков

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

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

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

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

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

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

 +---------------------------------------+
 |                                       |
 |---------------------------------------|
 | s | o | r | t |   |   |   |   |   |   |<----
 |---+---+---+---+---+---+---+---+---+---|
 | a |   |   |   |   |   |   |   |   |   |<----
 |---+---+---+---+---+---+---+---+---+---|
 | r | e | a | d |   |   |   |   |   |   |<----
 |---+---+---+---+---+---+---+---+---+---|
 | i |   |   |   |   |   |   |   |   |   |<----
 |---------------------------------------|
 |                                       |
 +---------------------------------------+

                  Рис. 7.1

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

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

1) h2(i)=(i+1) mod N

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

2) h2(i)=(i+k) mod N, где k и N взаимно просты.

По-существу это предыдущий вариант, но элементы накапливаются не в последовательных элементах, а "разносятся".

3) h2(i)=(a*i+c) mod N - "псевдослучайная последовательность".

Здесь c и N должны быть взаимно просты, b=а-1 кратно p для любого простого p, являщегося делителем N, b кратно 4, если N кратно 4 [6]. Поиск в таблице можно описать следующим алгоритмом:

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;

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

     +-------------------------------------
     |                  +------------------
     |                  |       +----------
     |                  |       |    +-----
     |                  |       |    |
     |                  |       |    +--------------+
     |                  |       |                   |
     v                  v       v                   v
----------------------------------------------------------+
  | s | o | r | t |EOS| a |EOS| r | e | a | d |EOS| i |EOS|
----------------------------------------------------------+

                          Рис. 7.2

     +---+
   0 |   |
     |---|
     |...|
     |---|   +----------+   +--------+
   9 | --+-->| Idenp |--+-->|    | x |
     |---|   +----------+   +--------+
     |---|      v            v
     |...|    Указатели на идентификаторы
     |---|   +------------+
  20 | --+-->| Idenp |  x |
     |---|   +------------+
     |---|      v
     |...|    Указатель на идентификатор
     |---|   +--------+   +--------+   +-------+
  32 | --+-->|    |  -+-->|    |  -+-->|   | x |
     |---|   +--------+   +--------+   +-------+
     |...|      v            v
     |---|     Указатели на идентификаторы
 210 |   |

              Рис. 7.3

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

Рассмотрим организацию таблицы символов с помощью таблицы расстановки. Таблица расстановки - это массив указателей на списки указателей на идентификаторы. В каждый такой список входят указатели на идентификаторы, имеющие одно значение функции расстановки (рис. 7.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;

             |--|       +------+      +------+
      H----->| -+-x---->|      |----->|      |----->
             |--| | +-->+------+      +------+
             |  | | |
             |--| | +------------+
                  |   +------+   |
                  +---|      |---+
            P-------->+------+

                         Рис. 7.4.

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

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

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

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

2. Преобразуем H, вычисленное выше, в номер списка, т.е. целое между 0 и m-1, где m - размер таблицы расстановки, например, взятием остатка при делении H на m. Функции расстановки, учитывающие все символы строки, распределяют лучше, чем функции, учитывающие только несколько символов, например в конце или середине строки. Но такие функции требуют больше вычислений. Простейший способ вычисления H - сложение кодов символов строки. Перед сложением с очередным символом можно умножить старое значение H на константу q. Т.е. полагаем H0=0, Hi=q*Hi- 1+ci для 1<=i<=k, k - длина строки. При q=1 получаем простое сложение символов. Вместо сложения можно выполнять сложение ci и q*Hi-1 по модулю 2. Переполнение при выполнении арифметических операций можно игнорировать. Функция Hashpjw, приведенная ниже [1], вычисляется, начиная с 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;
 }
         Рис. 7.5

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

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

        +---------------+
 TP --->|    |    |    -+--->Ident
        +-/----\--------+
         /      \
        v        v
      Left     Right

            Рис. 7.6

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

function SearchTree(Id,TP):Pointer;
 begin if Id=TP^.Ident then return(TP)
       elsif IdTP^Ident
          then return(Search_tree(Id,TP^.Right))
       else return(nil)
 end   end;

Занесение в таблицу осуществляется процедурой

function Insert_tree(Id,TP):Pointer;
 function fill(var P):Pointer;
 begin if P=nil then
         P:=new(Element);
         P^.Ident:=include(Id);
         P^.Left:=nil; P^.Right:=nil;
         return(P);
       else return(Insert_tree(Id,P))
 end   end;
 begin if Id=TP^.Ident then return(TP)
       elsif Id|   | -+----->|   | -+---->|   |   |
         +------+      +------+     +-------+
             T1           T2           Tn

                   Рис. 7.11

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

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