Gramática de atributos

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

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 $A=(G,V,F)\,$ onde:

• $G$ é uma gramática livre de contexto.
• $V$ é um conjunto finito de atributos distintos.
• $F$ é 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. 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

• Aho, Alfred V.; Ullman, Jeffrey D. (1977). Principles of Compiler Design. Reading, Massachusetts, EUA: Addison-Wesley. 604 páginas. ISBN 0-201-00022-9  !CS1 manut: Nomes múltiplos: lista de autores (link)

• Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. (1986). Compilers: Principles, Techniques and Tools. Reading, Massachusetts, EUA: Addison-Wesley. 796 páginas. ISBN 0-201-10088-6  !CS1 manut: Nomes múltiplos: lista de autores (link)

• Pittman, Thomas; Peters, James (1992). The Art of Compiler Design. Theory and Practice. Englewood Cliffs, New Jersey, EUA: Prentice Hall. 419 páginas. ISBN 0-13-048190-4  !CS1 manut: Nomes múltiplos: lista de autores (link)

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.