Грамматика атрибутов
Грамматика атрибутов — это формальный способ дополнить формальную грамматику обработкой семантической информации. Семантическая информация хранится в атрибутах , связанных с терминальными и нетерминальными символами грамматики. Значения атрибутов являются результатом правил оценки атрибутов, связанных с постановкой грамматики. Атрибуты позволяют передавать информацию из любого места абстрактного синтаксического дерева в любое другое место контролируемым и формальным способом. [1]
Каждая семантическая функция имеет дело с атрибутами символов, встречающимися только в одном продукционном правиле: и параметры семантической функции, и ее результат являются атрибутами символов из одного конкретного правила. Когда семантическая функция определяет значение атрибута символа в левой части правила, атрибут называется синтезированным ; в противном случае его называют унаследованным . [2] Таким образом, синтезированные атрибуты служат для передачи семантической информации вверх по дереву синтаксического анализа, а унаследованные атрибуты позволяют передавать значения от родительских узлов вниз и по всему синтаксическому дереву.
В простых приложениях, таких как вычисление арифметических выражений, грамматика атрибутов может использоваться для описания всей задачи, которую необходимо выполнить, помимо прямого анализа; в сложных системах, например, при создании инструмента языкового перевода, такого как компилятор, его можно использовать для проверки семантических проверок, связанных с грамматикой, представляющей правила языка, не указанные явно в определении синтаксиса. Он также может использоваться анализаторами или компиляторами для перевода синтаксического дерева непосредственно в код для какой-либо конкретной машины или на какой-либо промежуточный язык .
История [ править ]
Грамматики атрибутов были изобретены Дональдом Кнутом и Питером Вегнером . [3] Хотя Дональду Кнуту приписывают общую концепцию, Питер Вегнер изобрел унаследованные атрибуты во время разговора с Кнутом. Некоторые эмбриональные идеи восходят к [3] работам Эдгара Т. «Неда» Айронса, [4] автор ИМП .
Пример [ править ]
Ниже приведена простая контекстно-свободная грамматика , которая может описать язык, состоящий из умножения и сложения целых чисел.
Выраж → Выраж + Терм Выраж → Терм Термин → Терм * Фактор Термин → Фактор Фактор → "(" Выраж ")" Фактор → целое число
Следующая грамматика атрибутов может использоваться для вычисления результата выражения, записанного в грамматике. Обратите внимание, что эта грамматика использует только синтезированные значения и, следовательно, является с атрибутом S. грамматикой
Выражение 1 → Выражение 2 + Термин [ Выражение 1.значение = Выражение 2.значение + Термин.значение ] Выражение → Срок [ Выражение.значение = Термин.значение ] Термин 1 → Термин 2 * Фактор [ Значение термина 1 = Значение термина 2 * Значение фактора ] Термин → Фактор [ Термин.значение = Фактор.значение ] Коэффициент → "(" Выражение ")" [ Фактор.значение = Выраж.значение ] Фактор → целое число [ Фактор.значение = strToInt( целое число.str)]
Синтезированные атрибуты [ править ]
Синтезированный атрибут вычисляется на основе значений атрибутов дочерних элементов. Поскольку сначала необходимо вычислить значения дочерних элементов, это пример распространения снизу вверх. [5] Чтобы формально определить синтезированный атрибут, пусть быть формальной грамматикой, где
- это набор нетерминальных символов
- это набор терминальных символов
- это набор постановок
- является отличительным или стартовым символом
Тогда, учитывая строку нетерминальных символов и имя атрибута , является синтезированным атрибутом, если соблюдены все три условия:
- (т.е. это одно из правил грамматики)
- (т.е. каждый символ в теле правила является либо нетерминальным, либо терминальным)
- , где (т.е. значение атрибута является функцией применяется к некоторым значениям символов в теле правила)
Унаследованные атрибуты [ править ]
в Унаследованный атрибут узле дерева синтаксического анализа определяется с использованием значений атрибута в родительском или одноуровневом узлах. Унаследованные атрибуты удобны для выражения зависимости конструкции языка программирования от контекста, в котором она появляется. Например, мы можем использовать унаследованный атрибут, чтобы отслеживать, появляется ли идентификатор слева или справа от присваивания, чтобы решить, нужен ли адрес или значение идентификатора. В отличие от синтезированных атрибутов, унаследованные атрибуты могут принимать значения от родителя и/или дочерних элементов. Как и в следующей постановке,
- С → АВС
где A может получать значения от S, B и C. B может принимать значения от S, A и C. Аналогично, C может принимать значения от S, A и B.
Специальные типы грамматик атрибутов [ править ]
- Грамматика с L-атрибутами : унаследованные атрибуты могут быть оценены за один обход абстрактного синтаксического дерева слева направо.
- Грамматика с атрибутом LR : грамматика с атрибутом L, унаследованные атрибуты которого также могут быть оценены при синтаксическом анализе снизу вверх .
- Грамматика с атрибутом ECLR : подмножество грамматик с атрибутом LR, где классы эквивалентности могут использоваться для оптимизации оценки унаследованных атрибутов.
- Грамматика с S-атрибутами : простой тип грамматики атрибутов, использующий только синтезированные атрибуты , но без унаследованных атрибутов.
См. также [ править ]
Ссылки [ править ]
- ^ Кнут 1968 , с. 134.
- ^ Кнут 1968 , с. 132.
- ^ Перейти обратно: а б Д. Е. Кнут: Происхождение атрибутивных грамматик . Материалы международной конференции по грамматикам атрибутов и их приложениям (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 .)