Análise Sem

Compiladores: Análise Semântica
Aprenda os fundamentos da análise semântica, verificação de tipos e tabelas de símbolos - elementos essenciais para a construção de compiladores eficientes e robustos.
O Papel da Análise Semântica no Compilador
A análise semântica é a terceira fase do processo de compilação, ocorrendo após a análise léxica e sintática. Seu objetivo principal é verificar se o programa está semanticamente correto, mesmo quando sua sintaxe está perfeita.
Enquanto a análise sintática verifica se a estrutura do código segue as regras gramaticais da linguagem, a análise semântica verifica o significado do código, respondendo perguntas como:
As variáveis estão sendo usadas corretamente?
Os tipos são compatíveis nas operações?
As funções são chamadas com os parâmetros corretos?
A análise semântica é crucial para detectar erros que não podem ser identificados apenas pela análise sintática, garantindo que o programa tenha um significado coerente antes de gerar código.
Erros Sintáticos vs. Erros Semânticos
1
Erros Sintáticos
Violam as regras gramaticais da linguagem e são detectados durante a análise sintática.
if (x > 5 {     // Erro: Falta fechar parênteses
    print("Maior que 5");
}
Este erro é detectado pelo analisador sintático pois viola a estrutura da linguagem.
2
Erros Semânticos
Respeitam a sintaxe, mas violam regras de significado da linguagem.
int x = "texto";     // Erro: Tipo incompatível
y = 10;              // Erro: Variável não declarada
Estes erros exigem análise semântica para serem detectados, pois a sintaxe está correta.
Identificar a diferença entre estes tipos de erros é fundamental para compreender o papel do analisador semântico no processo de compilação.
Cadeia de Fases do Compilador
Análise Léxica
Transforma o código-fonte em tokens (unidades léxicas)
Análise Sintática
Verifica a estrutura gramatical e cria a árvore sintática
Análise Semântica
Verifica o significado e os tipos
Geração de Código
Produz código intermediário ou de máquina
A análise semântica recebe a árvore sintática produzida na fase anterior e a enriquece com informações de tipos e símbolos, detectando erros que passariam despercebidos nas fases anteriores.
O que é Semântica em Linguagens de Programação?
Semântica refere-se ao significado das construções em uma linguagem de programação. Enquanto a sintaxe define a forma e a estrutura, a semântica define o comportamento e o significado.
Na compilação, a análise semântica verifica se o programa faz sentido de acordo com as regras da linguagem, mesmo quando sua sintaxe está correta.
A semântica pode ser dividida em:
Semântica estática: verificada em tempo de compilação (tipos, escopo, etc.)
Semântica dinâmica: determinada durante a execução do programa
O analisador semântico lida principalmente com a semântica estática, verificando aspectos que podem ser determinados antes da execução do programa.
Verificação de Tipos: Tipagem Estática e Dinâmica
Tipagem Estática
A verificação de tipos ocorre durante a compilação, antes da execução do programa.
Java, C++, C#, Kotlin, TypeScript
Erros de tipo são detectados antes da execução
Exige declarações explícitas ou inferência de tipos
int x = 10;
x = "texto"; // Erro detectado na compilação
Tipagem Dinâmica
A verificação de tipos ocorre durante a execução do programa.
Python, JavaScript, Ruby, PHP
Erros de tipo aparecem apenas na execução
Variáveis podem mudar de tipo durante execução
x = 10
x = "texto"  # Permitido, tipo mudou dinamicamente
Na análise semântica para compiladores, o foco está na verificação estática de tipos, mesmo para linguagens com tipagem dinâmica.
Categorias de Erros Semânticos
Incompatibilidade de Tipos
Tentativas de usar operações entre tipos incompatíveis
Variáveis Não Declaradas
Uso de identificadores que não foram declarados no escopo atual
Redeclaração de Variáveis
Declarar a mesma variável múltiplas vezes no mesmo escopo
Erros de Escopo
Acesso a variáveis fora do seu escopo válido
Erros de Função
Número incorreto ou tipos errados de parâmetros
O analisador semântico é responsável por detectar todos estes tipos de erros, garantindo que o programa seja consistente antes da geração de código.
Exemplos de Erros Semânticos em Código
Incompatibilidade de tipos
int a = 5;
boolean b = true;
int c = a + b;  // Erro: Não pode somar int e boolean
Variável não declarada
int x = 10;
y = x + 5;  // Erro: 'y' não foi declarada
Parâmetros incorretos
void func(int x, String y) { ... }
func("texto", 10);  // Erro: ordem de tipos invertida
Redeclaração de variável
int contador = 0;
String contador = "abc";  // Erro: redeclaração
Todos estes erros respeitam a sintaxe da linguagem, mas violam regras semânticas e seriam detectados durante a fase de análise semântica do compilador.
Tipos Primitivos, Compostos e Derivados
1
2
3
1
Tipos Primitivos
Blocos básicos de construção
2
Tipos Compostos
Combinam tipos primitivos
3
Tipos Derivados
Baseados em outros tipos
Tipos Primitivos
Inteiros: int, byte, short, long
Ponto flutuante: float, double
Caracteres: char
Booleanos: boolean
Tipos Compostos
Arrays: int[], String[]
Registros/Structs/Classes
Conjuntos e Mapas
Tipos Derivados
Ponteiros e Referências
Enumerações
Union Types
Funções/Métodos
O sistema de tipos é fundamental para a análise semântica, permitindo verificar compatibilidade entre operações e detectar erros em tempo de compilação.
O que é uma Tabela de Símbolos?
A tabela de símbolos é uma estrutura de dados fundamental no processo de compilação que armazena informações sobre identificadores (variáveis, funções, classes) encontrados no programa fonte.
Funciona como um dicionário que mapeia nomes de identificadores para suas propriedades, como tipo, escopo, valor (quando constante), localização na memória, entre outros atributos.
É uma ferramenta essencial para o analisador semântico, permitindo verificar se as variáveis foram declaradas antes de serem usadas, se os tipos são compatíveis e se os escopos estão sendo respeitados.
A tabela de símbolos é consultada e atualizada durante a análise semântica, fornecendo informações necessárias para verificação de tipos e geração de código.
Funções da Tabela de Símbolos
Consulta de Identificadores
Verifica se uma variável ou função foi declarada e obtém suas informações
Inserção de Símbolos
Adiciona novos identificadores durante a análise de declarações
Gerenciamento de Escopo
Controla a visibilidade de identificadores em diferentes níveis do programa
Verificação de Tipos
Fornece informações de tipo para validar operações e expressões
Resolução de Referências
Conecta usos de variáveis com suas declarações originais
Alocação de Memória
Auxilia na atribuição de posições de memória para variáveis
A tabela de símbolos é um componente central do compilador, interagindo com praticamente todas as outras fases da compilação.
Informações Armazenadas na Tabela de Símbolos
Estas informações permitem ao analisador semântico realizar verificações completas sobre o uso de cada identificador no programa.
Estruturas de Dados para Tabelas de Símbolos
Implementações Comuns
Tabela Hash: Acesso rápido O(1) aos símbolos por nome
Árvore Binária: Organiza símbolos alfabeticamente
Lista Encadeada: Simples para implementações básicas
Tabelas Aninhadas: Para lidar com múltiplos escopos
Em Python, a tabela de símbolos é frequentemente implementada usando dicionários (dict), que são eficientes para busca, inserção e remoção de elementos.
As tabelas de símbolos aninhadas permitem representar diferentes escopos no programa, com cada escopo tendo acesso ao seu próprio escopo e aos escopos externos.
Exemplo Prático: Tabela de Símbolos com Python
class TabelaSimbolos:
    def __init__(self, pai=None):
        self.tabela = {}
        self.pai = pai  # Tabela do escopo pai (externo)
    
    def inserir(self, nome, tipo, categoria="variavel"):
        self.tabela[nome] = {
            'tipo': tipo,
            'categoria': categoria,
        }
    
    def buscar(self, nome):
        # Busca primeiro na tabela atual
        if nome in self.tabela:
            return self.tabela[nome]
        # Se não encontrar e tiver tabela pai, busca lá
        elif self.pai:
            return self.pai.buscar(nome)
        # Não encontrou em nenhum lugar
        return None
    
    def novo_escopo(self):
        # Cria nova tabela com esta como pai
        return TabelaSimbolos(self)
Esta implementação simples permite criar uma hierarquia de tabelas de símbolos para representar os diferentes escopos de um programa.
Checagem de Tipos: Como e Quando Ocorre
Construção da Árvore Sintática
A análise sintática cria a estrutura do programa
Coleta de Declarações
Símbolos são inseridos na tabela durante o primeiro percurso
Verificação de Usos
Cada uso de variável é verificado contra sua declaração
Análise de Expressões
Tipos são verificados para garantir compatibilidade
A verificação de tipos ocorre em duas fases principais: primeiro, todas as declarações são processadas e inseridas na tabela de símbolos; depois, os usos de variáveis e expressões são verificados para garantir consistência semântica.
Para expressões complexas, a análise é feita de forma recursiva, subindo pela árvore sintática e combinando os tipos de acordo com as regras da linguagem.
Coerção e Compatibilidade de Tipos
Compatibilidade de Tipos
Refere-se às regras que determinam quando um tipo pode ser usado em contextos que esperam outro tipo. Pode ser:
Compatibilidade estrita: Tipos devem ser idênticos
Compatibilidade de subtipos: Um tipo derivado pode ser usado onde se espera seu tipo base
Compatibilidade por conversão: Um tipo pode ser convertido para outro
Coerção de Tipos
É a conversão automática de um tipo para outro, como em:
int i = 5;
double d = i;  // Coerção int → double
As regras de coerção variam entre linguagens:
C/C++ permitem muitas coerções implícitas
Java é mais restritiva, permitindo apenas coerções seguras
Python faz coerções durante a execução
O analisador semântico precisa implementar as regras de compatibilidade e coerção da linguagem para verificar corretamente expressões e atribuições.
Inferência de Tipos
A inferência de tipos é um mecanismo que permite ao compilador deduzir automaticamente o tipo de uma expressão ou variável sem declaração explícita. Isto permite código mais conciso mantendo a segurança da tipagem estática.
Linguagens modernas como Kotlin, TypeScript, Scala e Swift fazem uso extensivo de inferência de tipos:
// Com tipo explícito
int x = 10;

// Com inferência de tipo
var x = 10;  // O compilador infere que x é int
Algoritmo básico de inferência:
Analisar o valor ou expressão do lado direito
Determinar seu tipo com base nas regras da linguagem
Associar esse tipo à variável do lado esquerdo
Propagar esse tipo para todos os usos da variável
Expressões Aritméticas e Verificação de Tipo
A verificação de tipos em expressões aritméticas segue regras específicas para cada operador. O tipo resultante de uma expressão depende dos tipos dos operandos e do operador utilizado.
A análise é feita recursivamente na árvore sintática, determinando o tipo de cada subexpressão até chegar ao tipo final da expressão completa.
Exemplos com Código Válido e Inválido
Código Semanticamente Válido
int a = 5;
double b = 3.14;
double c = a + b;  // OK: int + double → double

String s1 = "Olá";
String s2 = "Mundo";
String s3 = s1 + s2;  // OK: concatenação

if (a > 3) {  // OK: comparação int com int
    a = a * 2;
}
Código Semanticamente Inválido
int x = 10;
boolean y = true;
int z = x + y;  // ERRO: int + boolean

String s = "texto";
if (s) {  // ERRO: string em contexto booleano
    // ...
}

int valor = calcular();  // ERRO: função não declarada
Um bom analisador semântico deve detectar todos os erros no segundo exemplo, mesmo que a sintaxe esteja correta, e permitir todas as operações no primeiro exemplo.
Arquitetura Simples do Analisador Semântico
Entrada: Árvore Sintática
Recebe a AST do analisador sintático
Construção da Tabela de Símbolos
Processa declarações e preenche a tabela
3
3
Verificação Semântica
Analisa usos, tipos e escopos
Geração de Erros
Relata problemas semânticos encontrados
Saída: AST Anotada
Árvore com informações de tipo para geração de código
O analisador semântico percorre a árvore sintática, consulta e atualiza a tabela de símbolos, e realiza verificações semânticas em cada nó, produzindo uma árvore anotada com informações de tipo.
Representação da Tabela de Símbolos em Python
class Simbolo:
    def __init__(self, nome, tipo, categoria, escopo):
        self.nome = nome
        self.tipo = tipo
        self.categoria = categoria  # 'variavel', 'funcao', etc.
        self.escopo = escopo
        self.parametros = []  # para funções
        
class TabelaSimbolos:
    def __init__(self):
        self.escopos = [{}]  # Pilha de escopos, começa com escopo global
        
    def entrar_escopo(self):
        self.escopos.append({})  # Adiciona novo escopo
        
    def sair_escopo(self):
        if len(self.escopos) > 1:
            self.escopos.pop()  # Remove escopo atual
            
    def inserir(self, simbolo):
        self.escopos[-1][simbolo.nome] = simbolo
        
    def buscar(self, nome):
        # Busca do escopo mais interno para o mais externo
        for escopo in reversed(self.escopos):
            if nome in escopo:
                return escopo[nome]
        return None  # Símbolo não encontrado
Esta implementação usa uma pilha de dicionários para representar escopos aninhados, permitindo buscar variáveis do escopo atual até o escopo global.
Função de Verificação de Tipos: Análise por Nós
def verificar_expressao(no, tabela_simbolos):
    """Verifica tipos em uma expressão e retorna seu tipo."""
    
    if no.tipo_no == "LITERAL":
        # Retorna o tipo do literal (int, float, string, etc.)
        return inferir_tipo_literal(no.valor)
        
    elif no.tipo_no == "ID":
        # Busca o símbolo na tabela
        simbolo = tabela_simbolos.buscar(no.nome)
        if simbolo is None:
            erro(f"Variável {no.nome} não declarada")
            return "erro"
        return simbolo.tipo
        
    elif no.tipo_no == "OPERACAO_BINARIA":
        # Verifica o tipo de cada operando
        tipo_esq = verificar_expressao(no.esquerda, tabela_simbolos)
        tipo_dir = verificar_expressao(no.direita, tabela_simbolos)
        
        # Verifica compatibilidade dos tipos com o operador
        return verificar_compatibilidade(
            tipo_esq, tipo_dir, no.operador)
def verificar_compatibilidade(tipo1, tipo2, operador):
 """Verifica se os tipos são compatíveis com o operador."""
 
 if "erro" in (tipo1, tipo2):
 return "erro" # Propaga erros anteriores
 
 if operador in ("+", "-", "*", "/"):
 if tipo1 == "int" and tipo2 == "int":
 return "int"
 elif tipo1 in ("int", "float") and tipo2 in ("int", "float"):
 return "float"
 else:
 erro(f"Operador {operador} incompatível com {tipo1} e {tipo2}")
 return "erro"
 
 elif operador in (">", "<", ">=", "<=", "==", "!="):
 if tipo1 == tipo2:
 return "boolean"
 elif tipo1 in ("int", "float") and tipo2 in ("int", "float"):
 return "boolean"
 else:
 erro(f"Comparação incompatível entre {tipo1} e {tipo2}")
 return "erro"
Uso da Árvore Sintática para Análise Semântica
A análise semântica utiliza a árvore sintática (AST) produzida pelo analisador sintático como base para suas verificações. O processo envolve percorrer a árvore e realizar verificações em cada nó de acordo com seu tipo.
Nós de Declaração
Quando um nó representa uma declaração (variável, função, etc.), o analisador semântico:
Verifica se já existe um símbolo com mesmo nome no escopo atual
Cria um novo símbolo com as informações do nó
Insere o símbolo na tabela de símbolos
Nós de Expressão
Para nós que representam expressões, o analisador:
Verifica recursivamente o tipo de cada subexpressão
Aplica regras de compatibilidade de tipos
Anota o nó com seu tipo resultante
Nós de Comando
Para nós que representam comandos (if, while, etc.), o analisador:
Verifica se as condições têm tipo booleano
Verifica a compatibilidade dos tipos em atribuições
Processa blocos aninhados com seus próprios escopos
Exemplo: Verificação de Tipos em uma Expressão
Considerando a expressão: a + b * (c - 5)
# AST para a expressão
{
  "tipo_no": "OPERACAO_BINARIA",
  "operador": "+",
  "esquerda": {
    "tipo_no": "ID",
    "nome": "a"
  },
  "direita": {
    "tipo_no": "OPERACAO_BINARIA",
    "operador": "*",
    "esquerda": {
      "tipo_no": "ID",
      "nome": "b"
    },
    "direita": {
      "tipo_no": "OPERACAO_BINARIA",
      "operador": "-",
      "esquerda": {
        "tipo_no": "ID",
        "nome": "c"
      },
      "direita": {
        "tipo_no": "LITERAL",
        "valor": 5
      }
    }
  }
}
O algoritmo de verificação de tipos percorreria esta árvore da seguinte forma:
Verificar o tipo de a na tabela de símbolos (ex: int)
Para a subárvore direita do operador +, verificar:
Tipo de b na tabela de símbolos (ex: int)
Para a subárvore direita do operador *, verificar:
Tipo de c na tabela (ex: int)
Tipo do literal 5 (int)
Verificar compatibilidade: int - int → int
Verificar compatibilidade: int * int → int
Verificar compatibilidade final: int + int → int
O tipo resultante da expressão inteira seria int, e seria anotado no nó raiz da árvore.
Passo a Passo: Construindo um Analisador Semântico Simples
1
1. Definir Classes Básicas
Criar classes para representar a tabela de símbolos, símbolos e nós da AST.
2
2. Implementar Gestão de Escopos
Adicionar métodos para criar, entrar e sair de escopos aninhados.
3
3. Processar Declarações
Implementar a lógica para processar nós de declaração e popular a tabela.
4
4. Verificar Expressões
Desenvolver funções recursivas para verificar tipos em expressões.
5
5. Implementar Regras de Tipo
Codificar as regras de compatibilidade e coerção de tipos da linguagem.
6
6. Verificar Comandos
Adicionar a lógica para verificar comandos (if, while, atribuições).
7
7. Adicionar Tratamento de Erros
Implementar mecanismos para relatar erros semânticos de forma clara.
Este fluxo permite construir incrementalmente um analisador semântico, testando cada componente à medida que é implementado.
Inserindo Símbolos e Tipos
def processar_declaracao(no, tabela):
    """Processa uma declaração e insere o símbolo na tabela."""
    if no.tipo_no == "DECLARACAO_VARIAVEL":
        nome = no.nome
        tipo = no.tipo
        
        # Verificar se já existe no escopo atual
        if tabela.buscar_escopo_atual(nome):
            erro(f"Variável '{nome}' já declarada neste escopo")
            return False
            
        # Criar e inserir o símbolo
        simbolo = Simbolo(nome, tipo, "variavel", len(tabela.escopos) - 1)
        tabela.inserir(simbolo)
        
        # Se tiver inicialização, verificar compatibilidade
        if no.inicializacao:
            tipo_expr = verificar_expressao(no.inicializacao, tabela)
            if not tipos_compativeis(tipo, tipo_expr):
                erro(f"Tipo incompatível na inicialização de '{nome}'")
                return False
                
        return True
Esta função processa nós de declaração de variáveis, verifica redeclarações no mesmo escopo e insere o símbolo na tabela. Também verifica a compatibilidade de tipos se houver inicialização.
Detectando Tipos Incompatíveis em Tempo de Compilação
Exemplo de código com erro semântico
int main() {
    int x = 10;
    boolean flag = true;
    
    // Erro semântico: tipos incompatíveis
    int resultado = x + flag;
    
    return 0;
}
Saída do analisador semântico
Erro semântico na linha 5: 
Operador '+' incompatível entre tipos 'int' e 'boolean'
O analisador semântico verifica a expressão x + flag da seguinte forma:
Busca o tipo de x na tabela de símbolos → int
Busca o tipo de flag na tabela de símbolos → boolean
Verifica se o operador + é compatível com int e boolean
Como não é compatível, gera um erro semântico
O erro é detectado em tempo de compilação, antes da execução
Exercício Prático: Verificação Semântica de Código Exemplo
Código para análise
void exemplo() {
    int a = 5;
    int b = 10;
    float c = a / b;
    
    if (a > b) {
        string mensagem = "a é maior";
        print(mensagem);
    } else {
        int a = 20;  // Redeclaração de 'a'
        print(a + b);
    }
    
    print(mensagem);  // Erro: fora de escopo
}
Exercício: Encontre os erros semânticos
Analise o código acima e identifique todos os erros semânticos presentes. Para cada erro, especifique:
A linha onde ocorre o erro
O tipo de erro semântico
Uma explicação do porquê é um erro
Um analisador semântico bem implementado deve ser capaz de detectar todos estes erros automaticamente durante a compilação.
Existem pelo menos 3 erros semânticos no código. Tente identificá-los todos!
Atividade de Fixação com Mini Linguagem
Mini linguagem "SimpleLang"
Considere uma linguagem simples com a seguinte sintaxe:
Tipos: int, float, boolean, string
Operadores: +, -, *, /, >, <, ==, !=, and, or
Comandos: if, while, print, atribuição
Regras de tipo:
Operadores aritméticos (+, -, *, /) só funcionam entre int ou float
int + float resulta em float
Operadores relacionais (>, <, ==, !=) resultam em boolean
Operadores lógicos (and, or) só funcionam entre boolean
Strings só podem ser concatenadas com + e comparadas com == ou !=
Exercício: Implementar função de verificação
Implemente a função verificar_atribuicao que recebe um nó de atribuição, a tabela de símbolos, e verifica se os tipos são compatíveis:
def verificar_atribuicao(no, tabela):
 """
 Verifica se uma atribuição é válida semanticamente.
 no: Nó da árvore que representa a atribuição
 (contém campos 'variavel' e 'expressao')
 tabela: Tabela de símbolos atual
 
 Retorna True se válido, False caso contrário
 """
 # Seu código aqui
 # 1. Verificar se a variável existe
 # 2. Obter seu tipo
 # 3. Verificar o tipo da expressão à direita
 # 4. Verificar compatibilidade
 # 5. Retornar resultado
Resumo da Aula
O que Aprendemos
Conceitos fundamentais de análise semântica
Importância e funcionamento da tabela de símbolos
Verificação de tipos em expressões e comandos
Detecção de erros semânticos comuns
Implementação básica em Python
A análise semântica é uma fase crucial do compilador que garante a correção semântica do programa antes da geração de código. Com as técnicas aprendidas, é possível implementar verificações robustas que capturam erros sutis que passariam despercebidos na análise sintática.