Construir
Gerar nós de AST durante as reduções do Bison.
Centro de Estudos, Desenvolvimento e Inovação em Software — CEDIS | UnB
Construção da AST e da tabela de símbolos
FGA0003 — Compiladores 1 · Semana 6 · Aula prática
CEDISProduto esperado da aula
Registrar
Inserir declarações na tabela de símbolos.
Imprimir
Visualizar AST e tabela após processar um programa curto.
Preparar
Criar base para a análise semântica da próxima sprint.
CEDISRoteiro de laboratório
- 01Inspecionar o código da Semana 6 no GitHub
- 02Compilar e executar a linha de base
- 03Melhorar o modelo da AST
- 04Atualizar a tabela de símbolos
- 05Integrar lexer, parser, AST e tabela
- 06Testar, documentar e publicar
CEDISCódigo existente e limites
Já existe
- lexer.l e parser.y
- ast.c e ast.h
- tabela.c e tabela.h
- tipos.h e Makefile
Precisa evoluir
- AST sem tipos explícitos
- Tabela apenas global
- Declaração e uso misturados
- Pouca gestão de memória
Repositório oficial: https://github.com/sergioaafreitas/COMP1
CEDISRaio X do compilador
- Lexer produz tokens.
- Bison reduz regras.
- Ações semânticas constroem nós.
- Declarações alimentam a tabela.
CEDISEntrada e saída esperadas
Entrada
int a = 10; int b = 20; int soma = a + b * 2;
Saída
- AST hierárquica do programa
- Tabela com a, b e soma
- Tipos e linhas registrados
- Precedência preservada
CEDISCheckpoint inicial
1. Atualizar
git pull
2. Entrar
cd "semana 06/src"
3. Compilar
make clean && make
4. Executar
printf "a + b - 2\n" | ./parser
CEDIS
Da árvore concreta à AST
- A árvore concreta reflete a gramática.
- A AST reflete o significado estrutural.
- A precedência deve aparecer na hierarquia.
CEDISLimitações da AST atual
Caracteres mágicos
Usar espaços, i, + ou - como tipo dificulta evolução.
Poucas categorias
Expressões funcionam, mas declarações e comandos ficam frágeis.
Sem linha de origem
Diagnósticos posteriores ficam menos precisos.
Sem liberação
A AST deve ter função de desalocação.
CEDISAnatomia de um nó
- tipo identifica a categoria do nó;
- texto guarda identificadores;
- filhos representam a estrutura;
- proximo encadeia comandos.
CEDISTipos explícitos de nós
Enum mínimo
AST_PROGRAMA AST_DECLARACAO AST_NUMERO AST_IDENTIFICADOR
Operações
AST_SOMA AST_SUBTRACAO AST_MULTIPLICACAO AST_DIVISAO
CEDISFunções de criação
1
Número
ast_criar_numero(valor, linha)
2
Identificador
ast_criar_identificador(nome, linha)
3
Operação
ast_criar_operacao(tipo, esq, dir, linha)
4
Declaração
ast_criar_declaracao(nome, inicializacao, linha)
CEDIS
Redução do Bison criando um nó
- $1 e $3 são subárvores já reconhecidas.
- $$ é a subárvore produzida pela regra.
- A ação semântica roda durante a redução.
CEDISImpressão e liberação da AST
Imprimir
ast_imprimir(raiz, nivel) deve mostrar a hierarquia.
Identar
Use o nível para gerar uma saída legível.
Liberar
ast_liberar(raiz) deve percorrer filhos e lista.
Testar
Compare a saída com a árvore esperada.
CEDISTabela de símbolos
- Declarações inserem símbolos.
- Usos de identificadores consultam símbolos.
- Aula de hoje usa apenas escopo global.
CEDISLimitações da tabela atual
Atual
- nome
- tipo
- lista global
- duplicidade ignorada
Melhorar para
- categoria
- tipo enumerado
- escopo
- linha de declaração
- retorno de erro
CEDISOperações da tabela
Buscar
tabela_buscar(nome, escopo)
Inserir
tabela_inserir(nome, categoria, tipo, escopo, linha)
Imprimir
tabela_imprimir() para verificar o resultado.
Liberar
tabela_liberar() antes de encerrar.
CEDISAlterações no lexer
Novos tokens
- "int" → INT
- "=" → ASSIGN
- ";" → SEMICOLON
- operadores e parênteses
Valores semânticos
- NUM preenche valor_inteiro
- ID preenche texto
- %option yylineno
- "int" antes de ID
CEDISAlterações no parser
Declarações Bison
- %union com int, char* e NoAST*
- %token <valor_inteiro> NUM
- %token <texto> ID
- %type <no> expr e declaracao
Regras novas
- programa
- lista_comandos
- declaracao
- expr
- precedência de +, -, *, /
CEDISConstrução durante as reduções
1
Reduz NUM
cria nó AST_NUMERO.
2
Reduz ID
cria nó AST_IDENTIFICADOR.
3
Reduz operação
combina subárvores esquerda e direita.
4
Reduz declaração
insere símbolo e cria nó AST_DECLARACAO.
CEDISCompilação e testes
Compilar
make clean && make
Expressões
./parser < tests/01-expressoes.comp1
Declarações
./parser < tests/02-declaracoes.comp1
Precedência
./parser < tests/03-precedencia.comp1
CEDISNíveis de conclusão
Essencial
AST de números, identificadores e operações, com impressão hierárquica.
Esperado
Declarações, tabela de símbolos e testes versionados.
Avançado
Duplicidade, linha de origem, liberação completa e preparação para escopos.
CEDISChecklist de entrega
AST
Nós tipados e impressão hierárquica.
Tabela
Nome, categoria, tipo, escopo e linha.
Integração
Bison construindo AST e inserindo símbolos.
Qualidade
-Wall -Wextra, testes, README e commit.
CEDISMateriais e referências
- Repositório da disciplina: https://github.com/sergioaafreitas/COMP1
- Código da Semana 6: lexer.l, parser.y, ast.c, ast.h, tabela.c, tabela.h e tipos.h.
- WIRTH, N. Compiler Construction. Capítulos sobre parsing, árvores e análise semântica.
- TREMBLAY, J. P.; SORENSON, P. G. Theory and Practice of Compiler Writing. Seções sobre árvores e tabelas de símbolos.
CEDISEncerramento
Ao final da prática, o compilador da equipe deve começar a enxergar por dentro: AST para estrutura e tabela de símbolos para nomes declarados. Repositório: https://github.com/sergioaafreitas/COMP1