Атрибутивные грамматики: Семантический анализ и преобразование синтаксических деревьев
Attribute grammar
Атрибутивная грамматика: формальный метод добавления семантики к грамматике. Атрибуты и правила вычисления для обработки информации в синтаксическом дереве.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
Атрибутная грамматика – это формальный способ дополнения формальной грамматики обработкой семантической информации. Семантическая информация хранится в атрибутах, связанных с терминальными и нетерминальными символами грамматики. Значения атрибутов являются результатом применения правил вычисления атрибутов, связанных с продукциями грамматики. Атрибуты обеспечивают передачу информации из любой точки абстрактного синтаксического дерева в любую другую, контролируемым и формальным образом. Каждая семантическая функция оперирует атрибутами символов, встречающихся только в одном продукционном правиле: как параметры семантической функции, так и её результат являются атрибутами символов из одного конкретного правила. Если семантическая функция определяет значение атрибута символа, находящегося в левой части правила, этот атрибут называется синтезированным; в противном случае он называется унаследованным. Таким образом, синтезированные атрибуты служат для передачи семантической информации вверх по дереву разбора, а унаследованные атрибуты позволяют передавать значения от родительских узлов вниз и по дереву синтаксического анализа. В простых приложениях, таких как вычисление арифметических выражений, атрибутная грамматика может использоваться для описания всей задачи, которую необходимо выполнить, помимо синтаксического анализа, простым способом. В сложных системах, например, при создании инструмента для преобразования языка, такого как компилятор, она может использоваться для проверки семантических ограничений, связанных с грамматикой, представляющих правила языка, неявно заданные в определении синтаксиса. Она также может использоваться парсерами или компиляторами для непосредственного преобразования синтаксического дерева в код для конкретной машины или в промежуточный язык.
An attribute grammar is a formal way to supplement a formal grammar with semantic information processing. Semantic information is stored in attributes associated with terminal and nonterminal symbols of the grammar. The values of attributes are the result of attribute evaluation rules associated with productions of the grammar. Attributes allow the transfer of information from anywhere in the abstract syntax tree to anywhere else, in a controlled and formal way. Each semantic function deals with attributes of symbols occurring only in one production rule: both semantic function parameters and its result are attributes of symbols from one particular rule. When a semantic function defines the value of an attribute of the symbol on the left hand side of the rule, the attribute is called synthesized; otherwise it is called inherited. Thus, synthesized attributes serve to pass semantic information up the parse tree, while inherited attributes allow values to be passed from the parent nodes down and across the syntax tree. In simple applications, such as evaluation of arithmetic expressions, attribute grammar may be used to describe the entire task to be performed besides parsing in straightforward way; in complicated systems, for instance, when constructing a language translation tool, such as a compiler, it may be used to validate semantic checks associated with a grammar, representing the rules of a language not explicitly imparted by the syntax definition. It may be also used by parsers or compilers to translate the syntax tree directly into code for some specific machine, or into some intermediate language.
История
Атрибутные грамматики были изобретены Дональдом Кнутом и Питером Вегнером. Хотя Дональду Кнуту приписывают общую концепцию, Питер Вегнер изобрел наследуемые атрибуты в ходе беседы с Кнутом. Некоторые ранние идеи прослеживаются к автору IMP.
Attribute grammars were invented by Donald Knuth and Peter Wegner. While Donald Knuth is credited for the overall concept, Peter Wegner invented inherited attributes during a conversation with Knuth. Some embryonic ideas trace back the author of IMP.