Атрибутивная грамматика
Грамматика атрибутов-это формальный способ определения атрибутов для создания формальной грамматики, связывающий эти атрибуты со значениями. Вычисление происходит в узлах абстрактного синтаксического дерева, когда язык обрабатывается каким-либо синтаксическим анализатором или компилятором.
Атрибуты делятся на две группы: синтезированные атрибуты и унаследованные атрибуты. Синтезированные атрибуты являются результатом правил оценки атрибутов, а также могут использовать значения унаследованных атрибутов. Унаследованные атрибуты передаются от родительских узлов.
В некоторых подходах синтезированные атрибуты используются для передачи семантической информации вверх по дереву синтаксического анализа, в то время как унаследованные атрибуты помогают передавать семантическую информацию вниз и через него. Например, при создании инструмента перевода языка, такого как компилятор, он может использоваться для присвоения семантических значений синтаксическим конструкциям. Кроме того, можно проверить семантические проверки, связанные с грамматикой, представляющей правила языка, явно не переданные определением синтаксиса.
Атрибутивные грамматики могут также использоваться для перевода синтаксического дерева непосредственно в код для некоторой конкретной машины или на некоторый промежуточный язык.
Одной из сильных сторон атрибутивных грамматик является то, что они могут передавать информацию из любого места абстрактного синтаксического дерева в любое другое место контролируемым и формальным способом
История[править]
Атрибутивные грамматики были изобретены Дональдом Кнутом и Питером Вегнером.[1] в то время как Дональду Кнуту приписывают общую концепцию, Питер Вегнер изобрел унаследованные атрибуты во время разговора с кнутом. Некоторые эмбриональные идеи восходят[1] к работе Эдгара т. "Неда" Айронса, автора IMP.
Пример[править]
Ниже приводится простая контекстно-свободная грамматика, которая может описать язык, состоящий из умножения и сложения целых чисел.
Expr → Expr + Term
Expr → Term
Term → Term * Factor
Term → Factor
Factor → " ("Expr ")"
Фактор → целое число
Для вычисления результата выражения, записанного в грамматике, можно использовать следующую грамматику атрибутов. Обратите внимание, что эта грамматика использует только синтезированные значения и поэтому является s-атрибутивной грамматикой.
Expr1 → Expr2 + Термин [ Expr1.значение = Expr2.значение + термин.ценность ]
Expr → Термин [ Expr.значение = срок.ценность ]
Термин1 → Термин2 * Фактор [ Термин1.значение = термин2.значение * фактор.ценность ]
Термин → Фактор [ Термин.значение = фактор.ценность ]
Фактор → "(" Expr") " [ Фактор.значение = Expr.ценность ]
Фактор → целое число [ фактор.value = strToInt (целоечисло .ул) ]
Синтезированные атрибуты[править]
Синтезированный атрибут вычисляется из значений атрибутов дочерних элементов. Поскольку значения дочерних элементов должны быть вычислены в первую очередь, это пример распространения снизу вверх. Чтобы формально определить синтезированный атрибут, пусть G = ⟨ V n , V t , P , S ⟩ }это формальная грамматика, где
V n это набор нетерминальных символов V t это набор терминальных символов P П есть множество постановок S С является ли выделенный, или начальный, символ
Затем, заданная строка нетерминальных символов A Одини имя атрибута a один, A . a А. Аявляется синтезированным атрибутом, если выполняются все три из этих условий:
A → α ∈ P есть это одно из правил грамматики) α = α 1 … α n , ∀ i , 1 ≤ i ≤ n : α i ∈ ( V n ∪ V t ) (то есть каждый символ в теле правила является либо нетерминальным, либо терминальным) A . a = f ( α j 1 . a 1 , … , α j m . a m ) (т. е. значение атрибута - это функция f ф, применяемая к некоторым значениям из символов в теле правила)
Унаследованные атрибуты[править]
Унаследованный атрибут в узле синтаксического анализа дерево определяется с помощью значений атрибутов у родителя или братьев и сестер. Унаследованные атрибуты удобны для выражения зависимости конструкции языка программирования от контекста, в котором она появляется. Например, мы можем использовать унаследованный атрибут, чтобы отслеживать, появляется ли идентификатор слева или справа от назначения, чтобы решить, нужен ли адрес или значение идентификатора. В отличие от синтезированных атрибутов, унаследованные атрибуты могут принимать значения от родителей и / или братьев и сестер. Как и в следующем производстве,
S → ABC
где A может получать значения из S, B и C. B может принимать значения из S, A и C. аналогично, C может принимать значения из S, A и B. Специальные типы атрибутивных грамматик
- L-атрибутивная грамматика: унаследованные атрибуты могут быть оценены в одном обходе слева направо абстрактного синтаксического дерева
- LR-атрибутивная грамматика: L-атрибутивная грамматика, унаследованные атрибуты которой также могут быть оценены при анализе снизу вверх.
- Eclr-атрибутивная грамматика: подмножество LR-атрибутивных Грамматик, в которых классы эквивалентности могут использоваться для оптимизации оценки унаследованных атрибутов.
- S-атрибутивная грамматика: простой тип атрибутивной грамматики, использующий только синтезированные атрибуты, но не наследуемые атрибуты
См. также[править]
Пруф[править]
wiki.haskell.org/The_Monad.Reader/Issue4/Why_Attribute_Grammars_Matter