Uma gramática de atributos é uma formalização que permite definir os atributos para as produções de uma gramática formal, associando estes atributos com valores. A avaliação ocorre nos nodos da árvore sintática abstrata, quando a linguagem é processada por algum analisador sintático ou compilador.
Tipos de Atributos thumb|400px|Atributos Herdados e Sintetizados
Os atributos são divididos em dois grupos: os atributos sintetizados e atributos herdados. Os atributos sintetizados, também denominados derivados, são associados aos não-terminais das regras de produção aos quais eles se encontram ligados. Os atributos herdados são passados através dos nodos pais e são definidos por asserções nas produções cujo lado direito contenha referências ao não terminal ao qual se encontram ligados.
Em algumas abordagens, os atributos sintetizados são utilizados para transmitir informação semântica no sentido bottom-up na árvore sintática ao passo que os atributos herdados passam informações semânticas no sentido top-down na árvore sintática. Por exemplo, quando se está a construir uma ferramenta de tradução, como um compilador pode-se atribuir valores semânticos à construções sintáticas. Também é possível realizar verificações semânticas associadas à gramática de atributos, representando regras da linguagem não contempladas explicitamente pela sintaxe.
Gramáticas de atributos também podem ser utilizadas para traduzir a árvore sintática diretamente para o código específico de algumas máquinas, ou em alguma línguagem intermediária.
Definição Uma Gramática de Atributos é uma tupla onde:
é uma gramática livre de contexto. é um conjunto finito de atributos distintos. é um conjunto finito de asserções a atributos ou predicados.
Exemplo
O seguinte é uma gramática livre de contexto simples que pode descrever uma linguagem composta de multiplicação e adição de números inteiros.
Expr → Expr + Term Expr → Term Term → Term * Fator Term → Fator Fator → "(" Expr ")" Fator → inteiro
A seguinte gramática de atributos pode ser usada para calcular o resultado de uma expressão escrita na gramática. Note-se que essa gramática só usa valores sintetizados, e por isso é uma gramática S-atribuída. Expr1 → Expr2 + Term [ Expr1.valor = Expr22.valor + Term.valor ] Expr → Term [ Expr.valor = Term.valor ] Term1 → Term2 * Fator [ Term1.valor = Term2.valor * Fator.valor ] Term → Fator [ Term.valor = Fator.valor ] Fator → "(" Expr ")" [ Fator.valor = Expr.valor ] Fator → inteiro [ Fator.valor = strToInt(inteiro.str) ]
História As gramáticas de atributo foram inventadas por Donald Knuth e Peter Wegner.D. E. Knuth: The genesis of attribute grammars. Proceedings of the international conference on Attribute grammars and their applications (1990), LNCS, vol. 461, 1–12. Enquanto Donald Knuth tem o crédito pelo conceito geral, Peter Wegner inventou os atributos herdados durante uma conversa com Knuth. Algumas ideias embrionárias remontam à obra de Edgar T. "Ned" Irons, o autor da linguagem IMP.
Ver também Gramáticas de Van Wijngaarden
Bibliografia
Ligações Externas D. E. Knuth: O berço das Gramáticas de Atributo. Proceedings of the international conference on Attribute grammars and their applications (1990), 1–12. Some informal, historical information.
Categoria:Teoria da computação