Gramática de atributos

Uma gramática de atributos é uma maneira formal de definir atributos para as produções de uma dada textgramática, associando esses atributos a valores. A avaliação ocorre no nós da árvore de derivação quando a linguagem é tratada por um analisador sintáctico (ou um compilador).

Existem dois tipos distintos de atributos, sendo uns sintetizados e outros herdado. Os primeiros resultam das regras de produção da gramática, sendo que também podem usar o valor de atributos herdados. Os segundos são atributos que são passados para as folhas a partir de nós parentes.

Desta forma, as gramáticas de atributos podem transportar a informação de qualquer sítio para qualquer sítio na árvore sintáctica, isto de maneira controlada e formal. Assim sendo, ilustram-se as razões que tornam as gramáticas de atributos serem poderosas.

Herança

A herança é um principio permitindo a reutilização e adaptabilidade de um certo 'objecto'. O conceito segue o mesmo principio que o de uma árvore genealógica. Isto é, os 'filhos' (elementos derivados) herdam das características dos 'pais' (elementos base).

Esses objectos, ou elementos, possuem atributos e/ou métodos que são próprios a cada um e podem ser transmitidos aos elementos das próximas gerações na árvore. Desta forma, pode-se etiquetar a 'herança' como 'generalização' devido às relações ditas is-a (em Português, "é um/uma") representarem uma hierarquia entre elementos de qualquer natureza.

Cada um desses elementos 'filhos' podem então possuir as mesmas características que os elementos 'pais' e ainda possuir características suplementares que lhes são próprias. Note-se que um elemento 'filho' pode-se tornar 'pai' por sua vez, podendo assim construir-se uma 'árvore genealógica' com várias gerações.

Propagação de atributos

A propagação dos atributos numa GA pode ser um excelente sinónimo para o conceito de herança. De facto pode-se dizer que se propagam os atributos herdados através de um 'canal', podendo-se assim fazer o paralelismo entre o conceito de herança numa GA e uma pipeline.

Isto é, o início da pipeline é o nó raiz da árvore sintáctica. À medida que se encontra um símbolo não-terminal, passa-se os argumentos ("estado da computação") para estes por ordem hierárquica, isto é, entre 'pai' e 'filho' e seguidamente entre 'irmãos'. O resultado da computação dessa sub-árvore apenas é devolvido para cima quando todas as sub-árvores relativas esse ponto tenham sido processadas, assim sucessivamente até à raiz. Assim sendo, pode-se ver esse 'caminho' dos atributos como uma pipeline onde a entrada de uns é a saída dos outros, tal como exemplificado na seguinte figura:

Note-se a propagação dos atributos nas sub-árvores pode ser feita "em paralelo", o que quer dizer que não precisa de se esperar pela computação de todos os elementos anteriores para passar atributos para o próximo nó da árvore. Isto de ponto de vista teórico, como ordem que se infere no grafo de dependências é uma ordem topológica (ou seja parcial), há hipótese da computação dos elementos decorrer em paralelo. No entanto, e apesar de muitos estudos sobre a criação de Calculadores de Atributos Concorrentes, a maioria das vezes a implementação do grafo de dependências é de ordem total, tornando a propagação do atributos sequencial.