INÍCIO
Livros do Prof.
Construção de Compiladores: Guia Prático Passo a Passo
Domine as técnicas de construção de compiladores com este guia completo para estudantes de ciência da computação. Aprenda desde os conceitos básicos até a implementação prática em Python.
O que é um Projeto Guiado de Compilador?
Um projeto guiado de compilador é uma abordagem estruturada para aprender a construir compiladores através da prática direta, com orientação passo a passo. Diferente de abordagens puramente teóricas, você desenvolverá um compilador funcional para uma linguagem simples.
Este formato permite que você aplique conceitos teóricos em um projeto real, superando a curva de aprendizado inicial que muitos estudantes enfrentam ao estudar compiladores. O aprendizado acontece de forma incremental, começando com os módulos básicos até a construção completa.
O trabalho em grupo permite dividir tarefas complexas e simular um ambiente profissional de desenvolvimento.
Etapas do Compilador
Análise Léxica
Identifica tokens no código fonte, como palavras-chave, identificadores e operadores. É a primeira fase do processo de compilação.
Análise Sintática
Verifica se a sequência de tokens segue as regras gramaticais da linguagem, gerando uma árvore sintática.
Análise Semântica
Verifica o significado do programa, como tipos de dados e escopo de variáveis.
Geração de Código
Traduz a representação intermediária em código executável ou interpretável.
Neste projeto guiado, você implementará todas estas etapas para uma linguagem simples, focando inicialmente nas fases de análise léxica e sintática.
Objetivo Final do Projeto

O objetivo principal é construir um compilador funcional para uma mini linguagem de programação, trabalhando em equipe e aplicando conceitos teóricos em um projeto prático.
Ao final do projeto, seu compilador deverá ser capaz de:
  • Reconhecer tokens da linguagem definida
  • Analisar a estrutura sintática do código
  • Verificar regras semânticas básicas
  • Gerar código intermediário ou executável
  • Reportar erros de forma clara e útil
Este projeto servirá como uma base sólida para entender como linguagens de programação são processadas e implementadas na prática.
Formação dos Grupos e Divisão de Papéis
Líder do Projeto
Responsável pela coordenação geral e integração dos módulos. Mantém o cronograma e garante a comunicação entre membros.
Especialista em Análise Léxica
Foca na implementação do analisador léxico e na definição dos tokens da linguagem.
Especialista em Análise Sintática
Desenvolve o parser e implementa as regras gramaticais definidas para a linguagem.
Especialista em Análise Semântica
Trabalha na verificação de tipos e regras semânticas da linguagem.
Grupos ideais têm entre 3 e 5 membros. Cada integrante deve ter responsabilidades claras, mas todos devem entender o funcionamento completo do compilador para garantir integração eficiente dos módulos.
Escolha da Linguagem-Alvo
A escolha da linguagem-alvo é crucial para o sucesso do projeto. Recomenda-se começar com uma mini linguagem que possua funcionalidades básicas, mas significativas:
  • Declaração e atribuição de variáveis
  • Operações aritméticas simples
  • Estruturas condicionais (if-else)
  • Comandos de saída (print)
  • Opcional: estruturas de repetição simples
Uma linguagem simples permite focar nos aspectos fundamentais da construção de compiladores sem se perder em complexidades desnecessárias nesta fase de aprendizado.
Delimitação do Escopo do Compilador
Definir claramente o escopo do compilador é essencial para evitar projetos ambiciosos demais que não sejam concluídos no prazo. Considere:
  • Quais tipos de dados serão suportados (inteiros, strings)?
  • Quais estruturas de controle serão implementadas?
  • O compilador gerará código intermediário ou executável?
  • Como serão tratados os erros em cada fase?

Um erro comum é tentar implementar muitas funcionalidades. Comece com um subconjunto mínimo e amplie apenas quando o básico estiver funcionando perfeitamente.
Documente as limitações conhecidas e decisões de design para manter o foco durante o desenvolvimento e facilitar futuras extensões.
Exemplo de Mini Linguagem
# Exemplo de código na mini linguagem
var x = 10;
var y = 5;
var resultado = x + y;

