Грамматика атрибутов

Грамматика атрибута является формальным способом определения атрибутов для производств с формальной грамматикой , связывающих эти атрибуты со значениями. Оценка происходит в узлах абстрактного синтаксического дерева , когда язык обрабатывается каким-либо парсером или компилятором .

Атрибуты делятся на две группы: синтезированные атрибуты и унаследованные атрибуты. Синтезированные атрибуты являются результатом правил оценки атрибутов, и они также могут использовать значения унаследованных атрибутов. Унаследованные атрибуты передаются от родительских узлов.

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

Грамматики атрибутов также могут использоваться для перевода синтаксического дерева непосредственно в код для некоторой конкретной машины или на некоторый промежуточный язык .

Одной из сильных сторон атрибутивных грамматик является то, что они могут передавать информацию из любого места абстрактного синтаксического дерева в любое другое место контролируемым и формальным способом. ^{[ необходима цитата ]}

История [ править ]

Грамматики атрибутов были изобретены Дональдом Кнутом и Питером Вегнером . ^[1] В то время как Дональд Кнут считается автором общей концепции, Питер Вегнер изобрел унаследованные атрибуты во время разговора с Кнутом. Некоторые зародышевые идеи восходят ^[1] к работе Эдгара Т. «Неда» Айронса ^[2], автора IMP .

Пример [ править ]

Ниже приводится простая контекстно-свободная грамматика, которая может описывать язык, состоящий из умножения и сложения целых чисел.

 Expr → Expr + Term  Expr → Term  Term → Term * Factor  Term → Factor  Factor → "(" Expr ")" Factor → целое число

Следующая грамматика атрибутов может использоваться для вычисления результата выражения, записанного в грамматике. Обратите внимание, что эта грамматика использует только синтезированные значения и, следовательно, является грамматикой с S-атрибутами .

 Выражение ₁ → Выражение ₂ + Термин [ Выражение _1. Значение = Выражение _2. Значение + Термин. Значение ] Выражение → Термин [ Выражение. Значение = Термин. Значение] Термин ₁ → Термин ₂ * Фактор [ Термин _1. Значение = Термин ₂ . значение * Фактор. значение ] Термин → Фактор [ Термин. значение = Фактор. значение ] Фактор → "(" Expr ")" [ Factor .value = Expr .value] Factor → integer [ Factor .value = strToInt ( integer .str)]

Синтезированные атрибуты [ править ]

Синтезированный атрибут вычисляется из значений атрибутов дочерних элементов. Поскольку сначала необходимо вычислить значения дочерних элементов, это пример восходящего распространения. Чтобы формально определить синтезируемый атрибут, пусть будет формальная грамматика, где ${\ Displaystyle G = \ langle V_ {n}, V_ {t}, P, S \ rangle}$

${\ displaystyle V_ {n}}$ набор нетерминальных символов
${\ displaystyle V_ {t}}$ это набор терминальных символов
${\ displaystyle P}$ это множество постановок
${\ displaystyle S}$ это выделенный или начальный символ

Затем, учитывая строку нетерминальных символов и имя атрибута , это синтезированный атрибут, если выполняются все три из этих условий: ${\ displaystyle A}$ ${\ displaystyle a}$ ${\ displaystyle Aa}$

${\ displaystyle A \ rightarrow \ alpha \ in P}$ (т.е. это одно из правил грамматики) ${\ displaystyle A \ rightarrow \ alpha}$
$\alpha =\alpha _{1}\ldots \alpha _{n},\forall i,1\leq i\leq n:\alpha _{i}\in (V_{n}\cup V_{t})$ (т.е. каждый символ в теле правила является либо нетерминальным, либо конечным)
$A.a=f(\alpha _{j_{1}}.a_{1},\ldots ,\alpha _{j_{m}}.a_{m})$ , где (т.е. значение атрибута - это функция, применяемая к некоторым значениям из символов в теле правила) $\{\alpha _{j_{1}},\ldots ,\alpha _{j_{m}}\}\subseteq \{\alpha _{1},\ldots ,\alpha _{n}\}$ $f$

Унаследованные атрибуты [ править ]

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

S → ABC

где A может получать значения из S, B и C. B может принимать значения из S, A и C. Точно так же C может принимать значения из S, A и B.

Специальные типы грамматик атрибутов [ править ]

Грамматика с L-атрибутами : унаследованные атрибуты могут быть оценены за один обход абстрактного синтаксического дерева слева направо
Грамматика с LR-атрибутами : грамматика с L-атрибутами, унаследованные атрибуты которой также могут быть оценены при анализе снизу вверх .
Грамматика с атрибутами ECLR : подмножество грамматик с атрибутами LR, в которых классы эквивалентности могут использоваться для оптимизации оценки унаследованных атрибутов.
Грамматика с S-атрибутами : простой тип грамматики атрибутов, использующий только синтезированные атрибуты , но без унаследованных атрибутов

См. Также [ править ]

Ссылки [ править ]

^ ^a ^b Д. Э. Кнут: Генезис атрибутивных грамматик . Труды международной конференции по атрибутивным грамматикам и их приложениям (1990), LNCS, vol. 461 , 1–12.
^ http://zzcad.com/ned.htm

Внешние ссылки [ править ]

Почему грамматики атрибутов имеют значение , The Monad Reader, выпуск 4, 5 июля 2005 г. (В этой статье рассказывается о том, как формализм грамматик атрибутов привносит аспектно-ориентированное программирование в функциональное программирование , помогая писать катаморфизмы композиционно . Это относится к грамматике атрибутов Утрехтского университета система как реализация, используемая в примерах.)
Грамматика атрибутов применительно к Haskell и функциональному программированию .
Семантика контекстно-свободных языков , написанная Доном Кнутом , - это оригинальная статья, в которой вводятся атрибутивные грамматики.
Юкка Паакки: Парадигмы атрибутивной грамматики - высокоуровневая методология реализации языка . ACM Computing Surveys 27 : 2 (июнь 1995), 196–255.

[genesis-1] Д. Э. Кнут: Генезис атрибутивных грамматик . Труды международной конференции по атрибутивным грамматикам и их приложениям (1990), LNCS, vol. 461 , 1–12.

[2] ttp://zzcad.com/ned.htm

[1]