Грамматика атрибутов - Attribute grammar

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

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

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

История

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

Пример

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

 Expr → Expr + Term
 Expr → Term
 Term → Term * Factor
 Term → Factor
 Factor → "(" Expr ")"
 Factor → integer

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

 Expr₁ → Expr₂ + Term [ Expr₁.value = Expr₂.value + Term.value ]
 Expr → Term [ Expr.value = Term.value ]
 Term₁ → Term₂ * Factor [ Term₁.value = Term₂.value * Factor.value ]
 Term → Factor [ Term.value = Factor.value ]
 Factor → "(" 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}$
${\ displaystyle \ alpha = \ alpha _ {1} \ ldots \ alpha _ {n}, \ forall i, 1 \ leq i \ leq n: \ alpha _ {i} \ in (V_ {n} \ cup V_ { t})}$ (т.е. каждый символ в теле правила является либо нетерминальным, либо терминальным)
${\ displaystyle Aa = f (\ alpha _ {j_ {1}}. a_ {1}, \ ldots, \ alpha _ {j_ {m}}. a_ {m})}$ , где (т.е. значение атрибута - это функция, применяемая к некоторым значениям из символов в теле правила) ${\ displaystyle \ {\ alpha _ {j_ {1}}, \ ldots, \ alpha _ {j_ {m}} \} \ substeq \ {\ alpha _ {1}, \ ldots, \ alpha _ {n} \ }}$ ${\ displaystyle f}$

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

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

S → ABC

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

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

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

Смотрите также

использованная литература

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

Почему грамматики атрибутов имеют значение , The Monad Reader, выпуск 4, 5 июля 2005 г. (В этой статье рассказывается о том, как формализм грамматик атрибутов привносит аспектно-ориентированное программирование в функциональное программирование , помогая писать катаморфизмы композиционно . Это относится к грамматике атрибутов Утрехтского университета system (см. также Lrc: чисто функциональная система на основе грамматики атрибутов высшего порядка ) в качестве реализации, используемой в примерах.)
Грамматика атрибутов применительно к Haskell и функциональному программированию .
Оригинальная статья, вводящая атрибутированные грамматики: Knuth, Donald E. (1968). «Семантика контекстно-свободных языков» (PDF) . Математическая теория систем . 2 (2): 127–145. DOI : 10.1007 / BF01692511 . S2CID 5182310 .
Юкка Паакки: Парадигмы атрибутивной грамматики - высокоуровневая методология реализации языка . ACM Computing Surveys 27 : 2 (июнь 1995), 196–255.
Silver - это расширяемый язык и система спецификации грамматики атрибутов от Университета Миннесоты. (См. Также репозиторий GitHub .)

Languages

In other projects