Лекции по конструированию компиляторов. В.А. Серебряков (1134688), страница 12
Текст из файла (страница 12)
Эти трудности связаны как с самим формализмом, так и снекоторыми технологическими проблемами. К трудностям первого родаможно отнести несоответствие чисто функциональной природыатрибутного вычислителя и связанной с ней неупорядоченностью процессавычисления атрибутов (что в значительной степени являетсяпреимуществом этого формализма) и упорядоченностью элементовпрограммы.
Это несоответствие ведет к тому, что приходится идти наискусственные приемы для их сочетания. Технологические трудностисвязаны с эффективностью трансляторов, генерированных с помощьюатрибутных систем. Как правило, качество таких трансляторов довольнонизко из-за больших расходов памяти, неэффективности искусственныхприемов, о которых было сказано выше.Учитывая это, мы будем вести дальнейшее изложение на языке,сочетающем особенности атрибутного формализма и обычного языка, вкотором предполагается возможность управления порядком исполненияоператоров. Этот порядок привязывается к обходу атрибутированного72дерева разбора сверху вниз слева направо. Все атрибуты должны бытьвычислены за один такой обход.
Атрибутные грамматики, обладающиетаким свойством, называются L-атрибутными.При записи синтаксиса мы будем использовать расширенную БНФ.Элемент правой части синтаксического правила, заключенный в скобки [ ],может отсутствовать. Элемент правой части синтаксического правила,заключенный в скобки ( ), означает возможность повторения один илиболее раз. Элемент правой части синтаксического правила, заключенный вскобки [()], означает возможность повторения ноль или более раз.
Вскобках [] или [()] может указываться разделитель конструкций.Ниже дан синтаксис языка описания атрибутных грамматик.Атрибутная грамматика ::= 'ALPHABET'( ОписаниеНетерминала ) ( Правило )ОписаниеНетерминала ::= ИмяНетерминала'::' [( ОписаниеАтрибутов / ';')] '.'ОписаниеАтрибутов ::= ( ИмяАтрибута / ',') ':' ТипПравило ::= 'RULE' Синтаксис 'SEMANTICS' Семантика '.'Синтаксис ::= ИмяНетерминала '::=' ПраваяЧастьПраваяЧасть ::= [( ЭлементПравойЧасти )]ЭлементПравойЧасти ::= ИмяНетерминала| Терминал| '(' Нетерминал [ '/' Терминал ] ')'| '[' Нетерминал ']'| '[(' Нетерминал [ '/' Терминал ] ')]'Семантика ::= [( ЛокальноеОбъявление ])[( СемантическоеДействие ])СемантическоеДействие ::= Присваивание| [ Метка ] ОператорПрисваивание ::= Переменная ':=' ВыражениеПеременная ::= ЛокальнаяПеременная|АтрибутАтрибут ::= ЛокальныйАтрибут|ГлобальныйАтрибутЛокальныйАтрибут ::= ИмяАтрибута '<' Номер '>'ГлобальныйАтрибут ::= ИмяАтрибута '<' Нетерминал '>'Метка ::= Целое ':'| Целое 'Е' ':'| Целое 'А' ':'Оператор ::= Условный|ОператорПроцедуры|ЦиклПоМножеству73||ПростойЦиклЦиклСУсловиемОкончанияОписание атрибутной грамматики состоит из раздела описания атрибутови раздела правил.
Раздел описания атрибутов определяет состав атрибутовдля каждого символа грамматики и тип каждого атрибута. Правила состоятиз синтаксической и семантической части. В синтаксической частииспользуется расширенная БНФ. Семантическая часть правила состоит излокальных объявлений и семантических действий. В качествесемантических действий допускаются как атрибутные присваивания, так исоставные операторы.Метка в семантической части правила привязывает выполнениеоператора к обходу дерева разбора сверху-вниз слева направо.Конструкция "i : оператор" означает, что оператор должен быть выполненсразу после обхода i-й компоненты правой части.
Конструкция "i E :оператор" означает, что оператор должен быть выполнен, только еслипорождение i-й компоненты правой части пусто. Конструкция "i A :оператор" означает, что оператор должен быть выполнен после разборакаждого повторения i-й компоненты правой части (имеется в видуконструкция повторения).Каждое правило может иметь локальные определения (типов ипеременных). В формулах используются как атрибуты символов данногоправила (локальные атрибуты) и в этом случае соответствующие символыуказываются номерами в правиле (0 для символа левой части, 1 длясимвола правой части и т.д.), так и атрибуты символов предков левойчасти правила (глобальные атрибуты). В этом случае соответствующийсимвол указывается именем нетерминала. Таким образом, на деревеобразуются области видимости атрибутов: атрибут символа имеет областьвидимости, состоящую из правила, в которое символ входит в правуючасть, плюс все поддерево, корнем которого является символ, заисключением поддеревьев - потомков того же символа в этом поддереве(рис.
4.4).|.... N .. / \ .. /\ .. /\/\ .. / /\ /\ \ .. / -- -- \ ....N...........N.../\/\--Рис. 4.474Значение терминального символа доступно через атрибут VALсоответствующего типа.4.3.4. Классы атрибутных грамматик и их реализацияВ общем виде реализация атрибутных грамматик вызываетзначительные трудности. Это связано с тем, что множество значенийатрибутов, связанных с данным деревом, приходится вычислять всоответсвии со связями, которые образуют граф с произвольными связями.На практике стараются осуществлять процесс вычисления атрибутов,привязывая его к тому или иному способу обхода дерева. Рассматриваютмноговизитные, многопроходные и другие атрибутные вычислители. Этоведет как правило к ограничению допустимых зависимостей междуатрибутами, поддерживаемых вычислителем.Простейшими такими подклассами атрибутных грамматик,вычисления всех атрибутов для которых может быть осуществленоодновременно с синтаксическим анализом, являются S-атрибутные и Lатрибутные грамматики.
Атрибутная грамматика называется Sатрибутной, если все атрибуты на любом дереве для этой грамматикимогут быть вычислены снизу-вверх слева-направо (т.е. атрибутнаяграмматика имеет только синтезированные атрибуты). Все такие атрибутымогут быть вычислены в процессе разбора снизу-вверх.. Грамматиканазывается L-атрибутной, если все атрибуты на любом дереве для этойграмматики могут быть вычислены за один обход дерева сверху-внизслева-направо. Все такие атрибуты могут быть вычислены в процессеразбора сверху-вниз.Вычисление атрибутов для L-атрибутных грамматик можнопроизводить в процессе рекурсивного спуска. Для этого в каждойфункции, соответствующей нетерминалу, надо определить формальныепараметры, передаваемые по значению, для наследуюмых атрибутов, иформальные параметры, передаваемые по ссылке, для синтезируемыхатрибутов.
В качестве примера рассмотрим реализацию приведеннойвыше атрибутной грамматики.void int_part(float * V0, int * P0){if (Map[InSym]==Digit){ int I=InSym;InSym=getInSym();float V2;int P2;int_part(&V2,&P2);V0=I*exp(P2*ln(10))+V2;75P0=P2+1;else {V0=0;*P0=0;}}void fract_part(float * V0, int P0){if (Map[InSym]==Digit){ int I=InSym;InSym=getInSym();float V2;int P2=P0+1;fract_part(&V2,P2);V0=I*exp(-P2*ln(10))+V2;P0=P2+1;else {V0=0;}}void number(){ float V1,V3,V0;int P;int_part(&V1,&P);if (InSym!=’.’) error();fract_part(&V3,1);V0=V1+V3;}76Глава 5. Контекстные условия языковпрограммирования5.1. Описание областей видимости и блочной структурыЗадачей контекстного анализа является установление правильностииспользования объектов.
Наиболее часто решаемой задачей являетсяопределение существования объекта и соответствия его использованияконтексту, что осуществляется с помощью анализа типа объекта.Таким образом необходимо хранить объекты, их типы, уметьнаходить эти объекты и определять их типы, определять характеристикиконтекста. Совокупность доступных в даной точке объектов будемназывать "средой". Обычно среда программы состоит из частичноупорядоченного набора компонентE={DS1,...DSn}.Каждая компонента - это множество объявлений, представляющих собойпары <имя,тип>:DSi={<имя,тип>},где под типом будем подразумевать полное описание свойств объекта(объектом, в частности, может быть само описание типа).Корневаякомпонента(программа)процедурапроцедура(блок)процедура(блок)(блок)Рис. 5.1Между компонентами DSi и DSj имеет место отношение "DSiвключает DSj" тогда и только тогда, когда любой объект из DS i может77быть доступен из DSj (конкретный способ доступа определяетсяправилами видимости языка), но не наоборот.
Компоненты образуютдерево. Это дерево соответствует блокам или процедурам (рис. 5.1)Обычными операциями при работе со средой являются:- включить объект в компоненту среды;- найти объект в среде и получить доступ к его описанию;- образовать в среде новую компоненту, определеннымсвязанную с остальными;- удалить компоненту из среды.образомКомпоненты среды могут быть именованы. Поиск в среде обычно ведетсяс учетом упорядоченности компонент. Среда может включать в себя каккомпоненты, полученные при трансляции "текущего" текста программы,так и "внешние" компоненты.Для обозначения участков программы, в которых доступны те илииные описания, используются понятия "область действия" и "областьвидимости".
Областью действия описания является процедура (блок),содержащая описание, со всеми входящими в нее (подчиненными подереву) процедурами (блоками). Областью видимости описанияназывается часть области действия, из которой исключены те подобласти,в которых по тем или иным причинам описание недоступно.В разных языках понятия области действия и области видимостиуточняются по-разному.
В дальнейшем изложение ведется на примереязыка Модула -2.5.2. Структура среды Модулы-2Имеются четыре рода языковых конструкций, которые могут содержатьописания: 1) программный модуль или модуль реализации; 2) модульопределения; 3) процедура; 4) локальный модуль."Корневую" компоненту среды в Модуле-2 образует программныймодуль или модуль реализации. Объекты этой компоненты могут бытьописаны в самом модуле или могут быть импортированы из другихмодулей определений.
Такой импорт может быть квалифицированным(from M import X,Y, ...;) или не квалифицированным (import M;).78ЭкспортирующийКомпонента Импортирующийлокальный модуль средылокальный модульMODULE M1;EXPORT A1;MODULE X1;IMPORT A1;A1A1MODULE M2;EXPORTQUALIFIED A2M2MODULE X2;FROM M2IMPORT A2;A2A2MODULE M3;EXPORT M31;MODULE M31;EXPORT A31;MODULE M4;EXPORT M41;M31A31MODULE XIMPORT M31;A31M41MODULE X4;FROM M41IMPORT A41;A41MODULE M41;EXPORTQUALIFIED A41;MODULE M5;EXPORTQUALIFIED M51;MODULE M51;EXPORT A51;MODULE M6;EXPORTQULIFIED M61;MODULE M61;EXPORTQUALIFIED A61;MODULE X3;IMPORT A31;A31A41M5M51MODULE XIMPORT M41;A41MODULE X5;FROM M5IMPORT M51;M51.A51A51M6M61MODULE X6;FROM M6IMPORT M61M61.A61A61Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