if (resultado > 12) {
    print("Resultado maior que 12");
} else {
    print("Resultado menor ou igual a 12");
}
Esta mini linguagem inclui declaração de variáveis, operações aritméticas, estruturas condicionais e comandos de saída. É simples, mas suficiente para demonstrar os conceitos fundamentais de compiladores. A sintaxe é inspirada em C/JavaScript para facilitar a compreensão pelos estudantes.
Checklist de Funcionalidades Mínimas
1
Análise Léxica
Reconhecimento de identificadores, números, strings, operadores e palavras-chave. Implementação de um scanner que converte texto em tokens.
2
Análise Sintática
Parser capaz de validar se a sequência de tokens segue a gramática definida. Detecção e relatório de erros sintáticos.
3
Tabela de Símbolos
Estrutura para armazenar informações sobre identificadores (variáveis, funções) e seus atributos.
4
Tratamento de Erros
Mecanismos para detectar, reportar e possivelmente recuperar-se de erros nas diferentes fases da compilação.
Esta checklist serve como guia para garantir que todos os componentes essenciais sejam implementados durante o desenvolvimento do compilador.
O que é uma Gramática Formal?
Uma gramática formal é um conjunto de regras que define como formar sentenças válidas em uma linguagem. No contexto de compiladores, ela especifica a sintaxe da linguagem de programação.
Uma gramática formal é composta por:
  • Símbolos terminais: tokens da linguagem (palavras-chave, operadores)
  • Símbolos não-terminais: categorias sintáticas (expressão, comando)
  • Regras de produção: definem como combinar símbolos
  • Símbolo inicial: ponto de partida para derivar sentenças
A gramática serve como blueprint para o analisador sintático e documenta formalmente a estrutura da linguagem.
Definindo a Gramática da Mini Linguagem
Para definir a gramática da sua mini linguagem, comece identificando os componentes básicos:
  1. Liste todas as construções sintáticas (declarações, expressões, comandos)
  1. Defina regras para cada construção, do mais simples ao mais complexo
  1. Verifique ambiguidades e resolva conflitos
  1. Teste a gramática com exemplos reais
# Exemplo parcial de gramática BNF
programa    → declaração*
declaração  → varDecl | ifStmt | printStmt
varDecl     → "var" IDENT "=" expressão ";"
ifStmt      → "if" "(" expressão ")" bloco
             ("else" bloco)?
bloco       → "{" declaração* "}"
expressão   → termo (("+" | "-") termo)*
A gramática deve ser precisa o suficiente para descrever todas as construções válidas da linguagem, mas também deve ser clara e concisa para facilitar a implementação.
Exemplo de Gramática para Expressões
# Gramática BNF para expressões aritméticas
expr       → term (("+" | "-") term)*
term       → factor (("*" | "/") factor)*
factor     → INTEGER | "(" expr ")" | IDENTIFIER
Esta gramática define expressões aritméticas com precedência de operadores. Multiplicação e divisão têm precedência maior que adição e subtração. Parênteses podem ser usados para alterar a ordem de avaliação.
A notação utilizada é BNF (Backus-Naur Form), onde o símbolo "→" indica uma regra de produção, "|" representa alternativas, e "*" indica zero ou mais repetições do elemento anterior.
Construindo Regras EBNF ou BNF
EBNF (Extended Backus-Naur Form) estende a notação BNF com operadores adicionais para maior expressividade:
  • [ ] - Conteúdo opcional (zero ou uma ocorrência)
  • { } - Repetição (zero ou mais ocorrências)
  • ( ) - Agrupamento de elementos
  • "string" - Símbolo terminal literal
