Атрибутивная грамматика

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

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

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

История

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

Пример

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

 Выражение → Выражение + Термин  Выражение → Термин  Термин → Термин * Фактор  Термин → Фактор  Фактор → "(" Выражение ")" Фактор → целое число

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

 Выражение ₁ → Выражение ₂ + Термин [ Выражение ₁ .значение = Выражение ₂ .значение + Термин .значение ] Выражение → Термин [ Выражение .значение = Термин .значение ] Термин ₁ → Термин ₂ * Фактор [ Выражение ₁ .значение = Термин ₂ .значение * Фактор .значение ] Термин → Фактор [ Выражение .значение = Фактор .значение ] Фактор → "(" Выражение ")" [ Фактор .значение = Выражение .значение ] Фактор → целое число [ Фактор .значение = strToInt( целое число .str) ]

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

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

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

Тогда, если задана строка нетерминальных символов и имя атрибута , то это синтезированный атрибут, если выполняются все три условия: $А$ $а$ $Аа$

$A\rightarrow \альфа \in P$ (т.е. одно из правил грамматики) $A\rightarrow \альфа$
$\alpha =\alpha _{1}\ldots \alpha _{n},\forall i,1\leq i\leq n:\alpha _{i}\in (V_{n}\cup V_{t})$ (т.е. каждый символ в теле правила является либо нетерминальным, либо терминальным)
$Aa=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.
^ ab DE Knuth: Генезис атрибутных грамматик. Труды международной конференции по атрибутным грамматикам и их приложениям (1990), LNCS, т. 461, 1–12.
^ "Главное".
↑ Кнут 1968, стр. 130.

Оригинальная статья, представляющая атрибутированные грамматики: Knuth, Donald E. (1968). "Семантика контекстно-свободных языков" (PDF) . Математическая теория систем . 2 (2): 127–145. doi :10.1007/BF01692511. S2CID 5182310. Архивировано из оригинала 2020-05-19 . Получено 2018-03-23 .{{cite journal}}: CS1 maint: бот: исходный статус URL неизвестен ( ссылка ),

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

Почему атрибутивные грамматики имеют значение, The Monad Reader, выпуск 4, 5 июля 2005 г. (В этой статье рассказывается о том, как формализм атрибутивных грамматик привносит аспектно-ориентированное программирование в функциональное программирование, помогая писать катаморфизмы композиционно . В ней упоминается атрибутивная грамматика Утрехтского университета, заархивированная 05.06.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.)