В.А. Серебряков - Теория и реализация языков программирования (1134641), страница 25
Текст из файла (страница 25)
Эти трудности связаны какс самим формализмом, так и с некоторыми технологическими проблемами.К трудностям первого рода можно отнести несоответствие между чистофункциональной природой атрибутного вычислителя и связанной с ней неупорядоченностью процесса вычисления атрибутов (что в значительной степениявляется преимуществом этого формализма), с одной стороны, и упорядоченностью элементов программы — с другой.
Это несоответствие ведет к тому,что приходится идти на искусственные приемы для их сочетания. Технологические трудности связаны с эффективностью трансляторов, полученныхс помощью атрибутных систем. Как правило, качество таких трансляторовдовольно низко из-за больших расходов памяти и неэффективности вышеупомянутых искусственных приемов.Учитывая это, мы будем вести дальнейшее изложение на языке, сочетающем особенности атрибутного формализма и обычного языка программирования, в котором предполагается наличие операторов, а значит, и возможностьуправления порядком их исполнения. Этот порядок может быть привязанк обходу атрибутированного дерева разбора сверху-вниз слева-направо.
Чтокасается грамматики входного языка, то мы не будем предполагать принадлежность ее определенному классу (например, LL(1) или LR(1)). Будемсчитать, что дерево разбора входной программы уже построено как результат124Глава 5. Элементы теории переводасинтаксического анализа и что атрибутные вычисления осуществляются в результате обхода этого дерева. Таким образом, входная грамматика атрибутного вычислителя может быть даже неоднозначной, что не влияет на процессатрибутных вычислений.При записи синтаксиса мы будем использовать расширенную БНФ.
Элемент правой части синтаксического правила, заключенный в скобки [ ],может отсутствовать. Элемент правой части синтаксического правила, заключенный в скобки ( ), означает возможность повторения один или более раз.Элемент правой части синтаксического правила, заключенный в скобки [()],означает возможность повторения ноль или более раз. В скобках [ ] или[()] может указываться разделитель конструкций.Ниже дан синтаксис языка описания атрибутных грамматик. Приведентолько синтаксис конструкций, собственно описывающих атрибутные вычисления.
Синтаксис обычных выражений и операторов не приводится —он основывается на Си.Атрибутная грамматика::=’ALPHABET’( ОписаниеНетерминала ) ( Правило )ОписаниеНетерминала::=ИмяНетерминала’::’ [( ОписаниеАтрибутов / ’;’)]’.’ОписаниеАтрибутов::=Тип ( ИмяАтрибута / ’,’)Правило::=’RULE’ Синтаксис ’SEMANTICS’ Семантика’.’Синтаксис::=ИмяНетерминала ’::=’ ПраваяЧастьПраваяЧасть::=[( ЭлементПравойЧасти )]ЭлементПравойЧасти::=ИмяНетерминала| Терминал| ’(’ Нетерминал [ ’/’ Терминал ] ’)’| ’[’ Нетерминал ’]’| ’[(’ Нетерминал [ ’/’ Терминал ] ’)]’Семантика::=[(ЛокальноеОбъявление / ’;’)][( СемантическоеДействие / ’;’)]СемантическоеДействие::=Присваивание| [ Метка ] ОператорПрисваивание::=Переменная ’:=’ ВыражениеПеременная::=ЛокальнаяПеременная|АтрибутАтрибут::=ЛокальныйАтрибут|ГлобальныйАтрибутЛокальныйАтрибут::=ИмяАтрибута ’<’ Номер ’>’ГлобальныйАтрибут::=ИмяАтрибута ’<’ Нетерминал ’>’Метка::=Целое ’:’| Целое ’Е’ ’:’| Целое ’А’ ’:’5.3. Атрибутные грамматики125Описание атрибутной грамматики состоит из раздела описания атрибутови раздела правил.
Раздел описания атрибутов определяет состав атрибутовдля каждого символа грамматики и тип каждого атрибута. Правила состоятиз синтаксической и семантической частей. В синтаксической части используется расширенная БНФ. Семантическая часть правила состоит из локальныхобъявлений и семантических действий.
В качестве семантических действийдопускаются как атрибутные присваивания, так и составные операторы.Метка в семантической части правила привязывает выполнение оператора к обходу дерева разбора сверху-вниз слева-направо. Конструкцияi : оператор означает, что оператор должен быть выполнен сразу послеобхода i-й компоненты правой части. Конструкция i E : оператор означает,что оператор должен быть выполнен, только если порождение i-й компонентыправой части пусто.
Конструкция i A : оператор означает, что оператордолжен быть выполнен после разбора каждого повторения i-й компонентыправой части (имеется в виду конструкция повторения).Каждое правило может иметь локальные определения (типов и переменных). В формулах используются как атрибуты символов данного правила(локальные атрибуты), и в этом случае соответствующие символы указываются номерами в правиле (0 для символа левой части, 1 для первого символаправой части, 2 для второго символа правой части, и т.
д.), так и атрибутысимволов предков левой части правила (глобальные атрибуты). В этом случаесоответствующий символ указывается именем нетерминала. Таким образом,на дереве образуются области видимости атрибутов: атрибут символа имеетобласть видимости, состоящую из правила, в которое символ входит в правуючасть, плюс всё поддерево, корнем которого является символ, за исключениемподдеревьев — потомков того же символа в этом поддереве.Значение терминального символа доступно через атрибут VAL соответствующего типа.Пример 5.9. Атрибутная грамматика из примера 5.5 записывается следующимобразом:ALPHABET Num:: float V. Intint P.Frac:: float V;int P.digit :: int VAL.RULENum ::= Int ’.’ FracSEMANTICSV<0>=V<1>+V<3>; P<3>=1.RULE:: float V;126Глава 5.
Элементы теории переводаInt ::= eSEMANTICSV<0>=0; P<0>=0.RULEInt ::= digit IntSEMANTICSV<0>=VAL<1>*10**P<2>+V<2>; P<0>=P<2>+1.RULEFrac ::= eSEMANTICSV<0>=0.RULEFrac ::= digit FracSEMANTICSV<0>=VAL<1>*10**(-P<0>)+V<2>; P<2>=P<0>+1.Глава 6ПРОВЕРКА КОНТЕКСТНЫХ УСЛОВИЙ6.1. Описание областей видимости и блочной структурыЗадачей контекстного анализа является установление свойств объектови их использования. Наиболее часто решаемой задачей является определениесуществования объекта и соответствия его использования контексту, чтоосуществляется с помощью анализа типа объекта.
Под контекстом здесьпонимается вся совокупность свойств текущей точки программы, напримермножество доступных объектов, тип выражения и т. д.Таким образом, необходимо хранить объекты и их типы, уметь находитьэти объекты и определять их типы, определять характеристики контекста.Совокупность доступных в данной точке объектов будем называть средой.Обычно среда программы состоит из частично упорядоченного набора компонентE = {DS1 , DS2 , .
. . , DSn }Каждая компонента — это множество объявлений, представляющих собойпары (имя, тип):DSi = {(имяj , типj ) | 1 6 j 6 ki }где под типом будем подразумевать полное описание свойств объекта (объектом, в частности, может быть само описание типа).Рис. 6.1128Глава 6. Проверка контекстных условийКомпоненты образуют дерево, соответствующее этому частичному порядку. Частичный порядок между компонентами обычно определяется статической вложенностью компонент в программе. Эта вложенность можетсоответствовать блокам, процедурам или классам программы (рис. 6.1).
Компоненты среды могут быть именованы. Поиск в среде обычно ведется с учетомупорядоченности компонент. Среда может включать в себя как компоненты,полученные при трансляции «текущего» текста программы, так и «внешние»(например, раздельно компилированные) компоненты.Для обозначения участков программы, в которых доступны те или иныеописания, используются понятия области действия и области видимости.Областью действия описания является процедура (блок), содержащая описание, со всеми входящими в нее (подчиненными по дереву) процедурами(блоками).
Областью видимости описания называется часть области действия, из которой исключены те подобласти, в которых по тем или инымпричинам описание недоступно, например, оно перекрыто другим описанием.В разных языках понятия области действия и области видимости уточняютсяпо-разному.Обычными операциями при работе со средой являются:– включить объект в компоненту среды;– найти объект в среде и получить доступ к его описанию;– образовать в среде новую компоненту, определенным образом связаннуюс остальными;– удалить компоненту из среды.6.2. Занесение в среду и поиск объектовРассмотрим схему реализации простой блочной структуры, аналогичнойпроцедурам в Паскале или блокам в Си.
Каждый блок может иметь свойнабор описаний. Программа состоит из основного именованного блока, в котором имеются описания и операторы. Описания состоят из описаний типови объявлений переменных. В качестве типа может использоваться целочисленный тип и тип массива. Два типа T1 и T2 считаются эквивалентными,если имеется описание T1=T2 (или T2=T1). Операторами служат операторыприсваивания вида Переменная1=Переменная2 и блоки. Переменная — этолибо просто идентификатор, либо выборка из массива. Оператор присваивания считается правильным, если типы переменных левой и правой частиэквивалентны. Примером правильной программы может служитьprogram Example;type T1=array 100 of array 200 of integer;T2=T1;6.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
