Главная
страница 1


4. Семантический анализ

Семантический анализ является наименее формализуемой частью процесса трансляции, поскольку касается “смысла” тех конструкций языка, которые анализируются на этапах лексического и синтаксического анализа. Если же подходить к этому процессу с точки зрения “здравого смысла”, то транслятор должен построить в процессе трансляции в памяти некоторую структуру данных, в которой зафиксировать все смысловые (семантические) взаимоотношения между объектами программы. Обычно объектами программы являются типы, переменные и функции (процедуры), которые обозначаются именами (идентификаторами). Для них уже на этапе лексического анализа может быть составлена таблица, которая на этапе семантического анализа дополняется данными о семантике объектов. Отсюда вырисовывается общая схема взаимодействия фаз транслятора:



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

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

  • в процессе синтаксического анализа, при “свертывании” правила, в котором в качестве терминалов фигурируют имена, вызывается семантическая процедура, соответствующая этому правилу. Она должна получить ссылки на эти имена из соответствующих лексем;

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

  • фаза генерации кода или интерпретации обычно выполняется в виде такой же процедуры, как семантический анализ, в тех же самых условиях - в момент “свертки” правой части правила.

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

Пример: 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

s+=GetSize(&(p>child[i]));

return s;

// Размерность объединения – максимальная размерность элемента

case STRU:

int s,i,k;

for (s=0,i=0; i

{ k=GetSize(&(p->child[i])); if (k>s) s=k; }

return s;

}}
Содержание семантической таблицы для переменной естественным образом вытекает из ее основных свойств в языке и может включать в себя:


  • имя переменной;

  • указатель на описание типа в таблице типов;

  • смещение (адрес), который получает эта переменная при трансляции в том сегменте данных, где она размещается компилятором;

  • указатель на область памяти, где размещаются ее значение – для интерпретатора.

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

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

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

Понятие L-value

К семантическому анализу имеет отношение и понятие l-value, характеризующее некоторый “тонкий” семантический смысл выражения, которое касается способа формирования его значения. Если происходит анализ и свертка правила, соответствующего некоторой операции, то у транслятора существуют два способа формирования ее результата:



  • в виде нового объекта-значения. В таком случае транслятором должна быть “заведена” его семантика в виде некоторого внутреннего объекта, создаваемого в процессе работы программы;

  • в виде объекта-операнда или его части. В таком случае семантика этого объекта-результата включает в себя неявный указатель (ссылку) на “исходный” объект. Такой результат операции называется l-value, от слова LEFT, что означает, что данное выражение может стоять в левой части операции (оператора) присваивания.

Общая стратегия транслятора должна состоять в том, что он должен сохранять результат в виде l-value до тех пор, пока не встретится операция, в которой он не в состоянии это сделать. Тогда уже он может переходить к значениям - промежуточным объектам. Рассмотрим ряд примеров для Си-компилятора, проиллюстрировав внутреннее представление выражения через l-value средствами того же Си.

.

Выражение Код компилятора Примечание



B[i] &B[i] l-value

B[i].money &(B[i].name) l-value

B[i].money+5 x=(*&B[i].money)+5 транслятор поддерживает

признак l-value для



выражения до операции “+”


Романов Е.Л. Основы построения трансляторов. (конспект лекций) .



Смотрите также:
Античные мифологические оперные сюжеты в контексте культуры первой половины ХХ века семантический анализ
628.69kb.
3 стр.
Учебно-исследовательских работ по английскому языку для учащихся 10-11 класса
59.84kb.
1 стр.
Вступительного экзамена в аспирантуру мгимо (У) мид РФ по специальности 10. 02. 04 – германские языки (английская филология) при кафедре английского языка №1
35.14kb.
1 стр.
4. Семантический анализ
86.2kb.
1 стр.
Специфика идиостиля ю. Полякова (лексико-семантический аспект)
357.74kb.
1 стр.
Новые наименования лиц на рынке труда (структурно-семантический и функциональный аспекты)
320.62kb.
1 стр.
Функционально-семантический статус экзотических лексем в разноструктурных языках 10. 02. 20 Сравнительно-историческое, типологическое и сопоставительное языкознание
319.85kb.
1 стр.
Системный и компонентный анализ бизнес-среды организации
167.36kb.
1 стр.
«сленг в средствах массовой информации: функционально-семантический аспект
40.03kb.
1 стр.
Творчество Осипа Мандельштама входило в японское культурное пространство не сразу, а постепенно, отдельными стихотворениями. «Камень» (1923 г.) О. Мандельштама первый сборник
37.24kb.
1 стр.
Газпромбанк
208.37kb.
1 стр.
Лао цзы Дао Дэ Цзин «Чжyцзы цзичэн»: Шанхай; 1954
1341.2kb.
6 стр.