Teoria da Computabilidade e Compiladores

Computabilidade é a habilidade de resolver problemas de forma efetiva. É um tópico-chave para o campo da Teoria da Computabilidade dentro da Lógica Matemática e para a Teoria da Computação dentro da Ciência da Computação.

A computabilidade de um problema está intimamente ligada à existência de um algoritmo para resolver o problema. Um dos objetivos da Teoria da Computabilidade é determinar quais problemas, ou classes de problemas, podem ser resolvidos em cada modelo de computação.

O analisador léxico reúne os caracteres do programa-fonte em unidades léxicas que são os identificadores, as palavras especiais, os operadores e os símbolos de pontuação. O analisador léxico ignora os comentários no programa-fonte, porque eles não têm nenhuma utilidade para o compilador.

O analisador sintático pega as unidades do analisador léxico e usa-as para construir estruturas hierárquicas chamadas árvores de análise, as quais representam a estrutura sintática do programa. O analisador semântico faz parte integralmente do gerador de código intermediário e verifica se há erros difíceis, se não impossíveis, de serem detectados durante a análise sintática, como por exemplo, erros de tipo.

A tabela de símbolos serve como um banco de dados para o processo de compilação. Seu principal conteúdo são informações sobre tipos e atributos de cada nome definido pelo usuário no programa.

Híbridos: Eles traduzem programas em linguagem de alto nível para uma linguagem intermediária projetada para permitir fácil interpretação. Esse método é mais rápido do que a interpretação pura porque as instruções da linguagem-fonte são decodificadas somente uma vez.

O analisador léxico separa a sequência de caracteres que representa o programa-fonte em entidades ou tokens, símbolos básicos da linguagem. O analisador sintático agrupa os tokens fornecidos pelo analisador léxico em estruturas sintáticas, construindo a árvore sintática correspondente. Para isso, utiliza uma série de regras de sintaxe, que constituem a gramática da linguagem-fonte.

O compilador executa ainda a análise semântica. O analisador semântico utiliza a árvore sintática determinada pelo analisador sintático para:

A derivação 1 é uma derivação à esquerda e a Derivação 2 é uma derivação à direita. Percebe-se que as duas derivações são diferentes e resultam na mesma cadeia. Isso quer dizer que a gramática construída é ambígua.

O analisador léxico é a primeira fase de um compilador. Sua tarefa principal é a de ler os caracteres de entrada e produzir uma sequência de tokens que o analisador sintático utiliza.

Uma função essencial do compilador é registrar os identificadores usados no programa-fonte e coletar as informações sobre os seus diversos atributos. Uma tabela de símbolos é uma estrutura de dados contendo um registro para cada identificador, com os campos contendo os atributos do identificador.

As informações sobre o identificador são coletadas pelas fases de análise de um compilador e usadas pelas fases de síntese de forma a gerar o código-alvo. Durante a análise léxica, a cadeia de caracteres que forma um identificador é armazenada em uma entrada da tabela de símbolos. As fases seguintes do compilador acrescentam informações a esta entrada. A fase de geração utiliza as informações armazenadas para gerar o código adequado.

Um mecanismo de tabela de símbolos precisa permitir que adicionemos novas entradas e encontremos eficientemente as já existentes.