Ao construir suas regras, comece com estruturas simples e componha gradualmente estruturas mais complexas. Mantenha a recursividade controlada e evite ambiguidades sempre que possível.
Visualização da Gramática com Diagramas
Diagramas de sintaxe (também conhecidos como diagramas de ferrovia ou railroad diagrams) são representações visuais das regras gramaticais que facilitam a compreensão da estrutura da linguagem.
Benefícios dos diagramas de sintaxe:
  • Tornam a gramática mais acessível visualmente
  • Facilitam a identificação de caminhos alternativos
  • Ajudam a detectar problemas na gramática
  • Servem como documentação visual da linguagem
Ferramentas como Railroad Diagram Generator podem converter suas regras EBNF em diagramas automaticamente.
Identificação dos Tokens da Linguagem
Palavras-chave
Termos reservados com significado especial: var, if, else, print
Identificadores
Nomes de variáveis definidos pelo usuário, seguindo regras específicas (ex: começando com letra)
Operadores
Símbolos que representam operações: +, -, *, /, =, >, <, ==
Literais
Valores constantes: números inteiros, strings entre aspas
Delimitadores
Símbolos que agrupam ou separam elementos: ;, {, }, (, )
Cada token terá um padrão de reconhecimento específico implementado no analisador léxico.
Expressões Regulares para Tokens
Expressões regulares definem padrões para reconhecer tokens no código fonte. Elas são fundamentais para implementar o analisador léxico de forma eficiente, permitindo que o compilador identifique corretamente cada elemento da linguagem.
Usando PLY para o Analisador Léxico
PLY (Python Lex-Yacc) é uma implementação das ferramentas Lex e Yacc para Python, ideal para criar analisadores léxicos e sintáticos. Para o analisador léxico:
  1. Defina tokens como variáveis utilizando expressões regulares
  1. Crie funções t_TOKEN para cada padrão a ser reconhecido
  1. Implemente tratamento de erros com t_error
  1. Configure o objeto lexer com lex.lex()
O PLY simplifica significativamente a criação de analisadores léxicos, mantendo a flexibilidade necessária para personalizar o comportamento conforme necessário para sua linguagem.
Exemplo de Código para Análise Léxica
# Exemplo simplificado de analisador léxico com PLY
import ply.lex as lex

# Lista de tokens
tokens = [
 'IDENTIFIER',
 'INTEGER',
 'PLUS',
 'MINUS',
 'EQUALS',
 'SEMICOLON',
]

# Palavras reservadas
reserved = {
 'if' : 'IF',
 'else' : 'ELSE',
 'var' : 'VAR',
 'print' : 'PRINT',
}

tokens = tokens + list(reserved.values())

# Regras para tokens
t_PLUS = r'\+'
t_MINUS = r'-'
t_EQUALS = r'='
t_SEMICOLON = r';'

# Identificadores e palavras reservadas
def t_IDENTIFIER(t):
 r'[a-zA-Z][a-zA-Z_0-9]*'
 t.type = reserved.get(t.value,'IDENTIFIER')
 return t

# Números inteiros
def t_INTEGER(t):
 r'\d+'
 t.value = int(t.value) 
 return t

# Ignorar espaços e tabs
t_ignore = ' \t'

# Tratamento de erros
def t_error(t):
 print(f"Caractere ilegal '{t.value[0]}'")
 t.lexer.skip(1)

lexer = lex.lex()
Exercício Prático: Criando Tokens para sua Linguagem

Exercício: Defina os tokens para a mini linguagem que seu grupo escolheu, considerando todas as construções sintáticas planejadas.
  1. Liste todas as palavras-chave da linguagem
  1. Identifique todos os operadores e delimitadores
  1. Defina padrões para identificadores e literais (números, strings)
  1. Escreva as expressões regulares para cada token
  1. Implemente as regras no formato do PLY
Teste seu analisador léxico com exemplos simples e verifique se todos os tokens são reconhecidos corretamente. Considere casos extremos e como tratar erros léxicos de forma elegante.
Montagem do Parser com Base na Gramática
O parser analisa a sequência de tokens produzida pelo analisador léxico para verificar se segue as regras da gramática. Com PLY:
  1. Defina funções p_regra para cada regra de produção da gramática
  1. Cada função recebe um parâmetro p que representa a produção
  1. Acesse elementos da produção usando p[1], p[2], etc.
  1. Construa valores semânticos com p[0]
