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

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

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

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

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

Грамматики атрибутов были изобретены Дональдом Кнутом и Питером Вегнером . ^[3] Хотя Дональду Кнуту приписывают общую концепцию, Питер Вегнер изобрел унаследованные атрибуты во время разговора с Кнутом. Некоторые эмбриональные идеи восходят к ^[3] работам Эдгара Т. «Неда» Айронса, ^[4] автор ИМП .

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

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

 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) ]

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

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

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

Тогда, учитывая строку нетерминальных символов $A$ и имя атрибута $a$ , $A.a$ является синтезированным атрибутом, если соблюдены все три условия:

$A\rightarrow \alpha \in P$ (т.е. $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$ применяется к некоторым значениям символов в теле правила)

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

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

С → АВС

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

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

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

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

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

^ Кнут 1968 , с. 134.
^ Кнут 1968 , с. 132.
^ Jump up to: Перейти обратно: ^а ^б Д. Е. Кнут: Происхождение атрибутивных грамматик . Материалы международной конференции по грамматикам атрибутов и их приложениям (1990), LNCS, vol. 461 , 1–12.
^ "Основной" .
^ Кнут 1968 , с. 130.

Оригинальная статья, представляющая атрибутивные грамматики: Кнут, Дональд Э. (1968). «Семантика контекстно-свободных языков» (PDF) . Теория математических систем . 2 (2): 127–145. дои : 10.1007/BF01692511 . S2CID 5182310 . Архивировано из оригинала 19 мая 2020 г. Проверено 23 марта 2018 г. {{cite journal}}: CS1 maint: bot: исходный статус URL неизвестен ( ссылка ) ,

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

Почему грамматики атрибутов имеют значение , The Monad Reader, выпуск 4, 5 июля 2005 г. (Эта статья повествует о том, как формализм грамматик атрибутов привносит аспектно-ориентированное программирование в функциональное программирование, помогая писать катаморфизмы композиционно . Это относится к грамматике атрибутов Утрехтского университета. Архивировано 5 июня 2013 г. в системе Wayback Machine (см. также Lrc: Чисто функциональная система, основанная на грамматике атрибутов высшего порядка ) в качестве реализации, используемой в примерах.)
Грамматика атрибутов применительно к Haskell и функциональному программированию .
Юкка Паакки: Парадигмы атрибутивной грамматики — методология высокого уровня в языковой реализации . ACM Computing Surveys 27 :2 (июнь 1995 г.), 196–255.
Ox — это система компиляции грамматики атрибутов, которая дополняет спецификации Lex и Yacc определениями синтезированных и унаследованных атрибутов, написанными в комбинации синтаксиса Ox и C / C++ . Из этих спецификаций Ox генерирует обычные спецификации Lex и Yacc, которые строят и декорируют атрибутированное дерево разбора . Ox работает с версиями Lex и Yacc, распространяемыми в операционных системах Unix и Solaris , Flex , RE/flex , Bison , BYacc , BtYacc и MSTA (в репозитории DINO GitHub) . (См. репозиторий SourceForge .)
Silver — это расширяемый язык и система спецификации грамматики атрибутов, разработанный Университетом Миннесоты. (См. также репозиторий GitHub .)

[FOOTNOTEKnuth1968134-1] Кнут 1968 , с. 134.

[FOOTNOTEKnuth1968132-2] Кнут 1968 , с. 132.

[genesis-3] Jump up to: Перейти обратно: ^а ^б Д. Е. Кнут: Происхождение атрибутивных грамматик . Материалы международной конференции по грамматикам атрибутов и их приложениям (1990), LNCS, vol. 461 , 1–12.

[4] "Основной" .

[FOOTNOTEKnuth1968130-5] Кнут 1968 , с. 130.

[1]

[2]

[3]

[4]

[5]