Пример: cемантика данных для Си-компилятора
Рассмотрим, как можно представить семантику переменных и типов данных (ТД) для языка Си. Прежде всего, условимся, что все типы данных, явно или неявно определяемые в программе, будут размещаться в таблице (массиве) TYPES. Элементом этого массива является структура, которая содержит описание ТД (d_type). Компонентами этой структуры являются:
- name - имя ТД. Если этот ТД является базовым, то его имя инициализировано в таблице. Если это ТД определяется в спецификаторе typedef, то оно берется из определения. Кроме того, в контексте часто определяются ТД для переменных, а также абстрактные ТД, которые не имеют имени – для них имя содержит пустую строку;
- size - размерность памяти под ТД в байтах. Каждый ТД в Си имеет фиксированную размерность, которая используется для создания переменных такого типа;
- TYPE – идентификатор текущего ТД. Если ТД является базовым, то он идентифицируется значением BTD. Если это производный ТД, то он обычно представляет собой цепочку (или дерево) вложенных друг в друга ТД, Текущий ТД может быть указателем (PTR), массивом (ARR), структурой (STRU) или объединением (UNI) (функции здесь не рассматриваются).
- child – указатель на описание вложенного (составляющего) ТД. Для всех ТД, кроме структуры и объединения, имеется единственный составляющий ТД, на который ссылается указатель. Для структурированного типа указатель ссылается на массив описателей составляющих ТД;
- dim – количество элементов в составляющем ТД или его описании. Если текущий ТД – массив, то это количество его элементов, а child указывает на единственный описатель вложенного ТД. Если это структура или объединение, то dim определяет количество элементов структуры, а child указывает на массив описателей этих элементов;
- В следующем примере семантическая сеть для различных ТД задана с помощью инициализации, чтобы по ней можно было показать, каким образом определения различных ТД сохраняются в семантических таблицах.
Реально же инициализируются только описания базовых ТД, остальные строятся динамически в процессе семантического анализа явных и контекстных определений типов.
#define BTD 0
#define PTR 1
#define STRU 2
#define UNI 3
#define ARR 4
struct d_type
{
char name[20]; // Имя ТД
int size; // Размерность памяти ТД в байтах
int dim; // Количество элементов вложенного ТД
int TYPE; // Идентификатор типа
d_type *child; // Вложенный ТД (один или несколько)
};
extern d_type TYPES[100];
// Определение полей структурированного типа man
d_type XXX[]=
{‘name’, 20, 20, ARR, &TYPES[0]}, // char name[20];
{‘addr’, 2, 0, PTR, &TYPES[3]}, // char *addr;
{‘class’, 2, 2, BTD, &TYPES[1]}; // int class;
d_type TYPES[100] =
// Определение БТД
{“char”, 1, 0, BTD, NULL},
{“int”, 2, 0, BTD, NULL},
{‘long’, 4, 0, BTD, NULL},
// Неявное определение ТД или абстрактный ТД char*
{“”, 2, 0, PTR, &TYPES[0]},
// Явное определение ТД typedef char *PSTR
{“PSTR”, 2, 0, PTR &TYPES[0]},
// Неявное определение ТД или абстрактный ТД int [20];
{“”, 40, 20, ARR, &TYPES[1]},
// Определение структурированного типа man
{“man”, 24, 3, STRU, &XXX};
Понятно, что программы, работающие даже с такой семантической сетью, будут достаточно сложны. В качестве примера приведем программу, которая подсчитывает для произвольного ТД его размерность памяти в байтах с учетом всех вложенных в него ТД. Поскольку структурированный ТД предполагает ветвление семантической сети, то такая программа будет в добавок ко всему и рекурсивной.
int GetSize(d_type *p)
{
switch (p->TYPE)
{
// Размерность БТД фиксирована
case BTD: return p->size;
// Размерность указателя постоянна
case PTR: return 2;
// Размерность массива – произведение числа элементов
// на размерность вложенного ТД
case ARR: return dim * GetSize(p->child);
// Размерность структуры – сумма размерностей элементов
case STRU:
int s,i;
for (s=0,i=0; i<dim; i++)
s+=GetSize(&(p>child[i]));
return s;
// Размерность объединения – максимальная размерность элемента
case STRU:
int s,i,k;
for (s=0,i=0; i<dim; i++)
{ k=GetSize(&(p->child[i])); if (k>s) s=k; }
return s;
}}
Содержание семантической таблицы для переменной естественным образом вытекает из ее основных свойств в языке и может включать в себя:
- имя переменной;
- указатель на описание типа в таблице типов;
- смещение (адрес), который получает эта переменная при трансляции в том сегменте данных, где она размещается компилятором;
- указатель на область памяти, где размещаются ее значение – для интерпретатора.
Анализ семантики переменных при таком подходе может выглядеть следующим образом:
- при синтаксическом анализе правил определений и объявлений переменных семантическими процедурами параллельно строится семантическая сеть и заполняется таблица типов, в описание переменной в таблице переменных включается указатель на ее тип;
- при синтаксическом анализе правил построения выражений для заданной переменной семантические процедуры параллельно проверяют соответствие текущей операции текущему типу данных в семантической сети. Результат операции также получает указатель на элемент семантической сети, таким образом он связывается со своим типом данных для следующей операции.
