Дизайн компилятора - таблица символов

Таблица символов - это важная структура данных, созданная и поддерживаемая компиляторами для хранения информации о появлении различных объектов, таких как имена переменных, имена функций, объекты, классы, интерфейсы и т. Д. Таблица символов используется как для анализа, так и для синтеза. части компилятора.

Таблица символов может служить следующим целям в зависимости от используемого языка:

  • Хранить имена всех сущностей в структурированной форме в одном месте.

  • Чтобы проверить, была ли объявлена переменная.

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

  • Определить область имени (разрешение области).

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

<symbol name,  type,  attribute>

Например, если таблица символов должна хранить информацию о следующем объявлении переменной:

static int interest;

тогда он должен хранить запись, такую как:

<interest, int, static>

Предложение атрибута содержит записи, связанные с именем.

Реализация

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

  • Линейный (отсортированный или несортированный) список
  • Двоичное дерево поиска
  • Хеш-таблица

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

операции

Таблица символов, либо линейная, либо хэш-функция, должна обеспечивать следующие операции.

вставка ()

Эта операция чаще используется на этапе анализа, т. Е. В первой половине компилятора, где идентифицируются токены и имена хранятся в таблице. Эта операция используется для добавления в таблицу символов информации об уникальных именах, встречающихся в исходном коде. Формат или структура, в которой хранятся имена, зависит от используемого компилятора.

Атрибутом символа в исходном коде является информация, связанная с этим символом. Эта информация содержит значение, состояние, область и тип символа. Функция insert () принимает символ и его атрибуты в качестве аргументов и сохраняет информацию в таблице символов.

Например:

int a;

должен обрабатываться компилятором как:

insert(a, int);

Погляди()

Операция lookup () используется для поиска имени в таблице символов для определения:

  • если символ существует в таблице.
  • если он объявлен до его использования.
  • если имя используется в области.
  • если символ инициализирован.
  • если символ объявлен несколько раз.

Формат функции lookup () зависит от языка программирования. Базовый формат должен соответствовать следующему:

lookup(symbol)

Этот метод возвращает 0 (ноль), если символ не существует в таблице символов. Если символ существует в таблице символов, он возвращает свои атрибуты, хранящиеся в таблице.

Управление областью

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

Чтобы определить область имени, таблицы символов расположены в иерархической структуре, как показано в примере ниже:

. . . 
int value=10;

void pro_one()
   {
   int one_1;
   int one_2;
   
      {              \
      int one_3;      |_  inner scope 1 
      int one_4;      | 
      }              /
      
   int one_5; 
   
      {              \   
      int one_6;      |_  inner scope 2
      int one_7;      |
      }              /
   }
   
void pro_two()
   {
   int two_1;
   int two_2;
   
      {              \
      int two_3;      |_  inner scope 3
      int two_4;      |
      }              /
      
   int two_5;
   }
. . . 

Вышеуказанная программа может быть представлена в иерархической структуре таблиц символов:

Таблица символов

Глобальная таблица символов содержит имена для одной глобальной переменной (значение int) и двух имен процедур, которые должны быть доступны для всех дочерних узлов, показанных выше. Имена, упомянутые в таблице символов pro_one (и всех ее дочерних таблицах), недоступны для символов pro_two и его дочерних таблиц.

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

  • Сначала будет выполнен поиск символа в текущей области видимости, то есть в текущей таблице символов.

  • если имя найдено, то поиск будет завершен, иначе он будет найден в таблице родительских символов до тех пор, пока

  • либо имя найдено, либо имя таблицы было найдено в глобальной таблице символов.