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

редактировать

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

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

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

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

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

Содержание

1 История
2 Пример
3 Синтезированные атрибуты
4 Унаследованные атрибуты
5 Специальные типы грамматик атрибутов
6 См. Также
7 Ссылки
8 Внешние ссылки

История

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

Example

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

Expr → Expr + TermExpr → TermTerm → Term * FactorTerm → FactorFactor → "(" Expr ")" Фактор → целое число

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

Expr 1→ Expr 2+ Term [Expr 1.value = Expr 2.value + Term .value] Expr → Term [Expr .value = Term . значение] Термин 1→ Термин 2* Фактор [Термин 1.value = Термин 2.value * Фактор .value] Член → Фактор [Член .value = Фактор .value] Фактор → "(" Выражение ")" [Фактор .value = Выражение .value] Фактор → целое число [Фактор .value = strToInt (integer. str)]

Синтезированные атрибуты

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

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

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

$A → α ∈ P {\ displaystyle A \ rightarrow \ alpha \ in P}$ $A \ rightarrow \ alpha \ in P$ (т.е. $A → α {\ displaystyle A \ rightarrow \ alpha}$ ${\ displaystyle A \ rightarrow \ alpha}$ - одно из правил грамматики)
$α = α 1… α n, ∀ i, 1 ≤ i ≤ N: α я ∈ (В N ∪ В T) {\ Displaystyle \ альфа = \ альфа _ {1} \ ldots \ alpha _ {n}, \ forall i, 1 \ Leq я \ Leq п: \ альфа _ { i} \ in (V_ {n} \ cup V_ {t})}$ ${\ displaystyle \ alpha = \ alpha _ {1} \ ldots \ alpha _ {n}, \ forall i, 1 \ leq i \ leq n: \ alpha _ {i} \ in (V_ {n} \ чашка V_ {t})}$ (т.е. каждый символ в теле правила является либо нетерминальным, либо конечным)
$A. a = е (α j 1. a 1,…, α jm. am) {\ displaystyle Aa = f (\ alpha _ {j_ {1}}. a_ {1}, \ ldots, \ alpha _ {j_ {m }}. a_ {m})}$ ${\ displaystyle Aa = f (\ alpha _ {j_ {1}}. a_ {1}, \ ldots, \ alpha _ {j_ {m}}. a_ {m})}$ , где ${α j 1,…, α jm} ⊆ {α 1,…, α n} {\ displaystyle \ {\ alpha _ {j_ {1}}, \ ldots, \ alpha _ {j_ {m}} \} \ substeq \ {\ alpha _ {1}, \ ldots, \ alpha _ {n} \}}$ ${\ displaystyle \ {\ alpha _ {j_ {1}}, \ ldots, \ alpha _ {j_ {m}} \} \ substeq \ {\ alpha _ {1}, \ ldots, \ alpha _ {n} \}}$ (т.е. значение атрибута - это функция $f {\ displaystyle f}$ $f$ , применяемая к некоторым значениям из символов в теле правила)

Унаследованные атрибуты

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

S → ABC

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

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

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

См. также

Ссылки

Внешние ссылки

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