Gramática 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.[1]

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.

Uma Gramática de Atributos é uma tupla ${\displaystyle A=(G,V,F)\,}$ onde:

• ${\displaystyle G}$ é uma gramática livre de contexto.
• ${\displaystyle V}$ é um conjunto finito de atributos distintos.
• ${\displaystyle F}$ é um conjunto finito de asserções a atributos ou predicados.

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) ]

As gramáticas de atributo foram inventadas por Donald Knuth e Peter Wegner.[2] 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[2] à obra de Edgar T. "Ned" Irons,[3] o autor da linguagem IMP.

• Gramáticas de Van Wijngaarden

• 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)

• 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.