Учебники

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

Июнь 28, 2018

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

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

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

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

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

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

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

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

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

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

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

<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 и его дочерних таблиц.

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

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

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

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

73
Share: