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

No algoritmo top-down, ou em Português "análise sintáctica descendente", o reconhecimento é feito por expansão de regras sintácticas, substituindo símbolos não-terminais do lado esquerdo de produções pelo lado direito das produções. Isto significa que a recursividade é feita à direita, tal como acontece no LL(*). Seguidamente, a expansão das regras sintácticas verifica-se por emparelhamento dos símbolos da frase de entrada com os símbolos terminais das regras sintácticas.

De seguida descreve-se o algoritmo top-down de uma forma linear constituída por quatro passos fundamentais.

parâmetros de entrada

uma gramática G e um frase da linguagem L

resultado de retorno

um árvore de derivação

1. Criar a raiz da árvore com o símbolo inicial da gramática.
2. Substituir sucessivamente o símbolo não-terminal mais à esquerda da árvore de derivação pela expressão do lado direito numa produção onde o lado esquerdo é o símbolo em questão.
   Este passo termina quando o primeiro símbolo da produção for um símbolo terminal.
3. Caso o primeiro símbolo não processado da entrada não emparelhar com o primeiro símbolo da produção seleccionada (como descrito no ponto 2) ter-se-á de recuar um passo atrás e reverter o símbolo não-terminal então substituído. Depois, pesquisar outra alternativa na gramática, isto é, procurar outra produção cujo lado esquerdo corresponda ao símbolo não-terminal em questão. Esta técnica é apelida de "backtracking". Caso não existam alternativas, o algoritmo termina sem sucesso.
4. Emparelhar, da esquerda para a direita, os símbolos da frase de entrada com os símbolos terminais nas folhas da árvore de derivação até que aconteça umas das três hipóteses:
   • o emparelhamento de símbolos falha => o algoritmo termina sem sucesso ;
   • detecta-se um símbolo não-terminal numa folha da árvore de derivação => regressa-se ao segundo passo do algoritmo ;
   • todos os símbolos da frase de entrada foram emparelhados com todas as folhas da árvore de derivação, sendo que estas apenas contêm símbolos terminais => o algoritmo termina com sucesso.