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

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.

 ExprExpr + Term
 ExprTerm
 TermTerm * Fator
 TermFator
 Fator → "(" Expr ")"
 Fatorinteiro

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.

 Expr1Expr2 + Term [ Expr1.valor = Expr22.valor + Term.valor ]
 ExprTerm [ Expr.valor = Term.valor ]
 Term1Term2 * Fator [ Term1.valor = Term2.valor * Fator.valor ]
 TermFator [ Term.valor = Fator.valor ]
 Fator → "(" Expr ")" [ Fator.valor =  Expr.valor ]
 Fatorinteiro [ 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 
  • 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

  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 
  2. 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.
  3. «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.