Tabela de símbolos

A gramática de atributos é adequada para lidar com atributos com dependência local.

No entanto, podemos ter informação cuja origem não tem dependência directa na árvore sintáctica (por exemplo, múltiplas aparições duma variável), ou que pode mesmo residir no processamento de outro código fonte (por exemplo, nomes de classes definidas noutro ficheiro).

Assim, sempre que a linguagem utiliza símbolos para representar entidades do programa – como sejam: variáveis, funções, registos, classes, etc. – torna-se necessário associar à identificação do símbolo (geralmente um identificador) a sua definição (categoria do símbolo, tipo de dados associado).

É para esse fim que existe a tabela de símbolos.

A tabela de símbolos é um array associativo, em que a chave é o nome do símbolo, e o elemento um objecto que define o símbolo.

As tabelas de símbolos podem ter um alcance global, ou local (por exemplo: a uma bloco de código ou a uma função).

A informação associada a cada símbolo depende do tipo de linguagem definida, assim como de estarmos na presença de um interpretador ou de um compilador.

São exemplos dessas propriedades:

• Nome: nome do símbolo (chave do array associativo);

• Categoria: o que é que o símbolo representa, classe, método, variável de objeto, variável local, etc;

• Tipo: tipo de dados do símbolo;

• Valor: valor associado ao símbolo (apenas no caso de interpretadores);

• Visibilidade: restrição no acesso ao símbolo (para linguagem com encapsulamento).

Implementação

Numa aproximação orientada por objetos podemos definir a classe abstracta Symbol:

public abstract class Symbol {
    public Symbol(String name, Type type){...}
    public String name(){...}
    public Type type(){...}
}

Podemos agora definir uma variável:

public class VariableSymbol extends Symbol {
    public VariableSymbol(String name, Type type){
        super(name, type);
    }
}

A classe Type permite a identificação e verificação da conformidade entre tipos:

public abstract class Type{
    protected Type(String name){...}
    public String name(){...}
    public boolean subtype(Type other){
        assert other != null;
        return name.equals(other.name()); 
    }
}

Podemos agora implementar tipos específicos:

public class RealType extends Type {
    public RealType () { super("real"); }
}

public class IntegerType extends Type {
    public IntegerType() { super("integer"); }
    public boolean subtype (Type other) {
        return super.subtype(other) || other.name().equals("real");
    }
}

Agrupando símbolos em contexto

Se a linguagem é simples, contendo um único contexto de definição de símbolos, então o tempo de vida dos símbolos está ligado ao tempo de vida do programa, sendo suficiente uma única tabela de símbolos.

No entanto, se tivermos a possibilidade de definir símbolos em contextos diferentes, então precisamos de resolver o problema dos símbolos terem tempos de vida (e/ou visibilidade) que dependem do contexto dentro do programa.

Considere como exemplo o seguinte código (na linguagem C):

int x;            // global scope
void f() {        // global scope
    int y;        // local scope
    [ int x; ]    // nested local scope
    [ int Y; ]    // nested local scope
}
void g() {        // global scope
    int y;        // local scope
}

A numeração identifica os diferentes contextos de símbolos.

Um aspecto muito importante é o facto dos contextos poderem ser definidos dentro de outros contextos.

Para representar adequadamente esta informação estrutura-se as diferentes tabelas de símbolos numa árvore onde cada nó representa uma pilha de tabelas de símbolos a começar nesse nó até à raiz (tabela de símbolos global).

Consoante o ponto onde estamos no programa. temos uma pilha de tabelas de símbolos definida para resolver os símbolos.

Pode haver repetição de nomes de símbolos, valendo o definido na tabela mais próxima (no ordem da pilha).

Caso seja necessário percorrer a árvore sintáctica várias vezes, podemos registar numa lista ligada a sequência de pilhas de tabelas de símbolos que são aplicáveis em cada ponto do programa.