int а

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

а:=4 или а + b или read (a) и здесь а будут прикладными реализациями.

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

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

begin int a:

end;

begin char a

end .

В первом блоке а имеет вид ref int в Алголе 68 (т. е. ее значение относится к объекту вида int), а во втором- ref char. Так, в этих двух блоках а представляет два разнтх объекта.

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

1. Определяющая реализация идентификатора появляется (текстуально) раньше любой прикладной реализации.

2. Все описания в блоке помещаются непосредственно за begin, т. е. раньше всех операторов или предложений.

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

4. В одном и том же блоке идентификатор не может описываться более одного

раза.

Свойства 3 и 4 присущи практически всем языкам с блочной структурой, свойство 2 характерно для Алгола 60, а свойство 1 представляет собой ограничение, имеющееся в некотортх реализациях этого языка.

Допустим, что синтаксис описаний идентификаторов задается правилами:

DEC -real IDSinteger IDS boolean IDS IDS -id IDS -IDS, id а блок определяется как BLOCK-begin DECS; STATS end

DECS -DECS; DEC DECS-> DEC STATS-STATS;s STATS-s

Таблица символов может иметь такую структуру, как показано ни в любой

betr-

Put- (i I

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

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

mode btab = struct (int leuno, ref idlist idl, ref btab next) mode idlist = struct (int id, type, ref idlist next id)

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

ref btab bptr := nil (нулевой указатель) и выполняются действия, связанные с входом в блок и втходом из него:

BLOCK-begin <AI> DECS; STATS<A2>end

<A1>

bptr := heap btab := (In plusab 1, nil, bptr)

Здесь In представляет номер уровня текущего блока (т.е. глубину вложения) и первоначально является нулем.

<А2>

begin In minusab 1; bptr : = next of bptr end

Предусмотрено также действие для каждой определяющей реализации идентификатора. Это действие появляется в грамматике следующим образом: IDS -id<A3>

IDS, id<A3>

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

Это действие таково:

(A3)

begin ref idlist pnil = nil ; ref idlist ptr : = idl of bptr; bool error : = false ; while pir isnl pnil do

if id of ptr = iden then error : = true ; ptr : = pnil

ptr := next id of ptr od;

if error then print ( ("identifier", iden,"already declared")) else idl of bptr : = heap idlist : = (iden, type, idl of bptr) fi

iden - имя идентификатора, type - его тип. Здесь проверяется, был ли идентификатор уже описан в блоке или нет.

С прикладной реализацией идентификатора связано действие А4, которое отыскивает в таблице символов тип идентификатора:

A4>

begin bool found := false; ref idlist pnil = nil ; ref btab bnil = nil; ref btab b: = bptr; while b isnt bnil and not found do ref idlist ptr : = idl of b ;

while ptr isnt pnil and not found

if id of ptr= iden then type := type of ptr: found : - true fi;

ptr := next id of ptr od;

ft : = next of b od;

if not found

then print ("identifier not dec/ami"):

idl of bptr : = heap idlist : = (iden, default type, idl of hptr):

type : = default tvpe

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

На этом мы завершаем рассмотрение операций, производимтх с таблицей символов, которые требуются для нашего простого языка.

В таблице символов настоящего компилятора может содержаться другая