Лекции по конструированию компиляторов. В.А. Серебряков (1134688), страница 14
Текст из файла (страница 14)
В этом случае Imp_Set<0> - множество импортируемыхиз него объектов. Идентификатор включается в список импорта из модуля,иначе идентификатор - имя модуля и он включается в списокимпортируемых модулей. Если импорт квалифицированный, включить всписок импорта модуля весь список импортируемых объектов.RULEFrom ::= 'from'SEMANTICSQual<0>=true;Name<0>=Val<2>.IdentRULEExport ::= 'export' [ Qual ] ( Ident /',' )SEMANTICS0: Init(Entry<Mod_Head>->Exp_Set);2Е: Mode<2>=NotQual;Mode<0>=Mode<2>;3A: Include(Val<3>,Entry<Mod_Head>->Exp_Set).Включить идентификатор в экспортный список модуля; множествоэкспортируемых модулем объектов заносится в поле Exp_Set : Key NameSet Of Element в таблице объектов, поскольку при использованииквалифицированного импорта или обращении M.V, где M - имя модуля, аV - имя экспортируемого объекта, необходимо иметь доступ к спискуквалифицированного экспорта.RULEQual ::= 'qualified'85SEMANTICSQual<0>=Qualified.RULEDeclaration ::= 'var' ( Var_Decl ).RULEVar_Decl ::= Ident_List ':' Type_Des ';'SEMANTICSElement V;for (V in Ident_Set<1>){if (Find(V,Env<Block>)!=NULL)Error("Identifire declared twice");V.Object=VarObject;V.Type=Exit<3>;Include(V,Env<Block>)}.V - рабочая переменная для элементов списка.
Для каждогоидентификатора из множества Ident_Set<1> сформировать объектпеременную в текущей компоненте среды с соответствующимихарактеристиками.RULEIdent_List ::= ( Ident /',' )SEMANTICS0:Init(Ident_Set<0>);1A:Include(Val<1>,Ident_Set<0>).RULEType_Des ::= IdentSEMANTICSBlock * P;P=&<Block>;do{Exit<0>=Find(Val<1>,P->Env);if (P->Kind) P=P->Pred;}while (Exit<0>==NULL)&&(P->Kind);if (Exit<0>==NULL)Exit<0>=Find(Val<1>,Env<Prog>);if (Exit<0>==NULL) Error("Type Description notfound");else if (Exit<0>->Object!=TypeObject){Error("Not type object");Exit<0>:=Nil;86}.Рабочая переменная P - указатель на ближайший охватывающий блок.Переходя от блока от блоку, ищем объект в его среде.
Если не нашли, то,если блок - процедура, перейти к охватывающей. Если дошли до границымодуля, попытаться найти объект в предопределенной компоненте. Еслиобъект нашли, надо убедиться, что он - тип.Зависимости атрибутов на дереве разбора приведены на рис. 5.5.BlockEnvDec_ListDeclarationBlockEnvImp_Set Mod_HeadExp_SetImp_ListExportImportImp_SetImportFromIdentIdentIdentIdentIdentIdentIdentРис. 5.587Глава 6. Организация таблиц символов компилятораВ процессе работы компилятор хранит информацию об объектахпрограммы. Как правило, информация о каждом объекте состоит из двухосновных элементов: имени объекта и его свойств.
Информация обобъектах программы должна быть организована таким образом, чтобыпоиск ее был по возможности быстрей, а требуемая память повозможности меньше. Кроме того, со стороны языка программированиямогут быть дополнительные требования.
Имена могут иметьопределенную область видимости. Например, поле записи должно бытьуникально в пределах структуры (или уровня структуры), но можетсовпадать с именем объектов вне записи (или другого уровня записи). В тоже время имя поля может открываться оператором присоединения, и тогдаможет возникнуть конфликт имен (или неоднозначность в трактовкеимени).
Если язык имеет блочную структуру, то необходимо обеспечитьтакой способ хранения информации, чтобы, во-первых, поддерживатьблочный механизм видимости, а во-вторых - эффективно освобождатьпамять по выходе из блока. В некоторых языках (например, Аде)одновременно (в одном блоке) могут быть видимы несколько объектов содним именем, в других такая ситуация недопустима. Мы рассмотримнекоторые основные способы организации информации в компиляторах:таблицы идентификаторов, таблицы символов, способы реализацииблочной структуры.6.1.
Таблицы идентификаторов и таблицы символовКак уже было сказано, информацию об объекте обычно можно разделитьна две части: имя (идентификатор) и описание. Удобно этихарактеристики объекта хранить по отдельности. Это обусловлено двумяпричинами: 1) символьное представление идентификатора может иметьнеопределенную длину и быть довольно длинным; 2) как уже былосказано, различные объекты в одной области видимости и/или в разныхмогут иметь одинаковые имена и незачем занимать память для повторногохранения идентификатора. Таблицу для хранения идентификаторовназывают таблицей идентификаторов, а таблицу для хранения свойствобъектов - таблицей символов. В таком случае одним из свойств объектастановится его имя и в таблице символов хранится указатель на88соответствующий вход в таблицу идентификаторов.6.2. Таблицы идентификаторовЕсли длина идентификатора ограничена (или имя идентифицируется поограниченному числу первых символов идентификатора), то таблицаидентификаторов может быть организована в виде простого массива строкфиксированной длины, как это изображено на рис.
6.1. Некоторые входымогут быть заняты, некоторые - свободны.sorteadari.................Рис. 6.1Ясно, что, во-первых, размер массива должен быть не меньше числаидентификаторов, которые могут реально появиться в программе (впротивном случае возникает переполнение таблицы); во-вторых, какправило, потенциальное число различных идентификаторов существеннобольше размера таблицы. Поиск в такой таблице может быть организованметодом повторной расстановки.
Суть его заключается в следующем.Пусть число элементов массива равно N. Определим некоторуюфункцию h (первичную функцию расстановки), определенную намножестве идентификаторов и принимающую значения 0<=h(id)<=N-1, id- идентификатор. Если элемент таблицы h(id) свободен, то это означает,что идентификатора в таблице нет. Если же занят, то это еще не означает,что идентификатор id в таблицу занесен, поскольку (вообще говоря) многоидентификаторов могут иметь одно и то же значение функциирасстановки. Для того чтобы определить, нашли ли мы нужныйидентификатор, сравниваем id с элементом таблицы h(id). Если они равны- идентификатор нашли, если нет - надо продолжать поиск дальше.
Дляэтого вычисляют вторичную функцию расстановки h2(h). Вновь возможнычетыре варианта: либо элемент таблицы свободен, либо нашлиидентификатор, либо таблица вся просмотрена и идентификатора нет,89либо надо продолжать поиск. Для продолжения поиска применяют вновьфункцию h3(h2), и т.д. Как правило, hi=h2 для i>=2. Аргументом функцииh2 является целое в диапазоне [0,N-1] и она может быть быть устроена поразному. Приведем три варианта.1) h2(i)=(i+1) mod NБерется следующий (циклически) элемент массива. Этот вариант плох тем,что занятые элементы "группируются", образуют последовательныезанятые участки и в пределах этого участка поиск становится по-существулинейным.2) h2(i)=(i+k) mod N, где k и N взаимно просты.По-существу это предыдущий вариант, но элементы накапливаются не впоследовательных элементах, а "разносятся".3) h2(i)=(a*i+c) mod N - "псевдослучайная последовательность".Здесь c и N должны быть взаимно просты, b=а-1 кратно p для любогопростого p, являщегося делителем N, b кратно 4, если N кратно 4 [6].void Search(String id, boolean * Yes, int * Point){int H0=h(id),H=H0;while (1){if (!IdComp(H,id)){*Yes=true;*Point=H;return;}else if (Empty(H)){*Yes=false;*Point=H;return;}else H=h2(H);if (H==H0){*Yes=false;*Point=NULL;return;} } }Поиск в таблице можно описать функцией, приведенной выше.
ФункцияIdComp(H,id) сравнивает элемент таблицы по входу H с идентификатороми вырабатывает 0, если они равны. Функция Empty(H) вырабатывает 1,если вход H пуст. Функция Search присваивает параметру по ссылке resultзначения (true,P), если нашли требуемый идентификатор, и P - указатель на90него, (false,NIL), если искомого идентификатора нет и в таблице нетсвободного места, и (false,P), если искомого идентификатора нет, но втаблице есть свободный вход P.Занесение идентификатора в таблицу можно осуществитьследующей функцией:int Insert(String id){boolean Yes;int Point;Search(id,&Yes, &Point);if (!Yes && (Point!=NULL))InsertId(Point,id);return(Point);}Здесь функция InsertId(Point,id) заносит идентификатор id по входутаблицы Point.Второй способ организации таблицы идентификаторов - хранениеидентификаторов в сплошном массиве символов.
В этом случаеидентификатору соответствует номер его первого символа в этом массиве,как это изображено на рис. 6.2. Идентификатор в массиве заканчиваетсякаким-либо специальным символом (EOS). Второй возможный вариант - вкачестве первого символа идентификатора в массив заносится его длина.Для организации поиска в таком массиве таблица идентификаторовотделяется от таблицы расстановки (рис.
6.3).sor tEOSaEOSre adРис. 6.291EOSiEOS0...9Idenpx...Указатели на идентификаторы20Idenp x...Указатель на идентификатор32210x...Указатели на идентификаторыРис. 6.36.3. Таблицы символов и таблицы расстановкиРассмотрим организацию таблицы символов с помощью таблицырасстановки. Таблица расстановки - это массив указателей на спискиуказателей на идентификаторы. В каждый такой список входят указателина идентификаторы, имеющие одно значение функции расстановки (рис.6.3).Вначале таблица расстановки пуста (все элементы имеют значениеNIL). При поиске идентификатора id вычисляется функция расстановкиH(id) и просматривается линейный список T[H]. Поиск в таблице можетбыть описан следующей процедурой:structElement{String IdenP;struct Element * Next;};Element * Search(String Id){Element * P;P=T[h(Id)];while (1){if (P==NULL) return(NULL);else if (!IdComp(P->IdenP,Id)) return(P);92else P=P->Next;}}IdenTab - таблица идентификаторов.
Занесение объекта в таблицу можетосуществляться следующей процедурой:Element * Insert(Id:string){Element * P,H;P=Search(Id);if (P!=NULL) return(P);else{H=H(Id); P=new Element();P->Next=T[H]; T[H]=P;P->Idenp=Include(Id);}return(P);}HPРис. 6.4.Процедура Include заносит идентификатор в таблицу идентификаторов.Алгоритм иллюстрируется рис. 6.4.6.4. Функции расстановки.Много внимания было уделено тому, какой должна быть функциярасстановки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
