Compiladores e Interpretadores: fases de compilação, tabela de símbolos e gramática formal

Compilador

É um programa de computador que, a partir de um código fonte escrito em uma linguagem compilada, cria um programa semanticamente equivalente, porém escrito em outra linguagem (código objeto). Classicamente, um compilador traduz um programa de uma linguagem textual facilmente entendida por um ser humano para uma linguagem de máquina.

Interpretador

Percorre, linha a linha, as instruções do programa e as interpreta conforme as lê, enviando para o processador, que então executa cada ação correspondente.

Vantagens e Desvantagens

• Desvantagem: A cada execução, o programa precisa ser traduzido e interpretado novamente. A execução é mais lenta e o código-fonte sempre precisa ser lido.
• Vantagem: Consome menos memória, não precisa ser compilado para executar e as correções/alterações são mais rápidas de serem realizadas.

Estrutura de um Compilador

Análise Léxica

É a primeira fase do processo de compilação. O objetivo nesta fase é identificar unidades léxicas ou lexemas que compõem o programa. O analisador léxico lê todos os caracteres do programa fonte e verifica se eles pertencem ao alfabeto da linguagem. Caso um caractere não pertença ao alfabeto da linguagem, deve ser gerado um erro léxico.

Análise Sintática

Tem como objetivo validar a gramática do programa. Nesta etapa, o objetivo é reconhecer se a estrutura gramatical do código fonte está de acordo com as regras sintáticas da linguagem.

Nesta etapa é feita uma varredura na sequência de tokens recebida do analisador léxico e produzida uma estrutura de dados em formato de árvore, conhecida como árvore sintática.

Análise Semântica

Verifica se a semântica do programa fonte tem consistência. Para isso, utiliza a árvore sintática e as informações contidas na tabela de símbolos.

Geração de Código Intermediário

Gera uma sequência de código denominada código intermediário, que posteriormente, em outras fases, irá gerar o código objeto. Eventualmente, essa fase pode não existir, e a compilação pode ser feita diretamente para o código objeto, o que é comum em compiladores auto residentes.

Otimização de Código

Visa otimizar o código em termos de velocidade de execução e consumo de memória. Essa etapa não depende da arquitetura de máquina e tem como objetivo fazer transformações no código intermediário a fim de obter um código objeto mais otimizado.

Geração de Código Objeto

É a última etapa do processo de compilação e recebe como entrada uma representação intermediária que mapeia a linguagem objeto.

Conceitos Relacionados

Tabela de Símbolos

Durante toda a fase de compilação, algumas informações são armazenadas em uma tabela chamada de tabela de símbolos, que nada mais é do que uma estrutura de dados em forma de lista ou dicionário. As informações coletadas nessa tabela dependem do tipo de tradutor desenvolvido e do programa objeto a ser gerado.

Árvore Sintática

É uma estrutura de dados em forma de árvore ou grafo que representa a sequência hierárquica da linguagem de programação. Essa estrutura permite representar cada elemento do programa. Os demais passos do compilador consistem em visitar os nós dessa estrutura em uma determinada ordem.

Significado de 'Passo'

Refere-se ao número de vezes que o compilador varre o código.

Gramática Formal (G = (Vn, Vt, P, S))

Onde:

• Vn: Representa o vocabulário não-terminal da gramática. Este vocabulário corresponde ao conjunto de todos os símbolos dos quais a gramática se vale para definir as leis de formação das sentenças da linguagem.
• Vt: É o vocabulário terminal, contendo os símbolos que constituem as sentenças da linguagem. Dá-se o nome de terminais aos elementos de Vt.
• P: Representa o conjunto de todas as leis de formação utilizadas pela gramática para definir a linguagem. Para tanto, cada construção parcial, representada por um não-terminal, é definida como um conjunto de regras de formação relativas à definição do não-terminal a ela referente. A cada uma destas regras de formação que compõem o conjunto P dá-se o nome de produção da gramática.
• S ∈ Vn: Denota a principal categoria gramatical de G; é dito o símbolo inicial ou o axioma da gramática. Indica onde se inicia o processo de geração de sentenças.

Token

É um par consistindo de um nome de token e um valor de atributo opcional. O nome do token é um símbolo abstrato representando um tipo de unidade léxica (ex: palavra-chave, identificador, número, etc.).

Padrão

É uma descrição da forma que os lexemas de um token podem tomar. No caso de uma palavra-chave como um token, o padrão é a sequência de caracteres que formam a palavra-chave.

Lexema

É uma sequência de caracteres no programa fonte que corresponde a um padrão para um token e é uma instância desse token.