# Exemplo de regra para expressão de soma
def p_expression_binop(p):
    '''expression : expression PLUS term
                  | expression MINUS term'''
    if p[2] == '+':
        p[0] = p[1] + p[3]
    elif p[2] == '-':
        p[0] = p[1] - p[3]
O parser utiliza a gramática para construir uma representação estruturada do programa, que será usada nas próximas fases da compilação.
Definição das Regras de Parsing no PLY
No PLY, as regras de parsing são definidas como funções Python seguindo uma convenção específica:
  • O nome da função deve começar com p_
  • A docstring contém a regra de produção em formato BNF
  • O corpo da função implementa a ação semântica associada à regra
  • É crucial manter a precedência e associatividade corretas dos operadores
A ordem das regras não importa para o PLY, mas a precedência dos operadores deve ser definida explicitamente para evitar ambiguidades. Isso é feito com a variável precedence no código do parser.
Árvore Sintática Abstrata (AST)
A Árvore Sintática Abstrata (AST) é uma representação em forma de árvore da estrutura sintática do código fonte, onde:
  • Cada nó representa uma construção na linguagem
  • As folhas são geralmente tokens (literais, identificadores)
  • A estrutura captura relações hierárquicas entre elementos
  • Detalhes sintáticos irrelevantes são omitidos
AST para um comando if com expressão e bloco
Embora opcional para compiladores simples, a AST facilita significativamente a análise semântica e a geração de código, permitindo uma representação mais clara da estrutura do programa.
Exemplo de Parser para Expressões Matemáticas
# Exemplo simplificado de parser para expressões
import ply.yacc as yacc
from lexer import tokens # importa tokens do analisador léxico

# Regras de precedência, do menor para o maior
precedence = (
 ('left', 'PLUS', 'MINUS'),
 ('left', 'TIMES', 'DIVIDE'),
)

# Regra inicial
def p_expression(p):
 'expression : term'
 p[0] = p[1]

# Expressões binárias
def p_expression_binop(p):
 '''expression : expression PLUS term
 | expression MINUS term'''
 if p[2] == '+':
 p[0] = ('add', p[1], p[3])
 elif p[2] == '-':
 p[0] = ('sub', p[1], p[3])

# Termo
def p_term(p):
 'term : factor'
 p[0] = p[1]

# Operações de termo
def p_term_binop(p):
 '''term : term TIMES factor
 | term DIVIDE factor'''
 if p[2] == '*':
 p[0] = ('mul', p[1], p[3])
 elif p[2] == '/':
 p[0] = ('div', p[1], p[3])

# Fator
def p_factor_num(p):
 'factor : INTEGER'
 p[0] = ('num', p[1])

# Identificador
def p_factor_id(p):
 'factor : IDENTIFIER'
 p[0] = ('var', p[1])

# Expressão entre parênteses
def p_factor_expr(p):
 'factor : LPAREN expression RPAREN'
 p[0] = p[2]

# Tratamento de erro
def p_error(p):
 print(f"Erro de sintaxe: '{p.value}'")

parser = yacc.yacc()
Testes Iniciais com Entrada da Linguagem
Testar o compilador desde o início é crucial para identificar problemas cedo. Para os testes iniciais do analisador léxico e sintático:
  1. Crie arquivos de teste com exemplos da linguagem
  1. Execute o analisador léxico isoladamente para verificar tokens
  1. Teste o parser com expressões simples, aumentando gradualmente a complexidade
  1. Verifique se a estrutura produzida (árvore sintática) está correta
  1. Teste casos de erro para garantir que sejam detectados e reportados adequadamente
