Projeto do Compilador - Tabela de Símbolos

A tabela de símbolos é uma estrutura de dados importante criada e mantida por compiladores para armazenar informações sobre a ocorrência de várias entidades, como nomes de variáveis, nomes de funções, objetos, classes, interfaces, etc. A tabela de símbolos é usada tanto pela análise quanto pela síntese partes de um compilador.

Uma tabela de símbolos pode servir aos seguintes propósitos, dependendo do idioma em mãos:

Para armazenar os nomes de todas as entidades em um formulário estruturado em um só lugar.
Para verificar se uma variável foi declarada.
Para implementar a verificação de tipo, verificando as atribuições e expressões no código-fonte estão semanticamente corretas.
Para determinar o escopo de um nome (resolução de escopo).

Uma tabela de símbolos é simplesmente uma tabela que pode ser linear ou uma tabela hash. Ele mantém uma entrada para cada nome no seguinte formato:

<symbol name,  type,  attribute>

Por exemplo, se uma tabela de símbolos tiver que armazenar informações sobre a seguinte declaração de variável:

static int interest;

então ele deve armazenar a entrada, como:

<interest, int, static>

A cláusula de atributo contém as entradas relacionadas ao nome.

Implementação

Se um compilador deve lidar com uma pequena quantidade de dados, a tabela de símbolos pode ser implementada como uma lista não ordenada, que é fácil de codificar, mas só é adequada para pequenas tabelas. Uma tabela de símbolos pode ser implementada de uma das seguintes maneiras:

Lista linear (classificada ou não)
Árvore de pesquisa binária
Tabela de hash

Entre todas, as tabelas de símbolos são implementadas principalmente como tabelas hash, onde o próprio símbolo do código-fonte é tratado como uma chave para a função hash e o valor de retorno é a informação sobre o símbolo.

Operações

Uma tabela de símbolos, linear ou hash, deve fornecer as seguintes operações.

inserir()

Esta operação é mais frequentemente utilizada pela fase de análise, ou seja, a primeira metade do compilador onde os tokens são identificados e os nomes são armazenados na tabela. Esta operação é usada para adicionar informações na tabela de símbolos sobre nomes exclusivos que ocorrem no código-fonte. O formato ou estrutura em que os nomes são armazenados depende do compilador em mãos.

Um atributo para um símbolo no código-fonte é a informação associada a esse símbolo. Essas informações contêm o valor, estado, escopo e tipo do símbolo. A função insert () pega o símbolo e seus atributos como argumentos e armazena as informações na tabela de símbolos.

Por exemplo:

int a;

deve ser processado pelo compilador como:

insert(a, int);

olho para cima()

A operação lookup () é usada para pesquisar um nome na tabela de símbolos para determinar:

se o símbolo existe na tabela.
se for declarado antes de ser usado.
se o nome for usado no escopo.
se o símbolo for inicializado.
se o símbolo for declarado várias vezes.

O formato da função lookup () varia de acordo com a linguagem de programação. O formato básico deve corresponder ao seguinte:

lookup(symbol)

Este método retorna 0 (zero) se o símbolo não existir na tabela de símbolos. Se o símbolo existe na tabela de símbolos, ele retorna seus atributos armazenados na tabela.

Gerenciamento do escopo

Um compilador mantém dois tipos de tabelas de símbolos: a global symbol table que pode ser acessado por todos os procedimentos e scope symbol tables que são criados para cada escopo no programa.

Para determinar o escopo de um nome, as tabelas de símbolos são organizadas em estrutura hierárquica, conforme mostrado no exemplo abaixo:

. . . 
int value=10;

void pro_one()
   {
   int one_1;
   int one_2;
   
      {              \
      int one_3;      |_  inner scope 1 
      int one_4;      | 
      }              /
      
   int one_5; 
   
      {              \   
      int one_6;      |_  inner scope 2
      int one_7;      |
      }              /
   }
   
void pro_two()
   {
   int two_1;
   int two_2;
   
      {              \
      int two_3;      |_  inner scope 3
      int two_4;      |
      }              /
      
   int two_5;
   }
. . .

O programa acima pode ser representado em uma estrutura hierárquica de tabelas de símbolos:

A tabela de símbolos globais contém nomes para uma variável global (valor int) e dois nomes de procedimento, que devem estar disponíveis para todos os nós filhos mostrados acima. Os nomes mencionados na tabela de símbolos pro_one (e todas as suas tabelas filho) não estão disponíveis para os símbolos pro_two e suas tabelas filho.

Esta hierarquia da estrutura de dados da tabela de símbolos é armazenada no analisador semântico e sempre que um nome precisa ser pesquisado em uma tabela de símbolos, ele é pesquisado usando o seguinte algoritmo:

primeiro, um símbolo será pesquisado no escopo atual, ou seja, na tabela de símbolos atual.
se um nome for encontrado, a pesquisa é concluída, caso contrário, ele será pesquisado na tabela de símbolos pai até,
o nome foi encontrado ou a tabela de símbolos global foi pesquisada para o nome.

↰ Previous page Next page ↱