TRAN7 (1131496), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Число ::= Целая_часть ‘.’ Дробная_часть=>
Значение<0>=Значение<1>+Значение<3>;
Порядок<3>=1.
Целая_часть ::= e=>
Значение<0>=0; Порядок<0>=0.
Целая_часть ::= Цифра Целая_часть =>
Значение<0>=Значение<1>*10**Порядок<2>+Значение<2>;
Порядок<0>=Порядок<2>+1.
Дробная_часть ::= e =>
Значение<0>=0.
Дробная_часть ::= Цифра Дробная_часть=>
Значение<0>=Значение<1>*10**(-Порядок<0>)
+Значение<2>;
Порядок<2>=Порядок<0>+1.

4.3.2. Атрибутированное дерево разбора

Если дана атрибутная грамматика AG и цепочка, принадлежащая языку, определяемому G, то можно построить дерево разбора этой цепочки в грамматике G. В этом дереве каждая вершина помечена символом грамматики G. Припишем теперь каждой вершине множество атрибутов, сопоставленных символу, которым помечена эта вершина. Атрибуты, сопоставленные вхождениям символов в дерево разбора, будем называть вхождениями атрибутов в дерево разбора, а дерево с сопоставленными каждой вершине атрибутами - атрибутированным деревом разбора.

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

4.3.3. Язык описания атрибутных грамматик

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

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

Учитывая это, мы будем вести дальнейшее изложение на языке, сочетающем особенности атрибутного формализма и обычного языка, в котором предполагается возможность управления порядком исполнения операторов. Этот порядок привязывается к обходу атрибутированного дерева разбора сверху вниз слева направо. Все атрибуты должны быть вычислены за один такой обход. Атрибутные грамматики, обладающие таким свойством, называются L-атрибутными.

При записи синтаксиса мы будем использовать расширенную БНФ. Элемент правой части синтаксического правила, заключенный в скобки [ ], может отсутствовать. Элемент правой части синтаксического правила, заключенный в скобки ( ), означает возможность повторения один или более раз. Элемент правой части синтаксического правила, заключенный в скобки [()], означает возможность повторения ноль или более раз. В скобках [] или [()] может указываться разделитель конструкций.

Ниже дан синтаксис языка описания атрибутных грамматик.

Атрибутная грамматика ::= 'ALPHABET'
( ОписаниеНетерминала ) ( Правило )
ОписаниеНетерминала ::= ИмяНетерминала
'::' [( ОписаниеАтрибутов / ';')] '.'
ОписаниеАтрибутов ::= ( ИмяАтрибута / ',') ':' Тип
Правило ::= 'RULE' Синтаксис 'SEMANTICS' Семантика '.'
Синтаксис ::= ИмяНетерминала '::=' ПраваяЧасть
ПраваяЧасть ::= [( ЭлементПравойЧасти )]
ЭлементПравойЧасти ::= ИмяНетерминала
| Терминал
| '(' Нетерминал [ '/' Терминал ] ')'
| '[' Нетерминал ']'
| '[(' Нетерминал [ '/' Терминал ] ')]'
Семантика ::= [( ЛокальноеОбъявление ])
[( СемантическоеДействие ])
СемантическоеДействие ::= Присваивание
| [ Метка ] Оператор
Присваивание ::= Переменная ':=' Выражение
Переменная ::= ЛокальнаяПеременная
| Атрибут
Атрибут ::= ЛокальныйАтрибут
| ГлобальныйАтрибут

ЛокальныйАтрибут ::= ИмяАтрибута '<' Номер '>' ГлобальныйАтрибут ::= ИмяАтрибута '<' Нетерминал '>'
Метка ::= Целое ':'
| Целое 'Е' ':'
| Целое 'А' ':'
Оператор ::= Условный
| ОператорПроцедуры
| ЦиклПоМножеству
| ПростойЦикл
| ЦиклСУсловиемОкончания

Описание атрибутной грамматики состоит из раздела описания атрибутов и раздела правил. Раздел описания атрибутов определяет состав атрибутов для каждого символа грамматики и тип каждого атрибута. Правила состоят из синтаксической и семантической части. В синтаксической части используется расширенная БНФ. Семантическая часть правила состоит из локальных объявлений и семантических действий. В качестве семантических действий допускаются как атрибутные присваивания, так и составные операторы.

Метка в семантической части правила привязывает выполнение оператора к обходу дерева разбора сверху-вниз слева направо. Конструкция "i : оператор" означает, что оператор должен быть выполнен сразу после обхода i-й компоненты правой части. Конструкция "i E : оператор" означает, что оператор должен быть выполнен, только если порождение i-й компоненты правой части пусто. Конструкция "i A : оператор" означает, что оператор должен быть выполнен после разбора каждого повторения i-й компоненты правой части (имеется в виду конструкция повторения).

Каждое правило может иметь локальные определения (типов и переменных). В формулах используются как атрибуты символов данного правила (локальные атрибуты) и в этом случае соответствующие символы указываются номерами в правиле (0 для символа левой части, 1 для символа правой части и т.д.), так и атрибуты символов предков левой части правила (глобальные атрибуты). В этом случае соответствующий символ указывается именем нетерминала. Таким образом, на дереве образуются области видимости атрибутов: атрибут символа имеет область видимости, состоящую из правила, в которое символ входит в правую часть, плюс все поддерево, корнем которого является символ, за исключением поддеревьев - потомков того же символа в этом поддереве (рис. 4.4).

|
...
. N .
. / \ .
. / \ .
. /\ /\ .
. / /\ /\ \ .
. / -- -- \ .
...N...........N...
/\ /\
-- --
Рис. 4.4

Значение терминального символа доступно через атрибут 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;
P0=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;
}

92

Характеристики

Список файлов ответов (шпаргалок)