Р.У. Себеста - Основные копцепции языков программирования (2001) (1160794), страница 39
Текст из файла (страница 39)
а иногда — просто невозможно. Примером правил языка, определение которых трудно дать с покюшью формы БНФ. являются правила совместимости типов. Например, в языке эата число с плавающей точкой не может быть присвоено переменной целого типа, хотя обратное присвоение возможно. Несмотря на то что подобное ограничение может быть точно описано в форме БНФ, оно позребует дополнительных нетерминазьных символов и правил.
Если все полобные правила типов языка )ача точно опрелелить в рамках формы БНФ, то грамматика станет слишком громоздкой, поскольку ее размер определяет и размер программы синтаксического анализа. Обычное правило обязательного объявления переменных не может быть определено в форме БНФ. Другой пример: если за оператором епс( подпрограммы, написанной на языке Аоа. следует некоторое имя. то это имя должно совпадать с именем подпрограммы.
Эти лве проблемы служат примером правил статической семантики. Статическая семантика (з(апс зешаппсз) языка в основном связана с формами программ, а не с их содержанием (т.е. синтаксисом, а не семантикой). Во многих случаях правила статической семантики языка устанавливают ограничения, наложенные на типы.
Статическая семантика называется так потому, что анализ, требуемый для проверки этих условий, должен быть выполнен во время компиляции. Из-за с) шествования проблемы описания статической семантики с помощью формы БНФ для решения этой задачи было разработано множество более люшных механизмов. Разработка одного из таких механизмов.
описывающего синтаксис и статическую семантику программ и названного атрибутивнылш грамматиками, была выполнена Кнутом (Клайн 1968а). Обсуждение линамической семантики будет провелено в разлеле 3.6. 3.5.2. Оснояные понятия Атрибутивными грамматиками называются грамматики, к которым были добавлены атрибуты, атрибутнвные вычислительные функции и преликативные функции. Атрибут ы (аппЬшез), связанные с символами грамматики. подобны переменным в том смысле, что им,могут присваиваться значения.
Атрнбутнвные вычислительные функции (апПЬи(е сошрцгайоп Гцпс11опз), иногда называемые семантическими функциями, связаны с грамматическими правилами вычисления значений атрибутов. Предикативные функции (ргеб(саге Гцпс1(опз), устанавливающие некоторые синтаксические правила и правила сзаз ической семантики языка, связаны с грамматическими правилами. 3.5.3. Определение отрнбутняных грамматик Атрибутивными называются грамматики.
имеющие следующие дополнительные свойства. ° С каждой грамматикой связывается символ Х. обозначающий набор атрибутов А(Х). Набор А(Х) состоит из двух непересекающихся множеств 8(Х) и 1(Х), называемых синтезированными и унаследованными атрибутами, соответственно. Синтезированные атрибуты (зупгйез(ген апНЬцгез) используются лля передачи семантической информации вверх по дереву синтаксического анализа, тогда как Глава 3.
Описание синтаксиса и семантики унаследованные атрибуты ()пйепгед апг(Ьшез) используются для передачи семантической информации вниз по дереву. ° Правило, связанное с каждой грамматикой, является набором семантических функций и, возможно, пустого множества предикативных функций, определенных на атрибутах символов в грамматическом правиле. Для правила Хе ~ Х, ...Х„синтезированные атрибуты правила Х, вычисляются семантической функцией вила $(Хе) = ((А(Х~), ..., А(Х„)).
Таким образом, величина синтезированного атрибута узла дерева синтаксического анализа зависит исключительно от значений атрибутов дочерних узлов этого узла. Унаследованные атрибуты символов Хг 1<) <л (в правиле, приведенном выше) вычисляются семантической функцией вида 1(Х;) ((А(Х,),..., А(Х„)). Таким образом, значение унаследованного атрибута узла дерева синтаксического анализа зависит от значения атрибута родительского узла и значений атрибутов узлов того же уровня.
Отметим, что во избежание порочного круга унаследованные атрибуты часто ограничиваются ф>нкцией вила ИХ,) =((А(Хо),- А(Х)ч)). Такая форма предотвращает зависимость унаследованных атрибутов от самих же себя или от атрибутов, находящихся правее на дереве синтаксического анализа. Предиквтивная функция имеет вил булевского выражения, заданного нв множестве атрибутов (А(Хе), ..., А(Х„)). Единственными выводами, разрешенными в рамках атрибутивной грамматики, являются те, в которых все предикаты, связанные с каждым нетерминальным символом, истинны. Ложное значение предикативной функции указывает на нарушение синтаксических правил или правил статической семантики языка. Дерево синтаксического анализа атрибутивной грамматики базируется на грамматике формы БНФ, лежащей в основе данной атрибутивной грамматики.
с. возможно. пустым множеством значений атрибутов, связанных с каждым узлом. Если вычислены значения всех атрибутов дерева синтаксического анализа, то оно называется полностью определенным (бзИу аппЬцгед). Хотя на практике подобным образом поступают далеко не всегда, удобно полагать, что значения атрибутов вычисляются после создания дерева синтаксического анализа. З.ЗА.
Внутрвннив атрибуты Внутренние атрибуты (1пп(пз(с а[пЬц[ез) — это синтезированные атрибуты узлов, значения которых определяются вне дерева синтаксического анализа. Например. тип экземпляра переменной в программе может поставляться из таблицы илентификаторов, используемой для хранения имен переменных и их типов. Содержимое таблицы идентификаторов определяется выполненными ранее операторами объявления. Предположим, что изначально было создано дерево с неопределенными значениями атрибутов.
и нам нужно их определить. При этом единственными атрибутами, имеющими значения. являются внутренние атрибуты узлов. Поместив значения внутренних атрибутов на дерево синтаксического анализа, мы сможем использовать семантические функции для вычисления значений остальных атрибутов. 3.5. Атрибутивныв грамматики 3.5.5. Примеры атрибутивных грамматик Рассмотрим следующий фрагмент атрибутивной грамматики, описывающий правило, заключающееся в том, что нмя, следующее за оператором епа в конце процедуры языка Аба, должно совпадать с именем самой процедуры.
Атрибут строки <имя про)зедуры>, обозначенный как <имя процелуры>.строка, является реальной строкой символов, которая может обнаруживаться лексическим анализатором. Отметим, что при наличии в синтаксическом правиле атрибутивной грамматики нескольких нетерминальных символов, последние заключаются в скобки лишь с целью их различения. Ни индексы, ни скобки частью описываемого языка не являются. Синтаксическое правило: <определение процедуры> -~ ркооес[ике <имя процедуры>[1] <тело процедуры> вас[ <имя процедуры>[2]; Семантическое правило: <имя процедуры>[1].строка<имя процедуры>[2].строка Ниже показано, как с помощью атрибутивной грамматики проверить правила совместимости типов простого оператора присваивания.
Синтаксис и семантика этого оператора следующие: единственными именами переменных являются А, В и С. Правая сторона присваивания может быть переменной или выражением в форме сложения двух переменных. Переменные могут быть двух типов: целые и действительные. Если в правой части присваивания находятся две переменные, онн не обязаны иметь один и тот же тип.
Значение выражения, в котором фигурируют операнды различных типов, всегда имеют действительный тип. Тнп значения выражения с операндами одного типа совпадает с типом операндов. Тип левой части присваивания лолжен совпадать с типом правой части. Таким образом, типы операндов правой части мокнут смешиваться, но присваивание коррелтно только в том случае, если его левая часть и значение, полученное при вычислении правой части, имеют один н тот же тип.
Атрибутивная грамматика определяет описанные семантические правила. Синтаксическая часть атрибутивной грамматики, описывающей ланный пример, имеет слелуюший внд: <лрисваивание> -з <переменная> := <выражение> <выражение> -з <переменная> ь <переменная> <переменная> <переменная> -з А[В[С В следующих абзацах описываются атрибуты лля нетерминальных символов данной атрибутивной грамматики. Флкпшческпй гпип Синтезированный атрибут, связанный с нетерминальными символами <переменная> н <выражение>.
Он используется для запоминания фактического типа (в нашем примере целого или действительного) переменной или выражения. Для переменной фактический тип является внутренним. Для выражения он определяется на основе типов дочернего узла нли узлов нетерминального символа <выражение>. Ожидаеный аппп Внутренний атрибут, связанный с нетерминальным символом <выраженне>.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