Mantenha um conjunto de testes que possa ser executado automaticamente após cada modificação para evitar regressões.
Criação do Esboço do Compilador
1
Estrutura de Arquivos
Organize seu projeto com arquivos separados:
  • lexer.py: definição dos tokens e analisador léxico
  • parser.py: regras de parsing e construção da AST
  • main.py: ponto de entrada do compilador
  • ast.py: classes para representação da AST (opcional)
2
Fluxo de Processamento
Implemente o fluxo básico do compilador:
  1. Leitura do arquivo de entrada
  1. Análise léxica para obter tokens
  1. Análise sintática para verificar estrutura
  1. Saída de resultado ou erros
Este esboço inicial permite testar as primeiras etapas do compilador e serve como base para adicionar as próximas fases (análise semântica e geração de código).
Testes Básicos com Código de Entrada
# Arquivo de teste: exemplo.mini
var x = 10;
var y = 5;
var resultado = x + y;

if (resultado > 12) {
    print("Maior que 12");
} else {
    print("Menor ou igual a 12");
}

# Executando testes
$ python main.py exemplo.mini

# Saída esperada para teste léxico
TOKEN: VAR, valor: 'var'
TOKEN: IDENTIFIER, valor: 'x'
TOKEN: EQUALS, valor: '='
TOKEN: INTEGER, valor: 10
TOKEN: SEMICOLON, valor: ';'
...
Comece com testes de pequenos fragmentos de código e vá aumentando a complexidade. Verifique se cada token é reconhecido corretamente e se a estrutura sintática é validada adequadamente pelo parser.
Validação de Tokens e Erros de Sintaxe
Um bom compilador não apenas reconhece código válido, mas também fornece mensagens de erro úteis. Implemente:
  • Rastreamento de linha e coluna para localizar erros precisamente
  • Mensagens descritivas que expliquem o erro e sugiram correções
  • Recuperação de erros para continuar a análise após encontrar um erro
  • Destaque visual do local do erro no código fonte original
Teste deliberadamente com código contendo erros para verificar se seu compilador os detecta corretamente e fornece mensagens claras que ajudam a identificar e corrigir o problema.
Ambiente de Desenvolvimento Recomendado
VS Code
Editor recomendado por sua leveza e excelente suporte a Python. Configure extensões como Python, Pylance e Git para melhorar a produtividade.
Terminal Integrado
Use o terminal integrado do VS Code para executar testes e depurar seu compilador sem sair do ambiente de desenvolvimento.
Controle de Versão
Utilize Git para controle de versão, facilitando a colaboração em equipe e o acompanhamento das mudanças no código.
Organize seu ambiente com arquivos separados para cada componente do compilador. Isso facilita o desenvolvimento paralelo e a manutenção do código, especialmente em projetos em grupo.
Exercício Prático em Grupo

Implementar as fases de análise léxica e sintática para processar um programa simples na mini linguagem definida pelo grupo.
Tarefas:
  1. Definir a gramática formal da linguagem
  1. Implementar o analisador léxico com PLY
  1. Criar o parser para as construções básicas da linguagem
  1. Testar com um programa de exemplo que use todas as construções
  1. Documentar decisões de design e limitações atuais
Este exercício prático consolida o aprendizado das primeiras fases do compilador e prepara o terreno para as próximas etapas do projeto guiado. Trabalhe em equipe, dividindo responsabilidades conforme as habilidades de cada membro.
Próximos Passos: Análise Semântica e Geração de Código
Na próxima parte do projeto guiado, avançaremos para:
1
Análise Semântica
Verificação de tipos, escopo de variáveis e regras específicas da linguagem. Construção e uso da tabela de símbolos para rastrear informações sobre identificadores.
2
Representação Intermediária
Transformação da AST em uma forma intermediária mais próxima do código de máquina, facilitando otimizações e geração de código.
3
Geração de Código
Tradução da representação intermediária para código executável ou bytecode interpretável. Implementação de um ambiente de execução simples.
Continue desenvolvendo e testando os módulos atuais enquanto se prepara para estas próximas etapas. O projeto completo resultará em um compilador funcional para sua mini linguagem.