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.^[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.

Definição

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.

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.^[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.

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)

Referências

1. 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)
2. 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.
3. «Edgar T. Irons - Solebury, Pennsylvania 18963». Consultado em 3 de setembro de 2022

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.