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 editar
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 editar
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 editar
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 editar
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 editar
Bibliografia editar
- Aho, Alfred V.; Ullman, Jeffrey D. (1977). Principles of Compiler Design. Reading, Massachusetts, EUA: Addison-Wesley. 604 páginas. ISBN 0-201-00022-9
- 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
- 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
Referências
- ↑ 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
- ↑ a b 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.
- ↑ «Edgar T. Irons - Solebury, Pennsylvania 18963». Consultado em 3 de setembro de 2022
Ligações Externas editar
- 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.